Re: How to make a reverse for loop in python?
On Sep 21, 3:47 am, Steven D'Aprano [EMAIL PROTECTED]
cybersource.com.au wrote:
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
WOW you guys are really helpful, thanks everyone for all the replies.
Last question:
What IDE do you guys recommend, I'm currently using pydev.
Thanks again, Alex
--
http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Alex Snast a écrit : Hello I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) for (i = 0; i 10; i--) - for i in range(10): for (i = 10; i = 0; --i) - for i in range(10,-1,-1): Thoma -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 20, 11:16�am, Alex Snast [EMAIL PROTECTED] wrote: Hello I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) for i in xrange(10,-1,-1): print i, 10 9 8 7 6 5 4 3 2 1 0 Note the starting number is 10, the ending number is -1 because you want to include 0 and the step size is -1. -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Alex Snast [EMAIL PROTECTED] wrote: Hello I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i except you virtually never want to do that in Python. Don't expect just to translate statement by statement from one language to another: normally in Python you will iterate directly over the sequence you want to process rather than trying to count loop indices with all the telegraph pole errors that result. The usual way to iterate over a sequence in reverse is: for x in reversed(seq): print x although if you know it is a list, string or other object that supports extended slicing you can also do: for x in seq[::-1]: print x this may be less clear than using 'reversed', but does allow you to specify an explicit start, stop and step if you want to do only part of the sequence. -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
2008/9/20 Alex Snast [EMAIL PROTECTED]: I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) for i in range(10, 0, -1): print i -- Cheers, Simon B. -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Alex Snast wrote: I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) use range with a negative step: for i in range(10-1, -1, -1): ... or just reverse the range: for i in reversed(range(10)): ... (the latter is mentioned in the tutorial, and is the second hit if you google for python reverse for loop) /F -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Alex Snast wrote: Hello I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) -- http://mail.python.org/mailman/listinfo/python-list What are you trying to loop through? If it's the contents of a list, you can reverse the list (in place) first: L = [1,2,3] L.reverse() for item in L: print item Or you can create a new reversed (copy of the original) list and iterate through it for item in reversed(L): print item If it's just a sequence of numbers you want to generate: range(3) generates a forward list [0,1,2], and range(3,0,-1) generates a backward list [2,1,0] so for i in range(11,0,-1): might be what you want. If your list is huge, consider xrange rather than range. And as always, you could just roll your own index manipulation: i = 10 while i =0: # do whatever i -= 1 Gary Herron -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Fredrik Lundh wrote: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) use range with a negative step: for i in range(10-1, -1, -1): ... or just reverse the range: for i in reversed(range(10)): ... (and to include the 10 in the range, add one to the 10 above) /F -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Gary Herron wrote: Or you can create a new reversed (copy of the original) list and iterate through it for item in reversed(L): print item It's not a copy, it's a view: items = [1,2,3] r = reversed(items) items[:] = abc for item in r: print item ... c b a Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Duncan Booth: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i I'd use xrange there. Anyway, I have always felt that Python syntax not easy to understand at first sight, expecially when you try to convert a bit more complex inverted for loops from/to C to/from Python. It's one of the few cases where (for example) Pascal (loop) syntax wins a bit over Python syntax :-) Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 20, 8:13 pm, [EMAIL PROTECTED] wrote: Duncan Booth: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i I'd use xrange there. Anyway, I have always felt that Python syntax not easy to understand at first sight, expecially when you try to convert a bit more complex inverted for loops from/to C to/from Python. It's one of the few cases where (for example) Pascal (loop) syntax wins a bit over Python syntax :-) Bye, bearophile That's a lot of responses guys. Thanks a lot i think i got it. Another question, are there any pointers in python (or iterators) for when i use a data structure that doesn't support random access? Thanks again, Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 20, 8:13 pm, [EMAIL PROTECTED] wrote: Duncan Booth: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i I'd use xrange there. Anyway, I have always felt that Python syntax not easy to understand at first sight, expecially when you try to convert a bit more complex inverted for loops from/to C to/from Python. It's one of the few cases where (for example) Pascal (loop) syntax wins a bit over Python syntax :-) Bye, bearophile 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
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. You should treat Python lists as an opaque item. You shouldn't concern yourself with the implementation details. Python lists are fast and optimized for most use cases. Unless you have specific needs for highly specialized data types, use lists. Just *don't* try to abuse lists by creating fancy stuff e.g. linked lists. The memory overhead is going to kill your app. Christian -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
En Sat, 20 Sep 2008 20:27:41 -0300, Alex Snast [EMAIL PROTECTED] escribió: 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. Yes, lists are implemented as dynamic arrays (but you shouldn't care about it). Textbook linked lists are good for a CS course, but useless in most usual circumstances (think of memory fragmentation). There are AVL trees implemented in Python, but not built in. Read the Python Tutorial specially this section http://docs.python.org/tut/node7.html You may be interested in the collections module too http://docs.python.org/lib/module-collections.html -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sat, 20 Sep 2008 16:22:31 -0700, Alex Snast wrote: That's a lot of responses guys. Thanks a lot i think i got it. Another question, are there any pointers in python (or iterators) for when i use a data structure that doesn't support random access? That surely depends on the data structure. Assume it supports sequential access: data[0], data[1], data[2], etc in that order without skipping or going backwards. Then you can simply do this: for item in data: process(item) which is the equivalent of this: try: i = 0 while True: process(data[i]) i += 1 except IndexError: pass # we're done The data structure might not support sequential indexing, but still support sequential access: for item in iter(data): process(item) If the data structure is some sort of binary tree, then you would use a standard tree-walking algorithm, something like this: def prefix_traversal(node): process(node.info) prefix_traversal(node.left) prefix_traversal(node.right) and similarly for infix and postfix. (Although the specific names 'left', 'right', 'info' are arbitrary.) If you don't have any specific knowledge of how to iterate over the data structure, then try reading the docs *wink*. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
Christian Heimes: Unless you have specific needs for highly specialized data types, use lists. There's also the collections.deque for other related purposes. (I suggest people willing to look at some nice C code to read the sources of deque, Hettinger has created some refined code, very readable). Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sun, 21 Sep 2008 01:56:59 +0200, Christian Heimes wrote: Just *don't* try to abuse lists by creating fancy stuff e.g. linked lists. The memory overhead is going to kill your app. I agree with your advice not to abuse lists, but not for the reason you give. The memory overhead of a linked list implemented on top of a Python list probably isn't going to be that much greater than a dict or a class. I think the real reasons why linked lists get a bad rep in Python are: (1) they're unnecessary 99% of the time; (2) when they are necessary, a better implementation is to use classes (e.g. see traceback objects); and (3) the standard Lisp idiom for lists is horribly inefficient in CPython: alist = [1, [2, [3, [4, [5, [6, []]] But that's primarily inefficient because of the number of method calls needed to access an item. There is some memory overhead, but memory is cheap and the overhead of using objects in the first place is far larger than the overhead of a few extra pointers. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
