一尘不染

在Mathematica中查找(重复)列表周期的最佳方法是什么?

algorithm

在重复列表中找到期间的最佳方法是什么?

例如:

a = {4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2}

已重复{4, 5, 1, 2, 3},其余部分{4, 5, 1, 2}匹配,但不完整。

该算法应足够快以处理更长的情况,如下所示:

b = RandomInteger[10000, {100}];
a = Join[b, b, b, b, Take[b, 27]]

$Failed如果没有上述重复模式,则算法应返回。


阅读 334

收藏
2020-07-28

共1个答案

一尘不染

请查看注释,以及在代码中穿插的注释,以了解其工作原理。

(* True if a has period p *)
testPeriod[p_, a_] := Drop[a, p] === Drop[a, -p]

(* are all the list elements the same? *)
homogeneousQ[list_List] := Length@Tally[list] === 1
homogeneousQ[{}] := Throw[$Failed] (* yes, it's ugly to put this here ... *)

(* auxiliary for findPeriodOfFirstElement[] *)
reduce[a_] := Differences@Flatten@Position[a, First[a], {1}]

(* the first element occurs every ?th position ? *)
findPeriodOfFirstElement[a_] := Module[{nl},
  nl = NestWhileList[reduce, reduce[a], ! homogeneousQ[#] &];
  Fold[Total@Take[#2, #1] &, 1, Reverse[nl]]
  ]

(* the period must be a multiple of the period of the first element *)
period[a_] := Catch@With[{fp = findPeriodOfFirstElement[a]},
   Do[
    If[testPeriod[p, a], Return[p]],
    {p, fp, Quotient[Length[a], 2], fp}
    ]
   ]

请询问是否findPeriodOfFirstElement[]不清楚。我独立进行此操作(出于娱乐目的!),但是现在我看到该原理与Verbeia的解决方案相同,只是Brett指出的问题已解决。

我正在测试

b = RandomInteger[100, {1000}];
a = Flatten[{ConstantArray[b, 1000], Take[b, 27]}];

(请注意低整数值:同一时期内会有很多重复元素*)


编辑: 根据下面的[列昂尼德(eonid)的评论,通过使用专门为整数列表编译的自定义位置函数,可以再提高2-3倍的速度(在我的机器上约为2.4倍):

(* Leonid's reduce[] *)

myPosition = Compile[
  {{lst, _Integer, 1}, {val, _Integer}}, 
  Module[{pos = Table[0, {Length[lst]}], i = 1, ctr = 0}, 
    For[i = 1, i <= Length[lst], i++, 
      If[lst[[i]] == val, pos[[++ctr]] = i]
    ]; 
    Take[pos, ctr]
  ], 
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
]

reduce[a_] := Differences@myPosition[a, First[a]]

编译可以testPeriod在快速测试中进一步提高〜20%的速度,但是我相信这将取决于输入数据:

Clear[testPeriod]
testPeriod = 
 Compile[{{p, _Integer}, {a, _Integer, 1}}, 
  Drop[a, p] === Drop[a, -p]]
2020-07-28