Page 1 of 1
Storing a Sequence of Number Pairs
Posted: Wed Jun 24, 2015 5:12 am
by lassekliemann
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.
Re: Storing a Sequence of Number Pairs
Posted: Sat Jun 27, 2015 3:17 am
by edgar-rft
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
Re: Storing a Sequence of Number Pairs
Posted: Thu Jul 02, 2015 6:26 am
by hajovonta
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.