7 ms·

I think it's simpler than that: when you have arrays, linked lists and hash tables there aren't _that_ many cases when you need a binary tree, so I guess the de

I think it's simpler than that: when you have arrays, linked lists and hash tables there aren't _that_ many cases when you need a binary tree, so I guess the designers felt they weren't worth baking into the language at a syntax level. I agree it would have been nice to have in the standard library though.

chc 16y ago
This is sort of a "when all you have is a hammer…" situation. You don't need binary trees, but only in the same sense most of these data structures can stand in for one or more of the others. Binary trees can actually be better than hash tables in many cases where hash tables are used in mainstream scripting languages simply due to language support. An informative post on the subject: http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/ http://enfranchisedmind.com/blog/posts/problems-with-hash-ta...
- rg3 16y ago
  Your point about the need of certain data structures reminds me of the famous humorous text "Real programmers don't use Pascal", which said: "As all Real Programmers know, the only useful data structure is the Array. Strings, Lists, Structures, Sets-- these are all special cases of arrays and can be treated that way just as easily without messing up your programming language with all sorts of complications." The full text is available here and is a recommended read if you have some spare minutes: http://www.pbm.com/~lindahl/real.programmers.html http://www.pbm.com/~lindahl/real.programmers.html
- jemfinch 16y ago
  That's a great article, and I agree with most of it (e.g., that a balanced binary tree should be the default set/map data structure in programming languages; unfortunately it seems only C++ gets that right), but its reference to FNV as a good hash function is anachronistic. For a more modern and much faster hash, see http://sites.google.com/site/murmurhash/ http://sites.google.com/site/murmurhash/ . Murmurhash3 is an order of magnitude faster than FNV: http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3 .
  - chc 16y ago
    The article actually just says FNV is popular, not good. The point (as I understand it) was how common bad hash functions are.
  - eru 16y ago
    Haskell also gets it right. Look at Data.Map and Data.Set.
    - jemfinch 16y ago
      Haskell "gets it right" because you can't write an applicative hash table with the same computational complexity as a mutable one. Haskell's option is either "ordinary balanced binary trees" or "hash table in the IO monad".
- jerf 16y ago
  If you are seriously worried about the performance implications of a binary tree vs. the Python hashes, you are working in the wrong language. Whatever performance implications you are worried about are utterly dwarfed by the Python penalty. I am not being sarcastic or cynical. There really isn't much point in really nailing some of these things to the wall in Python or Perl or Ruby or the other interpreted languages hanging out at the bottom of the shootout[1] because you've already thrown performance out the window as a consideration just by cracking open your editor and starting a new file. This is an argument to take up with languages much higher up the shootout. [1]: http://shootout.alioth.debian.org/ http://shootout.alioth.debian.org/ , if you don't know what I mean by that. The benchmarks there may not see all and know all, but they aren't meaningless, either.
  - chc 16y ago
    I really hate arguments along these lines. Python programs might not be be as fast in the average case as, say, a C program, but that doesn't mean you don't care about performance at all. Yes, I will take a several-microsecond slowdown for the convenience of using Python over C. That's a fair tradeoff, as it really isn't noticeable from my perspective — it's the difference between, like, 10% CPU utilization and 1% utilization, and still done in the blink of an eye. But the difference between 56 seconds to process some data and 0.8 seconds? That matters.
    - jerf 16y ago
      I agree. But a binary tree vs. a hash table isn't going to be that difference. That's my point. Python won't excuse an O(n^3) when you should have been using an O(log n) algorithm, but the constant factors of Python are so huge they dominate a lot of the choices you'd make between two different O(log n) algorithms. You'd never notice the difference between the existing built-in Python dict and a hypothetical built-in binary tree, it would just be buried by some of the fundamentally-cache-hostile stuff Python does as it is bouncing all around memory with all the indirection it has on every line that has nothing to do with either structure.
    - jemfinch 16y ago
      > But the difference between 56 seconds to process some data and 0.8 seconds? That matters. This must be a purely theoretical argument for you, because you wouldn't be arguing this point if you were consistently analyzing data in Python and C/C++. I routinely analyze gigabytes of aggregated data in both Python and C++, and have occasionally rewritten the Python in C++ to be faster (as an aside, for basic processing it's surprising how simple the translation is). I routinely get between 10x and 100x improvement in computation speed, and often see similar reductions in memory used. Python is not slower than C/C++ by a few microseconds; it's slower for most operations by two or more orders of magnitude. Whether you have a dictionary implemented by a hash table or by a balanced binary tree is not going to have any significant impact on your analysis speed.

chc 16y ago

This is sort of a "when all you have is a hammer…" situation. You don't need binary trees, but only in the same sense most of these data structures can stand in for one or more of the others. Binary trees can actually be better than hash tables in many cases where hash tables are used in mainstream scripting languages simply due to language support. An informative post on the subject: http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/ http://enfranchisedmind.com/blog/posts/problems-with-hash-ta...

rg3 16y ago
Your point about the need of certain data structures reminds me of the famous humorous text "Real programmers don't use Pascal", which said: "As all Real Programmers know, the only useful data structure is the Array. Strings, Lists, Structures, Sets-- these are all special cases of arrays and can be treated that way just as easily without messing up your programming language with all sorts of complications." The full text is available here and is a recommended read if you have some spare minutes: http://www.pbm.com/~lindahl/real.programmers.html http://www.pbm.com/~lindahl/real.programmers.html
jemfinch 16y ago
That's a great article, and I agree with most of it (e.g., that a balanced binary tree should be the default set/map data structure in programming languages; unfortunately it seems only C++ gets that right), but its reference to FNV as a good hash function is anachronistic. For a more modern and much faster hash, see http://sites.google.com/site/murmurhash/ http://sites.google.com/site/murmurhash/ . Murmurhash3 is an order of magnitude faster than FNV: http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3 .
- chc 16y ago
  The article actually just says FNV is popular, not good. The point (as I understand it) was how common bad hash functions are.
- eru 16y ago
  Haskell also gets it right. Look at Data.Map and Data.Set.
  - jemfinch 16y ago
    Haskell "gets it right" because you can't write an applicative hash table with the same computational complexity as a mutable one. Haskell's option is either "ordinary balanced binary trees" or "hash table in the IO monad".
jerf 16y ago
If you are seriously worried about the performance implications of a binary tree vs. the Python hashes, you are working in the wrong language. Whatever performance implications you are worried about are utterly dwarfed by the Python penalty. I am not being sarcastic or cynical. There really isn't much point in really nailing some of these things to the wall in Python or Perl or Ruby or the other interpreted languages hanging out at the bottom of the shootout[1] because you've already thrown performance out the window as a consideration just by cracking open your editor and starting a new file. This is an argument to take up with languages much higher up the shootout. [1]: http://shootout.alioth.debian.org/ http://shootout.alioth.debian.org/ , if you don't know what I mean by that. The benchmarks there may not see all and know all, but they aren't meaningless, either.
- chc 16y ago
  I really hate arguments along these lines. Python programs might not be be as fast in the average case as, say, a C program, but that doesn't mean you don't care about performance at all. Yes, I will take a several-microsecond slowdown for the convenience of using Python over C. That's a fair tradeoff, as it really isn't noticeable from my perspective — it's the difference between, like, 10% CPU utilization and 1% utilization, and still done in the blink of an eye. But the difference between 56 seconds to process some data and 0.8 seconds? That matters.
  - jerf 16y ago
    I agree. But a binary tree vs. a hash table isn't going to be that difference. That's my point. Python won't excuse an O(n^3) when you should have been using an O(log n) algorithm, but the constant factors of Python are so huge they dominate a lot of the choices you'd make between two different O(log n) algorithms. You'd never notice the difference between the existing built-in Python dict and a hypothetical built-in binary tree, it would just be buried by some of the fundamentally-cache-hostile stuff Python does as it is bouncing all around memory with all the indirection it has on every line that has nothing to do with either structure.
  - jemfinch 16y ago
    > But the difference between 56 seconds to process some data and 0.8 seconds? That matters. This must be a purely theoretical argument for you, because you wouldn't be arguing this point if you were consistently analyzing data in Python and C/C++. I routinely analyze gigabytes of aggregated data in both Python and C++, and have occasionally rewritten the Python in C++ to be faster (as an aside, for basic processing it's surprising how simple the translation is). I routinely get between 10x and 100x improvement in computation speed, and often see similar reductions in memory used. Python is not slower than C/C++ by a few microseconds; it's slower for most operations by two or more orders of magnitude. Whether you have a dictionary implemented by a hash table or by a balanced binary tree is not going to have any significant impact on your analysis speed.