On Tue, Dec 30, 2014 at 05:40:04PM -0500, wolfrage8...@gmail.com wrote:
> On Tue, Dec 30, 2014 at 2:37 PM, Danny Yoo <d...@hashcollision.org> wrote:
> > If that's the case, then none of this requires linked list storage.
> >
> > Instead, we can represent this as a list of rows. Each row element
> > would be itself a list of tiles. In short, a matrix. See:
> > https://docs.python.org/2/faq/programming.html#how-do-i-create-a-multidimensional-list
>
> True, I could use a multidimensional list. And originally I was using
> a 2D list. But I wanted the ability to QUICKLY search across a row or
> up and down a column and so the added benefit of the linked list was
> that it simply requires me to access the next node reference.
[emphasis added]
Trust me on this, there is no linked list code you can write in
Python that will be faster than using a list of lists.
Even in C, traversing a linked list is slower than array access, and
Python is not C.
> > And finding neighboring tiles also wouldn't be too bad: Given a tile
> > at (i, j), we can find its neighbors through arithmetic (i plus or
> > minus one, j plus or minus one).
>
> From a coding perspective the linked list seemed simplier, because my
> other 2D list implementation required me to have a function that could
> map from any position to North, South, East, & West, plus it needed to
> perform bounds checking. Of course having the list now be doubly
> linked has added complexity.
Bounds checking is easy: cell [i, j] is in bounds if this is true:
(0 <= i < NUM_ROWS) and (0 <= j < NUM_COLS)
Fast access to any cell is possible:
array[i][j]
gives you access to the cell [i, j] effectively instantly, two
array accesses, which is much, much faster than having to traverse a
linked list:
cell = array
for x in range(i):
cell = cell.next_row
for x in range(j):
cell = cell.next_col
(or whatever scheme you use for linking to the next row/column).
As far as memory consumption goes, I don't think there is any
comparison. Here is a doubly-linked list of strings:
class Cell:
__slots__ = ['data', 'next', 'prev']
def __init__(self, data):
self.data = data
self.next = self.prev = None
x = y = Cell('alpha0')
for i in range(1, 10):
y.next = Cell('alpha' + str(i))
y.next.prev = y
y = y.next
Now let's see how much memory it uses:
from sys import getsizeof
size = 0
y = x
while y is not None:
size += getsizeof(y) + getsizeof(y.data)
y = y.next
On my system, that gives size of 630 bytes.
Let's do the same for a list. This only takes two lines of code:
x = ['alpha' + str(i) for i in range(0, 10)]
size = getsizeof(x) + sum(getsizeof(s) for s in x)
On my system, that gives a size of 406 bytes, considerably smaller.
--
Steven
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
