2016-08-10 5 views
2

У меня есть список, который составлен из трех слоев, глядя что-то подобное для иллюстративных целей:Каков самый быстрый способ доступа к элементам во вложенном списке?

a = [[['1'],['2'],['3'],['']],[['5'],['21','33']]] 

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

Первый слой будет содержать десятки списков. Следующий слой может содержать, возможно, миллионы списков, а нижний уровень будет содержать либо пустую строку, одну строку, либо несколько значений (каждая строка).

Теперь мне нужно получить доступ к значениям в самом нижнем слое и сохранить их в новом списке в определенном порядке, который выполняется внутри цикла. Каков самый быстрый способ доступа к этим значениям? Объем используемой памяти не имеет для меня первостепенной важности (хотя я, очевидно, тоже не хочу его разбавлять).

я могу думать о двух способов:

  1. Я список a доступа непосредственно для получения требуемого значения, например, a[1][1][0] вернется '21'.
  2. Я создаю копию элементов a, а затем обращаюсь к ним, чтобы сгладить список немного больше. В этом случае, например, например: b=a[0], c=a[1], поэтому вместо доступа к a[1][1][0] Теперь я получаю доступ к b[1][0] для извлечения '21'.

Есть ли какой-либо штраф за производительность при доступе к вложенным спискам? Таким образом, есть ли какая-либо польза в разбивке списка a в отдельные списки, или я просто беру на себя штраф за ОЗУ?

ответ

1

Эти два метода более или менее идентичны, поскольку b=a[0] связывает другое имя с этим индексом. Он не копирует список. Тем не менее, единственное различие заключается в том, что во втором методе единственная разница заключается в том, что вы, помимо доступа к вложенным спискам, в конечном итоге бросаете ссылки. Таким образом, теоретически это немного медленнее.

Как отметил @joaquinlpereyra, Питон Wiki содержит список сложности таких операций: https://wiki.python.org/moin/TimeComplexity

Итак, длинный ответ оборвался: Просто доступ элементов списка быстрее.

+1

Это теоретически быстрее, но назначение - это еще одна операция O (1), поэтому на практике это вообще ничего не изменит. – joaquinlpereyra

+0

@joaquinlpereyra - это не один O (1) для доступа к элементу, а один O (1) для назначения? –

+0

Да. И это все еще O (1). Сложность определяется как (математический) предел. Это довольно интересно: https://en.wikipedia.org/wiki/Big_O_notation. В основном. вы можете иметь N (n константу) O (1) операций и алгоритм будет по-прежнему O (1). – joaquinlpereyra

2

Доступ к элементам через их индекс (например: a [1] [1] [0]) является операцией O (1): source. Вы не получите намного быстрее, чем это.

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