4 ms·

Minimal examples of data structures and algorithms in Python

247 points by happy-go-lucky 10y ago

devsnd 10y ago
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#collections.abc.Iterable https://docs.python.org/3/library/collections.abc.html#colle... [2] http://stackoverflow.com/a/24944155/1191373 http://stackoverflow.com/a/24944155/1191373
- racerror 10y ago
  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.
  - leblancfg 10y ago
    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.
    - racerror 10y ago
      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.
santiagobasulto 10y ago
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-list/tree/solution 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.
- pryelluw 10y ago
  Stupid question: Interface.py follows a pattern Ive seen in Java but not in Python. Am I simply too much of a Python noob?
  - orf 10y ago
    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.
    - pryelluw 10y ago
      Ok, that's what I thought. Thanks for the reply.
- dahart 10y ago
  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 http://stackoverflow.com/a/283630/1424242
- zimablue 10y ago
kwk236 10y ago
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.
- a3n 10y ago
  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.
  - felixhummel 10y ago
    Along the same lines - use doctests maybe? if __name__ == "__main__": import doctest doctest.testmod() https://docs.python.org/3.5/library/doctest.html https://docs.python.org/3.5/library/doctest.html
    - majke 10y ago
      Agreed. Such code without decent doctests is close to useless. Also - try to get decent code coverage if you can.
    - a3n 10y ago
      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.
dahart 10y ago
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 http://ideone.com/WFv4f
- kwk236 10y ago
  That's just beautiful. I'll reference that.
- in9 10y ago
  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/generators.html http://numba.pydata.org/numba-doc/0.18.1/developer/generator...
witten 10y ago
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 https://gist.github.com/hrldcpr/2012250
tuna-piano 10y ago
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.
asteroidfodder 10y ago
Looks like count_bits loops infinitely if given a negative number. The wiki (https://wiki.python.org/moin/BitwiseOperators 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".
eminogrande 10y ago
Nice

247 points by happy-go-lucky 10y ago

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#collections.abc.Iterable https://docs.python.org/3/library/collections.abc.html#colle... [2] http://stackoverflow.com/a/24944155/1191373 http://stackoverflow.com/a/24944155/1191373

racerror 10y ago
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.
- leblancfg 10y ago
  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.
  - racerror 10y ago
    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.

santiagobasulto 10y ago

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-list/tree/solution 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.

pryelluw 10y ago
Stupid question: Interface.py follows a pattern Ive seen in Java but not in Python. Am I simply too much of a Python noob?
- orf 10y ago
  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.
  - pryelluw 10y ago
    Ok, that's what I thought. Thanks for the reply.
dahart 10y ago
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 http://stackoverflow.com/a/283630/1424242
zimablue 10y ago

kwk236 10y ago

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.

a3n 10y ago
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.
- felixhummel 10y ago
  Along the same lines - use doctests maybe? if __name__ == "__main__": import doctest doctest.testmod() https://docs.python.org/3.5/library/doctest.html https://docs.python.org/3.5/library/doctest.html
  - majke 10y ago
    Agreed. Such code without decent doctests is close to useless. Also - try to get decent code coverage if you can.
  - a3n 10y ago
    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.

dahart 10y ago

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 http://ideone.com/WFv4f

kwk236 10y ago
That's just beautiful. I'll reference that.
in9 10y ago
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/generators.html http://numba.pydata.org/numba-doc/0.18.1/developer/generator...

witten 10y ago

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 https://gist.github.com/hrldcpr/2012250

tuna-piano 10y ago

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.

asteroidfodder 10y ago

Looks like count_bits loops infinitely if given a negative number. The wiki (https://wiki.python.org/moin/BitwiseOperators 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".

eminogrande 10y ago

Nice