Effective Javascript Kit Structure

Question

Having read many similar questions:

• JavaScript implementation of an established data structure
• Javascript Role Kits?
• Node JS, traditional data structures? (e.g. Set, etc.), something like Java.util for node?
• Effective Javascript Array Search
• Best way to find an element in a JavaScript array?
• How to check if an array includes an object in JavaScript?

I still have a question: suppose I have a large array of strings (several thousand), and I have to do a lot of searches (i.e. check many times whether a given string is contained in this array). What is the most efficient way to do this in Node.js?

but. Sort an array of strings, then use binary search? or:

B. Convert strings to object keys, then use the "in" operator

?

I know that complexity A is O (log N), where N is the number of lines.

But I do not know complexity B.

If a Javascript object is implemented as a hash table, then complexity B is on average O (1), which is better than A. However, I do not know if the Javascript object is really implemented as a hash table!

Answer 1

For a fixed large array of strings, I suggest using some form of search in the radix format. Also, take a look at various data structures and algorithms (AVL trees, queues / heaps, etc.) in this package

I am sure that using the JS object as storage for strings will result in a "hash mode" for that object. Depending on the implementation, this can be O (log n) to O (1). See some jsperf tests for comparing property searches and binary searches on a sorted array.

In practice, especially if I will not use the code in the browser, I would unload this functionality to something like redis or memcached.

Answer 2

Update for 2016

Since you are asking about node.js, and this is 2016, now you can use the Set or Map object from ES6 as they are built into ES6. Both allow you to use any string as a key. The Set object is suitable when you just want to see if a key exists:

 if (mySet.has(someString)) { //code here } 

And, Map is suitable if you want to save the value for this key, as in:

 if (myMap.has(someString)) { let val = myMap[someString]; // do something with val here } 

Both ES6 features are now built into node.js with node V4 (the current version of node.js starting with this edit is v6).

See this performance comparison to see how much faster Set operations do than many others.

Old answer

All important performance issues should be tested using real-world performance tests in a tool such as jsperf.com. In your case, the javascript object uses the hash table implementation as an implementation, because without something that works pretty well, the whole implementation will be slow, since many JavaScript uses the object.

The string keys on the object will be the first that I checked, and I would prefer the best performer. Since the internals of the object are implemented in native code, I expect it to be faster than your own hash table or binary search implemented in javascript.

But, as I began my answer, you should really check your specific circumstance for the number and length of lines that you are most concerned about in a tool like jsperf.