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 |
dpavlin |
41 |
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 |
dpavlin |
40 |
</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 |
dpavlin |
41 |
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 |
dpavlin |
40 |
<a href="combo2/test.html">current version of combobox</a>. |
67 |
|
|
</p><p> |
68 |
dpavlin |
41 |
He also did <a href="combo2/test.php">php implementation</a> |
69 |
dpavlin |
40 |
(which is nice if you have php application and want to create comboboxes |
70 |
dpavlin |
41 |
on-the-fly from database). If you want to create static index file, you can |
71 |
|
|
use <tt>bfilter.pl</tt> script. |
72 |
dpavlin |
40 |
</p> |
73 |
|
|
|
74 |
dpavlin |
41 |
<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 |
dpavlin |
40 |
<h1>License</h1> |
93 |
|
|
|
94 |
|
|
<p> |
95 |
|
|
All code is licenced under |
96 |
dpavlin |
41 |
<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 |
dpavlin |
40 |
</p> |