Redigerer Mal:Str len/core/dok (avsnitt)

==== Search trees used ====

The search trees used in the loops are optimised based on the assumption that shorter strings are much more common. Note that finding 0 requires to do the "string >= 1" comparison, thus takes at least one operation. And finding for instance 1 means also checking the "string >= 2" comparison, thus takes at least two operations.

The numbers shown in the trees below are not the value searched for, but the value compared with. Thus <code>--4--</code> means the comparison "string >= 4".

0xx-4xx, using linear search since most strings will probably be less than 100 bytes:

<pre>
1--2--3--4

0 1 2 3 4 = Values to find.
1+2+3+4+4 = 14 comparisons to find all values once.
</pre>

x0x-x9x, using linear search for 0x-3x, binary search for 4x-9x, 
since most strings will probably be less than 40 bytes:

<pre>
1--2--3--4--6--8--9
            |  |
            5  7

0 1 2 3 4 5 6 7 8 9 = Values to find.
1+2+3+4+6+6+7+7+7+7 = 50 comparisons to find all values once.
</pre>

xx0-xx9, using binary search:

<pre>
4-----6--8--9
|     |  |
2--3  5  7
|
1

0 1 2 3 4 5 6 7 8 9 = Values to find.
3+3+3+3+3+3+4+4+4+4 = 34 comparisons to find all values once.
</pre>

For comparison, here is the data for a full linear search:

<pre>
1--2--3--4--5--6--7--8--9

0 1 2 3 4 5 6 7 8 9 = Values to find.
1+2+3+4+5+6+7+8+9+9 = 54 comparisons to find all values once.
</pre>