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

Я выполняю критическую работу с 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() 

Благодаря-

Джонатан

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. Хранение данных на диск, например, в базе данных.

В 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()] 

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

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

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

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

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

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

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

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

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

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

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

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

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

Хорошо, если вы все еще хотите сделать это in-situ, созерцайте это:

 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] 

Просто быть чистым:

 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) 

?