Minimal examples of data structures and algorithms in Python | Hacker News Reader

Minimal examples of data structures and algorithms in Python

github.com

247 pointshappy-go-lucky23 comments

Author here. This repo got popular before I had a chance to write README and organize code. I am going to make the code more consistent, add tests, and write brief tutorials by the following month. Please let me know if you have suggestions.

Suggestion: a short main() and if __name__ = ... for each file, serving as a demo/smoke test. It doesn't stop you from importing it as a module, and it's nice to see using code.

Along the same lines - use doctests maybe?

    if __name__ == "__main__":
        import doctest
        doctest.testmod()

https://docs.python.org/3.5/library/doctest.html

Agreed. Such code without decent doctests is close to useless. Also - try to get decent code coverage if you can.

A great idea. But I'd also like to see an all-in-one-place dog and pony show, constructing it and using it right next to each other.

I had a quick look at the examples and while they are written in python, they are not pythonic at all. `list_flatten` should use list a comprehension and probably use `collections.abc` [1] for the isinstance test. The `reverse_bits` function only works for 32 bit systems and should use `sys.intmax` [2] to find out how many bits to actually reverse. And `bit.subsets` will mutate the argument you gave to it to calculate the result (which is probably not intended). That's all the examples I looked at so far.

I know that the title says "minimal examples" and the goal is not make it "production ready", but as a learning resource you should always make sure to provide good examples, because that's what the students will use and write later on.

[1] https://docs.python.org/3/library/collections.abc.html#colle...

[2] http://stackoverflow.com/a/24944155/1191373

You could have cloned, made proposed changes to the source, pushed and made a pull request. Then, referenced it here, made the same point and provided the solution with the same amount of effort as your English-only criticism.

I don't think it's fair to ask of a stranger to take the time to fix someone else's cheat cheat if he's never going to use it. The criticism still holds, however.

I agree with you.

The point I was making, albeit poorly, was open-source is awesome. git, github and pull requests make it even better.

When someone contributes something that may be half-baked and someone else comes along to critique it. A pull-request that demonstrates the solution can be an equally efficient means of communicating the same criticism. Meanwhile, the whole community reaps the benefit of that effort.

TLDR; OSS devs should favor, "showing the way" and github makes that easy.

With all due respect, these might be good examples for people trying to learn algorithms and data structures, but it's not a good example of Pythonic code. Here's an example of one of the group projects in our course, that implements a "Pythonic" Linked List, relying on Iterators and Magic methods: https://github.com/rmotr-group-projects/pyp-w2-gw-linked-lis...

(switch to the branch master if you don't want to see the solution and want to give it a try by yourself).

In any case, if OP is the owner of the repo, good job compiling all that code together.

Stupid question:

Interface.py follows a pattern Ive seen in Java but not in Python. Am I simply too much of a Python noob?

No, it's not a particularly pythonic thing to do, but it's not uncommon to have a bass class with some methods that should be implemented by children and throw an exception if not. That's not quite an interface as Java has it though.

Ok, that's what I thought. Thanks for the reply.

So, the title does say these are examples of structure & algorithms, and doesn't claim to be "pythonic". But why do you feel like using iterators makes it more "pythonic" than not using iterators? Is your list implementation more concise or better expressed? Does it handle cases the article doesn't?

The code in the repo looks pythonic to me. This one looks pythonic to me. http://stackoverflow.com/a/283630/1424242

As someone who's written in a few languages and is now learning/writing Python full time, "pythonic" is starting to cause me a twitch of pain every time I read it.

It seems to imply the Python has the final solution in how to write code and therefore everything should be written in the way that Python elders have decided.

Main example: I don't really like list comprehensions. They're pretty much the same thing as map/filter but less understandable or composable, nevermind you fix (with your choice of brackets in multiple places) your choice of list vs generator vs "pushing source" (not sure the right word) which you wouldn't have to with transducers.

http://stackoverflow.com/questions/952914/making-a-flat-list...

I'd rather read code where someone wrote "flatten".

IMHO pythonic means that you adhere with the principle "there should be one --and preferably only one -- obvious way to do it". And that one way is set out by the BDFL Guido :).

I have theory that, python was introduced out of frustration with Perl. As we all know, Perl had the principle of TIMTOWTDI.

Another far more tangential and biased theory here: As Python imposes strict programming principles, it resembles Java in forcing the programmer to abide by the styles set out by the language designers. And maybe that's why schools prefer to teach Python instead of Ruby as a scripting language.

PS: I have nothing against Java and I love Python. My theory is based upon Guido's insistence on not opening the language fully to functional programming. I'd like to see better lambdas, functional programming without itertools etc. But I know Guido has his reasons, pythonic code uses list comprehensions instead of FP.

I quite like how minimal these are, very nice for understanding and for quick coding!

With minimal code like this, I'm a little torn between declaring a class with members and using an anonymous data structure. A tree for example can be a tuple in python, and doesn't need to be declared. How big do you let it get before taking the time to declare a class?

Re: primes_sieve_of_eratosthenes.py, after doing more primes problems on Project Euler than I care to admit, I ended up with this pretty minimal sieve. The repo's indexing and .append in the loop slow it down.

    sieve = [True] * n
    for i in xrange(2,int(n**0.5)+1): 
        if sieve[i]: sieve[i*i::i] = [False] * ((n-i*i-1)/(i)+1)

And total tangent but have you guys seen the amazing and extremely memory efficient postponed sieve generator? http://ideone.com/WFv4f

That's just beautiful. I'll reference that.

wouldnt this version you suggested, along with the postponed sieve generator, be Numba complaint code? From a quick read through, i think so. So then you could achieve, minimal JIT compiled code for your Project Euler problems :D

http://numba.pydata.org/numba-doc/0.18.1/developer/generator...

Relevant to this discussion, and not included in the linked repo as far as I can see.. A one-line tree in Python:

def tree(): return defaultdict(tree)

More here: https://gist.github.com/hrldcpr/2012250

Looks like count_bits loops infinitely if given a negative number.

The wiki (https://wiki.python.org/moin/BitwiseOperators) says:

Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011".

Examples look nice. Now we just need someone to ask a StackOverflow question for each subject and someone else to post each example as the answer, so I can find these when I need them.

Nice

Reply on news.ycombinator.com