Implement Analogy and Similarity Queries. #97
Conversation
sebpuetz
changed the title
src/finalfusion/embeddings.py
Outdated
| skip for skip in (self.vocab.word_index.get(skip) | ||
| for skip in skips) if skip is not None | ||
| ] | ||
| indices = sims.argsort()[::-1] |
There was a problem hiding this comment.
This does an O(n log n) sort. A good binary heap implementation should be faster, since insertions are O(1) in the average case. Also, the worst case would only be O(log k) if the heap is at most k items. So, inserting all items in the heap should be O(n) on average or O(n log k) worst case.
Another approach that would be faster is something like quickselect, where you'd only guarantee a particular item or set of items to be sorted. numpy seems to have a function for this:
https://numpy.org/doc/stable/reference/generated/numpy.argpartition.html
I think you could either use argpartition with an array, or you could use it to get the top-k elements and then sort, so that the running time of the sort is only O(k log k).
There was a problem hiding this comment.
Went with argpartition and sorting a heap after partioning.
src/finalfusion/embeddings.py
Outdated
| for skip in skips) if skip is not None | ||
| ] | ||
| indices = sims.argsort()[::-1] | ||
| mask = np.isin(indices, skip_indices, invert=True, assume_unique=True) |
There was a problem hiding this comment.
Looks like a bunch of sorting and array allocations, I was expecting some equivalent to
[idx for idx in indices if idx not in skip_indices]
|
Thanks for the review, I pushed an update! |
tests are taken from the Rust version.
Might make sense to also use a namedtuples for the iterators and the
embedding_with_normmethods...