How to make a reverse for loop in python?

[Steven D'Aprano]

On Sat, 20 Sep 2008 16:27:41 -0700, Alex Snast wrote:

> Another quick question please, is the List data structure just a dynamic
> array? If so how can you use static size array, linked list, AVL trees
> etcetera.

Before I answer your question, I should say that you can go a LONG way 
with just the standard Python built-in data structures list, dict and 
set, plus a handful of standard modules like array and collections. It's 
often (but not always) better to modify an algorithm to use a built-in 
data structure than to try to implement your own.


The underlying data structure for lists is implementation specific. Only 
the behaviour is specified by the language.

In the standard Python implementation written in C (usually known as 
"Python", although sometimes people explicitly describe it as CPython), 
lists are implemented as a fixed array of pointers. The array is 
periodically resized, either up or down, but only as needed. The largest 
consequence of that is that appending to the end of a list is much faster 
than inserting at the beginning of the list.

Other implementations (IronPython, Jython, PyPy, CLPython...) are free to 
implement lists whatever way they need.

If you want a static list, the simplest way is to create a list and 
simply not resize it. If you want to enforce that, here's a subclass to 
get you started:

class StaticList(list):
    def _resize(self):
        raise RuntimeError("list can't be resized")
    extend = append = pop = insert = remove = \
    __delitem__ = __delslice__ = _resize


I haven't dealt with __setitem__ or __setslice__, because they're more 
complicated: you need to make sure the slice you're setting has the same 
size as the bit you're replacing, so that this is allowed:

mylist[3:6] = [1, 2, 3]

but not these:

mylist[3:6] = [1, 2]
mylist[3:6] = [1, 2, 3, 4]


As for linked lists and trees, don't worry about pointers, just go ahead 
and implement them.

# basic, no-frills tree
class Node(object):
    def __init__(self, data, left=None, right=None):
        self.left = left
        self.right = right
        self.info = data

tree = Node('top of the tree')
tree.left = Node('left subtree')
tree.right = Node('right subtree', None, Node('another subtree'))
t = tree.right.right
t.left = Node('yet another subtree')

etc.

The CPython implementation of dict is a hash table, and dicts are 
extremely fast and efficient. So long as you don't mind losing the order 
of insertion, you won't beat dicts for speed and efficiency in anything 
you write in pure Python.



-- 
Steven