The author has a rather narrow definition of "efficient". Yes, he uses close to ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

cperciva on Sept 7, 2009 | parent | context | favorite | on: Binom Bijection - Storing k-Subsets Efficiently

The author has a rather narrow definition of "efficient". Yes, he uses close to the minimum number of bits of storage... but his encoding scheme is horribly slow -- encoding takes O(k^2 log n) time, and decoding using the presented algorithm takes O(k^2 n log n) time.

volkergrabsch on Sept 7, 2009 [–]

Yes, I meant just space efficiency. It might be handy if you have many subsets (e.g. a solution space) you need to store in memory or on disk.

I'm still looking for a faster algorithm that reaches the optimal space efficiency.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact