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 <a href="bfilter.html">problem was solved</a>. But, Matko |
54 |
sow my code and said: <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 bit, and that's why it's so ugly. |
64 |
</p><p> |
65 |
Matko then rewrote it in object-oriented JavaScript which produced |
66 |
<a href="combo2/test.html">current version of combobox</a>. |
67 |
</p><p> |
68 |
He also did <a href="combo2/test.php">php implementation</a> |
69 |
(which is nice if you have php application and want to create comboboxes |
70 |
on-the-fly from database). If you want to create static index file, you can |
71 |
use <tt>bfilter.pl</tt> script. |
72 |
</p> |
73 |
|
74 |
<h1>Installation</h1> |
75 |
|
76 |
<p> |
77 |
Depending on your usage (do you make static html for CD or dynamic web |
78 |
site?) you can use bfilter and checkbox in various ways. This is a toolbox. |
79 |
Some assembly is required to get full power of comboboxes in your web |
80 |
application. |
81 |
</p><p> |
82 |
There is no demo index supplied with this distribution. To create demo index |
83 |
file for static html examples (<tt>test.php</tt> does it for you), please |
84 |
type: |
85 |
<pre> |
86 |
make combo |
87 |
</pre> |
88 |
on your command prompt. It will create <tt>combo-test.js</tt> with first |
89 |
10000 entries from <tt>/usr/share/dict/words</tt>. |
90 |
</p> |
91 |
|
92 |
<h1>License</h1> |
93 |
|
94 |
<p> |
95 |
All code is licenced under |
96 |
<a href="http://www.gnu.org/licenses/gpl.html">GPL</a> v2 or later. |
97 |
</p><p> |
98 |
More restrictive licensing (if you don't want to share your changes) is |
99 |
available on request. |
100 |
</p> |