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


one can use symbols with names like


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