I have implemented a Trie datastructure to store a...

# codereview

[oday]

I have implemented a Trie datastructure to store a list of 235,000 words from a file and search through them I have also stored the same number of words in an ArrayList, so that I could compare.
the way I search within the Trie is using the prefix matching algorithm, the way I search within the ArrayList is list.filter { it.startsWith(input) } and then I measure the output, the Trie is always slower, always. I run a similar program written in Python that does the same thing, the trie is always faster, always. What's going on?

Trie implementation: https://hastebin.com/share/warefekava.kotlin
Main.kt: https://hastebin.com/share/baxuzonuti.kotlin
Words: you can ls /usr/share/dict/words if you are on Mac or Linux

Python script (trie impl and matcher): https://hastebin.com/share/ezokubugix.python

[oday]

other than the fact that it's always slower, the results themselves at each run are so inconsistent, sometimes the trie takes 9 ms to go through the list and not find anything, and sometimes 0ms

[oday]

Yea I’m gonna investigate this further myself actually

[Paul Griffith]

your trie impl was significantly faster on my m1 mbp

[Paul Griffith]

Untitled

Untitled

[Paul Griffith]

https://pl.kotl.in/DnWiT21hw
the only thing I really changed was making search inline

[oday]

https://hastebin.com/share/vatazexuri.markdown

[oday]

The definitive results

[oday]

Same trie impl, different way of measuring

[oday]

and the code https://hastebin.com/share/efuqerocuh.rust