Python列表操作的性能问题

Question

我正在学习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)

我很高兴这最后一个看起来如何,但表现是可怕的.当我运行第一个范围(1,1000000)时,它需要10秒,而第二个需要年龄(几分钟).为什么我能做些什么呢？

(如果读到这个,你想到了一个更好的方法来实现最初的目标,我当然会有兴趣听到它!)

Answer 1

之所以你的第二个代码慢得多的是,pop在列表的操作是很慢的(其运行时间是成正比的列表,而不是被固定的长度)解释在这里,除非你从列表的末尾弹出一个项目.

这是一个与您的第一个代码具有相似性能的代码(在我的机器上略胜一筹),但看起来更惯用.特别是,我使用的是列表中理解,而不是一系列的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)

一个非常快的实现:

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的筛子.