Эффективность конкатенации списка питов

Каков наиболее эффективный способ объединить два списка list_a и list_b, когда:

  • list_b элементы должны быть помещены перед list_a элементами
  • результат должен быть помещен в list_a

У меня есть 4 возможности:

# 1
list_a = list_b + list_a

# 2
for item in list_b:
    list_a.insert(0, item)

# 3
for item in self.list_a:
    list_b.append(item)
list_a = list_b

# 4
list_a[0:0] = list_b

Спасибо!

Ответы

Ответ 1

Здесь приведен график того, как тайминги, используемые в ответе BigYellowCactus, развиваются по мере увеличения длины списков. Вертикальная ось - это время, необходимое для инициализации обоих списков и вставки одного перед другим, в usec. Горизонтальная ось - это количество элементов в списках.

Asymptotic behaviour of the possibilities

Ответ 2

Вы можете назначить list_b срезу, который бывает пустым, но в начале списка_a:

list_a[0:0] = list_b

Это самый быстрый способ вставить список в другой список в любой позиции.

Ответ 3

Учитывая, что

list_a = list_b + list_a

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

Если вы также не заботитесь о том, чтобы это был именно список, но только об этом можно было бы повторить, вы можете использовать itertools.chain:

list_a = itertools.chain(list_b, list_a)

Если вы заботитесь о некоторых вещах списка, вы можете создать подобный тип вещей chain, который ведет себя как список - что-то вроде:

class ListChain(list):
    def __init__(self, *lists):
        self._lists = lists

    def __iter__(self):
        return itertools.chain.from_iterable(self._lists)

    def __len__(self):
        return sum(len(l) for l in self._lists)

    def append(self, item):
        self._lists[-1].append(item)

    def extend(self, iterable):
        self._lists.append(list(iterable))

    def __getitem__(self, item):
       for l in self._lists:
           if item < len(l):
              return l[item]
           item -= len(l)
       else:
          raise IndexError

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

Ответ 4

Почему бы просто timeit?

import timeit

create_data = """\
list_a = range(10)
list_b = range(10)
"""

t1 = timeit.Timer(stmt=create_data + """\
list_a = list_b + list_a
""")

t2 = timeit.Timer(create_data + """\
for item in list_b:
    list_a.insert(0, item)
""")

t3 = timeit.Timer(create_data + """\
for item in list_a:
    list_b.append(item)
list_a = list_b
""")

t4 = timeit.Timer(create_data + """\
list_a[0:0] = list_b
""")

for i, t in enumerate([t1,t2,t3,t4]):
    print i, "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)

Результат:

0 0.73 usec/pass
1 2.79 usec/pass
2 1,66 мксек/пропуск
3 0,77 мксек/проход

Ответ 5

попробуйте следующее:

list_a[0:0] = list_b