search

shirsig / aux-addon

Auction House addOn for Classic (1.13) IMPORTANT: The folder name must be "aux-addon" IMPORTANT: The Vanilla (1.12) version moved here https://github.com/shirsig/aux-addon-vanilla
https://www.curseforge.com/wow/addons/aux
196 stars 42 forks source link

Trie Data Structure for Search Completion #302

Open KevinTyrrell opened 4 years ago

KevinTyrrell commented 4 years ago

While talking in Discord, I would hit my Push-To-Talk keybind j while having the Aux window open. The resulting spam of jjjjjjjjjjjjjjjjjjjjjjjjjj causes Aux to continuously search for items of the name j, then jj, jjj, etc. My WoW client then freezes for ~8 seconds due to the sheer number of Aux operations being performed. However once jj is typed in, Aux should now know that there is no item named jj in the database of item names. Thus auto completion should cease. The way to implement this behavior is a Trie data structure, which is commonly used for text prediction for messaging apps, prefix+suffix searches, etc.

Each node of the Trie contains a table which associates letters -> another Trie node. Every item in the game is fed through into the Trie letter by letter. The table itself can be saved to the hard drive so that this process only needs to take place once per install.

shirsig commented 3 years ago

Thanks for the suggestion but with normal typing it's fast enough and this is too much work for such a corner case as holding down a key. Perhaps if I'm really bored sometime.

KevinTyrrell commented 3 years ago

Understandable. I must ask though:r in normal use of Aux do you ever have mini-stuttering/screen freezes while typing in the search bar? They last only ~200ms but after using it for an entire year its hard to ignore.

shirsig commented 3 years ago

I found a bug that was causing duplicates to be added to the autocomplete list, that's how it got so slow. The bug is fixed now but you still have to run /aux clear item cache and /run ReloadUI()

KevinTyrrell commented 3 years ago

Well done, appreciate the follow-up.

KevinTyrrell commented 3 years ago

@shirsig

Here's a video demonstration. https://streamable.com/b7uzx2

0:25 -> 1:32: Typed random characters which caused a minute long client freeze.

1:48: Item Cache clear

2:30 Ran into some weird behavior with item caching. I would have thought that searching the item would insert it into the autocomplete cache. Let me know if that is expected behavior.