0

I need a fast way to find if a string is in a set of strings.

My set does not change much over time, so putting it in a sorted array and using binary search is an option (as advised here: fastest way to determine if an element is in a sorted array)

But would using a trie be faster considering we are talking about String ? If so, is there a well known and supported implementation I could use ? (found a few one on github, but did not seem supported or broadly used).

I was also reading: Fast way to find if a string is in an array

Any chance this approach could beat using a trie ?

(I do not have the time to try to implement all the approaches and benchmark them.)

Community
  • 1
  • 1
Vince
  • 3,979
  • 10
  • 41
  • 69

1 Answers1

2

You have JavaScript. If you go with trie, it would be your own implementation in JavaScript, while a hash is pretty much the foundation the whole JavaScript is built on, optimised to hell in the execution environment. I'd just do this:

var STRINGS = {
  "foo": true,
  "bar": true
}

var fooExists = STRINGS.hasOwnProperty("foo");
Amadan
  • 191,408
  • 23
  • 240
  • 301
  • maybe this is just the answer I am looking for, just that building a dictionary for such purpose is so counter intuitive ... – Vince Nov 17 '14 at 08:41
  • If it helps you with the "counter-intuitive" bit, Ruby's `Set` and Java's `TreeSet` use the exactly same method (having a composed `Hash` and `TreeMap`, respectively) ;) – Amadan Nov 17 '14 at 08:45
  • yes, that actually helps :) Actually that may even explain why there are no broadly used implementation of trie ? – Vince Nov 18 '14 at 02:09
  • I don't know, really. For large databases I imagine native trie will beat a native hash (either in memory or in speed, depending on number of buckets hash is allocated with); but native hash to beat scripted trie. However, without a benchmark it's just speculation. – Amadan Nov 18 '14 at 02:34