如何测量值列表的周期性（或频率）？

Question

假设我有一个值列表：[0, 10, 20, 10, 0, 10, 20, 10, 0, ...]显然有周期性。我们看到每5个条目就有一个循环。我想测量上面列表中的平均周期，或完成一个周期所需的平均条目数。这似乎类似于测量自相关，但我不知道从哪里开始获得某种“频率”或“周期性”的测量值，也就是一个周期完成的速度。

Answer 1

最小版本：

a=[0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20]

n=len(a)

# The idea is to compare the repeated subset of the array with the original array

# while keeping the sizes equal

periods = [i for i in range(2,n//2+1) if a[:i]*(n//i)==a[:n - n % i]]

print('Min period=',periods[0], '\n',a[:periods[0]])

输出：

Min period: 4 

 [0, 10, 20, 10]

for循环版本：

这是与 for-loop 相同的想法，只是为了更清楚：

a=[0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20]

n = len(a)

periods=[]

for i in range(2, n // 2 + 1): # cycle's max length = 1/2 of sequence 

  m = n // i 

  word = a[:i]

  repeated_word = [a[:i]*m][0]

  same_size_array = a[:len(repeated_word)]

  isCycle = repeated_word == same_size_array

  if isCycle:

    periods.append(i)

  print(

      '%s-char word\t' % i,word,

      '\nRepeated word\t',repeated_word,

      '\nSame size array\t',same_size_array,

      '\nEqual(a Cycle)?\t',isCycle

      ,'\n'

      )

  

period = periods[0] # shortest cycle

print('Min period:',period,'\n',a[:period])

输出（长版）：

2-char word  [0, 10] 

Repeated word    [0, 10, 0, 10, 0, 10, 0, 10, 0, 10] 

Same size array  [0, 10, 20, 10, 0, 10, 20, 10, 0, 10] 

Equal(a Cycle)?  False 

3-char word  [0, 10, 20] 

Repeated word    [0, 10, 20, 0, 10, 20, 0, 10, 20] 

Same size array  [0, 10, 20, 10, 0, 10, 20, 10, 0] 

Equal(a Cycle)?  False 

4-char word  [0, 10, 20, 10] 

Repeated word    [0, 10, 20, 10, 0, 10, 20, 10] 

Same size array  [0, 10, 20, 10, 0, 10, 20, 10] 

Equal(a Cycle)?  True 

5-char word  [0, 10, 20, 10, 0] 

Repeated word    [0, 10, 20, 10, 0, 0, 10, 20, 10, 0] 

Same size array  [0, 10, 20, 10, 0, 10, 20, 10, 0, 10] 

Equal(a Cycle)?  False 

Min period: 4 

 [0, 10, 20, 10]

Answer 2

启动一个空列表

interval = []

并使用递归函数，如下所示：

def check_for_interval(interval,list):

    ## step 1: add first list element into your interval

    interval.append(list[0])

    ## step 2: remove that element from your list

    list.pop(0)

    ## step 3: get the current content of your interval, plus the next

    ## element, and check if the concatenated content appears another time     

    ## in the source list.

    ## first, make sure you got only strings in your list, for join to work

    str_interval = []

    for y in interval:

      str_interval.append(str(y))

    ## attach the next element, which now is the first one of the list

    ## because you popped the "new" first one above

    str_interval.append(str(list[0]))

    ## next, concatenate the list content as string, like so:

    current_interval = ",".join(str_interval)

    ## now, transform the current remaining list (except the "new" first

    ## element cause added in your test string above) into a string of the 

    ## exact same structure (elements separated by commas)

    str_test = []

    list_test = list[1:]

    for z in list_test:

      str_test.append(str(z))

    ## next,concatenate the list content as string, like so:

    remaining_elements = ",".join(str_test)

    ## finally, check if the current_interval is present inside the

    ## remaining_elements. If yes

    if remaining_elements.find(current_interval) != -1:

        ## check if the amount of remaining elements is equal to the amount

        ## of elements constituting the interval -1 at the moment, OR if the

        ## current_interval is found in the remaining elements, its

        ## starting index is equal to 0, and the len of str_test is a pair

        ## entire multiple of str_interval

        check_list_test = remaining_elements.split(",")

        check_list_interval = current_interval.split(",")

        if (len(str_interval) == len(str_test)) or (remaining_elements.find(current_interval) == 0 and len(str_test) % len(str_interval) == 0 and (len(str_test) / len(str_interval)) % 2 == 0 and (len(check_list_test) / len(check_list_interval)) * check_list_interval == check_list_test):

            ## If yes, attach the "new" first element of the list to the interval

            ## (that last element was included in str_interval, but is not yet

            ## present in interval)

            interval.append(list[0])

            ## and print the output

            print("your interval is: " + str(interval))

        else:

            ## otherwise, call the function recursively

            check_for_interval(interval,list)

    else:

        ## when the current interval is not found in the remaining elements,

        ## and the source list has been fully iterated (str_test's length

        ## == 0), this also means that we've found our interval

        if len(str_test) == 0:

            ## add the last list element into the interval

            interval.append(list[0])

            print("your interval is: " + str(interval))

        else:

            ## In all other cases, again call the function recursively

            check_for_interval(interval,list)

仅优化代码，无注释

def int_to_str_list(source):

    new_str_list = []

    for z in source:

        new_str_list.append(str(z))

    return new_str_list

def check_for_interval(interval,list):

    interval.append(list[0])

    list.pop(0)

    str_interval = int_to_str_list(interval)

    str_interval.append(str(list[0]))

    current_interval = ",".join(str_interval)

    str_test = int_to_str_list(list[1:])

    remaining_elements = ",".join(str_test)

    str_exam = remaining_elements.find(current_interval)

    if str_exam != -1:

        interval_size = len(str_interval)

        remaining_size = len(str_test)

        rem_div_inter = remaining_size / interval_size

        if (interval_size == remaining_size) or (str_exam == 0 and remaining_size % interval_size == 0 and rem_div_inter % 2 == 0 and rem_div_inter * str_interval == str_test):

            interval.append(list[0])

            print("your interval is: " + str(interval))

        else:

            check_for_interval(interval,list)

    else:

        if len(str_test) == 0 :

            interval.append(list[0])

            print("your interval is: " + str(interval))

        else:

            check_for_interval(interval,list)

做你想做的，只需在启动 [] 后运行你的函数

interval = []

check_for_interval(interval,list)

应该适用于几乎任何情况，将间隔作为输出提供给您。

Answer 3

“纯”平均周期必然等于列表的长度除以元素的出现次数。

我们还可以考虑第一次和最后一次出现，并在我们的计算中使用它，尽管这可能会以您不希望的方式影响您的计算：

from collections import Counter

values = [0, 10, 20, 10, 0, 10, 20, 10, 0]

counts = Counter(values)

periodicities = dict()

r_values = values[::-1]

for k, v in counts.items():

    print(r_values.index(k), values.index(k))

    periodicities[k] = (len(values) - r_values.index(k) - values.index(k) + 1) / v

print(periodicities)

结果：

{

  0: 3.3333333333333335,

  10: 2.0,

  20: 3.0

}

Answer 4

这是解决此问题的一种方法。基本上，您从 2 迭代到len(lst)//2 + 1并检查前 n 个元素是否与接下来的 n 个元素匹配，如果为真则返回 n。如果未找到匹配项，则返回 len(lst)

def get_periodicity(lst):

    t = len(lst)

    for n in range(2, t//2 + 1):

        for p in range(1, t//n):

            if lst[:n] != lst[n*p:n*p+n]:

                break

        else:

            rem = t%n

            if not rem or lst[-rem:] == lst[:rem]:

                return n

    else:

        return t

测试

>>> get_periodicity([0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20])

4

>>> get_periodicity([1,1,2,1,1,2,1,1,2,1,1,2])

3

>>> get_periodicity([1,1,2,1,1,2,1,1,2,1,1,2,3])

13

Answer 5

注意：我假设您指的是精确的周期性而不是自相关的某种度量。例如，[1, 5, 8, 1, 5, 8.0000000001]周期为 6 而不是 3。

这绝不是最优的，但在紧要关头，任何人都可以暴力破解出如下所示的解决方案。

def period(L):

    n = len(L)

    for i in range(1, n):

        if n%i:

            # save a little work if `i` isn't a factor of `n`

            continue

        if all(L[k:k+i]==L[:i] for k in range(0, n, i)):

            # `L` is just `L[:i]*x` for some `x`, and since `i` is

            # increasing this must be the smallest `i` where that

            # is true

            return i

    

    # if no factor suffices, the smallest generator is the entire list

    return n

通过多一点努力，我们可以获得线性性能而不是二次性能。进一步优化它留给不是我的人作为练习。

def period(L):

    if not L:

        return 0

    

    guess = 1

    for i, x in enumerate(L[1:], 1):

        if x != L[i%guess]:

            """

            We know for certain the period is not `guess`. Moreover, if we've

            gotten this far we've ruled out every option less than `guess`.

            Additionally, no multiple of `guess` suffices because the fact

            that `L` consists of repetitions of width `guess` up till now means

            that `i%(t*guess)!=x` for any `t` so that `t*guess<i`. Interestingly,

            that's the precisely the observation required to conclude

            `guess >= i+1`; there is some positive integer multiple of `guess`

            so that `L[:i+1]` consists of a copy of that width and some number

            of elements that are identical to that copy up to and excluding `x`.

            Since `L[:i+1]` has that structure, no width between that multiple

            of `guess` and `i` can generate `L`. Hence, the answer is at least

            `i+1`.

            """

            guess = i+1

            while len(L)%guess:

                """

                Additionally, the answer must be a factor of `len(L)`. This

                might superficially look quadratic because of the loop-in-a

                -loop aspect to it, but since `1<=guess<=len(L)` and `guess`

                is always increasing we can't possibly run this code more

                than some linear number of times.

                """

                guess += 1

            """

            If we've gotten this far, `guess` is a factor of `L`, and it is

            exactly as wide as all the elements we've seen so far. If we

            continue iterating through `L` and find that it is just a bunch

            of copies of this initial segment then we'll be done. Otherwise,

            we'll find ourselves in this same if-statement and reset our

            `guess` again.

            """

    return guess

如果您想要所有周期，那么这些只是最小周期的每一个倍数，也是总长度的因素。假设你有办法计算一个正整数的质因数分解或所有正因子（包括 1 和整数本身），下面的例程可以得到这些。实际上找到整数的因子可能超出范围并且在其他地方得到了很好的回答。

def all_periods(minimum_period, collection_size):

    p, n = minimum_period, collection_size

    if p==0:

        yield = 0

        return

    for f in positive_factors(n / p):

        yield f * p