By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,608 Members | 1,925 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,608 IT Pros & Developers. It's quick & easy.

Filtering Large Select Lists

P: n/a
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?

Any help is greatly appreciated!

Kevin

Aug 22 '05 #1
Share this Question
Share on Google+
13 Replies


P: n/a
Hi Kevin,
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?

Any help is greatly appreciated!

Kevin


Well, I could imagine, that a pure clientside-JS-Function for Filtering a list
of 1600 employees will allways need a little bit of extra time. I mean you have
to apply a regex to 1600 elements one after the other - IMHO not a good idea.
The AJAX-Solution should be the better way, serverside you have much more
possibilities to get the data filtered.

martin
Aug 22 '05 #2

P: n/a
<ke******@gmail.com> wrote in message news:11**********************@f14g2000cwb.googlegr oups.com...
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?


I.E. is known to be relatively slow at resolving form properties.
See what effect these two changes have. I can see other optimisations but they're harder to list.

In the init method, replace

for (var i=0; i < this.selectobj.options.length; i++)

with

for (var i=0, len=this.selectobj.options.length; i < len; i++)
and in the set method, replace

for (loop=0 ; loop < this.optionscopy.length; loop++)

with:

var len;
for (loop=0, len=this.optionscopy.length; loop < len; loop++)

--
S.C.
Aug 22 '05 #3

P: n/a
ke******@gmail.com wrote:
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?

Any help is greatly appreciated!


In addition to the suggestions from Stephen, you may want to research
lookup algorithms. 'filterlist' is not optimised at all, it searches
all the options every time (though the list does reduce with each
search). It copies the entire set of options, then removes the
non-matching ones.

With such a large list, it is probably much faster to sort your options
and create keys for the first search character. You may create separate
arrays for the options starting with A, B, C, etc. (or some optimised
set of keys). So at the first key press you 'filter' to only options
starting with that letter (just create a select from the appropriate
array or index key). Whether keys or arrays are faster/better will take
a small amount of testing.

Subsequent filtering should stop processing as soon as no more matches
are found - filterlist keeps going even when the last match has been found.

I'm not sure the object approach used by filterlist is optimal for this
process - it is quite elegant but objects are usually there for the
software designer or programmers' convenience, not because it is faster.
Sometimes you are better off to reduce the functionality to only what
is required (say case insensitive search, left to right and only from
the first character) and implement it in a purely procedural manner.

Good luck.

--
Rob
Aug 23 '05 #4

P: n/a
RobG wrote:
ke******@gmail.com wrote:
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?

[...]

The following is an example of a procedural method that filters 650
names in about 350ms in IE (2.4GHz P4) - Firefox takes about 15ms.
Increasing to 2,000 names took IE 3 seconds (Firefox 300 ms).

The code can likely be further optimised - passing around array
references is a bit tricky, I've likely not done the best job of it.
The increase in time is not linear, so there is obviously something more
you can do when the list is greater than say 1,000 names (like setting
up keys for the first letter match).

Try your luck with your 1600 - replace 'personData' with your own array
of names...
<script type="text/javascript">
var personData =
[
'Smith, John',
'Jones, Mary',
'Zeta, Catherine'
];

// Global to hold current list of options
var currentList = [];

// Builds options given an element and array
function buildOptions( el, a ){
if ( 'select' != el.nodeName.toLowerCase() ) {
alert('Got a ' + el.nodeName + ', need a \'select\'.');
return false;
}
var i = a.length;
el.length = i;
if ( i > 0 ) {
do {
el.options[--i].text = a[i];
} while ( i );
}
}

// Copy all elements of a to b
function copyArray( a ){
var i = a.length;
if ( i > 0 ){
var b = [];
do { b[--i] = a[i]; }
while ( i )
}
return b;
}

// Initialise option list
// el is a select, a is an array of strings to use as options
function initOptions( el, a ){
currentList = copyArray( a );
currentList.sort();
buildOptions( el, currentList );
}

// Filters array using txt, then builds options for el
// Filter from first character, case insensitive
function filterOptions( el, txt, a ) {

// for test, remove for prod
var start = new Date();
var loops = 0;

var re = new RegExp( '^' + txt, 'i' );
var i = a.length;
var b = [];
if ( i > 0 ) {
var j = 0;
var found = false;
var stop = false;
do {
found = re.test( a[j] );

// for test, remove for prod
loops++;

if ( found ) {
b.push( a[j] );
if ( !stop ) stop = true;
}
if (!found && stop ) {
i = j; // break out of loop

currentList = b; //
a = b; // keep new array, ditch old
}
} while ( ++j<i )

// Build new option list using reduced list
buildOptions( el, a );
}

// for test, remove for prod
var finish = new Date();
document.getElementById('runTime').innerHTML =
loops + ' loops<br>'
+ (finish-start) + '&nbsp;ms<br>'
+ personData.length + ' total people<br>'
+ a.length + ' people in current list'
;

}

</script>

<form action="" id="personSelector">
<input type="button" value="Initialise options" onclick="
initOptions( this.form.allNames, personData );
"><br>
<input type="text" id="sText">
<input type="button" value="Filter" onclick="
filterOptions(
this.form.allNames,
this.form.sText.value,
currentList );
">
<select id="allNames">
</select>
</form>
<p>That took: <span id="runTime">???</span>&nbsp;ms</p>

--
Rob
Aug 23 '05 #5

P: n/a
RobG wrote:
RobG wrote:
[...] The code can likely be further optimised - passing around array
references is a bit tricky, I've likely not done the best job of it. The
increase in time is not linear, so there is obviously something more you
can do when the list is greater than say 1,000 names (like setting up
keys for the first letter match).


Had a bit of a play, most (i.e. in nearly all) of the time is consumed
in making the new options.

Also discovered that setting the length of the options attribute to '0'
is quite slow - it is much faster to replace it with a new, empty
element. Note that this saves 100ms for a select with 2,000 options so
for your average select of 10 or 20 options no one will not notice.

It doesn't matter in IE if you set the option length to the new value
then loop through them to modify their attributes or use - new Option()
- to add them one by one, it takes about the same amount of time. The
new Option method is a bit quicker than DOM createElement()...

No feature testing is performed, it should be added.

Final version:

<script type="text/javascript">
var personData =
[
'Smith, John',
'Jones, Mary',
'Zeta, Catherine'
];

// Global to hold current list of options
var currentList = [];

// Replace a select with a new one built from an array
function buildOptions( el, a ){
if ( !el || 'select' != el.nodeName.toLowerCase() ) {
alert('Got a ' + el.nodeName + ', need a \'select\'.');
return false;
}
var j=0, i=a.length;

// for test remove for prod
var f = new Date()
msgTxt += '<br>Start building ' + i + ' options: ' + (f-globTime);
// end test code

// This is the slow bit in IE
if ( i > 0 ) {
var oSel = document.createElement('select');
do {
oSel.options[j] = new Option( a[j], '', false, false );
} while ( ++j < i );
oSel.id = el.id;

// for test remove for prod
var f = new Date()
msgTxt += '<br>Options built: ' + (f-globTime);
// end test code

el.parentNode.replaceChild(oSel, el);

// for test remove for prod
var f = new Date()
msgTxt += '<br>Options added: ' + (f-globTime);
// end test code

}
}

// Copy elements of a to b
function copyArray( a ){
var i = a.length;
if ( i > 0 ){
var b = [];
do {
b[--i] = a[i];
} while ( i )
}
return b;
}

// Initialise option list
// el is a select, a is an array of strings to use as options
function initOptions( el, a ){
currentList = copyArray( a );
currentList.sort();
buildOptions( el, currentList );
}

// Filters array 'a' using txt
// Filter from first character, case insensitive
function filterOptions( a, txt ) {
var b = [];
var i = a.length;
if ( i > 0 ) {
var re = new RegExp( '^' + txt, 'i' );
var j = 0;
var found = false;
var stop = false;
do {
found = re.test( a[j] );
if ( found ) {
b.push( a[j] );
if ( !stop ) stop = true;
}
if (!found && stop ) {
// break out of loop when finished finding matches
i = j;
}
} while ( ++j<i )
// If no matches, give b one element
if ( 0 == b.length ) {
b[0] = 'Ooops, no matches';
}
return b;
}
}

</script>

<form action="" id="personSelector">
<input type="button" value="Initialise options" onclick="
globTime = new Date();
msgTxt = '';
initOptions( this.form.allNames, personData );
msg.innerHTML = msgTxt;
"><br>
<input type="text" id="sText">
<input type="button" value="Filter" onclick="
globTime = new Date();
msgTxt = '';
currentList = filterOptions( currentList, this.form.sText.value );
buildOptions( this.form.allNames, currentList );
msg.innerHTML = msgTxt;
">
<input type="button" value="Delete all options" onclick="
var oSel = document.createElement('select');
var x = this.form.allNames;
oSel.id = x.id;
x.parentNode.replaceChild(oSel,x);
">
<select id="allNames">
<option>Not initialised yet
</select>
</form>
<p id="msg">msg</p>

<script type="text/javascript">
// Testing & debugging variables
var msgTxt = ''; // Write messages to this
var msg = document.getElementById('msg');
var globTime = new Date();
</script>


--
Rob
Aug 23 '05 #6

P: n/a
<ke******@gmail.com> wrote in > Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.

What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

I can code an Ajax solution that will should take under 3 seconds, but
would like to use something client side like this since the operation
seems simple.

Any suggestions?

Any help is greatly appreciated!

Kevin


I used an array to hold all the data and constructed the html onload, and
inserted into a <div> with InnerHTML. array processing is fast and you
update the page in 1 hit.

Herc
--
too intelligent
See - you do get intelligent people on here! Kay. Well, there's you
and me and Herc.... the rest are a bit sus though
Dave Budd ~ UK Mensa founder

Aug 23 '05 #7

P: n/a
ASM
RobG wrote:
ke******@gmail.com wrote:
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.
IE is knonw to crawl for whatever :-(

Tried with an option-list non sorted of more 100 entries
-> immediat filtering with FF and slower with IE (not too much)
What I mean by crawls is that it takes about 30 seconds to filter the
list in IE 6 versus about 1 in Firefox 1.5.

Any suggestions?
In addition to the suggestions from Stephen, you may want to research
lookup algorithms. 'filterlist' is not optimised at all, it searches
all the options every time (though the list does reduce with each
search). It copies the entire set of options, then removes the
non-matching ones.


How, yes, not too good if it doesn't search in the new reduced sub-array
but, this new sub-array won't it be set from new options list ?
With such a large list, it is probably much faster to sort your options
and create keys for the first search character.
I think it is a bit more difficult
because you can have to filter at same time on name *and* first-name
displayed together in same option's text
You may create separate
arrays for the options starting with A, B, C, etc. (or some optimised
set of keys). So at the first key press you 'filter' to only options
starting with that letter (just create a select from the appropriate
array or index key). Whether keys or arrays are faster/better will take
a small amount of testing.
only available if you search on name *without* first-name
(hope there is not a second-name)
Subsequent filtering should stop processing as soon as no more matches
are found - filterlist keeps going even when the last match has been found.


really ?

--
Stephane Moriaux et son [moins] vieux Mac
Aug 23 '05 #8

P: n/a
ASM
RobG wrote:
RobG wrote:
ke******@gmail.com wrote:
Hello everyone,

I have a list of about 1600 employees that I'd like to have displayed
in a form. I'd like to make the "search" for the user as easy as
possible.

I ran across this: http://www.barelyfitz.com/projects/filterlist/
filter that works quite well with small lists (on the site is a list of
20 names). It also works quite well in Firefox 1.5, but crawls in IE
6.
Any suggestions?


[...]

The following is an example of a procedural method that filters 650
names in about 350ms in IE (2.4GHz P4) - Firefox takes about 15ms.
Increasing to 2,000 names took IE 3 seconds (Firefox 300 ms).

The code can likely be further optimised


Tried this code,

IE5.2 Mac -> error : doesn't understand :
b.push( a[j] );

FF :
Needs to push filter button
Finds only name
Gives as result only *one* name even there are several
Searching on 3 caracteres doesn't display a new list

'runtime' tells :
That took: 187 loops
18 ms
208 total people
1 people in current list ms

no they are 3 people !

--
Stephane Moriaux et son [moins] vieux Mac
Aug 23 '05 #9

P: n/a
ASM
RobG wrote:
RobG wrote:
RobG wrote:
[...]
The code can likely be further optimised - passing around array
references is a bit tricky, I've likely not done the best job of it.
The increase in time is not linear, so there is obviously something
more you can do when the list is greater than say 1,000 names (like
setting up keys for the first letter match).

Had a bit of a play, most (i.e. in nearly all) of the time is consumed
in making the new options.


[snip]
Final version:


with previous as final versions

my IE (5.2 Mac) -> error : not understand :
b.push( a[j] );

my FF doesn't search on first-name

--
Stephane Moriaux et son [moins] vieux Mac
Aug 23 '05 #10

P: n/a
Thanks everyone for your replies. The solution I'd like is one that
searches the entire name, both first and last. RobG, thanks for the
code, although with the with the limited searching and speed issues, I
think I'm going to go the AJAX route.

Thanks again to all,
Kevin

Aug 23 '05 #11

P: n/a
ke******@gmail.com wrote:
Thanks everyone for your replies. The solution I'd like is one that
searches the entire name, both first and last. RobG, thanks for the
code, although with the with the limited searching and speed issues, I
think I'm going to go the AJAX route.


The speed issue is related to IE's ability to display option elements.
AJAX will not make any difference to that.

The 'limited searching' is due to the regular expression used. Modifing
it to match any part of the string and search the entire reduced list
every time will still allow the filter to run in less than 20ms on the
test machine noted.

I have a solution to IE's slow display speed if you want it. On the
test machine noted, all operations are virtually instantaneous.

Below is a modified filter function that searches the entire string and
the entire list (i.e. fits your search requirements):

function filterOptions( a, txt ) {
var b = [];
var i = a.length;
var re = new RegExp( txt, 'i' );
var j = 0;
do {
if ( re.test( a[j] ) b.push( a[j] );
} while ( ++j<i )
if ( 0 == b.length ) {
b[0] = 'Ooops, no matches';
}
return b;
}
--
Rob
Aug 23 '05 #12

P: n/a
On Tue, 23 Aug 2005 12:43:59 +0200, ASM
<st*********************@wanadoo.fr.invalid> wrote:
Final version:


with previous as final versions

my IE (5.2 Mac) -> error : not understand :
b.push( a[j] );


var test = new Array();
if ("undefined" == typeof test.push) {
function push() {
for (var ii = 0; ii < arguments.length; ++ii) {
this[this.length] = arguments[i];
}
}
Array.prototype.push = push;
}

It's intentionally unoptimized because I'm not sure precisely what the
IE 5.2 on the Mac supports. The following may work as well:

if ("undefined" == typeof Array.prototype.push) {
Array.prototype.push = function() {
for (var ii = 0; ii < arguments.length; ++ii) {
this[this.length] = arguments[ii];
}
}
}

Can anyone confirm that the code shown above works in IE 5.2 on the
Mac (ie - specifically that it supports directly testing
Array.prototype.push and assigning an anonymous function to that
prototype member)?

--
Grant Wagner <sq*******@yahoo.com>
comp.lang.javascript FAQ - http://jibbering.com/faq
Aug 24 '05 #13

P: n/a
Grant Wagner <sq*******@yahoo.com> wrote in message news:8o********************************@4ax.com...
On Tue, 23 Aug 2005 12:43:59 +0200, ASM
<st*********************@wanadoo.fr.invalid> wrote:
Final version:


with previous as final versions

my IE (5.2 Mac) -> error : not understand :
b.push( a[j] );


var test = new Array();
if ("undefined" == typeof test.push) {
function push() {
for (var ii = 0; ii < arguments.length; ++ii) {
this[this.length] = arguments[i];
}
}
Array.prototype.push = push;
}

It's intentionally unoptimized because I'm not sure precisely what the
IE 5.2 on the Mac supports. The following may work as well:

if ("undefined" == typeof Array.prototype.push) {
Array.prototype.push = function() {
for (var ii = 0; ii < arguments.length; ++ii) {
this[this.length] = arguments[ii];
}
}
}

Can anyone confirm that the code shown above works in IE 5.2 on the
Mac (ie - specifically that it supports directly testing
Array.prototype.push and assigning an anonymous function to that
prototype member)?


I tested it in the address bar by assigning Array.prototype.push=function(){}
A subsequent alert showed it as a function.

You can test: typeof Array().push

--
S.C.

Aug 24 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.