Hello, I'm trying to imitate the behaviour of the pivot-table in excel where you take a list of items and another list of their values and
you sum similar ones together (see toy example below). I have a list
of 30000 items and their associated values and in excel using a pivot- table the computation is done instantaneously (less than 2 seconds)
while the procedure I wrote in lisp will take about 12 hours !(I give
an example of only 15 items below, this goes fast of course because
only 15 items, but the 30,000 will take an estimate of about 12 hours;
I never reached that far because around 5 hours I give up). Do you
know why? Is there a way to enhance the procedure and make it as fast
as the pivot table? Thanks
;; Tabulate like the pivot table.
(time
(let ((ls (vector "a" "b" "c" "b" "a" "f" "e" "g"
"h" "k" "z" "k" "r" "u" "f"))
(counter (vector 1 5 8 7 14 8 3 7 9 4 3 21 5 7 9))
(i 0))
(loop while (< i (length ls)) do
(let ((j (+ i 1)))
(loop while (< j (length ls)) do
(when (and (equal (elt ls i) (elt ls j))
(not (equal (elt ls j) 'indic)))
(incf (elt counter i) (elt counter j))
(setf (elt ls j) 'indic
(elt counter j) 'indic))
(incf j)))
(incf i))
(values (delete 'indic ls)
(delete 'indic counter))))
Real time: 0.009765 sec.
Run time: 0.012 sec.
Space: 102408 Bytes
#("a" "b" "c" "f" "e" "g" "h" "k" "z" "r" "u") ;
#(15 12 8 17 3 7 9 25 3 5 7)
Pascal Bourguignon wrote:
Hello, I'm trying to imitate the behaviour of the pivot-table in excel
where you take a list of items and another list of their values and
you sum similar ones together (see toy example below). I have a list
of 30000 items and their associated values and in excel using a pivot-
table the computation is done instantaneously (less than 2 seconds)
while the procedure I wrote in lisp will take about 12 hours !(I give
an example of only 15 items below, this goes fast of course because
only 15 items, but the 30,000 will take an estimate of about 12 hours;
I never reached that far because around 5 hours I give up). Do you
know why? Is there a way to enhance the procedure and make it as fast
as the pivot table? Thanks
;; Tabulate like the pivot table.
(time
(let ((ls (vector "a" "b" "c" "b" "a" "f" "e" "g"
"h" "k" "z" "k" "r" "u" "f"))
(counter (vector 1 5 8 7 14 8 3 7 9 4 3 21 5 7 9))
(i 0))
(loop while (< i (length ls)) do
(let ((j (+ i 1)))
(loop while (< j (length ls)) do
(when (and (equal (elt ls i) (elt ls j))
(not (equal (elt ls j) 'indic)))
(incf (elt counter i) (elt counter j))
(setf (elt ls j) 'indic
(elt counter j) 'indic))
(incf j)))
(incf i))
(values (delete 'indic ls)
(delete 'indic counter))))
Real time: 0.009765 sec.
Run time: 0.012 sec.
Space: 102408 Bytes
#("a" "b" "c" "f" "e" "g" "h" "k" "z" "r" "u") ;
#(15 12 8 17 3 7 9 25 3 5 7)
Gauche Scheme
(use srfi-13) ;; string<
(use srfi-43) ;; vector-binary-search
(define (string-cmp a b)
(cond ((string< a b) -1)
((string= a b) 0)
(else 1)))
(define (do-the-pivot keys counts)
(let* ((unique-keys
(sort (delete-duplicates (vector->list keys)) string<))
(pivot-keys (list->vector unique-keys))
(pivot-counts (make-vector (vector-length pivot-keys) 0)))
(vector-for-each
(lambda (_ k n)
(let ((i (vector-binary-search pivot-keys k string-cmp)))
(vector-set! pivot-counts i
(+ n (vector-ref pivot-counts i)))))
keys
counts)
(values pivot-keys pivot-counts)))
(do-the-pivot
#("a" "b" "c" "b" "a" "f" "e" "g" "h" "k" "z" "k" "r" "u" "f")
#(1 5 8 7 14 8 3 7 9 4 3 21 5 7 9))
#("a" "b" "c" "e" "f" "g" "h" "k" "r" "u" "z")
#(15 12 8 3 17 7 9 25 5 7 3)
(defun pivot (k v)(flow (list k v)
(pivot#("a" "b" "c" "b" "a" "f" "e" "g" "h" "k" "z" "k" "r" "u" "f")
(defun pivot (k v)(flow (list k v)
(pivot#("a" "b" "c" "b" "a" "f" "e" "g" "h" "k" "z" "k" "r" "u" "f")
(defun pivot (k v)(flow (list k v)
(pivot#("a" "b" "c" "b" "a" "f" "e" "g" "h" "k" "z" "k" "r" "u" "f")
* there is already a WHILE in Common Lisp. No need to invent a new one:
(loop while (foo-p) do .... )
3. Loop is very powerful, granted, and many people are trying to
argue that "you can do so much with loop that it's unreadable."
This is not an argument.
[ ... ]* there is already a WHILE in Common Lisp. No need to invent a new one:
(loop while (foo-p) do .... )
Gauche Scheme
(while (read) (print "True enough."))
2
True enough.
#t
True enough.
'yes
True enough.
#f
(while (read) => x (print x " is truer than you think."))
Paul Graham:
I consider Loop one of the worst flaws in CL, and an example
to be borne in mind by both macro writers and language designers.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 326 |
Nodes: | 16 (2 / 14) |
Uptime: | 12:22:57 |
Calls: | 7,231 |
Calls today: | 4 |
Files: | 12,582 |
Messages: | 5,552,741 |