(LDA): Search complexity in SparseVector (word-topic and doc-topic vector) is log(K). Please consider to use HashVector in Breeze (or OpenAddressHashArray in Breeze) that is with O(1) about zen HOT 2 OPEN

Note that the aggregating (sum) of two HashVectors cost more than sum of two sparseVector. So the key is to avoid the new operation but with in-place add. Please be referred to aggregateByKey.

from zen.

I tried several open address Hashmap implementations used as HashVector backend, but surprisingly they are all slower than SparseVector (Java's HashMap >> Spark's OpenHashMap > Breeze's OpenAddressHashArray > fastutil's int-int map). Maybe because the conflicts happen at the average of log(K) times.
But now this issue is perfectly solved using a very easy trick: before we sample all the edges of one term, we transform the term's count vector into DenseVector first. Then finding n_kw will just need O(1).

from zen.