3 ms·

This article is a great example of what's so great about the Python ecosystem. I don't think I've ever seen something like this for the Ruby data structures (ex

• ComputerGuru 16y ago
  You should program in C++ then. Every single data structure in the standard library, boost, and 3rd party libraries dissected, analyzed, benchmarked, extended, rewritten, and optimized :) But there's a reason you don't. I chose C, others chose Ruby, and you chose Python :)
  • djacobs 16y ago
    I chose Ruby then Python [1]. I use them both for the same kinds of things (especially functional programming [2]), but I'm surprised almost daily at how these similar languages drive such different ecosystems. [1] http://news.ycombinator.com/item?id=1947723 http://news.ycombinator.com/item?id=1947723 [2] http://news.ycombinator.com/item?id=2130725 http://news.ycombinator.com/item?id=2130725
  • kingkilr 16y ago
    Aren't the computation complexity of STL data structures defined by the spec?
    • beoba 16y ago
      STL data structures are explicitly defined as to their internals, which in turn implies their performance. For example, when you're using a STL map, you know it's internally a tree and has the upsides, downsides, and performance characteristics of that structure. (for a hashmap you'd be using unordered_map) Or at least that's how I picture it.
      • ComputerGuru 16y ago
        Actually, it's the exact opposite. The STL specification specifies the complexity but not the underlying data structure. For instance, if you'll refer to section 23.1.2 of the C++ 2003 standard ("Associative Containers"), you'll find that nowhere does it mention "tree," though it does explicitly lay out the complexity requirements for associative containers such as map and multimap, that at the end of the day, can really only be had with one type of tree or the other. Table 69 goes through all the functions and operations and the complexities allotted for each. Some are even explicitly specified as "compile time" operations. No C++ implementation is allowed to deviate from this, even to provide better performance.
        • deleted 16y ago
          [deleted]
        • beoba 16y ago
          I think of it in these terms: If you're implementing a key for a std::map, you have to implement operator<, which in turn implies that std::map is tree-based. Similar for unordered_map, which would want operator== and a hash function. Either of these interfaces are effectively describing what the internals are going to look like, even if the official standard decides to be coy about using the terms "tree" or "hash map" when describing them. In the case of Python, the fact that {}.keys() has no guaranteed order (for example) already implies that dictionaries are hash based and would have similar characteristics to any other hash map.
          • ot 16y ago
            > I think of it in these terms: If you're implementing a key for a std::map, you have to implement operator<, which in turn implies that std::map is tree-based. Not necessarily. For example a skip list can satisfy the same requirements but it is not a tree
            • beoba 16y ago
              True, but you still end up with similar performance to a tree.