Python: ускорить удаление каждого n-го элемента из списка

Question

Я пытаюсь решить , и хотя решение (см. Код ниже) работает правильно, это слишком медленно для успешной подачи.

• Любые указатели, как это сделать быстрее (удаление каждого n-го элемента из списка)?
• Или предложения по лучшему алгоритму для вычисления того же самого; Кажется, я не могу думать ни о чем еще, кроме грубой силы на данный момент ...

В принципе, задача состоит в том:

 
GIVEN: 
L = [2,3,4,5,6,7,8,9,10,11,........] 
1. Take the first remaining item in list L (in the general case 'n'). Move it to 
    the 'lucky number list'. Then drop every 'n-th' item from the list. 
2. Repeat 1 

TASK: 
Calculate the n-th number from the 'lucky number list' (1 <= n <= 3000) 

Мой исходный код (он вычислил первые повезло 3000 числа в около секунды на моей машине - к сожалению, слишком медленный):

""" 
SPOJ Problem Set (classical) 1798. Assistance Required 
URL: http://www.spoj.pl/problems/ASSIST/ 
""" 

sieve = range(3, 33900, 2) 
luckynumbers = [2] 

while True: 
    wanted_n = input() 
    if wanted_n == 0: 
     break 

    while len(luckynumbers) < wanted_n: 
     item = sieve[0] 
     luckynumbers.append(item) 
     items_to_delete = set(sieve[::item]) 
     sieve = filter(lambda x: x not in items_to_delete, sieve) 
    print luckynumbers[wanted_n-1] 

EDIT: благодаря потрясающий вклад Марка Дикинсон, Steve Джессоп и gnibbler, I получили в следующем, что довольно много быстрее, чем мой исходный код (и успешно получил представленный на http://www.spoj.pl с 0,58 секунд!) ...

sieve = range(3, 33810, 2) 
luckynumbers = [2] 

while len(luckynumbers) < 3000: 
    if len(sieve) < sieve[0]: 
     luckynumbers.extend(sieve) 
     break 
    luckynumbers.append(sieve[0]) 
    del sieve[::sieve[0]] 

while True: 
    wanted_n = input() 
    if wanted_n == 0: 
     break 
    else: 
     print luckynumbers[wanted_n-1] 

Answer 1

Эта серия называется ludic numbers

__delslice__ должен быть быстрее, чем __setslice__ + filter

>>> L=[2,3,4,5,6,7,8,9,10,11,12] 
>>> lucky=[] 
>>> lucky.append(L[0]) 
>>> del L[::L[0]] 
>>> L 
[3, 5, 7, 9, 11] 
>>> lucky.append(L[0]) 
>>> del L[::L[0]] 
>>> L 
[5, 7, 11] 

Таким образом, цикл становится.

while len(luckynumbers) < 3000: 
    item = sieve[0] 
    luckynumbers.append(item) 
    del sieve[::item] 

который работает меньше, чем 0,1 второй

Answer 2

Вы лучше использовать массив и обнуления каждый N-й элемент, использующий эту стратегию; после того, как вы сделаете это несколько раз подряд, обновления начнут становиться сложными, поэтому вы захотите переформатировать массив. Это должно улучшить скорость, по крайней мере, в 10 раз. Вам нужно намного лучше этого?

Answer 3

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

sieve[::item] = [0]*-(-len(sieve)//item) 
sieve = filter(None, sieve) 

Редактировать: гораздо лучше просто использовать del sieve[::item]; см. решение гниблера.

Вы могли бы также быть в состоянии найти лучшее условие завершения для цикла в то время как: например, если первый оставшийся элемент в сите i то первые i элементов сита станут следующими i счастливых числами; поэтому, если len(luckynumbers) + sieve[0] >= wanted_n вы уже должны были вычислить нужный вам номер - вам просто нужно выяснить, где в sieve это так, что вы можете его извлечь.

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

while len(luckynumbers) + sieve[0] < wanted_n: 
    item = sieve[0] 
    luckynumbers.append(item) 
    sieve[::item] = [0]*-(-len(sieve)//item) 
    sieve = filter(None, sieve) 
print (luckynumbers + sieve)[wanted_n-1] 

Answer 4

объяснение о том, как решить эту проблему, можно найти here. (Проблема, с которой я связываюсь, запрашивает больше, но основной шаг в этой проблеме такой же, как тот, который вы пытаетесь решить.) На сайте, на котором я связан, также содержится примерное решение на C++.

Набор чисел может быть представлено в виде двоичного дерева, который поддерживает следующие операции:

• вернуть n й элемент
• стереть n й элемент

Эти операции могут быть реализована для запуска в O(log n) времени, где n - это количество узлов в дереве.

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

Каждый узлу в дереве необходима следующую информация:

• указатели на левый и правые дети
• Сколько элементов находятся в левых и правых поддеревах

С таким структура на месте, решение остальной части проблемы должно быть довольно простым.

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

Java-реализация вышеуказанного алгоритма принимается через 0,68 секунды на связанном вами веб-сайте.

(Извините за не предоставление какой-либо Python конкретной помощи, но, надеюсь, алгоритм, описанный выше, будет достаточно быстро.)

Answer 5

Почему бы не просто создать новый список?

L = [x for (i, x) in enumerate(L) if i % n]