3 ms·
I'm not sure about performance and memory efficiency of the other systems you mentioned. In Redis it is possible in theory to add a command to perform this task
by antirez 16y ago
I'm not sure about performance and memory efficiency of the other systems you mentioned. In Redis it is possible in theory to add a command to perform this task against a sorted set, without adding prefixes. Otherwise it's also possible to run binary search directly using ZRANGE, against the sorted set. This way the sorted set can only contain the actual words without prefixes (the memory complexity will be the same but with a smaller constant factor).
I don't think we'll add such a command, nor that a more complex implementation is a good idea, because this algorithm is pretty straightforward and very fast, and can be modeled using the pre-existing API. Also in most completion systems you want to complete only frequent items, so I'm not sure if it's a memory bound problem in practice.
That said I expect the proposed solution to be able to deliver at least 10k completions per second in a small virtual machine.
- bl4k 16y agoI benchmarked it. My binary search using ZRANGE was fast, but not as fast as your normalized method: Ran 10000 queries in 26.52s using bsearch Ran 10000 queries in 3.87s using normalized method the advantage in using the bsearch is that you have a clean data set, incase you use that set in other parts, and it is easier to manage the data.
- antirez 16y agoHello! like in most Redis benchmarks, without concurrent clients you are measuring latency in this way, not real performances! You need to spawn N threads, and if you do it the wrong way (N ruby scripts for instance) you'll not be ale to actual meter the performance as the clients will use all the CPU... I think the normalized method is faster indeed but it's not possible to tell from this benchmark.