Closed phoe closed 2 years ago
The disadvantage of doing it that way is when you have lists of wildly different lengths. Using longer
never traverses more than the shortest list, so if you have 100 lists one of which has 1000 elements and the rest have 10 elements, then each comparison only makes 10 calls.
I have a WIP branch with a different approach that should do the absolute minimum of list traversals.
The disadvantage of doing it that way is when you have lists of wildly different lengths.
OK, I see; this advantage kind of shrinks when you map #'longer
and therefore the shorter list is traversed multiple times, that's what I originally had in mind. And I see the commit, thank you.
I think this is addressed now.
https://github.com/ruricolist/serapeum/blob/51b308dc6e3602ded63679c9546382429988259f/sequences.lisp#L950-L960
This
reduce
will be quadratic with regard to computing the length of each list multiplied by the number of lists.E.g. if we have 100 lists out of which one has 1000 elements and the rest have 999 elements, then we will make 99 comparisons where each
longer
call will make 1000 recursive calls tonlet longer
, 99000 in total.A solution would be to precompute the length of the longer list, keep it in a lexical variable inside
longest
, and then either somehow pass it tolonger
or to compute the other directly inlongest
. The solution forshortest
is analogous.