bfilter/trunk/README.html

<h1>JavaScript binary filter</h1>

<p>
<small>
Written by Dobrica Pavlinusic
<a href="http://www.rot13.org/~dpavlin/"><tt>www.rot13.org/~dpavlin</tt></a>,
2004-11-21
</small>
</p>

<p>
I had a real-life problem: 17000 entries which I needed to filter in
near-real-time to present to users just some items in unsigned list. You
would probably say (as I would) that this is impossible in JavaScript.
</p><p>
First naive idea was to create gigantic 17000 element JavaScript array and
filter through this. This took 45 minutes (no, it's not a mistake, and
machine is pretty decent AMD Athlon box).
</p><p>
Something has to be done. First speedup was created by splitting huge 17000
element array into smaller slices (few characters) and require at least some
letters before displaying result. As you will soon find out, searching array
isn't the only problem: generating huge html (using DOM or innerHTML) can be
<em>very slow</em>.
<br/>
So, even if you manage to filter list fast enough, limiting filtering to
begin of two or three characters will dramatically reduce about of html
results that you have to create.
</p><p>
After initial implementation or split array, I was down from 45 minutes to
just 5-7 minutes which was almost 10-fold improvement. But, it was still
too slow for interactive use (which by old teletype standards should give
response to users below 3 seconds).
</p><p>
But, I had another idea at mind: why not pre-sort all segments and use fast
binary search? Of course, writing binary search in JavaScript isn't rocket
science, so approach should be valid. Buy, was I wrong. I used
<tt>bfilter.pl</tt> perl routine to produce my indexes. But, soon I found
out that sort order in JavaScript differs from browser to browser depending
on particular locale settings on machine.
</p><p>
While I could side-step that problem by writing localized version of sort (which
<a href="http://svn.rot13.org/~dpavlin/svnweb/index.cgi/js_locale/log/trunk/">
I actually did</a>), this was too slow for practical use.
<br/>
So, I decided just to write <a href="combo2/translate.js">unaccent</a>
in JavaScript and depend that sort order of 7-bit ASCII characters is same
in all JavaScript implementations (current routines work for
<tt>ISO-8859-2</tt> encoding which is used here in Croatia and Eastern
Europe).
</p><p>
Response time of binary search was below 3 seconds (and decent hardware
again), so this problem was solved. But, Matko sow my code and said:
<em>Eh, I could write combobox using this!</em>
</p>

<h1>JavaScript Combobox</h1>

<p>
Implementation of combobox has a little to do with me. Other than the fact
that it uses <tt>bfilter</tt> described above, all the other great work is
done my Matko Andjelinic. He has done <a href="combo.html">initial</a>
implementation on which I hacked a but, and then re-wrote it to
object-oriented JavaScript which produced
<a href="combo2/test.html">current version of combobox</a>.
</p><p>
Matko also did <a href="combo2/test.php">php implementation</a>
(which is nice if you have php application and want to create comboboxes
on-the-fly from database).
</p>

<h1>License</h1>

<p>
All code is licenced under
<a href="http://www.gnu.org/licenses/gpl.html">GPL </a> v2 or later.
by respective 
</p>
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>