Path: ...!feed.opticnetworks.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <No_spamming@noWhere_7073.org>
Newsgroups: comp.lang.lisp
Subject: Re: Slow Loop (alternatives in lisp?)
Date: Mon, 17 Jun 2024 23:45:07 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 71
Message-ID: <v4qhq1$vtkr$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Tue, 18 Jun 2024 01:45:07 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7f98368d3520ff7d5520391e04a235d5";
	logging-data="1046171"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/tpSThTw+50J4rs6PxlzFJ"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:EEST6FLP3rih4IlSj1IQ5iAOGKY=
Bytes: 3499

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)