Viewing a single comment thread. View all comments

Steve132 t1_j28og0o wrote

Reply to comment by RingoCatKeeper in [P]Run CLIP on your iPhone to Search Photos offline. by RingoCatKeeper

There's an O(n) algorithm for top k partitioning that could be much much faster than .sort() when you have thousands of elements.

QuickSelect. In C++ its available as std::nth_element in swift I couldn't find it directly but you can implement it in a few lines using .partition as a subroutine

7

RingoCatKeeper OP t1_j28p4zl wrote

Will certainly check it out!

1

ElectronicCress3132 t1_j29c108 wrote

Btw, one should take care not to implement the worst-case O(n) algorithm (which is Quickselect + Median of Medians), because it has high constant factors in the time complexity which slow it down in the average case. QuickSelect + Random Partitioning, or Introselect (the C++ standard library function mentioned) have good average time complexities and rarely hit the worst case.

1

ElectronicCress3132 t1_j29byah wrote

I think the one in the standard library is introselect, which is a hybrid of QuickSelect

1