4 ms·
Interesting, can you describe a sparse vector and how it’s packed using pop count?
by le-mark 4y ago
Interesting, can you describe a sparse vector and how it’s packed using pop count?
- Someone 4y agohttps://news.ycombinator.com/item?id=10329598 https://news.ycombinator.com/item?id=10329598: "You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i." FWIW: These kind of sparse array tricks have been around forever: https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html The original idea for that patch didn't come from philip bagwell's paper, but from some code from the late 80's i saw at IBM. Thus, i suspect this kind of thing has been around forever