Python优化Van序列

Question

我正在为平台编码游戏在python上编写代码。代码是关于Van Eck的序列的，我通过了66%的“测试”。一切都如期而至，问题是这个过程没有时间允许。是的，代码很慢。我不是python作者，我想问您，您是否可以对代码进行任何优化，以及您的方法是否很复杂(复杂，意味着您是否将使用向量化数据)，而不只是交换if (因为这很容易理解)来为您的选择提供一个很好的解释。这是我的问题代码

import sys
import math   

def LastSeen(array):

    startingIndex = 0 
    lastIndex = len(array) - 1 
    closestNum = 0    
    for startingIndex in range(len(array)-1,-1,-1):  
            if array[lastIndex] == array[startingIndex] and startingIndex != lastIndex :
                    closestNum = abs(startingIndex - lastIndex)
                    break

    array.append(closestNum)
    return closestNum


def calculateEck(elementFirst,numSeq):

    number = numSeq
    first = elementFirst
    result = 0
    sequence.append(first)
    sequence.append(0)
    number -= 2
    while number != 0 :
        result = LastSeen(sequence)
        number -= 1
    print(result)


firstElement = int(input())

numSequence = int(input())

sequence = []

calculateEck(firstElement,numSequence)

Answer 1

这是我没有字典的代码。van_eck包含最后的序列。通常，我会使用dict来跟踪每个元素的最后位置，以保存运行时。否则，您需要对列表进行迭代，以找到可能需要很长时间的最后一次出现。

我只是简单地初始化了一个足够大小的数组，并将其作为dict使用，而不是dict。要确定它的大小，请记住，van序列中的所有数字要么为0，要么告诉您上次发生的距离有多远。所以序列的第一个n数永远不会大于n。因此，您只需给数组一个长度，该长度等于您希望在最后得到的序列的大小。

-1意味着元素之前并不存在。

DIGITS = 100

van_eck = [0]
last_pos = [0] + [-1] * DIGITS

for i in range(DIGITS):
    current_element = van_eck[i]
    if last_pos[current_element] == -1:
        van_eck.append(0)
    else:
        van_eck.append(i - last_pos[current_element])
    last_pos[current_element] = i