Lists, tuples and memory.

[Elbert Lev]

Hi, all!

Here is the problem:
I have a file, which contains a common dictionary - one word per line
(appr. 700KB and 70000 words). I have to read it in memory for future
"spell checking" of the words comming from the customer. The file is
presorted. So here it goes:

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt "))

Works like a charm. It takes on my machine 0.7 seconds to do the trick
and python.exe (from task manager data) was using before this line is
executed
2636K, and after 5520K. The difference is 2884K. Not that bad, taking
into account that in C I'd read the file in memory (700K) scan for
CRs, count them, replace with '\0' and allocate the index vector of
the word beginnigs of the size I found while counting CRs. In this
particular case index vector would be almost 300K. So far so good!

Then I realized, that lstdict as a list is an overkill. Tuple is
enough in my case. So I modified the code:

t = tuple(file("D:\ \CommonDictiona ry.txt"))
lstdict = map(lambda x: x.lower().strip (), t)

This code works a little bit faster: 0.5 sec, but takes 5550K memory.
And maybe this is understandable: after all the first line creates a
list and a tuple and the second another tuple (all of the same size).

But then I decieded to compare this pieces:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

As expected, after line 2 memory was 5550K, but after line 3 it jumped
to 7996K!!!

The question:

If refference counting is used, why the second assignment to lstdict
(line 3) did not free the memory alocated by the first one (line 2)
and reuse it?

So one more experiment:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2
del lstdict # 3
lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 4

In this case executing line 4 did not add memory!

By the way, the search speed is very-very good when done by function:

def inDict(lstdict, word):
try:
return lstdict[bisect(lstdict, word) - 1] == word
except:
return False

500 words are tested in less then 0.03 seconds.

[Christopher T King]

On 15 Jul 2004, Elbert Lev wrote:

But then I decieded to compare this pieces:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

As expected, after line 2 memory was 5550K, but after line 3 it jumped
to 7996K!!!

The question:

If refference counting is used, why the second assignment to lstdict
(line 3) did not free the memory alocated by the first one (line 2)
and reuse it?

Because after line 2, you still have a 2MB tuple sitting around in 't'. ;)

Try this:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t)
del t # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

Python doesn't know that you're not going to try to access t at some
future point, even though there are no more accesses in your code.

A couple of other thoughts on what you're doing:

1) Stick with lists. Tuples are meant to be used not really as immutable
lists, but as a way to group related items of different types. e.g. the
sequence 'apple','orange ','pear','banan a' should be stored in a list,
whereas the group of related items 'apple','red',3 ,5 (presumably
describing an apple in some predefined manner, say,
fruit,color,wid th,height) should be stored in a tuple. At least that's
what Guido wants us to do. ;)

2) Assuming you're using a newer version of Python, try using a list
comprehension instead of map(). It's a little bit cleaner, and will
probably be a bit faster too:

lstdict = [x.lower().strip () for x in file("D:\\Commo nDictionary.txt ")]

If you've never worked with them before, list comprehensions are a new
syntax intended to replace map(), filter(), and other such constructs with
one unified syntax. They're usually very easy to read and write (as the
one above is) since they help you avoid using lambda.

[Larry Bates]

Any reason not to put the words into a dictionary?

Then your code becomes:

lstdict=dict([(x.lower().stri p(), None) for x in
file("D:\\Commo nDictionary.txt ")])
if lstdict.has_key (word):
do something

(not tested, but should be close)

I'll bet access is faster (even if loading is slightly slower).
You also benefit from the fact that the dictionary file
doesn't need to be kept sorted.

HTH,
Larry Bates
Syscon, Inc.

"Elbert Lev" <el*******@hotm ail.com> wrote in message
news:94******** *************** ***@posting.goo gle.com...

Hi, all!

Here is the problem:
I have a file, which contains a common dictionary - one word per line
(appr. 700KB and 70000 words). I have to read it in memory for future
"spell checking" of the words comming from the customer. The file is
presorted. So here it goes:

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt "))

Works like a charm. It takes on my machine 0.7 seconds to do the trick
and python.exe (from task manager data) was using before this line is
executed
2636K, and after 5520K. The difference is 2884K. Not that bad, taking
into account that in C I'd read the file in memory (700K) scan for
CRs, count them, replace with '\0' and allocate the index vector of
the word beginnigs of the size I found while counting CRs. In this
particular case index vector would be almost 300K. So far so good!

Then I realized, that lstdict as a list is an overkill. Tuple is
enough in my case. So I modified the code:

t = tuple(file("D:\ \CommonDictiona ry.txt"))
lstdict = map(lambda x: x.lower().strip (), t)

This code works a little bit faster: 0.5 sec, but takes 5550K memory.
And maybe this is understandable: after all the first line creates a
list and a tuple and the second another tuple (all of the same size).

But then I decieded to compare this pieces:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

As expected, after line 2 memory was 5550K, but after line 3 it jumped
to 7996K!!!

The question:

If refference counting is used, why the second assignment to lstdict
(line 3) did not free the memory alocated by the first one (line 2)
and reuse it?

So one more experiment:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2
del lstdict # 3
lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 4

In this case executing line 4 did not add memory!

By the way, the search speed is very-very good when done by function:

def inDict(lstdict, word):
try:
return lstdict[bisect(lstdict, word) - 1] == word
except:
return False

500 words are tested in less then 0.03 seconds.

[Roy Smith]

"Larry Bates" <lb****@swamiso ft.com> wrote:

Any reason not to put the words into a dictionary?
[...]
I'll bet access is faster (even if loading is slightly slower).

One trick I've used when I have something with a long startup time
because it's parsing static files and building data structures is to
build the data structure once, then pickle it (see the pickle and
cPickle modules).

You production code then just has to call cPickle.load (file) and you're
up and running way faster than re-parsing the original data files.

[Andrew MacIntyre]

On Fri, 15 Jul 2004, Elbert Lev wrote:

{...}

But then I decieded to compare this pieces:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

As expected, after line 2 memory was 5550K, but after line 3 it jumped
to 7996K!!!

The question:

If refference counting is used, why the second assignment to lstdict
(line 3) did not free the memory alocated by the first one (line 2)
and reuse it?

So one more experiment:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2
del lstdict # 3
lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 4

In this case executing line 4 did not add memory!

The reason the memory is not released without the explicit del is that the
reference count of the original object is not adjusted until the
rebinding of "lstdict" takes place, which is after the new object is fully
constructed. The del in your experiment forces this adjustment.

--
Andrew I MacIntyre "These thoughts are mine alone..."
E-mail: an*****@bullsey e.apana.org.au (pref) | Snail: PO Box 370
an*****@pcug.or g.au (alt) | Belconnen ACT 2616
Web: http://www.andymac.org/ | Australia

[Terry Reedy]

"Larry Bates" <lb****@swamiso ft.com> wrote in message
news:CL******** ************@co mcast.com...

Any reason not to put the words into a dictionary?
for spell checking, I think I would...
Then your code becomes:

lstdict=dict([(x.lower().stri p(), None) for x in
file("D:\\Commo nDictionary.txt ")])

The list comp creates an unnecessary (and, in this case, large)
intermediate list.
In 2.4, removing the [] pair would result in a generator expression.
In the meanwhile...

def lostrip(src): .... for w in src: yield w.lower().strip (), None
.... t = dict(lostrip(['abc ', 'DEG\n']))
t

{'abc': None, 'deg': None}

Terry J. Reedy

[Dennis Lee Bieber]

On Thu, 15 Jul 2004 15:52:53 -0400, Christopher T King
<sq******@WPI.E DU> declaimed the following in comp.lang.pytho n:

whereas the group of related items 'apple','red',3 ,5 (presumably
describing an apple in some predefined manner, say,
fruit,color,wid th,height) should be stored in a tuple. At least that's
Must be a mutant red pear <G>

I don't think I've ever seen an apple with a 2" difference in
height vs width. Granted, a Red Delicious (being a common apple) does
have a bit of a height advantage...

Now, if it were 3 (per pound) and 5 (pounds) <G> (I think one
reference for carb count [diabetic here] has small apples at 3/pound,
large at 2/pound).

-- =============== =============== =============== =============== == <
wl*****@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
wu******@dm.net | Bestiaria Support Staff <
=============== =============== =============== =============== == <
Home Page: <http://www.dm.net/~wulfraed/> <
Overflow Page: <http://wlfraed.home.ne tcom.com/> <

[Elbert Lev]

Andrew MacIntyre <an*****@bullse ye.apana.org.au > wrote in message news:<ma******* *************** *************** @python.org>...

On Fri, 15 Jul 2004, Elbert Lev wrote:

{...}

But then I decieded to compare this pieces:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 3

As expected, after line 2 memory was 5550K, but after line 3 it jumped
to 7996K!!!

The question:

If refference counting is used, why the second assignment to lstdict
(line 3) did not free the memory alocated by the first one (line 2)
and reuse it?

So one more experiment:

t = tuple(file("D:\ \CommonDictiona ry.txt")) # 1
lstdict = map(lambda x: x.lower().strip (), t) # 2
del lstdict # 3
lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt ")) # 4

In this case executing line 4 did not add memory!

The reason the memory is not released without the explicit del is that the
reference count of the original object is not adjusted until the
rebinding of "lstdict" takes place, which is after the new object is fully
constructed. The del in your experiment forces this adjustment.

Thanks!

This is what I wanted to know.

[Arthur]

On Thu, 15 Jul 2004 15:52:53 -0400, Christopher T King
<sq******@WPI.E DU> wrote:

1) Stick with lists. Tuples are meant to be used not really as immutable
lists, but as a way to group related items of different types. e.g. the
sequence 'apple','orange ','pear','banan a' should be stored in a list,
whereas the group of related items 'apple','red',3 ,5 (presumably
describing an apple in some predefined manner, say,
fruit,color,wi dth,height) should be stored in a tuple. At least that's
what Guido wants us to do. ;)
But with Fletcher's confession of sticking with tabs ... its anarchy
out there.

2) Assuming you're using a newer version of Python, try using a list
comprehensio n instead of map(). It's a little bit cleaner, and will
probably be a bit faster too:

Faster is good.

Modern and progessive governance. The tax incentive concept at work.

Art

[John Lenton]

On 15 Jul 2004 12:09:47 -0700, Elbert Lev <el*******@hotm ail.com> wrote:

Hi, all!

Here is the problem:
I have a file, which contains a common dictionary - one word per line
(appr. 700KB and 70000 words). I have to read it in memory for future
"spell checking" of the words comming from the customer. The file is
presorted. So here it goes:

lstdict = map(lambda x: x.lower().strip (),
file("D:\\Commo nDictionary.txt "))

Works like a charm. It takes on my machine 0.7 seconds to do the trick
and python.exe (from task manager data) was using before this line is
executed
2636K, and after 5520K. The difference is 2884K. Not that bad, taking
into account that in C I'd read the file in memory (700K) scan for
CRs, count them, replace with '\0' and allocate the index vector of
the word beginnigs of the size I found while counting CRs. In this
particular case index vector would be almost 300K. So far so good!

Then I realized, that lstdict as a list is an overkill. Tuple is
enough in my case. So I modified the code:

t = tuple(file("D:\ \CommonDictiona ry.txt"))
lstdict = map(lambda x: x.lower().strip (), t)

This code works a little bit faster: 0.5 sec, but takes 5550K memory.
And maybe this is understandable: after all the first line creates a
list and a tuple and the second another tuple (all of the same size).

any reason you didn't do it as

lstdict = tuple([x.strip().lower (), file("D:\\Commo nDictionary.txt ")])

?

also, you might find you can use chunks of the bisect module to speed
up your searching, if you find using a dict too expensive. That's
assuming the bisect module is written in C, which I haven't checked.

--
John Lenton (jl*****@gmail. com) -- Random fortune:
bash: fortune: command not found