It might actually make sense to rewrite the whole thing in Cython, as writing the logic in Python is making the 1 in O(1) an unnecessarily big number. `dok_matrix.__setitem__` is quite a bit slower than setting items into a dict.