3

i have been learning python over the past month or so. i like many of the things about the language, but i find the differentiation between tuples, lists, dicts, ordered dicts, and sets to be cumbersome. i know these each have their own performance benefits and tradeoffs, but it seems to me that it would be far simpler to combine them all into a single data structure - maybe a dict but which maintains the order originally specified - pretty much like json...

would this be a massive performance hit, or could the optimizer fully compensate to maintain equal performance?

i'm guessing the answer is that it could not be done more simply and efficiently any other way - otherwise the language would already have been written that way. this being the case, can anyone explain why not?

also, would there be any other downsides to replacing tuples, lists, dicts, ordered dicts and sets with a single json type data structure?

  • The most important concern is limiting the semantics of any one tool. The idea of specialized tools is a fundamental component of quality software design. – ChaosPandion Dec 5 '13 at 2:04
  • Is it really necessary to differentiate between ints and floats? – mouviciel Dec 10 '13 at 8:42
8

this being the case, can anyone explain why not?

The optimizer cannot compensate because the optimizer works at compile time. It cannot know how your collections will be used, so it cannot optimize the collections to the operations that are most common. Worse yet, the common operations may not be the important ones. Say you do 1000 inserts, but all those exist to let you do one quick lookup later. The inserts might not matter because they're done in the background while your app loads. There's no way for the optimizer to know.

would this be a massive performance hit

As with all things, it depends. Let me try to provide a quick, high level explanation why.

The reason that there cannot be one universal data structure is because of tradeoffs. If there existed a structure that was quick to insert, quick to search, quick to delete, quick to sort, memory efficient, thread safe, with no resizing penalties... well we'd certainly use it. The problem comes that if you optimize a data structure for say, quick insertions - something else will suffer. This table (thanks to this question) shows what all those tradeoffs.

And those tradeoffs are pretty significant. Having code do something common in O(n) (or worse) rather than O(1) is what takes the runtime of your app from milliseconds to seconds and from seconds to minutes or hours.

So yes, it is necessary to have all of these collections.

That said, it often doesn't matter if you use them. In C# for example, there's List<T> which is "good enough" for any basic collection and Dictionary<K,V> which is "good enough" when you need a lookup. Few apps need to be highly performant, and in those apps a small fraction of the app accounts for the majority of the runtime. Using the default collections until your profiler tells you differently is a fine approach for beginners, as long as you know that the other collections exist, and why they exist.

  • thanks. as you say, i can just use a single one until i have reason not to. the link is very useful as well. – mulllhausen Dec 5 '13 at 3:07
  • "the optimizer works at compile time" not true in general. Counterexample: PyPy. – user39685 Dec 10 '13 at 11:15
  • @MattFenwick - Enh, yes there are runtime optimizers but they are relatively rare in the universe of software development. And I cannot imagine one that would at runtime swap out your collection with a different one. – Telastyn Dec 10 '13 at 12:09
6

It sounds like you may have preconceived notions that come from PHP. I don't think any other commonly used language has such a "do-everything" data structure as PHP's arrays.

One purpose of multiple different kinds of collections is to clarify to the reader what the data structure might be used for. For example, if you're given a list you know that you can't ask for a["foo"]. If you're given a set you know that it doesn't make sense to ask for the fifth element. If you're given a tuple you know that you're not expected to be able to make changes to it.

As you mention, there are also performance considerations. While it is possible to construct a general purpose data container that has reasonable performance over most common cases, you can do better by constructing more specialised data structures.

These considerations simplify and clarify the processes of (a) constructing the software in the first place, and (b) making it easier for readers to understand the purpose of your data structures. If everything were a general purpose container such as the PHP "array", then it is less clear how the data ought to be used.

Finally, you mention a "single JSON type data structure", but JSON doesn't have a single type of data. The aggregate types within JSON are sequential arrays denoted with [], and name-value associates denoted with {}. That's already two different data types not counting the scalar types.

  • "I don't think any other commonly used language has such a "do-everything" data structure as PHP's arrays" — doesn't Perl? – detly Dec 5 '13 at 2:21
  • 1
    @detly: Not in the same way as PHP; Perl has at least arrays (@foo) and hashes (%foo) which are distinct. – Greg Hewgill Dec 5 '13 at 2:22
  • 1
    To be totally fair though, that's all the data structure we get in JS. [] and {}. I actually like that and I think when perf gets critical enough to care, I'd rather bind to C or C++ than have additional structures. Not that I don't respect Python. – Erik Reppen Dec 5 '13 at 2:44
  • 1
    @detly (or, for that matter, Tie the hash or list to a data structure that really does what one wants and retains the interface of the hash or list) – user40980 Dec 5 '13 at 3:32
  • 1
    @mulllhausen Using tuples solely as unchangeable lists isn't completely right. A better semantic use is for data that has meaning in a given position - the go-to example being (x, y, z) coordinates. Hence the existence of tuple unpacking. – Izkata Dec 5 '13 at 15:34
1

There are several reasons why:

  1. Some objects are more lightweight than others, as telastyn mentioned, performance would drop. A tuple, for example, functions much faster than a dict.

  2. The objects behave differently, and this is deliberate. Lists are accessible through numbered indexing (basically they are in chronological order and you can get the nth element). They are also iterable. Sets, on the other hand, deliberately have no order, and the same object in the set may not be repeated twice, as in a set, any object is either in or out. Tuples are primarily for performance. Because they cannot be modified, they are "read only", they run much faster, so it is best to use them if you do not modify your group after creation. Dicts act a lot like lists, only you assign the key. This is integral to python, for example it is necessary in an object.dict. These behaviors are meant so that there is an easy way to get whatever type of group you may want, instead of having to attempt to get a single group type to behave how you want it to. This way, code is easier to read and write.

  3. Python is object oriented (and managed), so it is very easy to make a new data structure. Because of this, it is not at all unlikely that a useful way to structure data will be included in python. It is much easier to add than a new type in C, for example.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.