7 ms·

''' The following data structures are a complete list for almost all practical programs: array linked list hash table binary tree ''' this is why it's such

• chc 16y ago
  Except for one. Quick: What's the syntax for a binary tree in Python? OK, I'll give away the answer: It's not there. I don't think binary trees are even in the standard library for Python or Ruby. It's a sadly neglected data structure because, when exposed for what it is, it's a little bit too computer science-y for most people's taste.
  • archangel_one 16y ago
    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.
  • jemfinch 16y ago
    Except for two, actually: there aren't any linked lists in Python, either. Why? Because there's only one thing that a linked list is better at than a growable array: O(1) splice. Everything else is better with a growable array.
    • jedbrown 16y ago
      cons
      • jemfinch 16y ago
        Yes, and? Growable arrays use the same or less memory and offer random access to elements. They're not applicative, but then, if you insist on applicative data structures you're obviously not very concerned with performance anyway so there's no reason to bother with any particular data structure.
        • loup-vaillant 16y ago
          The burden of proof should be on the mutable end, not of the applicative one. Purely functional data-structures are far less error prone than mutable ones. They have simpler APIs, which lead to simpler and clearer code. In other words, mutable state is the biggest source of errors. It should be avoided when possible, and insulated otherwise. http://www.loup-vaillant.fr/articles/assignment http://www.loup-vaillant.fr/articles/assignment Therefore, mutable data-structures are almost always an optimization. You shouldn't use them unless your program is demonstrably too slow for your needs. (Incidentally, the same argument applies more strongly to C itself.) Finally, immutable data structures can sometimes be faster, for instance when you do backtracking, or keep track of undo information. With mutable data structure, you have to copy the whole thing.
          • eru 16y ago
            Indeed. The lack of persistent data structures in a Python is a much bigger barrier to a functional coding style than the lack of tail call optimization. You can mostly get around the missing tail call optimization by using combinators and avoiding naked recursion---a good idea anyway. And then implement your combinators, say map or foldr, with a loop. It's ugly, but nobody has to see it. There's no real way around the ephemeral nature of python lists and dicts---short of implementing your own versions. To say something positive: Strings, numbers and tuples are immutable in Python, though.
  • scott_s 16y ago
    Balanced binary tree versus hash table is an implementation choice for the associative array abstract data type. Similarly, growable array versus linked list are implementation choices for the list abstract data type. I don't buy that balanced binary trees are "too computer sciencey for most people's taste" as an argument against not have them as implementations of native types in Python. Designing a good hash table is equally as subtle in terms of both the theory and the implementation itself. But those details are not exposed through the interface.
    • shadowmatter 16y ago
      "Balanced binary tree versus hash table is an implementation choice for the associative array abstract data type." You can treat it as an implementation detail, but it's a good idea to let the client know that the underlying key-value collection is actually sorted by key. This allows the client to iterate over the key-value pairs in sorted order without dumping the keys to an array and then sorting it, retrieving the k smallest keys through forward iteration, retrieving the k largest keys through reverse iteration, etc. I think Java solves this nicely by creating the SortedMap subinterface of Map; if you have a SortedMap, you're assured these properties hold. (The typical implementation of SortedMap is a balanced tree, while the typical implementation of Map is a hash table.)
    • caf 16y ago
      A binary tree also allows efficient iteration in key order ("next" and "previous" operations).
    • eru 16y ago
      Yes. As the other poster argued, a tree needs some kind of ordering (like Hashtables need the keys to be hashable). But trees also give you a persistent data structure. Most hashtables including Python's dict are ephemeral, i.e. not copy-on-write.
  • derefr 16y ago
    Python: conn = sqlite3.connect('foo') curs = conn.cursor() curs.execute('create table things (id INTEGER PRIMARY KEY, stuff TEXT)') curs.execute('CREATE UNIQUE INDEX tree ON things (id ASC)') Now "tree" is your tree. ;) Quite seriously, though, people (that aren't systems programmers) don't think "this is a load of data—I need a binary tree!" People instead think "this is a load of data—I need a database!" and then, when the database isn't actually help their queries go faster, they slap their foreheads and exclaim "oh, wait, I need an indexed database!" Of course, the index just happens to be stored as a b-tree—but they don't know that, and they don't care. So, to reinterpret, this is basically the data-structure-usage flowchart for the average app programmer: 1. Need quick random access? Use an array. 2. Need quick insertion and removal, or lazy reification (to support, i.e., infinite sequences)? Linked lists, then. 3. Need quick search by key? Hash tables have you covered. (Well, these days, any "hash table" ADT also carries around its keys, so you also get O(N) enumeration of pairs.) 4. And, if your data set makes any of the above solutions choke? Just throw a database at it, and hope it helps.
    • chc 16y ago
      I apologize for being a little bit pedantic here, but a B-tree is not the same thing as a balanced binary tree, and a SQL database is something different still. Even if the SQL database happens to use binary trees somewhere in its implementation, using that database is not at all the same as using a binary tree for your data structures.
      • derefr 16y ago
        I didn't mean to imply that they were the same—just that, in practice, where a systems programmer thinks "use an in-memory binary tree data structure", an application programmer thinks "use a database", and a B-tree is what they end up using under the layers of abstraction and encapsulation. Yes, a binary tree and a B-tree are bad substitutes for one another, but you'll be much, much better off substituting a B-tree for a binary tree, or vice-versa, than substituting in, say, a linked list. A cooking analogy: you wouldn't drink cream instead of milk—but if a recipe calls for milk and you don't have any, cream is a much better call than orange soda. For some things (implementing a virtual filesystem, say), the app programmer will make the call to use a database, and they'll be fine, because a B-tree is just what a virtual filesystem needs. For others—storing and evaluating a Lisp AST, for example—they'll have to make O(N) roundtrips through the database and create a bunch of useless indexing cruft, but if the AST is complex enough, and if they're beta-reducing and caching their results in each parent node as they go, then this is still likely to outperform an alternative implementation that naively uses any of the other three data structures.
• acqq 16y ago
  Still, Pike writes from the perspective of a C programmer. Having the pointers and 1-1 mapping between the types and the memory layout of the can combine the principles of the structures in something bigger and more complex. For example, the tree with where some elements are also linked in different lists. I'm not saying that you can't have some logical equivalent in higher languages, but you can't have that expressiveness and efficiency.