Engineering Faster Sorters for Small Sets of Items

Re:Engineering Faster Sorters for Small Sets of Items by renox on Friday February 14, 2020 @04:48PM (#22330740)

In the similar topic, I'm trying to find maps optimised for a small maximum number of items (8 or 16) indexed by integers. Curiously I failed to find discussions about this topic.. But std::map seems very badly fit for this kind of map.

[ Parent | on HN ]

Re:Engineering Faster Sorters for Small Sets of Items by matt_d on Friday February 14, 2020 @06:27PM (#22331474)

Perhaps it's worth considering succinct data structures (https://en.wikipedia.org/wiki/Succinct_data_structure), e.g.:

- BitMagic: http://bitmagic.io/, https://github.com/tlk00/BitMagic

- Succinct Data Structure Library 2.0: https://github.com/simongog/sdsl-lite, https://github.com/simongog/sdsl-lite/wiki/Literature

[ Parent | on HN ]

Re:Engineering Faster Sorters for Small Sets of Items by renox on Saturday February 15, 2020 @02:13AM (#22333859)

Thanks but these structures are size optimised, I'm looking for CPU usage optimised structures.

[ Parent | on HN ]

Re:Engineering Faster Sorters for Small Sets of Items by jdoerfert on Saturday February 15, 2020 @04:20AM (#22334196)

Does this sound interesting: http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexed... http://llvm.org/doxygen/IndexedMap_8h_source.html

[ Parent | on HN ]

Re:Engineering Faster Sorters for Small Sets of Items by renox on Sunday February 16, 2020 @01:38AM (#22340173)

I will have a look thanks. I think I'll implement it with two arrays one for keys one for values and a loop to find the key index, then return the corresponding value It may be better to fully unroll the loop, I'll have to benchmark this. SSE may be interesting too.

[ Parent | on HN ]