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]

РЕДАКТИРОВАТЬ: благодаря потрясающему вкладу Марка Дикинсона, Стива Джессопа и Гнибблера, яполучил следующее, что намного быстрее, чем мой исходный код (и был успешно отправлен на 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

Эта серия называется Неверные цифры

__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

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

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

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

Вы также можете найти лучшее условие завершения для цикла while: например, если первый оставшийся элемент в сите - 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 3

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

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

• Вернуть n й элемент
• Стереть n й элемент

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

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

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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