| 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> |
Parent Directory
| 
Revision Log