Pygorithm – A Python module for learning major algorithms | Hacker News Reader

Pygorithm – A Python module for learning major algorithms

github.com

191 pointsPleaseHelpMe41 comments

I have few Python algorithms and data structures here: https://github.com/lion137/Python-Algorithms 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...

In 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 ?

Jon Bentley showed this can have problems with overflow. Better,

mid = left + (right - left)/2;

https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...

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:

https://stackoverflow.com/questions/4581842/python-integer-r...

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.

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.

No, it's not a design pattern. Yes it likely should be included in the language library.

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.

Sure, but 1. someone has to implement them, and 2. they can serve an educational purpose regardless.

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?

So, which one do you use?

I make it a point not to spoil interview questions I'm currently using to bunker bust folks who know all the usual answers.

Sorry. ;)

Here 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]])

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.

It's a 1 liner in 2017. In 1985, it's 2, right?

In 1985 it's pseudocode.

Maybe? Certainly languages with equivalent expressive power existed.

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]

What is a "major" algorithm? This repo is pretty light, so the bar must be high.

The first one I see in the readme is bubble sort... so the bar obviously isn't at "useful".

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

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.)

Once upon a time I made a Github repo with the same name and intention 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) :(

Reply on news.ycombinator.com