Python: создайте функцию для изменения списка по ссылке, а не по значению

Question

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

Функциональность, которую я хочу реализовать:

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1
    return listOfElements

myList = range(10000)
myList = listCleanup(listOfElements)

Я не знаком с низкоуровневой работой Python. MyList передается по значению или по ссылке?

Как я могу сделать это быстрее?

Можно ли как-то расширить класс списка и реализовать в нем listCleanup ()?

myList = range(10000)
myList.listCleanup()

* 1013 Благодарения и *

Jonathan

Answer 1

Python передает все одинаково, но вызов его «по значению» или «по ссылке» не прояснит все, так как семантика Python отличается от языков, к которым обычно применяются эти термины. Если бы я должен был описать это, я бы сказал, что все передачи были по значению, и что значение было ссылкой на объект. (Вот почему я не хотел это говорить!)

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

foo = range(100000)
new_foo = []
for item in foo:
    if item % 3 != 0: # Things divisble by 3 don't get through
        new_foo.append(item)

или с использованием синтаксиса списка

 new_foo = [item for item in foo if item % 3 != 0]

Python не будет копировать объекты в списке, а foo и new_foo будут ссылаться на одни и те же объекты. (Python неявно копирует какие-либо объекты.)

---

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

Для решения проблемы производительности:

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

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

• Измерение. Время или перепрофилирование памяти при внесении изменения, чтобы увидеть, вносит ли изменение улучшение и если да, то что это улучшение.

• Чтобы сделать ваш код более чувствительным к памяти, вам часто понадобится смена парадигмы в способе хранения ваших данных, а не микрооптимизация, как не создание второго списка для фильтрации. (То же самое верно и для времени: действительно, переход на более качественный алгоритм почти всегда дает наилучшее ускорение. Однако об оптимизации скорости сложнее обобщать).

  Некоторые общие изменения парадигмы для оптимизации потребления памяти в Python включают

  1. Использование генераторов. Генераторы являются ленивыми итерациями: они не загружают целый список в память сразу, они выясняют, какие их следующие элементы находятся на лету. Для использования генераторов приведенные выше фрагменты будут выглядеть как

     foo = xrange(100000) # Like generators, xrange is lazy
     def filter_divisible_by_three(iterable):
         for item in foo:
             if item % 3 != 0:
                 yield item
     
     new_foo = filter_divisible_by_three(foo)
     

     или, используя синтаксис выражения генератора,

     new_foo = (item for item in foo if item % 3 != 0)
     

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

  3. Хранение данных на диск, например, в базе данных.

Answer 2

В Python списки всегда передаются по ссылке.

Размер объектов в списке не влияет на производительность списков, поскольку в списках хранятся только ссылки на объекты. Однако количество элементов в списке влияет на производительность некоторых операций, таких как удаление элемента, а это O (n).

Как написано, listCleanup является наихудшим O (n ** 2), поскольку у вас есть операция O (n) del внутри цикла, который потенциально является самим O (n).

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

В противном случае вам лучше воссоздать список. Это O (n), и ваш алгоритм должен быть как минимум O (n), так как вам нужно проверить каждый элемент. Вы можете отфильтровать список в одну строку следующим образом:

listOfElements[:] = [el for el in listOfElements if el.MeetsCriteria()]

Answer 3

Я не думаю, что кто-то упоминал, что на самом деле использует фильтр. Поскольку многие ответы были получены от уважаемых людей, я уверен, что я что-то упустил. Может ли кто-нибудь объяснить, что было бы не так с этим:

new_list = filter(lambda o: o.meetsCriteria(), myList)

Answer 4

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

В этом конкретном случае вам не нужно беспокоиться о размере объекта. При копировании списка используется понимание списка, или срез будет выполнять только поверхностное копирование (копирование ссылок на объекты, даже если этот термин не совсем подходит для Python). Но количество элементов в списке может иметь значение, потому что del is O (n). Могут быть и другие решения, такие как замена элемента на None или обычный объект Null или использование другой структуры данных, такой как набор или словарь, где стоимость удаления элемента намного ниже.

Answer 5

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

Во-первых, как этот мусор попал в список? Профилактика лучше лечения.

Во-вторых, сколько элементов в списке и какой процент, вероятно, потребуется удалить? Чем выше этот процент, тем выше вероятность создания нового списка.

Хорошо, если вы все еще хотите сделать это на месте, подумайте:

def list_cleanup_fail(alist, is_bad):
    i = 0
    for element in alist:
        print "i=%d alist=%r alist[i]=%d element=%d" % (i, alist, alist[i], element)
        if is_bad(element):
            del alist[i]
        i += 1

def list_cleanup_ok(alist, is_bad):
    for i in xrange(len(alist) - 1, -1, -1):
        print "i=%d alist=%r alist[i]=%d" % (i, alist, alist[i])
        if is_bad(alist[i]):
            del alist[i]

def is_not_mult_of_3(x):
    return x % 3 != 0

for func in (list_cleanup_fail, list_cleanup_ok):
    print
    print func.__name__
    mylist = range(11)
    func(mylist, is_not_mult_of_3)
    print "result", mylist

и вот вывод:

list_cleanup_fail
i=0 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=0 element=0
i=1 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=1 element=1
i=2 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=3 element=3
i=3 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=4 element=4
i=4 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=6 element=6
i=5 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=7 element=7
i=6 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=9 element=9
i=7 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=10 element=10
result [0, 2, 3, 5, 6, 8, 9]

list_cleanup_ok
i=10 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=10
i=9 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=9
i=8 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=8
i=7 alist=[0, 1, 2, 3, 4, 5, 6, 7, 9] alist[i]=7
i=6 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=6
i=5 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=5
i=4 alist=[0, 1, 2, 3, 4, 6, 9] alist[i]=4
i=3 alist=[0, 1, 2, 3, 6, 9] alist[i]=3
i=2 alist=[0, 1, 2, 3, 6, 9] alist[i]=2
i=1 alist=[0, 1, 3, 6, 9] alist[i]=1
i=0 alist=[0, 3, 6, 9] alist[i]=0
result [0, 3, 6, 9]

Answer 6

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

myList = [element for element in listOfElements if not element.meetsCriteria()]

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

myList = (element for element in listOfElements if not element.meetsCriteria())

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

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

Answer 7

Просто чтобы прояснить:

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1
    return listOfElements

myList = range(10000)
myList = listCleanup(listOfElements)

совпадает с

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1

myList = range(10000)
listCleanup(listOfElements)