List access times versus array access times

[shercipher]

For very large lists/arrays, what is the time improvement for accessing the last element of either structure? I imagine that for arrays, the time taken to access the last element is flat, but for lists grows as the list size grows.



Do arrays have restrictions on size (e.g., can't be indexed past the size of a 32-bit int?)

[Lutz]

Accessing an element in an array is of equal speed for any index. The max index would be a 32-bit integer (31 + sign bit), but for practical purposes much smaller.



On lists access time grows proportional to the index-size because the list has to be walked sequentially to reach the indexed element; but the last element can be accessed as fast as the first, because newLISP keeps a pointer to it in the list header. This optimization makes pushing/popping to/from the end of a list using -1 as an index as fast as pushing/popping to/from the beginning of the list.



If you plan working with arrays a lot, you should also read this chapter:



http://www.newlisp.org/newlisp_manual.html#arrays">http://www.newlisp.org/newlisp_manual.html#arrays



Note that all mathematical operations like 'det','invert','mat','multiply' and 'transpose' work as fast on lists as they do on arrays. There is no necessity of converting from list to arrays to speed up these operations.



As a general rule: for lists with only a few dozen elements, its normally not worth to convert to arrays. Use the 'time' function to benchmark your functions.