Message from JavaScript discussions

May 2017

— But by doing that, you can run a search, "Do all characters in X exist in the character set", and if so, then run your probabilistic search on the linked list

Message permanent page


Because the character set only has unique characters, the first check has a linear time complexity of O(n) with n being the number of unique characters in the set, but not words

— A bloom filter is slower than a native set.

— It's meant to be faster than a DB lookup.

— Hmmm

— Is binary search impossible?

— I could just store ascii values as digits:
[ 72, 101, 108, 108, 111 ]

— And then keep list sorted

— And check at the middle of the list if the first char matches, then go to 1 / 4 or 3 / 4 based on higher / lower, then repeat for the next level, and keep going

Message permanent page

— You could make a binary search tree.

— But it's not space efficient.

— I was thinking a linear list