Должен ли я использовать dict или список?

Question

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

authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"], ... ] 

и получите список, который содержит все имена, что происходит в авторах.

Когда я цикл по списку, мне нужен контейнер для хранения имен я уже видел, я задаюсь вопросом, должен ли я использовать список или Dict:

со списком:

seen = [] 
for author_list in authors: 
    for author in author_list: 
     if not author in seen: 
      seen.append(author) 
result = seen 

с Dict:

seen = {} 
for author_list in authors: 
    for author in author_list: 
     if not author in seen: 
      seen[author] = True 
result = seen.keys() 

который один быстрее? или есть лучшие решения?

Answer 1

Вы действительно хотите set. Наборы быстрее, чем списки, поскольку они могут содержать только уникальные элементы, что позволяет им реализовывать как хэш-таблицы. Хэш-таблицы позволяют проводить тестирование членства (if element in my_set) в O(1) времени. Это контрастирует со списками, где единственный способ проверить, если элемент находится в списке, чтобы проверить каждый элемент списка, в свою очередь (в O(n) времени.)

dict похож на set в том, что оба позволяют уникальным только ключи, и оба они реализованы как хэш-таблицы. Они оба допускают тестирование на членство в O(1). Разница в том, что set имеет только ключи, а dict имеет как ключи, так и значения (что лишние накладные расходы вам не нужны в этом приложении.)

---

Использование set, и заменяя вложенный цикл с itertools.chain(), чтобы сгладить список 2D к 1D списку:

import itertools 
seen = set() 
for author in itertools.chain(*authors): 
    seen.add(author) 

или короче:

import itertools 
seen = set(itertools.chain(*authors)) 

Edit (спасибо, @jamylak) больше памяти для больших списков:

import itertools 
seen = set(itertools.chain.from_iterable(authors)) 

---

Пример в списке списков:

>>> a = [[1,2],[1,2],[1,2],[3,4]] 
>>> set (itertools.chain(*a)) 
set([1, 2, 3, 4]) 

---

P.S. : Если вместо поиска всех уникальных авторов вы хотите указать кол-во количество раз, когда вы видите каждого автора, используйте collections.Counter, специальный словарь, оптимизированный для подсчета вещей.

Вот пример подсчета символов в строке:

>>> a = "DEADBEEF CAFEBABE" 
>>> import collections 
>>> collections.Counter(a) 
Counter({'E': 5, 'A': 3, 'B': 3, 'D': 2, 'F': 2, ' ': 1, 'C': 1}) 

Answer 2

Вы можете использовать набор -

from sets import Set 

seen = Set() 

for author_list in authors: 
    for author in author_list: 
     seen.add(author) 

result = seen 

Таким образом, вы спасаясь «если» проверки, следовательно, решение будет быстрее.

Answer 3

set должно быть быстрее.

>>> authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"]] 
>>> from itertools import chain 
>>> set(chain(*authors)) 
set(['Lisa', 'Bob', 'Jim', 'Molly', 'Alice']) 

Answer 4

с использованием dict или set является way faster затем с помощью list

import itertools 
result = set(itertools.chain.from_iterable(authors)) 

Answer 5

Если вы заботитесь о выполнении операций поиска, поиски в списках О (п), в то время как поиски в словарях амортизируются до O (1).

Дополнительная информация here.

Answer 6

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

Словари немного походят на телефонную книгу. Учитывая имя автора, вы можете очень быстро проверить, указан ли автор в телефонной книге, и найти номер телефона, указанный вместе с ним. Но вы можете включать только каждого автора один раз (с одним номером телефона), и вы не можете помещать авторов там в любом порядке, который вам нравится, они должны быть в порядке, который имеет смысл для телефонной книги. В реальной телефонной книге этот порядок является алфавитным; в словарях Python порядок полностью непредсказуем (и он изменяется, когда вы добавляете или удаляете вещи в словарь), но Python может находить записи еще быстрее в словаре, чем это было в телефонной книге.

Устанавливает, с другой стороны, как телефонные книги, которые просто имена списков, а не номера телефонов. Вы все еще не можете иметь одно и то же имя, включенное более одного раза, оно либо в наборе, либо нет. И вы по-прежнему не можете использовать порядок, в котором имена находятся в наборе для чего-либо полезного. Но вы можете очень быстро проверить, указано ли имя в наборе.

---

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

Списки плохие для этого случая; они прилагают усилия к тому, чтобы помнить дубликаты в любом порядке, который вы указали, и они медленно ищут. Но вам также не нужно отображать ключи в значениях, что и делает словарь.Чтобы вернуться к аналогии телефонной книги, у вас нет ничего эквивалентного «номеру телефона»; в вашем примере словаря вы делаете эквивалент написания телефонной книги, в которой каждый номер указан как True, так зачем вообще указывать номера телефонов?

Комплект, OTOH, делает именно то, что вам нужно.