Python列表操作的性能问题 - python

我正在学习python，并且有一个运动，我有一个整数列表，必须保留两个数字中的一个，然后是2上3，然后是3上4 ...然后最后看剩下的内容。
例如:
[1,2,3,4,5,6,7,8,9]-> [1,3,5,7,9]-> [1,3,7,9]-> [1 ，3,7]

我的第一次尝试，只是看输出(当心，令人震惊的肮脏代码):

n=input()
list2=list(range(1,int(n))) 
list1=[]
step=2
while list1 != list2 :
    countSteps=1
    position=0
    list1=list2
    list2=[]
    lenlist1=len(list1)
    while position < lenlist1 :
      while countSteps != step and position < lenlist1 :
        list2.append(list1[position])
        countSteps+=1
        position+=1
      position+=1
      countSteps = 1
    step+=1
print(list2)

那里的“想法”是使用两个列表，然后将2/3/4 ...上的1/2/3 ...从一个添加到另一个。在我看来(也许我错了)，从内存的角度来看这是一个错误的选择，因此我提出了以下建议:

n=input()
list1=list(range(1,int(n)))
lenCached=0
step=1
while lenCached!=len(list1) :
  lenCached = len(list1)
  position = step
  while position < len(list1):
    list1.pop(position)
    position+=step
  step+=1
print(list1)

我对最后一个外观看起来很满意，但性能太差了。当我使用range(1,1000000)运行第一个时，它需要10s，而第二个则需要时长(几分钟)。
为什么并且我可以对此做些什么？

(如果阅读此书，您会想到一种更好的方法来实现最初的目标，我当然会对听到它感兴趣!)

python大神给出的解决方案

您的第二个代码要慢得多的原因是列表上的pop操作非常慢(其运行时间与列表的长度成比例，而不是常数)，如here所述，除非您从列表的末尾。

这是一个代码，其性能与您的第一个代码相似(在我的机器上稍好一些)，但看起来更加惯用。特别是，我使用的是list comprehension而不是您用来从append构造l2的l1系列:

n=input()
l = list(range(1, n))
step = 2
while step <= len(l):
    l = [num for ind, num in enumerate(l) if (ind + 1) % step != 0]
    step += 1
print(l)

一个更快的numpy实现:

import numpy as np

n = input()
a = np.arange(1, n)
step = 2
while step <= len(a):
    mask = np.ones(len(a), dtype=bool)
    ind = np.arange(step-1,len(a), step)
    mask[ind] = False
    a = a[mask]
    step += 1
print(a)

顺便说一句，此过程称为Flavius Josephus's sieve。