сделать словарь из первых элементов в списке списка

Это вопрос о производительности использования set() для понимания списка внутри понимания словаря по сравнению с пониманием словаря и повторным присвоением новому словарю

Итак, у меня есть набор данных, который представляет собой список списков, и мне нужно получить уникальный список элементов с индексом «0» в каждом из этих списков внутри большого списка, чтобы иметь возможность создать новый словарь из них.. что-то вроде dict.fromkeys().. здесь мне нужно предоставить список уникальных ключей..

я использую

[1] { x : [] for x in set([i[0] for i in data])}

а также используя

[2] { i[0] : [] for i in data}

пример данных для справки здесь может быть таким: [[1,3,4], [3,5,2], [1,5,2]]

результатом выполнения [1] и [2] выше будет: { 1:[], 3: [] }

Я попробовал %timeit для обоих операторов, и оба они дают почти одинаковые результаты, что затрудняет определение того, какой из них лучше с точки зрения производительности для большого списка списков.

Как мне определить потенциальное узкое место здесь?

ИЗМЕНИТЬ:

Если это поможет в объяснении результатов..

In [172]: data_new = data * 10000

In [173]: %timeit { i[0] : [] for i in data_new}
10 loops, best of 3: 160 ms per loop

In [174]: %timeit { x : [] for x in set([i[0] for i in data_new])}
10 loops, best of 3: 131 ms per loop

In [175]: data_new = data * 100000

In [176]: %timeit { x : [] for x in set([i[0] for i in data_new])}
1 loops, best of 3: 1.37 s per loop

In [177]: %timeit { i[0] : [] for i in data_new}
1 loops, best of 3: 1.58 s per loop

In [178]: data_new = data * 1000000

In [179]: %timeit { i[0] : [] for i in data_new}
1 loops, best of 3: 15.8 s per loop

In [180]: %timeit { x : [] for x in set([i[0] for i in data_new])}
1 loops, best of 3: 13.6 s per loop

python python-2.7 set list-comprehension dictionary-comprehension
person arcolife    schedule 28.01.2015    source источник
comment
Сгенерируйте много случайных данных и используйте их, а затем повторите время... 2 в конце концов выйдет быстрее, так как он выполняет гораздо меньше работы (например: не строит список, а затем строит набор )   -  person Jon Clements♦    schedule 28.01.2015
comment
Разница во времени равна времени, которое требуется для создания дополнительной set в #1... это несколько мс в списке из миллиона элементов. Другими словами, ищите узкое место в другом месте.   -  person roippi    schedule 28.01.2015
comment
Вы не можете использовать dict.fromkeys здесь, потому что dict.fromkeys(..., []) будет делиться списком, что, возможно, вам не нужно.   -  person thefourtheye    schedule 28.01.2015
comment
@thefourtheye, я согласен. Я этого не сделал. Упомянул это только для того, чтобы дать представление о том, чего я пытаюсь здесь достичь.   -  person arcolife    schedule 28.01.2015
comment
@JonClements Удивительно, но 1 оказалось быстрее.. Я добавлю результаты в рассматриваемое редактирование.. в любом случае, все еще ищу объяснение.. может быть, что-то, связанное с set(), разработанным в библиотеке C со звуковым алгоритмом сортировки и назначения ключей существующему словарю медленнее, чем первый.   -  person arcolife    schedule 28.01.2015
comment
1-й может быть быстрее, потому что он не создает заново новые пустые списки для каждого повторяющегося ключа. 2-й также может быть быстрее с некоторыми другими значениями, особенно если дубликатов не так много.   -  person Antti Haapala    schedule 28.01.2015
comment
С другой стороны, словарь и набор ведут себя в основном одинаково...   -  person Antti Haapala    schedule 28.01.2015
comment
@roippi Я использовал длину 206000000 для окончательного% timeit. и разница стала 2,2 с. Но я понимаю вашу точку зрения. Тем не менее описание того, как [1] ​​быстрее, чем [2], в конечном итоге было бы здорово! :)   -  person arcolife    schedule 28.01.2015
comment
@arcolife Не могли бы вы попробовать и это set(i[0] for i in data_new)?   -  person thefourtheye    schedule 28.01.2015
comment
Еще быстрее используется set-comp { x: [] for x in {i[0] for i in data}}... - это означает, что dicts заменяет повторяющиеся ключи, что является узким местом   -  person Jon Clements♦    schedule 28.01.2015
comment
Да, dict() действительно нужно делать дополнительный подсчет ссылок и прочее, тогда как set() просто говорит, что ключ здесь, теперь идем дальше.   -  person Antti Haapala    schedule 28.01.2015

Ответы (2)


arrow_upward
4
arrow_downward

Создайте больший набор данных, затем засеките время:

Код:

import random
data = [ [random.randint(1, 9) for _ in range(3)] for _ in range(1000000)]

Время:

%timeit { x : [] for x in set([i[0] for i in data])}
# 10 loops, best of 3: 94.6 ms per loop
%timeit { i[0] : [] for i in data}
# 10 loops, best of 3: 106 ms per loop
%timeit { x: [] for x in set(i[0] for i in data)}
# 10 loops, best of 3: 114 ms per loop
%timeit { x: [] for x in {i[0] for i in data}}
# 10 loops, best of 3: 77.7 ms per loop

Обоснование:

Ограничение доступного пространства ключей сначала означает, что словарь должен назначить (с учетом randint выше) только 9 уникальных ключей для 9 новых списков. При использовании dict comp словарь должен неоднократно создавать и повторно назначать значение своего ключа вновь созданному списку... Разница заключается в накладных расходах при освобождении отброшенных пустых списков (будучи мусором). собрано) и время, затраченное на создание нового пустого списка.

При равномерном распределении из randint получается 111 111 выделений и освобождений пустых списков для 9 уникальных значений в наборе из 1 000 000 элементов — это намного больше, чем просто 9.

person Jon Clements♦    schedule 28.01.2015

arrow_upward
2
arrow_downward

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

Далее L = [[1,3,4], [3,5,2], [1,5,2]] * 100000

In [1]: %timeit { x : [] for x in {i[0] for i in L]}}
10 loops, best of 3: 58.9 ms per loop

In [2]: %timeit { i[0] : [] for i in L}
10 loops, best of 3: 68.1 ms per loop

Теперь протестируйте с постоянным значением None здесь:

In [3]: %timeit { x : None for x in set([i[0] for i in L])}
10 loops, best of 3: 59 ms per loop

In [4]: %timeit { i[0] : None for i in L}
10 loops, best of 3: 54.3 ms per loop

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

У меня не было ipython для Python 2, и я немного ленив, но вы хотели бы заметить, что Python 2.7 поддерживает понимание наборов, которые, по крайней мере, в Python 3.4 намного быстрее, чем создание наборов. из списков:

In [7]: %timeit { x : [] for x in {i[0] for i in L}}
10 loops, best of 3: 48.9 ms per loop
person Antti Haapala    schedule 28.01.2015