Quote:Original post by swiftcoder
Quote:Original post by Krypt0n
which version is faster depends on the image size, the bit table has contant cost regarding the amount of pixel O(1) while the sorting is probably O(n log n).
A better solution is to iterate over every pixel in the image, and insert the pixel into a std::tr1::unordered_multiset (i.e. a hash table) of colours.
Insertion into an unordered_set is amortized constant time, so the total cost is O(N) with respect to the number of pixels, in *both* time and memory.
By contrast, pbryant's solution is O(N) in terms of time, but that is dwarfed by a massive constant cost in memory, and Brother Bob's solution is O(N log N) in terms of time, with (almost) no cost in memory.
A hash table for int will result in a std::vector that indexes with modulo (the compiler will optimize that if po2) and quite some buckets.
unordered_multiset (actually, why not using unordered_set?) is a nice hash-table implementation, but which version is faster purely depends on the distribution of pixels, if you have bad luck (and that's not impossible in a picture) and your colors are all near offset+n^hash_table_size (histograms show that usually), you'll have a linear time increase O(N*N) (for reference: http://msdn.microsoft.com/en-us/library/bb982739.aspx "In the worst case, when all of the elements are in one bucket, the number of operations is proportional to the number of elements in the sequence (linear time)".
Even in best case, every lookup won't be faster than the bit-test (it will have more indirections and more cache trashing due to bigger structures).
And it will result in a slightly more complicated trade-of question
-bit/channel
-image resolution
-checking for doublication vs. counting
-pixel distribution
From that point of view, I'd prefer the quicksort over the unordered_set.
And my point of view is, that it is really random, purely depending on the input, which version will be faster.