Memory ?

[Alex Martelli]

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