Yes, it is really nice you made a thing to help others, but it makes me angry if somebody want to teach something with TERRIBLE CODE. If you want to teach people, you should be proficient, write clean, elegant and readable code without stupid mistakes! TEACHING IS A RESPONSIBILITY.
That's why there is so much shit software out there today...
I repeat, the intent is nice, but only people with high motivation and quality code should do it. If you do it for yourself, nice, ok, nobody cares, but don't teach bad taste, acceptable mistakes and stuff like this.
Yes, I could make a pull request and I will, but I don't have the time to make pull requests for every wannabe teacher ever.
# 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.
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. :/
> 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 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)
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.
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?
The CPython list implementation does indeed sacrifice performance to use less size. It uses a pre-allocated array for the list and when the list gets too large, it needs to allocate a new array to hold the list and re-insert all the items into the new array.
You may have done this in an intro CS class and doubled the array size to get an amortized O(1) append time, but you only need to increase the size by at least a constant fraction of the current size. Python increases by 1/8 of the current size, plus 6. This means more reallocations over a large number of operations, but less memory overhead at any given time.
Because of this implementation, you can pop from the right by just changing the size of the array, but to pop from the left requires shifting the entire array. You can pop the kth element from the right in O(k) time by just shifting those elements, which may be what the wiki means. I didn't read the code thoroughly enough to verify that it actually does this, but it seems reasonable.
Popping from the right is still slower than a deque because in order to save memory, the list gets resized whenever it falls below half of its maximum allocated size. A deque is always O(1) for every push/pop operation, but lists have occasional expensive operations that bump up the runtime a bit. Deques require linear time to access elements due to being implemented as doubly-linked lists. They're really only meant for accessing the elements on the ends.
You can get fast popleft on a list if you also keep a left pointer, but this complicates the implementation and has a corresponding performance penalty. You can even do a fast appendleft on a list if you allocate the elements so they start with empty cells on both the left and the right, but this makes the tradeoff between memory and performance even worse.
Even weirder is just the fact that it bases the stack data structure on the Python list, which is already a fully-functional stack. If this is supposed to teach you how to build a stack, it should implement its own stack rather than just wrapping an existing one.
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.
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.
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.
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.
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.
I am looking for a few and uh, I mean modulo the fact that it's in python so there are some odd limitatoins, the search and sort didn't have any obvious bugs. As soon as I sit down I'll run them through some test cases. Ofc, my Python is weak (or rather, my tolerance for Python is weak), so I'll check later.
Seriously, it's github. This is an education effort, and even if the author made some mistakes (sounds like the data structures section in particular needs some cleanup?) it has didactic value for folks involved to correct this.
It would be nice to have a discussion on why you used // instead of /. Depending on who reads your code, explaining this "obvious" choice might be interesting.
There are also other discussions topic : what happens if the array is empty ? what happens if the array is twice the size of the computer's RAM ? What happens if all the numbers in the array are equal ?
I don't believe Python has this problem though as it will automatically promote a fixed sized int to an arbitrary precision int if the former isn't sufficient. See:
Yep, that's why I didn't raise the point. Now, Python can certainly not represent number of infinite sizes...
I'll add that the super cool thing about "simple" algorithms such as binary search is that their practical application is full of edge cases which are very interesting to study to properly understand what these algorithms "mean". There's an awful lot to be said about even the simplest things.
It is sitting there alone... abandoned... Sorry poor repo that I never made something big from you. You deserve much more stars (p.s. don't tell him that the only one is from me) :(
Hate to be that guy and I know it's just for fun, but that is not a one-liner.
Not at a 135-characters length :)
And I'm not even accounting for the 1-char useless var/func names.
EDIT: To clarify, I don't think that the above "1 liner" has anything to offer.
1) It's not pythonic, 2) it's not 1-liner by any of python's standards and 3) it's a bad example of programming.
While on the other hand there are numerous other 1-liners that do not have these bad traits.
Neither is it fun, readable or implies any sorts of knowledge of the language.
- One-char function names.
- You call a "list" a list. Shadows built-ins. At least use lst.
- if list==[] is non PEP8. Should be if not list.
- [list[0]] could be written as list[:1]
If something is a “major” algorithm, isn’t this just like a “Design Pattern”, in that it really is something which should be built into the language, and ideally isn’t something you should implement yourself?
In fact, all of these seem to be ones that are actually built into Python already.
Does it make sense for a language to implement all of the sorting algorithms though, especially the inefficient but simple ones like bubble sort? I would be surprised to find bubble sort in the standard library, so having this as an educational exercise makes a lot of sense to me.
Not necessarily.Not all algorithms are universally applicable, nor are they universally desirable on all inputs.
For example, if you have a very long (practically infinite) stream of mostly ordered items coming in and you want to semi-order a sliding window so downstream consumers have an easier time, what do you do?
You can't just call Array#sort.
Another example in the same vein: You get a large and mostly sorted dataset on an older 32 bit machine. It's about 500 million elements long, and loaded in memory on Python. Which sort algorithm do you use?
This is great! If I could make a suggestion it would be to add the space complexity of each algorithm to the comments(the time complexity is already there.)
This is a neat learning tool. Will recommend to those starting out. A couple of suggestions if you have the time or will try to send a pull (!) ..
1) A built in dataset (numbers, chars, wordlist)
2) a single step mode
44 comments
[ 1.4 ms ] story [ 133 ms ] threadI repeat, the intent is nice, but only people with high motivation and quality code should do it. If you do it for yourself, nice, ok, nobody cares, but don't teach bad taste, acceptable mistakes and stuff like this.
Yes, I could make a pull request and I will, but I don't have the time to make pull requests for every wannabe teacher ever.
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.
That's somewhat surprising. The documentation at 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:
agrees with you rather than with wiki.python.org: 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:
and there it does appear to be approximately constant time (which is what I expected): Changing the Python program to use a deque (and changing pop to popleft) gives results similar to Perl: 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:
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:
Deque: OK...so that's why we don't just use deque everywhere.I did the same thing with my Perl program:
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?The CPython list implementation does indeed sacrifice performance to use less size. It uses a pre-allocated array for the list and when the list gets too large, it needs to allocate a new array to hold the list and re-insert all the items into the new array.
You may have done this in an intro CS class and doubled the array size to get an amortized O(1) append time, but you only need to increase the size by at least a constant fraction of the current size. Python increases by 1/8 of the current size, plus 6. This means more reallocations over a large number of operations, but less memory overhead at any given time.
Because of this implementation, you can pop from the right by just changing the size of the array, but to pop from the left requires shifting the entire array. You can pop the kth element from the right in O(k) time by just shifting those elements, which may be what the wiki means. I didn't read the code thoroughly enough to verify that it actually does this, but it seems reasonable.
Popping from the right is still slower than a deque because in order to save memory, the list gets resized whenever it falls below half of its maximum allocated size. A deque is always O(1) for every push/pop operation, but lists have occasional expensive operations that bump up the runtime a bit. Deques require linear time to access elements due to being implemented as doubly-linked lists. They're really only meant for accessing the elements on the ends.
You can get fast popleft on a list if you also keep a left pointer, but this complicates the implementation and has a corresponding performance penalty. You can even do a fast appendleft on a list if you allocate the elements so they start with empty cells on both the left and the right, but this makes the tradeoff between memory and performance even worse.
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.
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.
- 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.
Teaching is a responsibility, so try not posting when you are angry next time.
If you care so much, rewrite it or make pull requests. Don't sit on your high horse and berate someone for trying to offer something useful to others.
Time and again I find older discussions from 5 years ago that were much more lively, open and interesting.
A lot of interesting commenters have left and it is easy to see why.
I am looking for a few and uh, I mean modulo the fact that it's in python so there are some odd limitatoins, the search and sort didn't have any obvious bugs. As soon as I sit down I'll run them through some test cases. Ofc, my Python is weak (or rather, my tolerance for Python is weak), so I'll check later.
Seriously, it's github. This is an education effort, and even if the author made some mistakes (sounds like the data structures section in particular needs some cleanup?) it has didactic value for folks involved to correct this.
mid = (left + right) // 2
It would be nice to have a discussion on why you used // instead of /. Depending on who reads your code, explaining this "obvious" choice might be interesting.
There are also other discussions topic : what happens if the array is empty ? what happens if the array is twice the size of the computer's RAM ? What happens if all the numbers in the array are equal ?
mid = left + (right - left)/2;
https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...
https://stackoverflow.com/questions/4581842/python-integer-r...
I'll add that the super cool thing about "simple" algorithms such as binary search is that their practical application is full of edge cases which are very interesting to study to properly understand what these algorithms "mean". There's an awful lot to be said about even the simplest things.
It is sitting there alone... abandoned... Sorry poor repo that I never made something big from you. You deserve much more stars (p.s. don't tell him that the only one is from me) :(
def q(list): return [] if list==[] else q([x for x in list[1:] if x < list[0]]) + [list[0]] + q([x for x in list[1:] if x >= list[0]])
Not at a 135-characters length :)
And I'm not even accounting for the 1-char useless var/func names.
EDIT: To clarify, I don't think that the above "1 liner" has anything to offer. 1) It's not pythonic, 2) it's not 1-liner by any of python's standards and 3) it's a bad example of programming.
While on the other hand there are numerous other 1-liners that do not have these bad traits.
In fact, all of these seem to be ones that are actually built into Python already.
For example, if you have a very long (practically infinite) stream of mostly ordered items coming in and you want to semi-order a sliding window so downstream consumers have an easier time, what do you do?
You can't just call Array#sort.
Another example in the same vein: You get a large and mostly sorted dataset on an older 32 bit machine. It's about 500 million elements long, and loaded in memory on Python. Which sort algorithm do you use?
Sorry. ;)