On 16 Aug., 11:42, Francogrex <······@grex.org> 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
>
> ;;Toy example on only 15 items:
> ;; ls is the list and counter is the associated values
> (defvar ls '("a" "b" "c" "b" "a" "f" "e" "g" "h" "k" "z" "k" "r" "u"
> "f"))
> (defvar counter '(1 5 8 7 14 8 3 7 9 4 3 21 5 7 9))
Two points:
1) Name special variables using asterisks "*ls*"
2) Never use literal objects if you plan to destructively modify them
(see below)
Minor issue - naming variables is often better done using the
semantics within the program and
not their actual type (I guess you you used "ls" as an abbreviation of
"list").
> ;;while macro similar to dotimes.
> (defmacro while (condition &rest body)
> (let ((var (gensym)))
> `(do ((,var nil (progn ,@body)))
> ((null ,condition) ,var))))
Why to the hell do you need this macro if you actually really want
dotimes (a counting loop)?
> ;;Tabulate like the pivot table.
> (setf i 0)
> (while (< i (length ls))
> (setf j (+ i 1))
> (while (< j (length ls))
> (if (AND (equal (nth i ls) (nth j ls)) (not (equal (nth j ls)
> 'indic)))
> (AND (setf (nth i counter)
> (+ (nth j counter) (nth i counter)))
> (AND (setf (nth j ls) 'indic) (setf (nth j counter) 'indic))))
> (incf j))
> (pprint i)(incf i))
> ;;Remove the indicators.
> (delete 'indic ls)
> (delete 'indic counter)
> ;; printing ls and counter now gives the summed values.
You're using LENGTH and NTH within each iteration of your loop. This
functions have a time complexity of O(N) with N being the length of
the used lists. As your algorithm itself is actually O(N^2) (two
nested loops) the number of accesses to the list are quite obscene.
Each one of the NTH calls within your inner loop will have N accesses
to the list so its N*N*N=N^3*8 accesses to the loop (not counting
accesses in outer loops). If your list has 30000 elements this would
mean something like 216,000,000,000,000 accesses to the list! On a
4GHz computer with one access counted oversimplified as one cycle this
would be somewhere around 15 hours of list accessing. If you just
eliminate the O(N) accesses to the list - the estimated runtime would
go down to something like 1.8 seconds.
ciao,
Jochen
--
Jochen Schmidt
CRISPYLOGICS
Uhlandstr. 9, 90408 Nuremberg
Fon +49 (0)911 517 999 82
Fax +49 (0)911 517 999 83
mailto:(format nil "~(····@~36r.~36r~)" 870180 1680085828711918828
16438) http://www.crispylogics.com
On Aug 16, 8:21 am, Francogrex <······@grex.org> wrote:
> On Aug 16, 12:21 pm, Jochen Schmidt <····@crispylogics.com> wrote:
>
> > You're using LENGTH and NTH within each iteration of your loop. This
> > functions have a time complexity of O(N) with N being the length of
> > the used lists. As your algorithm itself is actually O(N^2) (two
> > nested loops) the number of accesses to the list are quite obscene.
> > Each one of the NTH calls within your inner loop will have N accesses
> > to the list so its N*N*N=N^3*8 accesses to the loop (not counting
> > accesses in outer loops). If your list has 30000 elements this would
> > mean something like 216,000,000,000,000 accesses to the list! On a
> > 4GHz computer with one access counted oversimplified as one cycle this
> > would be somewhere around 15 hours of list accessing. If you just
> > eliminate the O(N) accesses to the list - the estimated runtime would
> > go down to something like 1.8 seconds.
>
> Thanks, you gave me good tips on a better style and I think I can
> substitute LENGTH so the program would be less troubled with repeated
> access to that function, but you didn't give me an alternative to
> using NTH: how else and more efficiently would I be accessing
> individual elements of the list?
Don't write useless macros like WHILE and use (LOOP WHILE ....)
Use VECTORs. As Jochen has told you list operations are inherently
linear. Just don't use them for this sort of numerical work and use
vectors or arrays instead. Access is then constant time.
Cheers
--
Marco