/[bfilter]/trunk/README.html
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /trunk/README.html

Parent Directory Parent Directory | Revision Log Revision Log


Revision 41 - (show annotations)
Mon Nov 22 13:34:21 2004 UTC (14 years, 6 months ago) by dpavlin
File MIME type: text/html
File size: 4058 byte(s)
more documentation

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>

  ViewVC Help
Powered by ViewVC 1.1.26