1 |
dpavlin |
40 |
<h1>JavaScript binary filter</h1> |
2 |
|
|
|
3 |
|
|
<p> |
4 |
|
|
<small> |
5 |
|
|
Written by Dobrica Pavlinusic |
6 |
|
|
<a href="http://www.rot13.org/~dpavlin/"><tt>www.rot13.org/~dpavlin</tt></a>, |
7 |
|
|
2004-11-21 |
8 |
|
|
</small> |
9 |
|
|
</p> |
10 |
|
|
|
11 |
|
|
<p> |
12 |
|
|
I had a real-life problem: 17000 entries which I needed to filter in |
13 |
|
|
near-real-time to present to users just some items in unsigned list. You |
14 |
|
|
would probably say (as I would) that this is impossible in JavaScript. |
15 |
|
|
</p><p> |
16 |
|
|
First naive idea was to create gigantic 17000 element JavaScript array and |
17 |
|
|
filter through this. This took 45 minutes (no, it's not a mistake, and |
18 |
|
|
machine is pretty decent AMD Athlon box). |
19 |
|
|
</p><p> |
20 |
|
|
Something has to be done. First speedup was created by splitting huge 17000 |
21 |
|
|
element array into smaller slices (few characters) and require at least some |
22 |
|
|
letters before displaying result. As you will soon find out, searching array |
23 |
|
|
isn't the only problem: generating huge html (using DOM or innerHTML) can be |
24 |
|
|
<em>very slow</em>. |
25 |
|
|
<br/> |
26 |
|
|
So, even if you manage to filter list fast enough, limiting filtering to |
27 |
|
|
begin of two or three characters will dramatically reduce about of html |
28 |
|
|
results that you have to create. |
29 |
|
|
</p><p> |
30 |
|
|
After initial implementation or split array, I was down from 45 minutes to |
31 |
|
|
just 5-7 minutes which was almost 10-fold improvement. But, it was still |
32 |
|
|
too slow for interactive use (which by old teletype standards should give |
33 |
|
|
response to users below 3 seconds). |
34 |
|
|
</p><p> |
35 |
|
|
But, I had another idea at mind: why not pre-sort all segments and use fast |
36 |
|
|
binary search? Of course, writing binary search in JavaScript isn't rocket |
37 |
|
|
science, so approach should be valid. Buy, was I wrong. I used |
38 |
|
|
<tt>bfilter.pl</tt> perl routine to produce my indexes. But, soon I found |
39 |
|
|
out that sort order in JavaScript differs from browser to browser depending |
40 |
|
|
on particular locale settings on machine. |
41 |
|
|
</p><p> |
42 |
|
|
While I could side-step that problem by writing localized version of sort (which |
43 |
|
|
<a href="http://svn.rot13.org/~dpavlin/svnweb/index.cgi/js_locale/log/trunk/"> |
44 |
|
|
I actually did</a>), this was too slow for practical use. |
45 |
|
|
<br/> |
46 |
|
|
So, I decided just to write <a href="combo2/translate.js">unaccent</a> |
47 |
|
|
in JavaScript and depend that sort order of 7-bit ASCII characters is same |
48 |
|
|
in all JavaScript implementations (current routines work for |
49 |
|
|
<tt>ISO-8859-2</tt> encoding which is used here in Croatia and Eastern |
50 |
|
|
Europe). |
51 |
|
|
</p><p> |
52 |
|
|
Response time of binary search was below 3 seconds (and decent hardware |
53 |
|
|
again), so this problem was solved. But, Matko sow my code and said: |
54 |
|
|
<em>Eh, I could write combobox using this!</em> |
55 |
|
|
</p> |
56 |
|
|
|
57 |
|
|
<h1>JavaScript Combobox</h1> |
58 |
|
|
|
59 |
|
|
<p> |
60 |
|
|
Implementation of combobox has a little to do with me. Other than the fact |
61 |
|
|
that it uses <tt>bfilter</tt> described above, all the other great work is |
62 |
|
|
done my Matko Andjelinic. He has done <a href="combo.html">initial</a> |
63 |
|
|
implementation on which I hacked a but, and then re-wrote it to |
64 |
|
|
object-oriented JavaScript which produced |
65 |
|
|
<a href="combo2/test.html">current version of combobox</a>. |
66 |
|
|
</p><p> |
67 |
|
|
Matko also did <a href="combo2/test.php">php implementation</a> |
68 |
|
|
(which is nice if you have php application and want to create comboboxes |
69 |
|
|
on-the-fly from database). |
70 |
|
|
</p> |
71 |
|
|
|
72 |
|
|
<h1>License</h1> |
73 |
|
|
|
74 |
|
|
<p> |
75 |
|
|
All code is licenced under |
76 |
|
|
<a href="http://www.gnu.org/licenses/gpl.html">GPL </a> v2 or later. |
77 |
|
|
by respective |
78 |
|
|
</p> |