Memory ?
Alex Martelli
aleax at aleax.it
Mon Jul 8 05:57:58 EDT 2002
Shagshag13 wrote:
>
> Great thanks for the reply ! It helps a lot to understand !
>
>> I'm not sure what you mean by "boxed" in this context.
>
> That i can' t guess the size of my arrays (range from 0 to ???)
Both the array.array type, and the vastly more powerful Numeric.array
type from the Numeric extension package, are arrays that can grow and
shrink.
>> But if you don't need such alterations and
>> insertions, a mapping from the compact set [0..N) to any multiset of
>> N values is indeed faster and less memory-hungry as a sequence, typically
>> a list, than as a dictionary
>
> Sorry to ask but what do you call a "mapping" ?
Python containers are divided into "mappings" and "sequences".
Typical examples of sequences are lists, tuples, strings, instances
of array.array.
Typical examples of mappings are dictionaries.
The lines between them are a bit blurry, particularly now that you
can iterate directly on a dictionary (and presumably other mappings).
In some fields of maths (abstract algebra) a mapping, or map, also
called a function, is a relation M between sets D and R such that
for each and every element d1 of D one, and only one pair (d1,r) is
in M. The terminology about this is all over the map (:-) but it's
still a useful concept to keep in mind -- it hints at underlying
commonalities between (pure) functions, sequences, and mappings in
the Python sense of the word, and implicitly suggests attempting
interchanges between these implementation-separate approaches at
the same (or, very similar) abstract functionality.
In my paragraph that you quote above, they key issue is the clause
*if you don't need such alterations and insertions*. Often, you do.
Consider a FIFO queue implemented in the way that comes immediately
to mind:
class Fifo1(list):
def get(self): return self.pop(0)
def put(self, value): self.append(value)
Now this is fine and dandy, BUT -- self.pop(0) removes the first
element and thus is O(N) where N is the number of items in the
queue at that time. If that is unacceptable, and you need O(1)
behavior (or thereabouts), you can, instead, try:
class Fifo2(list):
def get(self): return self.pop(-1)
def put(self, value): self.insert(0, value)
but this just moves the O(N) behavior to put instead of get.
The simplest way to get O(1) (roughly) on both operations is:
class Fifo3(dict):
def __init__(self):
self.start = self.end = 0
def get(self):
result = self[self.start]
del self[self.start]
self.start += 1
return result
def put(self, value):
self[self.end] = value
self.end += 1
In Python 2.3 I might code the get method a bit differently:
def get(self):
try: return self.pop(self.start)
finally: self.start += 1
but that doesn't change the essential characteristics at all,
it just lets get and put have a more similar structure and
thus arguably enhances clarity.
Alex
More information about the Python-list
mailing list