Ok, sorry, I misinterpreted.
Tom wrote:Be careful substituting :INITFORM for :DEFAULT-INITARGS, they are distinctly different. The difference lies in how they are handled by
SHARED-INITIALIZE and mainly causes problems, at least in my experience, when using
REINITIALIZE-INSTANCE.
REINITIALIZE-INSTANCE wrote:The system-supplied primary method for reinitialize-instance checks the validity of initargs and signals an error if an initarg is supplied that is not declared as valid. The method then calls the generic function shared-initialize with the following arguments: the instance, nil (which means no slots should be initialized according to their initforms), and the initargs it received.
There are probably other areas where you can run into problems using :INITFORM and :DEFAULT-INITARGS inter-changeably, so I try to be careful about how I use them.
I didn't say I use them inter-changeably, I always use
:initarg and
:initform. I never needed to use
shared-initialize of
reinitialize-instance, maybe that is the reason. But thank you for the information, I'll keep that in mind.
Warren Wilkinson wrote:Sorting In SBCL
In my application I store a lot of data presorted on disk; once there are enough updates, the updates and data are merged and rewritten to disk. In the mean time, however, I must still merge the data I've loaded from the disk and the in memory patches together everytime users request any range of that data.
I had considered storing a lazily computed 'final location' with each update, so I avoid needlessly recomputing that location (which I initially would have done the simplist way: linear search). Then I had a better idea: Since the data will be largely in order anyway, why not just cons it then sort?
How well this works depends on the sorting algorithm and (perhaps) the format of the data (list vs vector). Before taking this route, I checked out sort in the SBCL git repository, and ran some timing tests. SBCL uses merge sort which is brilliant because its optimal for linked list, and as far as I can tell it works great when data is mostly sorted.
Call it coincidence or not, I was checking SBCL's sorting algorithms performance-wise as well. I'm programing various sorting methods and see how fast they are.
Just as a note, SBCL's
sort uses heapsort for vectors, while
stable-sort uses merge sort. I actually found out that, in at least two systems (one x86 with DDR RAM and another x86-64 with DDR2 RAM),
stable-sort is faster than
sort except for cases with a lot of collisions (and by a lot of collisions I mean the vector having at most 2 different elements). I already posted on SBCL's mailing list and, once I finish my tests, I said I would commit a patch.
SBCL's merge sort is interesting, though. Instead of doing the standard recursion method, it uses a loop that sorts progressively larger subvectors or sublists across the sequence.
Warren Wilkinson wrote:Its fast for both lists and vectors, whichever I prefer to use:
Code: Select all
(defun worsen (thing) (let ((a (random 800)) (b (random 800)))
(let ((temp (elt thing b)))
(setf (elt thing b) (elt thing a)
(elt thing a) temp))))
(defvar *badness0* (iota 800))
(defvar *badness10* (iota 800))
(defvar *badness100* (iota 800))
(defvar *badness1000* (iota 800))
(loop repeat 10 do (worsen *badness10*))
(loop repeat 100 do (worsen *badness100*))
(loop repeat 1000 do (worsen *badness1000*))
(defvar *vbadness0* (make-array 800 :initial-contents (iota 800)))
(defvar *vbadness10* (make-array 800 :initial-contents (iota 800)))
(defvar *vbadness100* (make-array 800 :initial-contents (iota 800)))
(defvar *vbadness1000* (make-array 800 :initial-contents (iota 800)))
(loop repeat 10 do (worsen *vbadness10*))
(loop repeat 100 do (worsen *vbadness100*))
(loop repeat 1000 do (worsen *vbadness1000*))
(defun time-sort (array &aux (copies (loop repeat 10000 collect (copy-seq array))))
(time (dolist (copy copies) (sort copy #'<))))
(time-sort *badness0*) ;; 5.048 seconds
(time-sort *badness10*) ;; 6.248 seconds
(time-sort *badness100*) ;; 7.354 seconds
(time-sort *badness1000*) ;; 7.803 seconds
(time-sort *vbadness0*) ;; 3.308 seconds
(time-sort *vbadness10*) ;; 3.388 seconds
(time-sort *vbadness100*) ;; 3.325 seconds
(time-sort *vbadness1000*) ;; 3.535 seconds
Just a small tip:
Code: Select all
(defun worsen (thing) (let ((a (random 800)) (b (random 800)))
(rotatef (elt thing b) (elt thing a)))