Storing a Sequence of Number Pairs

A sequence of pairs of integers shall be stored in a way that it can be efficiently iterated over. AFAIK, the best is to have one number after the other in a contiguous chunk of memory. If I were to use an array and represent each pair (a,b) as a (cons a b), then I presume that not the integers will be stored in the array, by pointers to those cons cells. This is not cache-efficient. Can we somehow tell the array: store the object, not a reference to it?

Of course, I can have an array of integers a,b,... and put an abstraction in between that will give me two consecutive numbers as a pair. But I'm trying to find a native way first.

How Common Lisp data types are stored in memory and how sequences are iterated over is entirely implementation dependent. To find out the fastest way either read the source code of your Common Lisp implementation or write all possible combinations in Lisp code and use TIME to check the execution speed. Also take into account that there are several OPTIMIZE settings related to speed. Not only the SPEED declaration itself, for maximum speed you also need to set SAFETY (the amount of run-time tests) to zero. It's up to you to decide if a SAFETY of zero makes sense with your code. But even then the speed remains implementation dependent and the tests must be repeated with all Common Lisp implementations you want to support.

Other Common Lisp data structures for storing pairs of numbers:

• COMPLEX numbers are pairs of two numbers.

• Or use a two-dimensional array (MAKE-ARRAY '(size 2) ...), where size is the maximum number of pairs.

Of course complex numbers must be constructed with COMPLEX and destructured by REALPART and IMAGPART and mult-dimensional arrays must be destructured by multiple AREF calls. Wether all this is faster than CONS, CAR, and CDR is again implementation-dependent and must be tested with TIME.

- edgar

If the first numbers are unique, I may use a hashtable, which is usually a very efficient data type. I'm not sure about the purpose of your data, though.