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