Комментарии 28
Почему в формуле выбора размера Вы используете «2**3», а не «8»? Есть какая-то скрытая причина?
+1
>Самая известная разница между ними состоит в том, что кортежи неизменяемы.
Вообще, кортежи это не изобретение питона, они скорее из реляционного исчисления или из математики. И для них характерно то, что элемент i принадлежит домену i. Т.е. типы элементов разные, и известны заранее, как и их количество. Для списка же все наоборот.
А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.
Вообще, кортежи это не изобретение питона, они скорее из реляционного исчисления или из математики. И для них характерно то, что элемент i принадлежит домену i. Т.е. типы элементов разные, и известны заранее, как и их количество. Для списка же все наоборот.
А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.
+2
А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.Свойство полезное настолько, что почти обязательное:
>>> some_set = {(1, 'one'), (2, 'two')}
>>> (1, 'one') in some_set
True
>>> another_set = {[1, 'one'], [2, 'two']}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
-1
Просто у tuple определен __hash__, а у list нет.
Это весьма годное и правильно решение, но не единственно возможное.
Это весьма годное и правильно решение, но не единственно возможное.
class hlist(list):
def __hash__(self): return hash(tuple(self))
>>> another_set = {hlist([1, 'one']), hlist([2, 'two'])}
>>> another_set
{[1, 'one'], [2, 'two']}
+1
Это весьма годное и правильно решение, но не единственно возможное.Я настаивал именно на правильности и годности. Определить можно всё, что угодно, особенно когда речь идёт о питоне. Имеет ли это определение смысл — вопрос.
>>> for i in another_set:
... print "before:", i in another_set
... i[0] = 3
... print "after:", i in another_set
...
before: True
after: False
before: True
after: False
0
Я с вами согласен, иммутабельность кортежей в Python — крайне важная фишка.
Но и sshikov прав, говоря что иммутабельность не является характеристикой кортежей самих по себе. Есть языки, в которых кортежи мутабельны (например std::tuple в C++).
С вашим примером согласен, но опять же а) есть языки, где мутабельные списки хешабельны; b) в Python полно объектов с __hash__, которые на самом деле можно мутировать (если захотеть себе палок в колеса).
Но и sshikov прав, говоря что иммутабельность не является характеристикой кортежей самих по себе. Есть языки, в которых кортежи мутабельны (например std::tuple в C++).
С вашим примером согласен, но опять же а) есть языки, где мутабельные списки хешабельны; b) в Python полно объектов с __hash__, которые на самом деле можно мутировать (если захотеть себе палок в колеса).
Например fractions.Fraction технически мутабельный
>>> from fractions import Fraction
>>> s = {Fraction(1, 3), Fraction(1, 5)}
>>> for x in s:
... print("before:", x in s)
... x._denominator += 1
... print("after:", x in s)
...
before: True
after: False
before: True
after: False
+1
в Python полно объектов с __hash__, которые на самом деле можно мутировать (если захотеть себе палок в колеса).
Да, но, опять же, в питоне много чего можно. С одной стороны, ты пользуешь фичи ООП, а, с другой стороны, тебе прямо говорят, что так делать не стоит:
Fraction instances are hashable, and should be treated as immutable.
Т.е. за всех разработчиков не скажу, но, по крайней мере, те, кто писал документацию для fractions, прямо связывают immutable с __hash__. Вообще, возвращаясь к оригинальному комментарию, для меня (пишу на питоне) разница между кортежами и списками — это именно immutable. В сях, как я понял, это связано с другим свойством, гомогенностью.
0
Так с полезностью никто и не спорит. Я про другое слегка.
0
НЛО прилетело и опубликовало эту надпись здесь
Список сначала создается пустым, а уже потом туда добавляется элемент. Вы можете посмотреть байткод данного выражения или убедится что CPython переиспользует пыстые списки в его исходниках :)
In [3]: def test():
...: a = [1,]
...:
In [4]: dis.dis(test)
2 0 LOAD_CONST 1 (1)
2 BUILD_LIST 1
4 STORE_FAST 0 (a)
6 LOAD_CONST 0 (None)
8 RETURN_VALUE
+1
у меня тоже как то не сошлось:
Python 3.7.0 (default, Jul 4 2018, 20:22:06)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.4.0 -- An enhanced Interactive Python. Type '?' for help.
In [1]: a = (1,2,3)
In [2]: id(a)
Out[2]: 139724211253896
In [3]: del a
In [4]: b = (1,2,4)
In [5]: id(b)
Out[5]: 139724211206904
0
Лучше использовать стандартный REPL питона для таких тестов, IPython слишком умный. Пока вы печайте код он сам много всяких внутренних стуктур создает и мог перехватить свободный кортеж раньше. Особенно когда вы автодополнение используйте.
Я эти оптимизации не из головы взял, а в коде CPython подсмотрел, поэтому они точно существуют. github.com/python/cpython/blob/e271ca78e37a502b3dc1036f824aa3999efcd56b/Objects/tupleobject.c#L79
Я эти оптимизации не из головы взял, а в коде CPython подсмотрел, поэтому они точно существуют. github.com/python/cpython/blob/e271ca78e37a502b3dc1036f824aa3999efcd56b/Objects/tupleobject.c#L79
+3
Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.Почему заняты будут 9 а не 8? Я Python не знаю.
0
Ну есть же уже 8 элементов, добавляем еще 1, получаем список из 9 элементов.
А про расширение и алгоритм, рекомендую почитать www.laurentluce.com/posts/python-list-implementation
А про расширение и алгоритм, рекомендую почитать www.laurentluce.com/posts/python-list-implementation
+2
Расширение размера списка в n раз, когда заканчивается место — это совсем не особенность Python. Так работают вообще все списки, которые хранят элементы непрерывно в памяти.
+5
Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.
0
В начало будет дольше всех, питон от нужного индекса все элементы справа двигает на один шаг в право обычным циклом.
-1
Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.Это был сарказм? Я недавно слушал доклад о модных структурах в сях (конечно, их есть не только в сях): trees и тому прочее. Оказалось, что все эти сферические преимущества типа вставить элемент за O(log(N)), а потом найти его за тот же O(log(N)) работают только в вакууме (читай: только когда программа со всеми данными помещается в кэше процессора). Если идёт поиск по дереву или, не дай Б-г, по linked list — на каждом шаге тратится куча тактов только на то, чтобы подгрузить очередной кусок оперативной памяти.
Просто к слову пришлось.
-1
Ну почему только в вакууме? Не только. Всё относительно. Вопрос в том, какие N и каков масштабный коэффициент обработки одного элемента. Если в дереве хранить ссылки на данные в медленном хранилище, то обработать O(N) или O(N^2) может занять часы, против секунд или миллисекунд. Замечательное тому подтверждение — индексы в реляционных БД. При неправильно составленном плане сложный запрос с джойнами может работать сутками, а логарифмический доступ в правильном порядке решит вопрос за миллисекунды. Были такие случаи в личной практике. При этом на маленьких наборах (читай при сдаче проекта, когда не набралось много данных) всё на тех же запросах работает и не вызывает ощущения дискомфорта.
+2
Спасибо.
Побольше бы такой информации, которую не встретишь в обычных учебниках.
Побольше бы такой информации, которую не встретишь в обычных учебниках.
+2
Что-то я много раз проверял, и какой-то значимой разницы между временем работы кортежей и списков не обнаруживал. Вот написал ещё один тест.
В нём списки/кортежи генерируются из 1000000 строчек с числами, после чего в случайном порядке вычитываются все элементы списка/кортежа, потом читаются 3 элемента с фиксированными индексами.
Вот результат:
ИМХО при выборе список/кортеж нужно использовать только следующие соображения:
1. Если нужно использовать как ключ словаря/элемент множества, то только кортеж, без вариантов;
2. Если нужно добавлять/удалять элементы, или менять элементы внутри, то список, без вариантов;
3. Если внутри есть разнородные данные (то есть смысл элементов индексом i и индексом j может различаться, например ('Ivanov', 5)), то используем кортеж;
4. Если данные однородные, то используем список.
В контексте пп.3-4 тип как бы намекает:
если список, то он так и просит одинаковой обработки разных элементов:
а если кортеж, то он так и просит чего-нибудь в духе
В нём списки/кортежи генерируются из 1000000 строчек с числами, после чего в случайном порядке вычитываются все элементы списка/кортежа, потом читаются 3 элемента с фиксированными индексами.
Вот результат:
Num tests: 1000000, total numbers: 128524778, avg: 128.524778, median: 20, std: 269.0942898722472
Dummy. Crt:5.29, read:2.38, read fixed:0.0622, tot:7.73
Tuples. Crt:29.7, read:4.88, read fixed:0.108, tot:34.7
Lists. Crt:29.4, read:4.58, read fixed:0.106, tot:34.0
One run more
Dummy. Crt:8.35, read:2.63, read fixed:0.0704, tot:11.0
Lists. Crt:28.3, read:4.4, read fixed:0.102, tot:32.8
Tuples. Crt:29.2, read:4.79, read fixed:0.105, tot:34.1
Вот код для python 3.7
try:
from time import perf_counter_ns
dv = 1e9
except ImportError:
print('Use python 3.7!')
from time import perf_counter as perf_counter_ns
dv = 1
import random
def gen_test():
NTESTS = 1000000
LENS = list(range(11)) + [15, 20, 25, 35, 55, 75, 100, 300, 1000]
WEIGHTS = [100] * 11 + [100] * 4 + [200] * 2 + [200] * 3
assert len(LENS) == len(WEIGHTS)
tests = []
for __ in range(NTESTS):
l = random.choices(population=LENS, weights=WEIGHTS)[0]
data = ' '.join(str(random.randint(0, 10 ** 9)) for __ in range(l)) # Данные, которые будем писать
checks = list(range(l)) # Индексы, которые будем читать
random.shuffle(checks)
tests.append((data, checks))
return tests
def prt_test_stats(tests):
tests_lens = [len(tst[0].split()) for tst in tests]
tests_lens.sort()
avg = sum(tests_lens)/len(tests_lens)
median = tests_lens[len(tests_lens)//2]
std = (sum((l-avg)**2 for l in tests_lens)/(len(tests_lens) - 1))**.5
print(f'Num tests: {len(tests)}, total numbers: {sum(tests_lens)}, avg: {avg}, median: {median}, std: {std}')
def test_tuple(tests, tm=perf_counter_ns):
dur_crt = 0
dur_read = 0
dur_read_fixed = 0
for data, checks in tests:
t1 = tm()
row = tuple(map(int, data.split()))
t2 = tm()
for ind in checks:
val = row[ind]
t3 = tm()
if len(row) > 10:
t4 = tm()
val = row[1]
val = row[7]
val = row[0]
t5 = tm()
dur_read_fixed += t5 - t4
dur_crt += t2 - t1
dur_read += t3 - t2
return dur_crt, dur_read, dur_read_fixed
def test_list(tests, tm=perf_counter_ns):
dur_crt = 0
dur_read = 0
dur_read_fixed = 0
for data, checks in tests:
t1 = tm()
row = list(map(int, data.split()))
t2 = tm()
for ind in checks:
val = row[ind]
t3 = tm()
if len(row) > 10:
t4 = tm()
val = row[1]
val = row[7]
val = row[0]
t5 = tm()
dur_read_fixed += t5 - t4
dur_crt += t2 - t1
dur_read += t3 - t2
return dur_crt, dur_read, dur_read_fixed
def test_dummy(tests, tm=perf_counter_ns):
dur_crt = 0
dur_read = 0
dur_read_fixed = 0
for data, checks in tests:
t1 = tm()
row = data.split()
t2 = tm()
for ind in checks:
val = ind
t3 = tm()
if len(row) > 10:
t4 = tm()
val = 1
val = 7
val = 0
t5 = tm()
dur_read_fixed += t5 - t4
dur_crt += t2 - t1
dur_read += t3 - t2
return dur_crt, dur_read, dur_read_fixed
tests = gen_test()
prt_test_stats(tests)
dur_crt, dur_read, dur_read_fixed = test_dummy(tests)
print(f'Dummy. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
dur_crt, dur_read, dur_read_fixed = test_tuple(tests)
print(f'Tuples. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
dur_crt, dur_read, dur_read_fixed = test_list(tests)
print(f'Lists. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
print(f'One run more')
dur_crt, dur_read, dur_read_fixed = test_dummy(tests)
print(f'Dummy. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
dur_crt, dur_read, dur_read_fixed = test_list(tests)
print(f'Lists. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
dur_crt, dur_read, dur_read_fixed = test_tuple(tests)
print(f'Tuples. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
ИМХО при выборе список/кортеж нужно использовать только следующие соображения:
1. Если нужно использовать как ключ словаря/элемент множества, то только кортеж, без вариантов;
2. Если нужно добавлять/удалять элементы, или менять элементы внутри, то список, без вариантов;
3. Если внутри есть разнородные данные (то есть смысл элементов индексом i и индексом j может различаться, например ('Ivanov', 5)), то используем кортеж;
4. Если данные однородные, то используем список.
В контексте пп.3-4 тип как бы намекает:
если список, то он так и просит одинаковой обработки разных элементов:
for el in my_list:
pass
а если кортеж, то он так и просит чего-нибудь в духе
name, result, __, __, __, email = my_tuple()
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Изменить настройки темы
Оптимизации, используемые в Python: список и кортеж