Уменьшение сложности следующего кода

Что я хотел сделать, это искать в списке и удалять значение.Уменьшение сложности следующего кода

Так что я написал следующий код

for x in range(10): 
    if x in list1: 
     list1.remove(x)

ли эта функция порядка ~ (п^2), так как сначала ищет значение, а затем удаляет и помещает остальные значения в обратном направлении ??

также есть способ превратить это в порядке п с помощью Try/за исключением

try: 
    for x in range(10): 
    list1.remove(x) 
except ValueError: 
    # make it go back to next iteration

источник

2010-12-12 Anonymous

Во втором случае, почему бы не попробовать/кроме IN for loop? – extraneon

Не связано с вопросом, но вам лучше не использовать встроенное имя для имени переменной. Python позволяет вам это делать, но это может иметь непреднамеренные последствия, если вы не знаете точно, что делаете. –

@Tim: Очень верно, хотя это может быть хуже (с динамическим охватом - eeeevil);) – delnan

Это звучит как работа для filter():

>>> filter(lambda x: not x in (4, 5, 7), xrange(10)) 
[0, 1, 2, 3, 6, 8, 9]

Update: еще один пример, где я построить список с помощью list comprehension:

>>> filter(lambda x: not x[0] in (4, 5, 7), [[a] for a in xrange(10)]) 
[[0], [1], [2], [3], [6], [8], [9]]

источник

2010-12-12 12:06:09

Эй, а как же, если мой x находится во вложенном списке, например a = [[1], [2], [2]], и я хочу сделать то же самое, то есть вычислить все эти значения LIST, не входящие в a, вместо работы xrange? – 2010-12-12 12:11:04

Это создает новый список, но проверяет каждый элемент в существующем (или итераторе в примерах) на каждый элемент в другой последовательности тех, которые нужно удалить. Это может быть немного быстрее, чем 'for', потому что он использует' filter() ', но, вероятно, это не так уж и более эффективно. – martineau

Я полностью осознаю его свойства, ведь последний является еще одним примером. –

Использование:

L = [x for x in L if x not in removal_list]

removal_list может быть любой контейнер, но если вы используете набор() или frozenset() вы достигнете O (n) (с n = len (L)).

источник

2010-12-12 12:05:38

+1, но '/(.*) remove_list \\]/remove_set = установить \\ (remove_list \\) \ n \ 1 remove_set \\] /'. Почему бы вам не хотеть получить от «O (n ** 2)» до «O (n)» с таким простым изменением? – delnan

'L = [x for in x in L, если x not in remove_list]' является недопустимым синтаксисом. – martineau

@martineau Это правильно, когда я тестировал его ..... учитывая, что remove_list - это список – 2010-12-12 16:59:41

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

Во-вторых, если Python похож на Java, тогда существует правило для хорошего кода. Не используйте исключения для потока процессов. Это исключает ваше второе предложение. Также вполне вероятно, что он будет работать плохо. замена

источник

2010-12-12 12:09:27 drekka

Почему вы говорите, что это будет плохо? с точки зрения накладных расходов ??? – 2010-12-12 12:12:06

@ Derek: в Python максим «лучше попросить прощения, чем разрешение». Второй пример (с помощью 'try' внутри цикла) является разумным стилем Python и будет достаточно эффективным. –

@Derek вы могли бы прояснить «Не использовать исключения для потока процессов» для Java? Зачем? – khachik

фрагмента:

a[:] = (l for l in a if l not in set(list_of_removable))

источник

2010-12-12 12:25:43 kevpie

Как Джованни Бахо предлагает, список понимание круто, но если вы будете использовать результат только один раз, генераторы еще лучше:

l = [1,23,2,24,3,26,1] 
(x for x in l if x not in xrange(10))

xrange() является генератор также и быстрее, чем range() Если вы хотите использовать результат более одного раза, я бы воспользовался:

[x for x in l if x not in xrange(10)]

источник

2010-12-12 12:38:51

Чтобы ответить на исходный вопрос: не обойти тот факт, что вам придется сравнивать каждый элемент списка-к-remove-elements от каждого элемента элементов, содержащих список-съемные. Таким образом, в этом смысле каждая версия этого кода O (N^2) (при условии, что мы можем иметь произвольно много элементов в каждом списке). Вы можете скрыть циклы с помощью различных конструкций (и во многих случаях это будет быстрее, потому что цикл может выполняться «внутренне» в коде C интерпретатора, а не путем интерпретации большего байт-кода), но петли все еще остаются там (и помните, что постоянные факторы игнорируются анализом больших O).

источник

2010-12-12 17:44:13

Уменьшение сложности следующего кода

ответ

Смежные вопросы