Устранить эту ненужную копию в list.extend

Question

Учитывая два нормальных списки питона, newlist и oldlist, с целым числом index < len(oldlist), я хотел бы выполнить следующую операцию:

newlist.extend(oldlist[index:]) 

, но без создания промежуточного список oldlist[index:], или, что эквивалентно,

newlist.extend(oldlist[i] for i in xrange(index, len(oldlist))) 

без накладных расходов генератора. Возможно ли это без использования C?

Редактировать: Этот вопрос вытекает из некоторых примеров реализации некоторых операций с списком, в частности для list.extend(), когда интерпретатор определяет, что он может угадать размер хвоста, добавляемого в список, он выделяет полный размер в главный список и копирует элементы по мере их создания; для других случаев он выделяет несколько элементов за раз (около восьми, если используется память) и копирует элементы в несколько раз за раз.

Конкретные случаи, когда он выполняет полное распределение, по-видимому, для списков python и нескольких других типов, которые имеют __len__. Насколько я могу судить, нет встроенного типа «просмотра списка», который бы удовлетворял этим требованиям.

Answer 1

Не догадывается, измерить

create = """ 
oldlist = range(5000) 
newlist = range(5000, 10000) 
index = 500 
""" 
tests = [ 
    "newlist.extend(oldlist[index:])", 
    "newlist.extend(oldlist[i] for i in xrange(index, len(oldlist)))", 
    "newlist.extend(islice(oldlist, index, None))", 
    """\ 
while index < len(oldlist): 
    newlist.append(oldlist[index]) 
    index+=1""", 
] 

import timeit 
for test in tests: 
    t = timeit.Timer(create + test, setup='from itertools import islice') 
    print test, min(t.repeat(number=100000)) 

---

newlist.extend(oldlist[index:]) 17.2596559525 
newlist.extend(oldlist[i] for i in xrange(index, len(oldlist))) 53.5918159485 
newlist.extend(islice(oldlist, index, None)) 19.6523411274 
while index < len(oldlist): 
    newlist.append(oldlist[index]) 
    index+=1 123.556715012 

Answer 2

Очевидным решением было бы:

while index < len(oldlist): 
    newlist.append(oldlist[index]) 
    index += 1 

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

Answer 3

appendnew = newlist.append 
try: 
    while 1: 
     appendnew(oldlist[index]) 
     index += 1 
except IndexError: 
    pass 

или чуть меньше умопомрачителен:

appendnew = newlist.append 
for i in xrange(index, len(oldlist)): 
    appendnew(oldlist[i]) 

Answer 4

Некоторых подсказок на лучшем бенчмаркинг

Измерьте накладные расходы и вычтите их.

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

from itertools import islice 
def f0(newlist, oldlist, index): 
    pass 
def f1(newlist, oldlist, index): 
    newlist.extend(oldlist[index:]) 
def f2(newlist, oldlist, index): 
    newlist.extend(oldlist[i] for i in xrange(index, len(oldlist))) 
def f3(newlist, oldlist, index): 
    newlist.extend(islice(oldlist, index, None)) 
def f4(newlist, oldlist, index): 
    while index < len(oldlist): 
     newlist.append(oldlist[index]) 
     index += 1 


>python -mtimeit -s"old=range(1000);new=range(5000,10000);ix=500;import xtnd"; "xtnd.f4(new,old,ix)" 

Если код будучи протестированные имеет переменную N (в данном случае N = Len (oldlist) - индекс), тест с более чем одним значением N. Если ожидать O (N) поведение, O (1) результаты должны быть причиной для расследования.

Также сравнивайте результаты по парам кандидатов с разумными ожиданиями --- следует исследовать дикие вариации; они могут быть вызваны экспериментальной ошибкой.