Re: efficiently accumulating values



liyer.vijay@xxxxxxxxx wrote:
Ken Tilton wrote:

liyer.vijay@xxxxxxxxx wrote:


Any other suggestions? What am I doing wrong?

Maybe nothing, but ever since you found that timing mistake that caused
one Lisp version to only seem to go blazingly fast I keep wondering if
you had the same bug in the Python timing. :)

Do you have a full standalone example others could run? Toss in the
Python version as well. Maybe the ACL profiler will reveal something,
though to be honest I have a wicked hard time understanding its output
(hint to Franz <g>).


I too had a hard time with SBCL's profiler, though, admittedly, I
didn't spend too much time reading the SBCL manual.


I would also be interested in the counts, shy of a full reproducible.
What are the dimensions, how many words found, etc, etc.

kenny



Here is the lisp I wrote when I fisrt came with my questions.

Actually, now I wish I had just the counts. esp, how many words are being stored and how many distinct prefixes, because...


(defpackage :vijay.boggle
(:use :cl)
(:export :boggle :read-dictionary-file)
(:nicknames :boggle))

(in-package :boggle)


(defvar *words* (make-hash-table :test #'equal)
"The actual dictionary of words.")
(defvar *prefixes* (make-hash-table :test #'equal)
"The prefixes of all the words.")
(defparameter *minimum-length* 3 "The minimum length for any word.")

(defun read-dictionary-file (filename)
"Reads the dictionary in FILENAME and stores it."
(with-open-file (file filename) (read-dictionary file)))

(defun read-dictionary (stream)
"Reads in STREAM and stores its words in the dictionary."
(loop as line = (read-line stream nil nil)
while line
as word = (string-downcase (string-trim #(#\Space #\Tab) line))
if (> (length word) 2) do (add-word word)))

(defun add-word (word)
"Add WORD to the dictionary."
(setf (gethash word *words*) t)
(loop as i from 2 below (1- (length word)) ; prefix ends at
penultimate char
as prefix = (subseq word 0 i)

"subseq creates a sequence that is a copy of the subsequence of sequence bounded by start and end. "

Ouch. Just to store a prefix we first cons up an entire copy of the prefix? Hello performance hit. I be guessing Python, being a C derivative, is just using a fixed pointer and length from the i subscript and hashing off the intervening characters. The lisp equivalent would be....? I don't know. I am no array wizard, but it seems to me you need some costless way to take a full word and hand increasingly long subsequences (not using SUBSEQ!) to gethash just by incrementing a pointer (which is what I am guessing Python is doing).

I'll leave that as an exercise, but this is the classic Lisp newby performance gotcha. Yeah, subseq is awesome for the 99 times out of 100 that you do not want to get killed by side effects (or is that 9999 out of 10000?), but whenever a Lispnik is writing code they know will get hit a kazillion times and they also need it to run close to the speed of C, well, when they get tempted to use subseq or any other such chunking form they know enough to look it up in the CLHS to see if it copies.

kt

--
Cells: http://common-lisp.net/project/cells/

"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
.

Relevant Pages

  • Re: Python syntax in Lisp and Scheme
    ... Consider this python code: ... 15 while stack: ... 12;; like os.listdir, but traverses directory trees ... Forgetting to indent properly in a lisp program does not yield ...
    (comp.lang.python)
  • Re: Python syntax in Lisp and Scheme
    ... Consider this python code: ... 15 while stack: ... 12;; like os.listdir, but traverses directory trees ... Forgetting to indent properly in a lisp program does not yield ...
    (comp.lang.lisp)
  • Re: Python syntax in Lisp and Scheme
    ... > the parens until the matching one at the beginning of the DOLIST begins ... > Forgetting to indent properly in a lisp program does not yield ... of course forgetting to indent does not *directly* yield erroneous code. ... if you make an edit in python the result of this edit is immediately ...
    (comp.lang.python)
  • Re: Python syntax in Lisp and Scheme
    ... > the parens until the matching one at the beginning of the DOLIST begins ... > Forgetting to indent properly in a lisp program does not yield ... of course forgetting to indent does not *directly* yield erroneous code. ... if you make an edit in python the result of this edit is immediately ...
    (comp.lang.lisp)
  • Re: merits of Lisp vs Python
    ... The prefix position needs of more abstraction ... LISP form is confusing. ... region in the hypersurface and localization is 'infix'. ... I am not trying to convince some LISPer to change the chip; ...
    (comp.lang.lisp)