Problem-solving: No easy way of getting the N highest/lowest items on a list

[FCO]

Currently, we have no easy and performative way of getting the N highest (or lowest) items on a list. If N is one, it's easy:

@list.max

but for anything higher than one, it's much more difficult. The easiest way would be:

@list.sort.tail: $n

but the problem with that is that sort costs more than it's needed to just find the biggest $n items it $n is small and the list is big.

[FCO]

I think the best way of doing that would be adding an optional Int parameter to .max and .min that, by default, would be 1 and would represent how many elements it should return. Or maybe it could be a named parameter.

It could just iterate N times on the list getting the N highest/lowest items. It could also, depending on the size of the list and the value of N use .sort.head($n).

[coke]

This seems like very specific functionality to add to the language.

my @a = rand xx 50;
my $n = 5;
dd @a.sort({-$^a})[^$n]

Whether it's hidden behind a method or not, we'd still have to check the entire list to find the highest ones...

[FCO]

Yes, even though, iterating 5 times is still faster than sorting it and getting the 5 first elements on that case...

[FCO]

I'm thinking something like this:

raku -e '

my @a = ^50 .pick(*);

my $n = 5;
my $used = any();
say gather for ^$n {
   my $max = -Inf;
   my $max-i = -1;
   for @a.kv -> $i, $v {
      next if $i == $used;
      if $v > $max {
         $max = $v;
         $max-i = $i
      }
   }
   take $max;
   $used |= $max-i
}

'
(49 48 47 46 45)

[lizmat]

A .max(N) and a .min(N) could also work on Supplys, without needing to keep all the values in memory.

[FCO]

Another interesting thing that .min/.max could accept was :k, :v and :p

[AlexDaniel]

Not just supplies but even Seqs.

[AlexDaniel]

@lizmat any reason .sort.head(5) can't do the proposed behavior? Can't we have a specialized .head/.tail implementation on the Seq that is currently being returned from .sort?

[lizmat]

$ raku -e 'dd <a b c>.sort.iterator.^name'
"Rakudo::Iterator::ReifiedListIterator"

sort builds a list and returns a Seq from that. It needs to build the list to be able to sort. So, all the sorting has been done already before we get a Seq.

One could envision a named parameter on sort: .sort(:head(5)) or .sort(:tail(5)) to get the desired behaviour: that would then not do an actual sort, but create a list of the highest / lowest values seen. But if we're going that way, I feel using .max(5) or .min(5) to be mnemonically better, because adding that functionality to .sort would actually make that do something else than "sort".

Hope this made sense :-)

[FCO]

Would also a .max(*) and .min(*) make sense? With that we could iterate over the elements (first iteration would get the max, the second the second max, etc) and we could stop iterating whenever we want...

my $sum = @a.sum;
my $til-now = 0;
for @a.max: * -> $val  {
   return $val if ($til-now += $val) >= $sum /2
}

That way, for example, we could find what we want without having to sort the array...

[lizmat]

@FCO that would be sort, no ?

[FCO]

You could not interrupt sort in the middle...
If you have an array with 1000 items and want to get the max until it’s equal something and that item is the second max, with sort you would have to complete sort the whole array before getting the second value. With .max(*) it would iterate over the array once, test the value, iterate twice test the value and that’s it...

[lizmat]

That feels like an awfully inefficient sort algorithm to me. Especially for higher values of N where N is the number of values that you would like max to produce.

[tmtvl]

Yes, it's basically selection sort.

[jnthn]

I've pondered this for a while, but am unconvinced that we need a new API for this, for the following reasons:

• Relative to how often this is wanted, .sort.head(5) feels correctly huffmanized.
• The most potentially compelling advantage would be that we can offer an option with better algorithmic complexity. However, on analysis, I make it pretty slim winnings. A sort of n items is O(n * log(n)). The complexity of picking m items by repeated iterations through the list is O(n * m), so grows in m far faster than than log(n) would. I believe that through use of a priority queue (picking an appropriate concrete data type) you could do it in O(n * log(m)). However, again, logarithmic things grow slowly. The biggest win would be when m is very much smaller than n, but even there, contrasting O(n * log(n)) with O(n * log(m)) , the growth in n is exponentially more significant.
• Constant factors matter too, but it's not clear there's a big win here either. As n gets significantly larger, cache effects of a multi-pass approach will start to hurt. A priority queue would likely fare far better in that regard, assuming a well engineered implementation of it. This may be worth exploring in the implementation, but even if it is worthwhile, it doesn't warrant a new API, since...
• While a sort needs to consume all of its inputs before it can produce its first output, and thus is typically considered an eager operation, there's no reason for sort to actually do that work until it is asked for the first value. This opens a range of options, such as lazily doing the merge phase to only produce the required number of results up to adopting a different algorithm if the requester is head or tail. Thus, should there be experimental evidence that there's a significant enough win, we can make .sort.head($m) work more efficiently, thus sparing the language user another thing to learn, and making it faster for all those who would simply miss the alternative faster operation.

In summary:

• No new API
• Experimentation with making sort a tad less eager are welcome, provided the win justifies the added implementation complexity.