4 ms·
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
by Sesse__ 1y ago
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)).
- dooglius 1y agoWhy would iterating over the dense vector be O(m) rather than O(n)?
- Sesse__ 1y agoSorry, I meant iterating over the sparse vector, not the dense vector (I find the nomenclature in the article somehow inverted).
- dzaima 1y agoWouldn'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__ 1y agoTrue. The constant factor is nasty, though, compared to the 256-bits-per-instruction of normal bit sets.
- dzaima 1y agoRight; 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).