7 ms·

Don't be so abrasive without linking to proof. I looked at a couple files and they looked fine.

by aw3c2 9y ago

daveFNbuck 9y ago
Check the bfs code at https://github.com/OmkarPathak/pygorithm/blob/b7a5c1cda3b945591c1f1b08b5d64edf9f12e479/pygorithm/searching/breadth_first_search.py https://github.com/OmkarPathak/pygorithm/blob/b7a5c1cda3b945...: # breadth first search algorithm def search(graph, startVertex): # Take a list for stoting already visited vertexes if startVertex not in graph or graph[startVertex] is None or graph[startVertex] == []: return None # create a list to store all the vertexes for BFS and a set to store the visited vertices visited, queue = set(), [startVertex] while queue: vertex = queue.pop(0) if vertex not in visited: visited.add(vertex) queue.extend(graph[vertex] - visited) return visited It returns None if there is a bad input or if the start node is a leaf. That's very weird, as None would seem to indicate an error but searching from a leaf is not normally an error. You should return a set just containing the start vertex if you start on a leaf. This doesn't need to be a special case. The initial guard also checks whether graph[startNode] is None, but this is never checked when looking up other nodes in the graph. Whether you check this should be consistent. The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. This makes the bfs implementation have quadratic worst-case complexity rather than the linear complexity it should have. The Python standard library has a deque class that can be used to fix this, and it would be more instructive and more correct to use that. This also means the time complexity function is wrong. So 2 clear bugs and 1 weird and probably unnecessary check in the bfs implementation. Also, the implementation has no comments to explain how it works, why it has the time complexity it does, or how you might tweak it to accomplish different goals. I don't see how someone who didn't already know BFS could learn from this. There's nothing here that teaches the algorithm, and the implementation is weirdly flawed. On top of all this, the package claims to teach all major algorithms but only contains a handful of sorting and searching algorithms. It doesn't even have a UI to help people discover and learn about the algorithms it does teach. You just have to know which ones are there and import them, then run a bunch of commands to print out the source code. This UI is worse than just browsing the source on GitHub, and that's much worse than just looking the algorithms up on Wikipedia or reading a textbook. I really don't get why someone would share this on HN in its current state. It looks like what you'd throw together for sample data before you started working on your algorithm teaching package.
- loeber 9y ago
  Agreed. This also breaks PEP8 everywhere. This is unfortunate, because it's obviously well-intended and the algorithms are mostly decently implemented, but not well. This package teaches bad design patterns, both in terms of algorithm design and writing Python. Bummer. :/
- tzs 9y ago
  > The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. That's somewhat surprising. The documentation at https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity says that the time complexity of pop(k) on a list of size of n is O(k). Since k is constant in this program, that time complexity should be constant, not linear. However, a quick little test program: import sys import time n = int(sys.argv[1]) l = list(range(n)) print("list ready") start = time.time() for i in range(1000): l.pop(0) took = time.time() - start; print(n, took) agrees with you rather than with wiki.python.org: 10000 0.00488591194152832 100000 0.06201004981994629 1000000 0.7796049118041992 10000000 12.354434967041016 The documentation for deques at docs.python.org does say that pop(0) on a list is O(n), so it looks like the wiki needs clarification. I tried it in Perl, too: use Time::HiRes qw(gettimeofday tv_interval); my $n = shift; my @list = (1 .. $n); my $start = [gettimeofday]; for ($i = 0; $i < 1000; ++$i) { shift @list; } my $elapsed = tv_interval($start, [gettimeofday]); print "$n $elapsed\n"; and there it does appear to be approximately constant time (which is what I expected): 10000 0.000135 100000 0.000142 1000000 0.000178 10000000 0.000163 100000000 0.000176 Changing the Python program to use a deque (and changing pop to popleft) gives results similar to Perl: 10000 0.00017404556274414062 100000 0.00018596649169921875 1000000 0.0001850128173828125 10000000 0.0001819133758544922 100000000 0.00019288063049316406 The numbers are essentially the same popping from the other side. Out of curiosity I then changed the Python program to pop the last item of the list instead of the first, and got this: 10000 0.00025200843811035156 100000 0.00026297569274902344 1000000 0.0002658367156982422 10000000 0.0002770423889160156 100000000 0.0002639293670654297 So even on the fast side, the list is slower at popping than the deque. I was then curious to compare list and deque for accessing interior elements. I changed the programs from poping item to adding 1000 items from the list or deque spaced evenly throughout. List: 10000 0.0002741813659667969 100000 0.0003039836883544922 1000000 0.0004611015319824219 10000000 0.0005731582641601562 100000000 0.0006010532379150391 Deque: 10000 0.00033092498779296875 100000 0.0014951229095458984 1000000 0.03908801078796387 10000000 0.45997095108032227 100000000 16.526084899902344 OK...so that's why we don't just use deque everywhere. I did the same thing with my Perl program: 10000 0.000301 100000 0.000375 1000000 0.000511 10000000 0.000624 100000000 0.000638 It's interesting that Perl's array seems to combine the fast access at both ends of Python's deque with the fast random access of Python's list. I wonder how it does this? The Perl array seems to use more memory than the Python list, so maybe Perl is trading off size to get versatility?
r3dey3 9y ago
You must not have looked at linked list. Besides being non-pythonic and having get and set functions, they don't even consistently use them. Then there's the bug that you can't delete the first node in a list. And then there's the fact that double linked list doesn't have a tail pointer. And then there's the fact that they use the same node class in double linked as single, but the previous member is set by the list, but isn't always set so you might get an exception some times. Then there's the fact that search is only implemented for single linked .. Oh and its RECURSIVE! It'd be one thing if this was just them showing how they learned something in a blog post... But this was meant for teaching.... And yet there's no description and clearly obvious bugs.
- Rotareti 9y ago
  > Besides being non-pythonic Could someone please tell me why his code is considered 'non-pythonic'? This statement worries me a little, because his code looks pretty similar to what I write.
  - aidos 9y ago
    I only looked at the linked_list but there are a few examples that jump out straight away: - Getters and setters are used all over the place (setData, getData etc) - Strangely named variables - eg List = [] and newNode = Node(data) - Non-pythonic conditionals eg I'd expect while(temp.next != None): to read while temp.next: - functions are commented outside the function instead of in docstrings, which, ironically would have made it much better for learning the algorithms :-) Not that it's bad code, it's just not very pythonic.
- 0xdeadbeefbabe 9y ago
  I disagree with the idea that teaching is all about teaching students to copy the teacher. Teaching is about lighting a fire, and it's obviously lit in this case. Mission accomplished.
  - daveFNbuck 9y ago
    How was a fire lit in this case? I don't see how someone who wasn't already extremely motivated could get anything from this, and there are much better sources for motivated students.

Don't be so abrasive without linking to proof. I looked at a couple files and they looked fine.

by aw3c2 9y ago

Don't be so abrasive without linking to proof. I looked at a couple files and they looked fine.

Check the bfs code at https://github.com/OmkarPathak/pygorithm/blob/b7a5c1cda3b945591c1f1b08b5d64edf9f12e479/pygorithm/searching/breadth_first_search.py https://github.com/OmkarPathak/pygorithm/blob/b7a5c1cda3b945...: # breadth first search algorithm def search(graph, startVertex): # Take a list for stoting already visited vertexes if startVertex not in graph or graph[startVertex] is None or graph[startVertex] == []: return None # create a list to store all the vertexes for BFS and a set to store the visited vertices visited, queue = set(), [startVertex] while queue: vertex = queue.pop(0) if vertex not in visited: visited.add(vertex) queue.extend(graph[vertex] - visited) return visited It returns None if there is a bad input or if the start node is a leaf. That's very weird, as None would seem to indicate an error but searching from a leaf is not normally an error. You should return a set just containing the start vertex if you start on a leaf. This doesn't need to be a special case. The initial guard also checks whether graph[startNode] is None, but this is never checked when looking up other nodes in the graph. Whether you check this should be consistent. The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. This makes the bfs implementation have quadratic worst-case complexity rather than the linear complexity it should have. The Python standard library has a deque class that can be used to fix this, and it would be more instructive and more correct to use that. This also means the time complexity function is wrong. So 2 clear bugs and 1 weird and probably unnecessary check in the bfs implementation. Also, the implementation has no comments to explain how it works, why it has the time complexity it does, or how you might tweak it to accomplish different goals. I don't see how someone who didn't already know BFS could learn from this. There's nothing here that teaches the algorithm, and the implementation is weirdly flawed. On top of all this, the package claims to teach all major algorithms but only contains a handful of sorting and searching algorithms. It doesn't even have a UI to help people discover and learn about the algorithms it does teach. You just have to know which ones are there and import them, then run a bunch of commands to print out the source code. This UI is worse than just browsing the source on GitHub, and that's much worse than just looking the algorithms up on Wikipedia or reading a textbook. I really don't get why someone would share this on HN in its current state. It looks like what you'd throw together for sample data before you started working on your algorithm teaching package.

loeber 9y ago
Agreed. This also breaks PEP8 everywhere. This is unfortunate, because it's obviously well-intended and the algorithms are mostly decently implemented, but not well. This package teaches bad design patterns, both in terms of algorithm design and writing Python. Bummer. :/
tzs 9y ago
> The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. That's somewhat surprising. The documentation at https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity says that the time complexity of pop(k) on a list of size of n is O(k). Since k is constant in this program, that time complexity should be constant, not linear. However, a quick little test program: import sys import time n = int(sys.argv[1]) l = list(range(n)) print("list ready") start = time.time() for i in range(1000): l.pop(0) took = time.time() - start; print(n, took) agrees with you rather than with wiki.python.org: 10000 0.00488591194152832 100000 0.06201004981994629 1000000 0.7796049118041992 10000000 12.354434967041016 The documentation for deques at docs.python.org does say that pop(0) on a list is O(n), so it looks like the wiki needs clarification. I tried it in Perl, too: use Time::HiRes qw(gettimeofday tv_interval); my $n = shift; my @list = (1 .. $n); my $start = [gettimeofday]; for ($i = 0; $i < 1000; ++$i) { shift @list; } my $elapsed = tv_interval($start, [gettimeofday]); print "$n $elapsed\n"; and there it does appear to be approximately constant time (which is what I expected): 10000 0.000135 100000 0.000142 1000000 0.000178 10000000 0.000163 100000000 0.000176 Changing the Python program to use a deque (and changing pop to popleft) gives results similar to Perl: 10000 0.00017404556274414062 100000 0.00018596649169921875 1000000 0.0001850128173828125 10000000 0.0001819133758544922 100000000 0.00019288063049316406 The numbers are essentially the same popping from the other side. Out of curiosity I then changed the Python program to pop the last item of the list instead of the first, and got this: 10000 0.00025200843811035156 100000 0.00026297569274902344 1000000 0.0002658367156982422 10000000 0.0002770423889160156 100000000 0.0002639293670654297 So even on the fast side, the list is slower at popping than the deque. I was then curious to compare list and deque for accessing interior elements. I changed the programs from poping item to adding 1000 items from the list or deque spaced evenly throughout. List: 10000 0.0002741813659667969 100000 0.0003039836883544922 1000000 0.0004611015319824219 10000000 0.0005731582641601562 100000000 0.0006010532379150391 Deque: 10000 0.00033092498779296875 100000 0.0014951229095458984 1000000 0.03908801078796387 10000000 0.45997095108032227 100000000 16.526084899902344 OK...so that's why we don't just use deque everywhere. I did the same thing with my Perl program: 10000 0.000301 100000 0.000375 1000000 0.000511 10000000 0.000624 100000000 0.000638 It's interesting that Perl's array seems to combine the fast access at both ends of Python's deque with the fast random access of Python's list. I wonder how it does this? The Perl array seems to use more memory than the Python list, so maybe Perl is trading off size to get versatility?

r3dey3 9y ago

You must not have looked at linked list. Besides being non-pythonic and having get and set functions, they don't even consistently use them. Then there's the bug that you can't delete the first node in a list. And then there's the fact that double linked list doesn't have a tail pointer. And then there's the fact that they use the same node class in double linked as single, but the previous member is set by the list, but isn't always set so you might get an exception some times. Then there's the fact that search is only implemented for single linked .. Oh and its RECURSIVE! It'd be one thing if this was just them showing how they learned something in a blog post... But this was meant for teaching.... And yet there's no description and clearly obvious bugs.

Rotareti 9y ago
> Besides being non-pythonic Could someone please tell me why his code is considered 'non-pythonic'? This statement worries me a little, because his code looks pretty similar to what I write.
- aidos 9y ago
  I only looked at the linked_list but there are a few examples that jump out straight away: - Getters and setters are used all over the place (setData, getData etc) - Strangely named variables - eg List = [] and newNode = Node(data) - Non-pythonic conditionals eg I'd expect while(temp.next != None): to read while temp.next: - functions are commented outside the function instead of in docstrings, which, ironically would have made it much better for learning the algorithms :-) Not that it's bad code, it's just not very pythonic.
0xdeadbeefbabe 9y ago
I disagree with the idea that teaching is all about teaching students to copy the teacher. Teaching is about lighting a fire, and it's obviously lit in this case. Mission accomplished.
- daveFNbuck 9y ago
  How was a fire lit in this case? I don't see how someone who wasn't already extremely motivated could get anything from this, and there are much better sources for motivated students.