Hi.

O(n) vs O(1) is large difference, however, there is rather simple way
out of the problem: instead of one vector L with indexes 10000,...,99999

L[10000],...,L[99999]

one can use symbols with names like

L10000,...,L99999

If Picolisp is fast enough with symbols, i.e. symbol access
time is O(log n), then

---------
(bench (for (i 10000 (<= i 99999)(inc i)) (set (intern (pack 'L i)) i)))
0.292 sec -> 99999

(bench (do 1000000 (inc 'L50000)))
0.035 sec -> 1050000
---------

For a comparison, access to list is much slower:

---------
(bench (do 1000000 (inc (nth List 50000))))
149.812 sec
---------

Generation of the symbol names has its price,
however, for lot of data, it is still faster
than list access.

----------
(bench (do 1000000 (inc (intern (pack 'L 10001)))))
2.620 sec -> 1010001

(bench (do 1000000 (inc (intern (pack 'L 99998)))))
3.016 sec -> 1099998
----------

The code is somehow ugly, but I guess that with few
helper functions, it can be prettier.

Furthermore, I think this approach is good Lisp style,
because I adapted symbols to array-like use; on similar
way, symbols can be adapted to other data structures,
without need for intervention of the implementer.

Am I right? Is it what Henrik wrote?





--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to