3
$\begingroup$

I don't know what to call this, so I'm calling it "clumping by color".

Suppose I have an array of length $n$ where each of the items has one of $m$ "colors". I'd like to permute the elements so that all the items are "clumped" together with other items of the same color. That is, in the final array ordering

$$ x_0, x_1, \cdots x_{n-1}$$

if $x_i \neq x_{i+1}$, then $\forall j \lt i,\, x_j \neq x_{i+1}$ and $\forall k \gt i+1,\, x_k \neq x_i$.

I know I can solve this "in place" in time $O(n \log n)$, and additional space $O(\log n)$ because I can use an in-place sort (like introsort to produce a permutation that satisfies the clumping constraint, but I'm hoping for at least a smaller constant factor by taking advantage of the fact that I don't care about the order of the colors.

Right now we have an $O(n^2)$ algorithm that is analogous to selection sort

i = 1
while i < n:
  pivot = x[i-1]
  while (i < n) and (x[i] == pivot):
    i = i+1

  for j = i+1 to n:
    if x[j] == pivot:
      swap(x[i], x[j])
      i = i+1

We've also tried a quicksort, which works a little better when the number of colors is large and mostly sorted by the arbitrary integer values assigned to the colors, but worse when the number of colors is small. It would seem that something like counting sort might be a desirable way to go but (a) we really need this to be in-place (the colors actually represent pages, we're doing the clumping to avoid tlb misses, and out-of-place sorts (like counting sort) are just going to make the tlb thrashing worse.) And (b) while the number of colors in an array of length $n$ obviously can't be larger than $n$, the number of colors in the "universe" is much larger (something like $2^{52}$ on a machine with 64-bit virtual addresses). And (c) part of the reason quicksort is often worse than our $O(n^2)$ algorithm is that it sorts the colors by their arbitrary numeric value, which wastes time.

$\endgroup$
  • $\begingroup$ The word you are looking for may be clustering. Picking a quicksort implementation, be sure to use one that doesn't degenerate when the pivot value occurs many times - look for/into three-way-partitioning and dual pivot. It would seem advantagous to be able to specify an expected cluster size to shift the cut-off for "recursion". $\endgroup$ – greybeard Jun 8 '15 at 5:45
3
$\begingroup$

If I understand correctly, you're asking if preserving the locations of grouped values will give a speedup over reordering them, so for instance {2,2,2,1,1,1} would be left in place instead of rewriting the array as {1,1,1,2,2,2}. I would say no, because comparing-and-swapping is not slower than simply comparing in practice, and you probably need the same number of compares regardless.

I've done tests of different Dutch National Flag algorithms and found no variation in times between versions that do a lot of swaps vs. ones which do little (there was a period when that number was important, and a number of papers have been published on it). They all do the same number of comparisons, but the mechanics of moving elements into cache, etc. seems to make swaps almost free.

As greybeard notes, you're probably using the wrong Quicksort. Try the one described here: https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf . 2-way Quicksort is quadratic with duplicate values, for instance n duplicates will take o(n^2) since it will place all remaining values on one side of the pivot during each recursion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.