6 ms·
Pygorithm – A Python module for learning major algorithms
- Walkman 9y agoYes, 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.
- aw3c2 9y agoDon't be so abrasive without linking to proof. I looked at a couple files and they looked fine.
- daveFNbuck 9y agoCheck 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 agoAgreed. 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 agoYou 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 agoI 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 agoI 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 agoHow 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.
- inimino 9y agoSometimes the best person to learn from is someone who recently learned what you are learning. Teaching is a responsibility, so try not posting when you are angry next time.
- zabana 9y agoWow, what's with the hate ? Get a l(w)ife ... Good Job OP ! Don't let people bring you down. You'll improve with time I'm sure.
- deleted 9y ago[deleted]
- sctb 9y agoThis comment breaks the guidelines by being gratuitously negative: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html. (They also ask us not to use uppercase for emphasis.)
- AN91932 9y agoYou are going to delete this, but this kind of zealotry is ruining the site. 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.
- nxsynonym 9y agoCompletely unnecessary hostility. Either offer advice and constructive criticism or don't offer anything. 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.
- KirinDave 9y agoYou should PR the mistakes. 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.
- wiz21c 9y agoIn the binary search algorithm : 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 ?
- gshubert17 9y agoJon Bentley showed this can have problems with overflow. Better, mid = left + (right - left)/2; https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...
- bogomipz 9y agoI 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: https://stackoverflow.com/questions/4581842/python-integer-ranges https://stackoverflow.com/questions/4581842/python-integer-r...
- wiz21c 9y agoYep, 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.
- ssijak 9y agoOnce upon a time I made a Github repo with the same name and intention https://github.com/ssijak/pygoritm https://github.com/ssijak/pygoritm 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) :(
- wooptoo 9y agoHere is a fun one-liner quicksort in Python: 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]])
- rantanplan 9y agoHate 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.
- heavenlyblue 9y agoNeither 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]
- tu7001 9y agoI have few Python algorithms and data structures here: https://github.com/lion137/Python-Algorithms https://github.com/lion137/Python-Algorithms https://github.com/lion137/Python-Data-Structures https://github.com/lion137/Python-Data-Structures You can use them if you want to extend a bit your; all tested and working (as far as I know). Let me know if you need me to add any comments/explanations to code...
- teddyh 9y agoIf 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.
- boomlinde 9y agoSure, but 1. someone has to implement them, and 2. they can serve an educational purpose regardless.
- JustSomeNobody 9y agoNo, it's not a design pattern. Yes it likely should be included in the language library.
- tedmiston 9y agoDoes 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.
- KirinDave 9y agoNot 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?
- in9 9y agoSo, which one do you use?
- thesmallestcat 9y agoWhat is a "major" algorithm? This repo is pretty light, so the bar must be high.
- torrent-of-ions 9y agoThe first one I see in the readme is bubble sort... so the bar obviously isn't at "useful".
- bogomipz 9y agoThis 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.)
- hakcermani 9y agoThis 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