generating 2D bit array variants with specific algorythm
Hi, I need to generate all variants of a 2D array with variable dimension sizes which fit a specific rule. (up to 200*1000) The rules are: - Values are only 0 or 1 - the sum of each line bust be 1 - only valid results must be generated (generating all and only returning the valid results takes to long; that's what I tried already) So for a 2x2 array these would be the valid results: 10 01 01 10 10 10 01 01 Must be possible with nested loops and a counter per line. But I don't get it. Can someone help? Thanks Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
1011 What I mean is do you throw away the carry or does each row have only one zero? Not sure what you mean. Each row must have one 1. The rest must be 0. No combinations not fitting this rule must be generated. -- https://mail.python.org/mailman/listinfo/python-list
Re: which data structure to use?
Unlikely. Are you sure that .heap and .lookup contents are still in sync with your modification? No it's not. Atfer having read about heapq it's clear why. Thanks for the hint. allows you to delete random nodes, but the lowest() method will slow down as it has to iterate over all dict values. Thanks a lot for the alternative class. I will go with two lists, each using one of the aproaches. In one list I always need to have only hte object with lowest .f. With the other list I may have to delete random nodes. So I can make perfect use of both classes. One important caveat: both Nodes classes lead to data corruption if you modify a .pos attribute while the node is in a Nodes instance. The same goes for the first implementation and the .f attribute. That's fine. pos is static and identifies the node. Thanks again to all who responded. I learned a lot. -- https://mail.python.org/mailman/listinfo/python-list
use class in class
Hi, I have a problem using a class object within another class. It is about the line: self.openlist.append(Node(self.start, None, 0, 0)) If I use it in __init__ it works. If I use it in calcRoute(self) I get the following error: local variable 'node' referenced before assignment The error occures in AMap.calcRoute() Where is my mistake? Thanks Robert import numpy as np from matplotlib import pyplot as plt import matplotlib.cm as cm class Node(object): def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h class NewAMap(object): def __init__(self, size, start, target): self.size = size self.start = start self.target = target self.openlist = [] self.closedlist = set() self.EmptyValue = 0 self.clear() self.addStart(self.start) self.addTarget(self.target) #self.openlist.append(Node(self.start, None, 0, 0)) def clear(self): self.OccMap = np.zeros(shape=(self.size[0],self.size[1]),dtype=int) def display(self): print np.swapaxes(self.OccMap,0,1) self.PicMap = np.zeros(shape=(self.size[0],self.size[1]),dtype=(float,3)) for x in xrange(0,self.size[0]): for y in xrange(0,self.size[1]): if self.OccMap[x][y] == 0: self.PicMap[y][x]=(1,1,1) elif self.OccMap[x][y] == -1: self.PicMap[y][x]=(0,0,0) elif self.OccMap[x][y] == -2: self.PicMap[y][x]=(1,0,0) elif self.OccMap[x][y] == -3: self.PicMap[y][x]=(0,0,1) #print self.PicMap plt.imshow(self.PicMap, interpolation='nearest') plt.show() def addBlocked(self, blockposs): self.OccMap[blockposs[0]][blockposs[1]]=-1 def addStart(self, start): self.OccMap[start[0]][start[1]]=-2 def addTarget(self, target): self.OccMap[target[0]][target[1]]=-3 def calcRoute(self): self.openlist.append(Node(self.start, None, 0, 0)) for Node in self.openlist: print Node.pos, Node.parent, Node.g, Node.h, Node.f def main(): AMap = NewAMap((20,20),(1,12),(12,12)) for y in range(8,17): AMap.addBlocked((8,y)) AMap.calcRoute() AMap.display() if __name__ == '__main__': main() -- https://mail.python.org/mailman/listinfo/python-list
Re: use class in class
I recommend using a different name for the instances here, probably with a lower-case first letter. That would solve your problem _and_ make your code more readable. Thanks a lot! I was confused by the debuger gifing me the wrong line as containing the error. I changed it regarding your advide. And it works. Robert -- https://mail.python.org/mailman/listinfo/python-list
which data structure to use?
Hi, which would be the best data structure to use for the following case? I have objects like this: class Node(object): def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h I need to build a list of these objects. The amount is unknown. On this list I need to regularly 1. check if a specific item - identified by Node.pos - is in the list. 2. find the object with the lowest Node.f attribute and update or remove it What would be a good approach. Using a list I always need to traverse the whole list to do one of the above actions. Thanks Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: which data structure to use?
On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtl�nder wrote: I have objects like this: class Node(object): def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h I need to build a list of these objects. The amount is unknown. On this list I need to regularly 1. check if a specific item - identified by Node.pos - is in the list. 2. find the object with the lowest Node.f attribute and update or remove it First thanks to all who responded. Although I only partially understand your answers as I am a Python starter. What's clear to me is the difference between object and instance of an object. Just didn't explain it well. Maybe I give some more info on what I need / want to do. I will also provide a working code example. Should have done this before. I would very much appreciate a working example of what you mean. Then I have a chance to understand it. :-) I would like to implement a class for a A* pathfinding algorithm. (there are ready libraries out there but I would like to learn it myself) This requires to maintain a list of nodes to be processed and nodes already processed. For new nodes I need to check if they are on one of the lists. I also need to regularly pick the node with the lowest value f from the list. Here some working code. For one function I sill need a solution. Any better solution is welcome. Thanks Robert --- class Node: def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h def isinlist(nodeToSeatch): for item in openlist: if item.pos == nodeToSeatch: return True return False def lowestF(): lowestF = '' for item in openlist: if item.f lowestF: lowestF = item return lowestF def deleteItemWithPos(pos): ## need this function or different approach pass openlist=[] openlist.append(Node((1,1),None,1,5)) openlist.append(Node((1,2),(1,1),4,6)) openlist.append(Node((1,3),(1,2),9,10)) for item in openlist: print item.pos, item.f print isinlist((1,1)) print isinlist((1,5)) nextNode = lowestF() print nextNode.pos, nextNode.f -- https://mail.python.org/mailman/listinfo/python-list
Re: which data structure to use?
Am Dienstag, 21. Januar 2014 14:38:34 UTC+1 schrieb Robert Voigtländer: On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtl�nder wrote: I have objects like this: class Node(object): def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h I need to build a list of these objects. The amount is unknown. On this list I need to regularly 1. check if a specific item - identified by Node.pos - is in the list. 2. find the object with the lowest Node.f attribute and update or remove it First thanks to all who responded. Although I only partially understand your answers as I am a Python starter. What's clear to me is the difference between object and instance of an object. Just didn't explain it well. Maybe I give some more info on what I need / want to do. I will also provide a working code example. Should have done this before. I would very much appreciate a working example of what you mean. Then I have a chance to understand it. :-) I would like to implement a class for a A* pathfinding algorithm. (there are ready libraries out there but I would like to learn it myself) This requires to maintain a list of nodes to be processed and nodes already processed. For new nodes I need to check if they are on one of the lists. I also need to regularly pick the node with the lowest value f from the list. Here some working code. For one function I sill need a solution. Any better solution is welcome. Thanks Robert Sorry - found a bug right after my post. Here the corrected version. class Node: def __init__(self, pos, parent, g , h): self.pos = pos self.parent = parent self.g = g self.h = h self.f = g+h def isinlist(nodeToSeatch): for item in openlist: if item.pos == nodeToSeatch: return True return False def lowestF(): lowestF = '' for item in openlist: if item.f lowestF: lowestF = item.f lowestFItem = item return lowestFItem def deleteItemWithPos(pos): ## need this function or different approach pass openlist=[] openlist.append(Node((1,1),None,1,5)) openlist.append(Node((1,2),(1,1),4,6)) openlist.append(Node((1,3),(1,2),9,10)) for item in openlist: print item.pos, item.f print isinlist((1,1)) print isinlist((1,5)) nextNode = lowestF() print nextNode.pos, nextNode.f -- https://mail.python.org/mailman/listinfo/python-list
Re: use class in class
copy/paste of the whole thing. The actual error message could not have said node, as there's no such name in the method. You are correct. I copied the error before I renamed node into Node. I have to be more consistent here. :-) The source for the error was still the same. -- https://mail.python.org/mailman/listinfo/python-list
Re: which data structure to use?
Am Dienstag, 21. Januar 2014 15:19:54 UTC+1 schrieb Peter Otten: Peter Otten wrote: def pop(self): f, node = heapq.heappop() del lookup[node.pos] return node That should be def pop(self): f, node = heapq.heappop(self.heap) del self.lookup[node.pos] return node Hi Peter, this works great. I will try to find some info about the functionality you used and to understnad what you did. Maybe you can add a function to remove a node? Thanks for your support and all tthe swift answers. Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: which data structure to use?
def pop(self): f, node = heapq.heappop() del lookup[node.pos] return node That should be def pop(self): f, node = heapq.heappop(self.heap) del self.lookup[node.pos] return node Hi Peter, this works great. I will try to find some info about the functionality you used and to understnad what you did. Maybe you can add a function to remove a node? Thanks for your support and all tthe swift answers. Robert Just realized what the pop function is for. I changed it from: def pop(self): to def pop(self,pos): and it works. Now I go on with trying to understand it. -- https://mail.python.org/mailman/listinfo/python-list
Re: min max from tuples in list
Wow, thanks for the educating answer. I'll work through all the varaints. And yes, I meant keep it unsorted. As I read it, sorting may be required then if I don't want to use the slowest variant. I'll test them all. Thanks Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: min max from tuples in list
I've heard the term used often. It means something like, performs well or runs fast. It may or may not be an English word, but that doesn't stop people from using it :-) If google can be used to mean make huge amouts of money with a product that is inherently flawed then I'll happily accept performant as an English word, regardless of whether the English variant is UK, US, Australian, New Zealand, Soth African, Geordie, Glaswegian or any other :) Indeed it's not an english word. I have to stop using it. In German it's used with the meaning of runs fast. Even though it's already not that clearly defined there. Thanks for the help on the topic of data aggregation. It helped a lot and I again learned somthing. I have a performant .. well .. fast running solution now. -- https://mail.python.org/mailman/listinfo/python-list
min max from tuples in list
Hi, I have a list like this: a = [(52, 193), (52, 193), (52, 192), (51, 193), (51, 191), (51, 190), (51, 189), (51, 188), (50, 194), (50, 187), (50, 186), (50, 185), (50, 184), (49, 194), (49, 183), (49, 182), (49, 181), (48, 194), (48, 180), (48, 179), (48, 178), (48, 177), (47, 194), (47, 176), (47, 175), (47, 174), (47, 173), (46, 195), (46, 172), (46, 171), (46, 170), (46, 169), (45, 195), (45, 168), (45, 167), (45, 166), (44, 195), (44, 165), (44, 164), (44, 163), (44, 162), (43, 195), (43, 161), (43, 160), (43, 159), (43, 158), (42, 196), (42, 157), (42, 156), (42, 155), (41, 196), (41, 154), (41, 153), (41, 152), (41, 151), (40, 196), (40, 150), (40, 149), (40, 148), (40, 147), (39, 196), (39, 146), (39, 145), (39, 144), (39, 143), (38, 196), (38, 142), (38, 141), (38, 140), (37, 197), (37, 139), (37, 138), (37, 137), (37, 136), (36, 197), (36, 135), (36, 134), (36, 133)] I need to find a -performant- way to transform this into a list with tuples (a[0],[a[0][1]min],[a[0][1]max]). Hard to explaint what I mean .. [0] of the first three tuples is 52. [1] is 193,193 and 192. What I need as result for these three tuples is: (52,192,193). For the next five tuples it is (51,188,193). Extra challenges: - This list is sorted. For performance reasons I would like to keep it unsorted. - There may be tuples where min=max. - There my be tupples where [0] only exists once. So mix is automatically max I hope I was able to explain what I mean. Thanks Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: squeeze out some performance
Actually for optimised code it looks very similar to some code posted here http://www.daniweb.com/software-development/python/threads/321181/python-bresenham-circle-arc-algorithm over three years ago. This is where it origins from. I just extended it for my needs and now want to optimize it. List comprehensions instead of some for loops brought another 25%. And made the code shorter. -- https://mail.python.org/mailman/listinfo/python-list
Re: squeeze out some performance
Am Samstag, 7. Dezember 2013 00:01:49 UTC+1 schrieb Dan Stromberg: On Fri, Dec 6, 2013 at 2:38 PM, Mark Lawrence bream...@yahoo.co.uk wrote: On 06/12/2013 16:52, John Ladasky wrote: On Friday, December 6, 2013 12:47:54 AM UTC-8, Robert Voigtländer wrote: I try to squeeze out some performance of the code pasted on the link below. http://pastebin.com/gMnqprST Several comments: 1) I find this program to be very difficult to read, largely because there's a whole LOT of duplicated code. Look at lines 53-80, and lines 108-287, and lines 294-311. It makes it harder to see what this algorithm actually does. Is there a way to refactor some of this code to use some shared function calls? A handy tool for detecting duplicated code here http://clonedigger.sourceforge.net/ for anyone who's interested. Pylint does this too... Thanks again. I'll try to compress the code and have a look at the multiple comparisons topic. Robert -- https://mail.python.org/mailman/listinfo/python-list
squeeze out some performance
Hi, I try to squeeze out some performance of the code pasted on the link below. http://pastebin.com/gMnqprST The code will be used to continuously analyze sonar sensor data. I set this up to calculate all coordinates in a sonar cone without heavy use of trigonometry (assuming that this way is faster in the end). I optimized as much as I could. Maybe one of you has another bright idea to squeeze out a bit more? Thanks Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: squeeze out some performance
Thanks for your replies. I already did some basic profiling and optimized a lot. Especially with help of a goof python performance tips list I found. I think I'll follow the cython path. The geometry approach also sound good. But it's way above my math/geometry knowledge. Thanks for your input! -- https://mail.python.org/mailman/listinfo/python-list
Re: squeeze out some performance
Am Freitag, 6. Dezember 2013 17:36:03 UTC+1 schrieb Mark Lawrence: I already did some basic profiling and optimized a lot. Especially with help of a goof python performance tips list I found. Wonderful typo -^ :) Oh well :-) ... it was a good one. Just had a quick look at Cython. Looks great. Thanks for the tip. -- https://mail.python.org/mailman/listinfo/python-list
Re: calculate part of solid circle in 2D array
OK. Found a good one here: http://www.daniweb.com/software-development/python/threads/321181/python-bresenham-circle-arc-algorithm Now only filling is needed. Any help is welcome ... Thanks Robert Am Montag, 25. November 2013 08:26:19 UTC+1 schrieb Robert Voigtländer: Hi, I wonder if someone can help me with a function I need for programming my robot. I want to update an 2D occupancy grid based on sonar data. The sonar “view angle” is cone shaped. So I need to calculate all cells of a 30° slice of a filled circle. Something like this: http://www.intechopen.com/source/html/37778/media/fig2.jpg Using trigonometry is too expensive. I think something like Brenham’s circle algorithm would be a good candidate. But I need it filled (that would be doable for me I think) and I don’t need the full circle but only a part of it. I wonder if someone has a function like this lying around. If so I would be glad to not have to reinvent the wheel Thanks and cheers Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: calculate part of solid circle in 2D array
Thanks a lot for the links. I don't need it to be drawn. I need the fields within the arc for some statistical calculations for an occupancy map. So the target is a 2D array, not a picture. Robert -- https://mail.python.org/mailman/listinfo/python-list
Re: calculate part of solid circle in 2D array
Great discussion started here To answer some of the questions and to give more background: - The grid resolution is 1x1cm. The problem starts when the distance of the readings gets high. Then a 1° resolution doesn’t cover all cells anymore. And cells get counted double on short distance – which needs to be compensated. So for larger distances I need to get down to about 0.1 degree in reality to not miss cells. - So far I ran the logic for the robot on a PC. No problem here with the performance using trigonometry (in java). But I am on my way porting everything to a raspberry pi which will be on the robot itself. Due to the limited calculation power I want to avoid too heavy calculation for regular jobs. The scans come in about every 40ms. So the calculation needs to be as fast as possible. - I surely will benchmark the new approach vs. the trigonometry solution which I will port from my current java solution. Maybe I will be surprised – but I think the trig approach will be slower. The lookup table is also a great idea! I can produce it for any resolution needed and on runtime it is simply combining lists for the slices needed…..not bad. So far I have the circle points as well as the lines – using the Brenham’s circle and line functions. Code: http://pastebin.com/GzUzuAnb I just need to get the filling done….. Robert -- https://mail.python.org/mailman/listinfo/python-list
calculate part of solid circle in 2D array
Hi, I wonder if someone can help me with a function I need for programming my robot. I want to update an 2D occupancy grid based on sonar data. The sonar “view angle” is cone shaped. So I need to calculate all cells of a 30° slice of a filled circle. Something like this: http://www.intechopen.com/source/html/37778/media/fig2.jpg Using trigonometry is too expensive. I think something like Brenham’s circle algorithm would be a good candidate. But I need it filled (that would be doable for me I think) and I don’t need the full circle but only a part of it. I wonder if someone has a function like this lying around. If so I would be glad to not have to reinvent the wheel Thanks and cheers Robert -- https://mail.python.org/mailman/listinfo/python-list
