Re: [Tutor] Making Doubly Linked List with Less Lines of Code.
On 2014-12-30 14:40, wolfrage8...@gmail.com wrote:
True, I could use a multidimensional list. And originally I was using
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.
This problem interested me right from when it was first posted a few
days ago so I tried to code up a solution to what I perceived it (the
problem) to be.
In the process of doing so I discovered that list multiplication does
not at all behave the way I expected (as demonstrated by the
'bad_flip_2_D' function.)
Code follows; comments appreciated. (Since the issue now is list
multiplication,
should this fork into a new subject?)
# script begins here:
#!/usr/bin/env python3
# file: 'two_D_list.py'
"""
OP:
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.
My interpretation/comments:
Required are methods to access/search along column or row.
Assume 2D list already exists.
Can we further assume that all rows are the same length?
Using a class might be the preferable way to go but leave that
for later refactoring.
Assume everyone assumes 0 based numbering.
"""
two_D = [
[0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, 10, 11]
] # For testing purposes.
def get_n_rows(array):
"""Returns length of the array == number of rows."""
return len(array)
def get_n_columns(two_D_array):
"""Returns the length of the first (zero'th) row.
We assume all rows are the same length."""
return len(two_D_array[0])
def search_row(two_D_array, row_num, item):
"""Returns None if not there, else it returns the indices
of the first instance of item found in the row specified.
Not tested."""
try:
col_num = two_D_array[row_num].index(item)
return (row_num, col_num)
except ValueError:
return None
def show_array(array):
for row in range(len(array)):
for col in range(len(array[row])):
entry = array[row][col]
if not entry:
entry = 0
print("{:>3}".format(entry), end='')
print()
print()
def flip_2_D(two_D_array):
"""Flips a two dimensional array so columns become rows
and the rows become columns."""
ret = []
for i in range(get_n_columns(two_D_array)):
ret.append([])
for j in range(get_n_rows(two_D_array)):
ret[i].append([])
for i in range(get_n_rows(two_D_array)):
for j in range(get_n_columns(two_D_array)):
temp = two_D_array[i][j]
# print("putting {} into ({}, {})."
# .format(temp, j, i))
ret[j][i] = temp
# show_array(ret) # For debugging purposes.
return ret
def bad_flip_2_D(two_D_array):
"""Flips a two dimensional array so columns become rows
and the rows become columns.
Demonstrates unexpected (by me) results of array multiplication."""
ret = [[[0]] * get_n_rows(two_D_array)] * get_n_columns(two_D_array)
for i in range(get_n_rows(two_D_array)):
for j in range(get_n_columns(two_D_array)):
temp = two_D_array[i][j]
print("putting {} into ({}, {})."
.format(temp, j, i))
ret[j][i] = temp
show_array(ret) # For debugging purposes.
return ret
def search_col(two_D_array, col_num, item):
"""Returns None if not there, else it returns the indices of
the first instance of item found in the column specified.
Simply reconstruct the array and then use search_row."""
flipped = flip_2_D(two_D_array)
return search_row(flipped, col_num, item)
if __name__ == "__main__":
print("Running Python3 script: 'two_D_list.py'...")
print(get_n_rows(two_D), get_n_columns(two_D))
print
show_array(two_D)
show_array(flip_2_D(two_D))
# end of script
Other possibly required info:
alex@x301:~/Python/Tutor$ uname -a
Linux x301 3.13.0-43-generic #72-Ubuntu SMP Mon Dec 8 19:35:44 UTC 2014
i686 i686 i686 GNU/Linux
cheers,
Alex
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Making Doubly Linked List with Less Lines of Code.
On Tue, Dec 30, 2014 at 2:37 PM, Danny Yoo 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. > > 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. > > If the game grid were a lot more dynamic and non-squarish, then that > might make it appropriate. Linked lists give us a flexible way to > represent such a game board. But at the moment, I think it's overkill > for the scenario you're showing us. That may be True. I would like to know, if you know, would this doubly linked list be more or less memory efficient than the 2D list method and which one would provide faster look-ups? I do know that the doubly linked list has an initial speed cost in constructing it, which is obviously more than the 2D list. The overall application to which this code will be applied is a Kivy App that will be deployed to mobile devices, that is why I have these questions, although I realize this is pre-optimizing which is the root of evil... ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Making Doubly Linked List with Less Lines of Code.
>> What are the _operations_ you want to support? Can you say more about >> this? > > I need to support lookups, no insertions or deletions are required. This > code will be used to quickly lookup nodes, and check for specific patterns > by checking the nodes values in either a row or column. As it stands, I believe you want these operations: * Construct a game grid with a certain number of rows and columns * Find a tile within the grid, given its row and column. * Given a tile in the grid, find the neighboring tiles around it. 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 Its construction wouldn't be too bad. Something like: self.rows = [[None] * self.num_of_cols for i in range(self.num_of_rows)] Finding a tile (i, j) in such a structure would be direct list indexing. self.rows[i][j] 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). If the game grid were a lot more dynamic and non-squarish, then that might make it appropriate. Linked lists give us a flexible way to represent such a game board. But at the moment, I think it's overkill for the scenario you're showing us. Good luck! ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Making Doubly Linked List with Less Lines of Code.
This is my most recent rendition of the code. It still needs to be
improved. Below I am answering some questions that were posed. Also I
think my code is currently wrong because I think the print_by functions
are both printing the list the same way. Tomorrow I will fix this and
improve the code.
Thank you guys for your help so far.
class GameTile():
def __init__(self, id, **kwargs):
self.id = id
self.value = None
self.next_node_in_row = None
self.next_node_in_col = None
self.prev_node_in_row = None
self.prev_node_in_col = None
class GameGrid():
def __init__(self, **kwargs):
self.num_of_cols = 8
self.num_of_rows = 10
# Each variable below is a list of links to the head
# node in the respective row or column.
self.rows = [None] * self.num_of_rows
self.cols = [None] * self.num_of_cols
self.skip_to_row = None
self.skip_to_col = None
self.tile_list = list()
def make_grid_nodes(self):
for row in range(0, self.num_of_rows):
for column in range(0, self.num_of_cols):
tile = GameTile(id=str(column) + ',' + str(row))
self.tile_list.append(tile)
if column == 0: # New Head of Row
self.rows[row] = tile
else:
prev_row.next_node_in_row = tile
tile.prev_node_in_row = prev_row
prev_row = tile
if row == 0: # New Head of Column
self.cols[column] = tile
else:
prev_col.next_node_in_col = tile
tile.prev_node_in_col = prev_col
prev_col = tile
def print_by_rows(self):
for col, the_column in enumerate(self.cols):
print(the_column.id)
if the_column.next_node_in_row is not None:
node = the_column.next_node_in_row
while node.next_node_in_row is not None:
print(node.id)
node = node.next_node_in_row
def print_by_row(self):
for row in self.rows:
print(row.id)
if row.next_node_in_row is not None:
node = row.next_node_in_row
while node.next_node_in_row is not None:
print(node.id)
node = node.next_node_in_row
def print_by_col(self):
for col in self.cols:
print(col.id)
if col.next_node_in_col is not None:
node = col.next_node_in_col
while node.next_node_in_col is not None:
print(node.id)
node = node.next_node_in_col
def draw_grid(self):
import time
sep = '─'
f = '░│'
l = '◈│'
row = sep + '\n│'
last_col = None
current_col = None
val = None
for node in self.tile_list:
if node.value == None:
val = l
else:
val = f
current_col = node.id.split(',')[1]
if last_col is None:
row += val
elif current_col == last_col:
row += val
else:
row += '\n' + sep + '\n│' + val
last_col = node.id.split(',')[1]
row += '\n' + sep
print(row)
#time.sleep(1)
temp = GameGrid()
temp.make_grid_nodes()
#temp.draw_grid()
temp.print_by_row()
print('BREAK Now COLUMNS')
temp.print_by_col()
On 12/25/2014 12:31 AM, Danny Yoo wrote:
What are the _operations_ you want to support? Can you say more about this?
I need to support lookups, no insertions or deletions are required. This
code will be used to quickly lookup nodes, and check for specific
patterns by checking the nodes values in either a row or column. The
code to perform the pattern matching was already written and is fast,
but I will add it to the code once the creation
On 12/24/2014 04:56 PM, Steven D'Aprano wrote:
Wow. It certainly is bloated.
Agreed.
Look for the opportunity to write code like this instead of using range:
for col, the_column in enumerate(self.columns):
self.columns[col] = process(the_column)
This caught my eye, and I did try to implement it. But why use this
instead of range? I am using Python3. I did find that enumerate is
potentially faster but sometimes slower, as it depends on what is being
done. Perhaps because it is considered more Pythonic? So what is your
reason for this suggestion?
Any time you write more than a trivial amount of code twice, you should
move it into a function. Then, instead of:
I agree, should have done, and need to look for these opportunities sooner.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] [OT] Best Practices for Scientific Computing
- On Tue, Dec 30, 2014 12:34 PM CET Alan Gauld wrote: >On 29/12/14 23:50, Patti Scott wrote: >> Could someone clarify "Modularize code rather than copying and pasting?" > >Joel and Danny have given the basic answer in terms of putting >loose code into functions. But it goes a little further too. > >You can be tempted to copy/paste functions because they almost >do what you want but not quite (maybe the take a list of values >and you want to use a dictionary). Its easy to copy the function >and change all the numerical indexes into keys and use the >dictionary. But it would be better to change the original function >so that it can work with both, if possible. This usually involves >representing the variations in behaviour as parameters in the >function (usually with defaults to retain the original semantics). But isn't there a point where you break the 'law' that a function should have one and only one goal? At a certain point you end up with a big fat juicy function that not only takes dicts and lists, but also scratches your back, does the laundry,... >Another case might be where you have a bunch of functions that operate on a >global data structure. Then you want to have a second similar data structure >but you can't use the functions on it because they access >the existing global. You could copy/paste the functions and change the data >reference. But it would be better to either add the data structure reference >to the functions as a parameter, or you create a class that has the data as an >internal instance attribute. > >Finally, you might have some code in a program that you want to use in another >program. But you can't just import the first program because >it runs all sorts of other stuff you don't need. So you just copy >out the functions you want. Or you could put the loose code into a function >(main() usually) and call that within a Say you have a file 'helpers.py' that contains functions that you might use across projects. How do you only display the functions that you actually used in your (Sphinx) documentation of a particular project? >if __name__ === "__main__": main() > >line in your original program, turning it into a reusable module >which you can now safely import. > >So modularize can have several meanings, it applies to any >mechanism used to bundle up code for reuse. The point being that reusing code, >whether as a function, module or class, is more >flexible and reliable than copy/pasting it. > >PS. >Note that reuse is not universally a good thing, it does >have negative aspects too, in test and maintenance costs >and, often, in performance impact. I often use python for data analysis. I would be afraid that a modification to a generic function for project B would affect the results of project A (which may be long-running analysis). Hmmm, maybe 'git submodule' would be useful here. But in the vast majority >of cases the positives vastly outweigh the negatives. > >HTH >-- Alan G >Author of the Learn to Program web site >http://www.alan-g.me.uk/ >http://www.amazon.com/author/alan_gauld >Follow my photo-blog on Flickr at: >http://www.flickr.com/photos/alangauldphotos > > >___ >Tutor maillist - Tutor@python.org >To unsubscribe or change subscription options: >https://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] [OT] Best Practices for Scientific Computing
On 29/12/14 23:50, Patti Scott wrote: Could someone clarify "Modularize code rather than copying and pasting?" Joel and Danny have given the basic answer in terms of putting loose code into functions. But it goes a little further too. You can be tempted to copy/paste functions because they almost do what you want but not quite (maybe the take a list of values and you want to use a dictionary). Its easy to copy the function and change all the numerical indexes into keys and use the dictionary. But it would be better to change the original function so that it can work with both, if possible. This usually involves representing the variations in behaviour as parameters in the function (usually with defaults to retain the original semantics). Another case might be where you have a bunch of functions that operate on a global data structure. Then you want to have a second similar data structure but you can't use the functions on it because they access the existing global. You could copy/paste the functions and change the data reference. But it would be better to either add the data structure reference to the functions as a parameter, or you create a class that has the data as an internal instance attribute. Finally, you might have some code in a program that you want to use in another program. But you can't just import the first program because it runs all sorts of other stuff you don't need. So you just copy out the functions you want. Or you could put the loose code into a function (main() usually) and call that within a if __name__ === "__main__": main() line in your original program, turning it into a reusable module which you can now safely import. So modularize can have several meanings, it applies to any mechanism used to bundle up code for reuse. The point being that reusing code, whether as a function, module or class, is more flexible and reliable than copy/pasting it. PS. Note that reuse is not universally a good thing, it does have negative aspects too, in test and maintenance costs and, often, in performance impact. But in the vast majority of cases the positives vastly outweigh the negatives. HTH -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.amazon.com/author/alan_gauld Follow my photo-blog on Flickr at: http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
