0

I have an Array of Objects which has a key say PhoneNumber (along with other key-value pairs). I have a phone number value that I'm looking for in this Array. I'm performing a linear search on this array for the phone number and breaking the loop as soon as I find the object (hence If I'm lucky, I may not need traverse through entire Array).

Best case here is only if I find the phone number in Array (and don't search further), but chances are more that I'll not find it, and will traverse whole array in vain.

Update

I thought to provide this, the search space (the Array of Objects) will have around ~500 elements, so looking specifically at this linear search may not be a performance concern, but there are many other tasks which are performed alongside this search, so I'm looking for as many micro-optimizations as possible.

Update 2 (In response to Elias Van Ootegem's comment)

I think my Array has something inappropriate in its structure such that neither of JSON.stringify() (Uncaught TypeError: Converting circular structure to JSON) or Ext.JSON.encode() (Maximum call stack exceeded) works to convert array into JSON string.

But, anyway to do this even faster?

Community
  • 1
  • 1
Kushal
  • 3,112
  • 10
  • 50
  • 79
  • 1
    How about: `JSON.stringify(yourArray).indexOf('thekeyyouneedtofind')`, if it's >= 0, you can perform the search loop/method, if it's -1, there's no need to traverse the array in vain... – Elias Van Ootegem Feb 26 '13 at 11:06
  • `indexOf`... I'm blocked here by IE7 and IE8 support ([discussion](http://stackoverflow.com/questions/2790001/fixing-javascript-array-functions-in-internet-explorer-indexof-foreach-etc)). – Kushal Feb 26 '13 at 11:10
  • Do you have to use this array of objects which contains key value pairs ? How often do you perform this search ? – Christophe Roussy Feb 26 '13 at 11:10
  • @ChristopheRoussy: Yes, I have to use this Array (its bound to a ExtJS Store), and I'm not backend developer of this webapp, so can't control what's coming in what format. – Kushal Feb 26 '13 at 11:12
  • @Kush Elias uses `String.indexOf()` in his example... You could even calculate an approximately value where to start the loop. How does `JSON` work in IE7, I thought MS introduced it in IE8? – Teemu Feb 26 '13 at 11:19
  • If your array is unordered and linear search is fine, also have a look at this post: http://stackoverflow.com/questions/237104/array-containsobj-in-javascript – Christophe Roussy Feb 26 '13 at 11:22
  • @Teemu, @Elias Oh, I totally over-looked that it is indeed `string.indexOf()` which looks like, [is supported](http://stackoverflow.com/questions/5937609/is-it-true-that-ie7-doesnt-support-indexof-javascript) in older IE. But I'll have to check if it does the job in my case. As far as `JSON` is concerned in IE7-8, `Ext.JSON.encode()` will do the job. :-) – Kushal Feb 26 '13 at 11:25
  • @Kush: json.org, there's a little json2.js file you can download for browsers that don't offer native JSON support – Elias Van Ootegem Feb 26 '13 at 12:29

2 Answers2

0

It deppends on the usage.

If you use this array many times, you should use a map instead of using an array. Create a hash with {key: data}, and get the data given its key. (convert the array to a hash in the javascript)

If you only use the array once, the process of converting it to a map will take longer than the search itself. The best way, linear search.

The cost of boths solutions are (considering n: array lenght, and m, number of searches): first solution: n*log(n) + m * log(n)

Secons solution: n*m

Mateu
  • 2,636
  • 6
  • 36
  • 54
0

Create a lookup object, which maps the phone number (as key) to the index inside the array.

var dataset = [{phone:'0123 456 689'},{phone:'0987 654 321'},...];
var lookup = {'0123 456 689':0,'0987 654 321':1,...};

// search like this...

var number = '0987 654 321';
var obj = dataset[lookup[number]];

But this is probably overkill for most use-cases, as a linear search should be fast enough for users even with thousands of entries.

Graham
  • 6,484
  • 2
  • 35
  • 39