How can I use the stdlib efficiently and elegantly...
# getting-started
h
How can I use the stdlib efficiently and elegantly to subset a range between a start and a final element in a list of unique items? My solution does not seem very pretty yet
Copy code
val items = (1..10).shuffled()
val from =3
val to =7
 
val from3o7Incl = items.dropWhile { it != from }.takeWhile { it != to } + listOf(to)
w
It depends on the data structure. One thing you could do is add
asSequence
. Now it won't make intermediate lists, and it will not iterate any values after
to
.
Copy code
val from3o7Incl = items.asSequence().dropWhile { it != from }.takeWhile { it != to } + sequenceOf(to)
If you are working on the JVM and you use a sorted set, you can efficiently lookup the range by calling
sortedSet.subSet(from, to)
. Iterating this subset will have
O(log(N) + M)
time complexity, with
N
being the size of your initial set, and
M
being the size of the subset. If it's a sorted list or array, you can use
items.subList(items.binarySearch(from), items.binarySearch(to))
for the same
O(log(N) + M)
time complexity. You will need to handle the cases when
from
and
to
are not in
items
h
Thanks. Yes, I am on JVM, and I'm sure that
from
and
end
are in items which is list of item. Using
subList
or
subSet
felt a bit wrong to be, since I naively I would just need to traverse the list once to figure the subset. so it should be something like
O(n)
if the list is sorted and I'm sure that both from and end are included and showing up in order. Essentially what I am hoping for is a flavor of
takeWhile
which is inclusive of the last element where the predicate fails. Something like ``takeWhileWithLast` ...
w
Using
subList
or
subSet
felt a bit wrong to be, since I naively I would just need to traverse the list once to figure the subset. so it should be something like
O(n)
if the list is sorted and I'm sure that both from and end are included and showing up in order.
Well, you are in luck, both
subList
aswell as `TreeSet`'s
subSet
functions only return a view. While might be dangerous in case of mutations to the original list collection*, it does not have the allocations intermediate lists* you fear.
Essentially what I am hoping for is a flavor of
takeWhile
which is inclusive of the last element where the predicate fails. Something like ``takeWhileWithLast` ...
This does not exist unfortunately, you'd have to add such extension method yourself.
h
Perfect, thanks for your kind support
👍 1
h
Thanks for the pointer
w
Feel free to add your use case. The Kotlin team relies on strong use cases when designing their language :)