[Sesse__]

An elegant optimization, but how would you intersect two of these efficiently? It sounds like you'd need to iterate over the entire dense vector and do a sparse-vector check for each and every value (O(m) with a very high constant factor). Either that, or sort both sparse vectors (O(n log n)).

[dzaima]

Wouldn't it be just a trivial O(n) of a loop of "for (x in dense vector of one set) { if (is x a member of the other set) add to result; }"?

[Sesse__]

True. The constant factor is nasty, though, compared to the 256-bits-per-instruction of normal bit sets.

[dzaima]

Right; generally the constant factors of this approach are horrible though, can't think of any situation where it'd be worth it on systems with, well, cache (or a TLB for that matter, which is even worse off with the sparse memory usage).

[dooglius]

Why would iterating over the dense vector be O(m) rather than O(n)?

[Sesse__]

Sorry, I meant iterating over the sparse vector, not the dense vector (I find the nomenclature in the article somehow inverted).

[dooglius]

You could do intersection by iterating over the dense vector though, not sure why you would need to iterate over the sparse one

[Sesse__]

Yeah, sure, you can iterate over the dense vector and check in the other side's sparse vector, that's correct.