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:[email protected]?subject=Unsubscribe
