optimize search through large js string array?

if I have a large javascript string array that has over 10,000 elements, how do I quickly search through it?

Right now I have a javascript string array that stores the description of a job, and I"m allowing the user to dynamic filter the returned list as they type into an input box.

So say I have an string array like so:
var descArr = {"flipping burgers", "pumping gas", "delivering mail"};

and the user wants to search for: "p"

How would I be able to search a string array that has 10000+ descriptions in it quickly? Obviously I can't sort the description array since they're descriptions, so binary search is out. And since the user can search by "p" or "pi" or any combination of letters, this partial search means that I can't use associative arrays (i.e. searchDescArray["pumping gas"] ) to speed up the search.

Any ideas anyone?

-------------Problems Reply------------

As regular expression engines in actual browsers are going nuts in terms of speed, how about doing it that way? Instead of an array pass a gigantic string and separate the words with an identifer. Example:

  • String "flipping burgers""pumping gas""delivering mail"
  • Regex: "([^"]*ping[^"]*)"

With the switch /g for global you get all the matches. Make sure the user does not search for your string separator.

You can even add an id into the string with something like:

  • String "11 flipping burgers""12 pumping gas""13 delivering mail"
  • Regex: "(\d+) ([^"]*ping[^"]*)"
  • Example: http://jsfiddle.net/RnabN/4/ (30000 strings, limit results to 100)

There's no way to speed up an initial array lookup without making some changes. You can speed up consequtive lookups by caching results and mapping them to patterns dynamically.

1.) Adjust your data format. This makes initial lookups somewhat speedier. Basically, you precache.

var data = {
a : ['Ant farm', 'Ant massage parlor'],
b : ['Bat farm', 'Bat massage parlor']
// etc
}

2.) Setup cache mechanics.

var searchFor = function(str, list, caseSensitive, reduce){
str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace
var found = [];
var reg = new RegExp('^\\s?'+str, 'g' + caseSensitive ? '':'i');
var i = list.length;
while(i--){
if(reg.test(list[i])) found.push(list[i]);
reduce && list.splice(i, 1);
}
}

var lookUp = function(str, caseSensitive){
str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace
if(data[str]) return cache[str];
var firstChar = caseSensitive ? str[0] : str[0].toLowerCase();
var list = data[firstChar];
if(!list) return (data[str] = []);
// we cache on data since it's already a caching object.
return (data[str] = searchFor(str, list, caseSensitive));
}

3.) Use the following script to create a precache object. I suggest you run this once and use JSON.stringify to create a static cache object. (or do this on the backend)

// we need lookUp function from above, this might take a while
var preCache = function(arr){
var chars = "abcdefghijklmnopqrstuvwxyz".split('');
var cache = {};
var i = chars.length;
while(i--){
// reduce is true, so we're destroying the original list here.
cache[chars[i]] = searchFor(chars[i], arr, false, true);
}
return cache;
}

Probably a bit more code then you expected, but optimalisation and performance doesn't come for free.

I can't reproduce the problem, I created a naive implementation, and most browsers do the search across 10000 15 char strings in a single digit number of milliseconds. I can't test in IE6, but I wouldn't believe it to more than 100 times slower than the fastest browsers, which would still be virtually instant.

Try it yourself: http://ebusiness.hopto.org/test/stacktest8.htm (Note that the creation time is not relevant to the issue, that is just there to get some data to work on.)

One thing you could do wrong is trying to render all results, that would be quite a huge job when the user has only entered a single letter, or a common letter combination.

This may not be an answer for you, as I'm making some assumptions about your setup, but if you have server side code and a database, you'd be far better off making an AJAX call back to get the cut down list of results, and using a database to do the filtering (as they're very good at this sort of thing).

As well as the database benefit, you'd also benefit from not outputting this much data (10000 variables) to a web based front end - if you only return those you require, then you'll save a fair bit of bandwidth.

I suggest trying a ready made JS function, for example the autocomplete from jQuery. It's fast and it has many options to configure.

Check out the jQuery autocomplete demo

Category:javascript Views:0 Time:2010-10-20

Related post

  • Search a large c++ string from a file mapping quickly and efficiently 2012-01-24

    A quick preface, I'm very comfortable in .Net, but have limited experience in c++, so I'm not sure if I'm doing this well. I'm using a file mapping object to retrieve what could potentially be a relatively long string, comprised of up to several thou

  • Can large String Arrays freeze my program? 2010-10-10

    I recently created a program that gets medi-large amounts of xml data and converts it into arrays of Strings, then displays the data. The program works great, but it freezes when it is making the arrays (for around 16 seconds depending on the size).

  • How can I optimize search on array of String array? 2011-05-11

    I have String arrays of arrays. List<String[]> mainList = new ArrayList<String[]>(); String[] row1 = {"foo", "bar", "moo"} String[] row2 = {"cocoa", "zoo", "milk", "coffee"} mainList.add(row1); mainList.add(row2); Let's say I want to find

  • searching through a string-array in android 2012-01-18

    I have a rather large string-array with a lot of strings (obviously), and i want to put a search bar in the top. This string array comes out in a listview. I want to be able to search for some string in the list, and then hide the results that does n

  • Sequential search on String array in Java 2012-02-15

    I am supposed to write sequential/linear search on a String array. I am very close to finishing, but part of the assignment confuses me. It says to compare the target item with successive element of the list until the target matches or target is less

  • C# - How do you search a large text file for a string without going line by line? 2010-01-19

    I have a large text file that I need to search for a specific string. Is there a fast way to do this without reading line by line? This method is extremely slow because of the size of the files (100mb+) --------------Solutions------------- Given the

  • C++ string array binary search 2010-03-29

    string Haystack[] = { "Alabama", "Alaska", "American Samoa", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "District of Columbia", "Florida", "Georgia", "Guam", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas",

  • Cheap way to search a large text file for a string 2010-10-08

    I need to search a pretty large text file for a particular string. Its a build log with about 5000 lines of text. Whats the best way to go about doing that? Using regex shouldn't cause any problems should it? I'll go ahead and read blocks of lines, a

  • Searching an String array for a sub-string? 2011-02-26

    I am trying to write a little method in java, but I cannot figure it out. What I want to be able to do is enter a string, and then the value of an int variable is set to the index of this in the array, i.e if I have an array consisting of [0] 'hi guy

  • In java, how can i search String array in another String array? 2011-04-28

    I have two different String array. String[] str1={(ABC),(CDE),(DEF),(FGE),(ERT)}; String[] str2={(ABC),(FGE)}; I wanna know is str1 have str2's all members?How can i search str2 in str1? --------------Solutions------------- Arrays.asList(str1).contai

  • In java, search String array in String array 2011-04-28

    I have two different String array. String[] str1={(ABC),(CDE),(DEF),(FGE),(ERT)}; String[] str2={(ABC),(FGE)}; I wanna know is str1 have str2's all members?How can i search str2 in str1? --------------Solutions------------- Arrays.asList(str1).contai

  • Algorithm to search and assign the BEST string for each element of a string array (from another string array) 2011-06-07

    This is for automating a testing process. I have two string arrays (extracted from two different sources for testing). Each string in one of the arrays has to be assigned to a string in the other array. The strings may not always match exactly, but t

  • Searching for a string in a String-Array item element 2011-06-28

    How to search for a specific text inside a string-array item element? The following is an example of the xml file. The string-array name is android. I have some items inside the string-array. Now I want to do a search for the word "software". Please

  • Search a String array in Delphi 2011-12-07

    Is there a function in the Delphi standard library to search string arrays for a particular value? e.g. someArray:=TArray<string>.Create('One','Two','Three'); if ArrayContains(someArray, 'Two') then ShowMessage('It contains Two'); -------------

  • Searching for parts of string in multi level array 2012-03-13

    Is there a function that allows me to search inside a multidimensional array that goes multiple levels deep? An example of an array can be found below. What I want is to be able to search in the entire array, regardless of how deep it goes (3 levels

  • Android search through an string-array and get results into a ListView 2012-04-23

    I want to search into a string-array and get the result into a ListView. So, if I have <string-array name="Colors"> <item>Red</item> <item>Yellow</item> <item>Blue</item> <item>DarkRed</item> <

  • What is the fastest search method for a sorted array? 2011-01-20

    Answering to another question, I wrote the program below to compare different search methods in a sorted array. Basically I compared two implementations of Interpolation search and one of binary search. I compared performance by counting cycles spent

  • What is the best way to count and sort a string array 2012-02-13

    I am trying to find if there is a good way to search (count number of occurrences) and then sort a String array in a efficient way... that is a way that will work well in embedded systems (32Mb) Example: I have to count the number of time the charact

  • Efficiently merge string arrays in .NET, keeping distinct values 2008-09-28

    I'm using .NET 3.5. I have two string arrays, which may share one or more values: string[] list1 = new string[] { "apple", "orange", "banana" }; string[] list2 = new string[] { "banana", "pear", "grape" }; I'd like a way to merge them into one array

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.097 (s). 11 q(s)