Faster data structure for autocomplete (Radix Tree)

bobbylight / AutoComplete

A code completion library for Swing text components, with special support for RSyntaxTextArea.

BSD 3-Clause "New" or "Revised" License

165 stars 55 forks source link

Faster data structure for autocomplete (Radix Tree) #12

Open ricardojlrufino opened 9 years ago

ricardojlrufino commented 9 years ago

Hello,

I have a tip that can be interesting, would be to use a more appropriate data structure for autocomplete.

https://code.google.com/p/concurrent-trees/

Maven repo http://mvnrepository.com/artifact/com.googlecode.concurrent-trees/concurrent-trees/1.0.0

Comparisons http://sujitpal.blogspot.com.br/2007/02/three-autocomplete-implementations.html

ricardojlrufino commented 9 years ago

Another

https://github.com/vivekn/autocomplete

tttwang23 commented 7 years ago

Hmm, but the completions array in AbstractCompletionProvider was declared with "protected" visibility. You can't switch out the implementation because some client code may already have a dependency on its data type.

Right now the insertion cost is n * n * log(n), which is not that good. There should be a way to reduce it to n * log(n) without changing the data type.