LastWhereOrNull is Inefficient on Large Lists

[PvtPuddles]

Hello,

List.lastWhereOrNull(...) (from IterableExtensions) is inefficient for lists compared to calling List.reversed.firstWhereOrNull(...).

Consider this example:

final myList = List.generate(1_000_000, (i) => i);
final slowImpl = myList.lastWhereOrNull((i) => i >= 900_000);
final fastImpl = myList.reversed.firstWhereOrNull((i) => i >= 900_000);

In this case, slowImpl is computed by iterating through 1,000,000 elements. On the other hand, fastImpl completes after iterating through only 1,000 elements.

Since iterable does not have a reversed property (and since we would not know if it is efficient if there was one), I propose creating a ListExtensions extension (an idea also floated here) that can take advantage of List.reversed being an O(1) operation.

[PvtPuddles]

Ah, sorry. I overlooked the fact that the list is not guaranteed to be sorted 🤦‍♂️

[PvtPuddles]

Wait I'm silly again. lastWhereOrNull doesn't care if the list is sorted. Sorry again 😅

[jakemac53]

The iterable extension could also check if it is a List and do a reverse search (this would work for cases where the static type is Iterable, but it is in fact a List, which is actually quite common).

[lrhn]

This is indeed inefficient because lastWhereOrNull is an extension method, so when you call it on a List that is statically typed as an Iterable, it calls the iterable version, which cannot assume that you can iterate backwards or have efficient random access.

If it's statically typed as a List, it should call a different version that is optimized for lists. Since it doesn't, that version is probably missing. (It is, no lastWhereOrNull in the file where it should be.)

As @jakemac53 says, another option is to have the Iterable version check if the value is a List, and delegate to the more efficient version if it is.
That's an extra overhead on every call that isn't a List, but probably acceptable (if our compilers have become efficient at Iterable<T> e; if (e is List<T>) ..., and don't spend time checking the type parameter).
It also doesn't handle any other optimized case, but an Iterable being a List or Set is probably the most common specialized Iterables, so optimizing for those is most bang for the buck. And Set has no extra efficient method, so it's only List.

Probably still worth doing, even after adding a List-specialized lastWhereOrNull.