Python что быстрее list или tuple

Tuples vs. Lists vs. Sets in Python

In Python, there are four built-in data types that we can use to store collections of data. With different qualities and characteristics, these built-in data types are List ( list ), Tuple (tuple), Set ( set ), and Dictionary ( dict ).

In this article, we are going to dig into the rabbit holes of Lists, Tuple, and Sets in Python. We will go through their differences and when to use these data types.

As Dictionary associates keys with their respective values, which is a very different use case compared to List, Tuple, and Set (which simply just contain values), it won’t be part of this discussion.

For the sake of simplicity, I will use Set and Dictionary interchangeably, as they are based on Hash Table (or Hash Map).

Python built-in data types to store collections of data

Why do we care?

For the most part, these data types can be used interchangeably within an application without much trouble.

Yet, imagine if we were given a task to check if a needle exists in a sizable haystack. What would be the most efficient way in terms of speed and memory to do so?

Should the haystack be a List? What about a Tuple? Or why not always use a Set (or a Dictionary)? What are the caveats that we should look out for?

Differences between List, Tuple, and Set

Duplicates

If I were to explain this, List and Tuple are like siblings in Python. On the other hand, Set (or Dictionary) is like a cousin to both of them.

Unlike a List or Tuple, a Set cannot contain duplicates. In other words, the elements in a Set are unique.

With this knowledge in mind, we now know that Set can also be used to remove duplicates from a list!

Sorting Order

You might have heard the statement “Set and Dictionary are not ordered in Python.” Well, that is only half the truth today, depending on which version of Python you are using.

Before Python 3.6, Dictionaries and Sets do not keep their insertion order. Here’s an example if you try it out in Python 3.5:

Today, that statement is out of date by a couple of years. Starting from Python 3.7, Dictionary and Set are officially ordered by the time of insertion.

Anyway, in case you wondered, Lists and Tuples are ordered sequences of objects.

Mutability

When you describe an object as mutable, it’s simply a fancy way of saying the object’s internal state can be changed.

The key difference here is that Tuple is immutable (not changeable), whereas List and Set are mutable.

Although Sets are mutable, we cannot access or change any element of a Set via indexing or slicing. Hence, we can only add new elements into a set — not change them.

Do note that the update method in a Set simply means the ability to add multiple elements at once.

Indexing

Both Tuple and List support indexing and slicing, while Set does not.

When to use List vs. Tuple?

As we mentioned earlier, Tuples are immutable, whereas Lists are mutable. By the same token, Tuples are fixed size in nature, whereas Lists are dynamic.

Use List

1. When you need to mutate your collection.
2. When you need to remove or add new items to your collection of items.

Use Tuple

1. If your data should or does not need to be changed.
2. Tuples are faster than lists. We should use a Tuple instead of a List if we are defining a constant set of values and all we are ever going to do with it is iterate through it.
3. If we need an array of elements to be used as dictionary keys, we can use Tuples. As Lists are mutable (unhashable type), they can never be used as dictionary keys.

When to use Set vs. List/Tuple?

As Set uses Hash Table as its underlying data structure, Set is blazingly fast when it comes to checking if an element is inside it (e.g. x in a_set ).

The idea behind it is that looking up an item in a hash table is an O(1) (constant time) operation.

«So, should I always use Set or Dictionary?»

Essentially, if you do not need to store duplicates, Set is going to be better than List. Period.

Summary

If you’re a numbers geek like me, check out this speed comparison between Tuple, List, and Set when iterating or checking if an object is present in a collection.

Оптимизации, используемые в Python: список и кортеж

В Python, есть два похожих типа — список (list) и кортеж (tuple). Самая известная разница между ними состоит в том, что кортежи неизменяемы.

Вы не можете изменить объекты в tuple:

Но вы можете модифицировать изменяемые объекты внутри кортежа:

Внутри CPython (стандартного интерпретатора), список и кортеж реализованы как лист из указателей (ссылок) на Python объекты, т.е. физически они не хранят объекты рядом с друг другом. Когда вы удаляете объект из списка происходит удаление ссылки на этот объект. Если на объект ещё кто-то ссылается, то он продолжит находиться в памяти.

Кортежи

Несмотря на тот факт, что кортежи намного реже встречаются в коде и не так популярны, это очень фундаментальный тип, который Python постоянно использует для внутренних целей.

Вы можете не замечать, но вы используете кортежи когда:

• работаете с аргументами или параметрами (они хранятся как кортежи)
• возвращаете две или более переменных из функции
• итерируете ключи-значения в словаре
• используете форматирование строк

Пустые списки vs пустые кортежи

Пустой кортеж работает как синглтон, т.е. в памяти запущенного Python скрипта всегда находится только один пустой кортеж. Все пустые кортежи просто ссылаются на один и тот же объект, это возможно благодаря тому, что кортежи неизменяемы. Такой подход сохраняет много памяти и ускоряет процесс работы с пустыми кортежами.

Но это не работает со списками, ведь они могут быть изменены:

Оптимизация выделения памяти для кортежей

Для того, чтобы снизить фрагментацию памяти и ускорить создание кортежей, Python переиспользует старые кортежи, которые были удалены. Если кортеж состоит из менее чем 20 элементов и больше не используется, то вместо удаления Python помещает его в специальный список, в котором хранятся свободные для повторного использования кортежи.

Этот список разделен на 20 групп, где каждая группа представляет из себя список кортежей размера n, где n от 0 до 20. Каждая группа может хранить до 2 000 свободных кортежей. Первая группа хранит только один элемент и представляет из себя список из одного пустого кортежа.

В примере выше, мы можем видеть, что a и b имеют одинаковый адрес в памяти. Это происходит из-за того, что мы мгновенно заняли свободный кортеж такого же размера.

Оптимизация выделения памяти для списков

Так как списки могут изменяться, такую же оптимизацию как в случае с кортежами провернуть уже не получится. Несмотря на это, для списков используется похожая оптимизация нацеленная на пустые списки. Если пустой список удаляется, то он так же может быть переиспользован в дальнейшем.

Изменение размера списка

Чтобы избежать накладные расходы на постоянное изменение размера списков, Python не изменяет его размер каждый раз, как только это требуется. Вместо этого, в каждом списке есть набор дополнительных ячеек, которые скрыты для пользователя, но в дальнейшем могут быть использованы для новых элементов. Как только скрытые ячейки заканчиваются, Python добавляет дополнительное место под новые элементы. Причём делает это с хорошим запасом, количество скрытых ячеек выбирается на основе текущего размера списка — чем он больше, тем больше дополнительных скрытых слотов под новые элементы.

Эта оптимизация особенно выручает, когда вы пытайтесь добавлять множество элементов в цикле.

Паттерн роста размера списка выглядит примерно так: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…

Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.

Формула выбора размера написанная на Python:

Скорость

Если сравнивать эти два типа по скорости, то в среднем по больнице, кортежи слегка быстрее списков. У Raymond Hettinger есть отличное объяснение разницы в скорости на stackoverflow.

Why is tuple faster than list in Python?

I’ve just read in «Dive into Python» that «tuples are faster than lists».

Tuple is immutable, and list is mutable, but I don’t quite understand why tuple is faster.

Anyone did a performance test on this?

8 Answers 8

The reported «speed of construction» ratio only holds for constant tuples (ones whose items are expressed by literals). Observe carefully (and repeat on your machine — you just need to type the commands at a shell/command window!).

I didn’t do the measurements on 3.0 because of course I don’t have it around — it’s totally obsolete and there is absolutely no reason to keep it around, since 3.1 is superior to it in every way (Python 2.7, if you can upgrade to it, measures as being almost 20% faster than 2.6 in each task — and 2.6, as you see, is faster than 3.1 — so, if you care seriously about performance, Python 2.7 is really the only release you should be going for!).

Anyway, the key point here is that, in each Python release, building a list out of constant literals is about the same speed, or slightly slower, than building it out of values referenced by variables; but tuples behave very differently — building a tuple out of constant literals is typically three times as fast as building it out of values referenced by variables! You may wonder how this can be, right?-)

Answer: a tuple made out of constant literals can easily be identified by the Python compiler as being one, immutable constant literal itself: so it’s essentially built just once, when the compiler turns the source into bytecodes, and stashed away in the «constants table» of the relevant function or module. When those bytecodes execute, they just need to recover the pre-built constant tuple — hey presto!-)

This easy optimization cannot be applied to lists, because a list is a mutable object, so it’s crucial that, if the same expression such as [1, 2, 3] executes twice (in a loop — the timeit module makes the loop on your behalf;-), a fresh new list object is constructed anew each time — and that construction (like the construction of a tuple when the compiler cannot trivially identify it as a compile-time constant and immutable object) does take a little while.

That being said, tuple construction (when both constructions actually have to occur) still is about twice as fast as list construction — and that discrepancy can be explained by the tuple’s sheer simplicity, which other answers have mentioned repeatedly. But, that simplicity does not account for a speedup of six times or more, as you observe if you only compare the construction of lists and tuples with simple constant literals as their items!_)

Python Tuples vs Lists — Comparison Between Lists and Tuples

In this article, we are going to try to explain review difference between tuples and lists. They are both similar sequence types in python. There is a big difference when considering lists and tuples. Tuples are immutable list but it isn’t true for lists. So, you cannot change their size as well as their immutable objects.

Tuples refer directly to their elements. Also, the lenght and order of objects are important. But lists have an extra layer of indirection to an external array of pointers. This provides speed advantage to tuple for indexed lookups and unpacking.

There are two benefits to using tuple.

1. Clarity: When you see a tuple in the code, you know that lenght information will never change.
2. Performance: A tuple uses less memory than a list of the same length.

Example 1. We can’t changes items in a tuple:

Example 2. if there is any list(mutable) in a tuple, we can change it.

Example 3. A tuple’s size is fixed and don’t over-allocate. Thus, it can be stored more compactly than lists which need to over-allocate to make append() operations efficient.

Example 4. Empty tuple always acts only one tuple as a singleton. It returns immediately itself. Also, It has a length of zero. When we create an empty tuple, points to the already preallocated one by python. Thus, both of them has the same address. They are saving memory.

Example 5. Since tuples are immutable, they do not have to be copied. Lists are mutable objects and requires all the data to be copied to a new list:

Where is tuple usually used ?

• string formatting.
• working with arguments and parameters.
• iterating over dictionary key-value pairs.
• returning 2 or more items from a function.

Summary

In this article, we explained the tuple and list sequence types. Tuple(Mutable) sequence is more compact, faster and more to use. It can hold list(mutable) objects and be sure to use these objects correctly with nested data structures. Although It cannot be changed, it can change if it contains a list(mutable) object.