1 |
<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> |