最长等距子序列

最长等距子序列

更新： Armin
Rigo的第二个答案
已废除了这里描述的第一个算法，该算法更简单，更有效。但是这两种方法都有一个缺点。他们需要许多小时才能找到一百万个整数的结果。因此，我尝试了另外两个变体（请参阅此答案的后半部分），其中假定输入整数的范围是有限的。这种限制允许更快的算法。我也尝试优化Armin
Rigo的代码。最后查看我的基准测试结果。

---

这是使用O（N）内存的算法思想。时间复杂度为O（N 2 log N），但可以降低为O（N 2）。

算法使用以下数据结构：

1. prev

   ：索引数组，指向（可能不完整）子序列的前一个元素。

2. hash

   ：具有key的哈希图=子序列中的连续对之间的差，而value =其他两个哈希图。对于这些其他哈希图：键=子序列的开始/结束索引，值=对（子序列长度，子序列的结束/开始索引）。

3. pq

   ：优先级队列，用于存储在

   prev

   和中的子序列的所有可能的“差异”值

   hash

   。

算法：

1. prev

   用索引初始化

   i-1

   。更新

   hash

   并

   pq

   注册在此步骤中发现的所有（不完整）子序列及其“差异”。
2. 从中获取（并删除）最小的“差异”

   pq

   。从

   hash

   第二级哈希图中获取相应的记录并进行扫描。此时，具有给定“差异”的所有子序列均已完成。如果第二级哈希图包含的子序列长度比迄今为止找到的更好，请更新最佳结果。
3. 在数组中

   prev

   ：对于在步骤＃2中找到的任何序列的每个元素，递减索引，并更新

   hash

   和可能

   pq

   。更新时

   hash

   ，我们可以执行以下 *** 作之一：添加新的长度为1的子序列，或将现有的子序列增加1，或合并两个现有的子序列。
4. 删除在步骤2中找到的哈希映射记录。

5. pq

   不为空时，从步骤2继续。

该算法

prev

每次更新O（N）次的O（N）个元素。这些更新中的每一个都可能需要为添加新的“差异”

pq

。如果我们使用的简单堆实现，所有这些都意味着O（N 2 log N）的时间复杂度

pq

。为了将其减少到O（N
2），我们可以使用更高级的优先级队列实现。此页面列出了一些可能性：优先队列。

请参阅Ideone上相应的Python代码。此代码不允许列表中有重复的元素。可以解决此问题，但无论如何还是要删除重复项（并找到重复项之外最长的子序列），这将是一个很好的优化。

和相同的代码经过一点优化。只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就会终止。

---

Armin
Rigo的代码简单而高效。但是在某些情况下，它会执行一些额外的计算，这些计算可以避免。只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就会终止：

def findLESS(A):  Aset = set(A)  lmax = 2  d = 1  minStep = 0  while (lmax - 1) * minStep <= A[-1] - A[0]:    minStep = A[-1] - A[0] + 1    for j, b in enumerate(A):      if j+d < len(A):        a = A[j+d]        step = a - b        minStep = min(minStep, step)        if a + step in Aset and b - step not in Aset:          c = a + step          count = 3          while c + step in Aset: c += step count += 1          if count > lmax: lmax = count    d += 1  return lmaxprint(findLESS([1, 4, 5, 7, 8, 12]))

---

如果源数据（M）中的整数范围较小，则可以使用O（M 2）时间和O（M）空间的简单算法：

def findLESS(src):  r = [False for i in range(src[-1]+1)]  for x in src:    r[x] = True  d = 1  best = 1  while best * d < len(r):    for s in range(d):      l = 0      for i in range(s, len(r), d):        if r[i]:          l += 1          best = max(best, l)        else:          l = 0    d += 1  return bestprint(findLESS([1, 4, 5, 7, 8, 12]))

它类似于Armin
Rigo的第一种方法，但是它不使用任何动态数据结构。我想源数据没有重复项。并且（为了使代码简单），我还假设最小输入值是非负的，并且接近零。

---

如果我们不是使用布尔数组，而是使用位集数据结构和按位运算来并行处理数据，则可能会改进以前的算法。下面显示的代码将位集实现为内置的Python整数。它具有相同的假设：没有重复项，最小输入值是非负值并且接近零。时间复杂度为O（M
2 * log L），其中L为最佳子序列的长度，空间复杂度为O（M）：

def findLESS(src):  r = 0  for x in src:    r |= 1 << x  d = 1  best = 1  while best * d < src[-1] + 1:    c = best    rr = r    while c & (c-1):      cc = c & -c      rr &= rr >> (cc * d)      c &= c-1    while c != 1:      c = c >> 1      rr &= rr >> (c * d)    rr &= rr >> d    while rr:      rr &= rr >> d      best += 1    d += 1  return best

---

基准测试：

输入数据（大约100000整数）通过以下方式生成：

random.seed(42)s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

对于最快的算法，我还使用了以下数据（大约1000000整数）：

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

所有结果以秒为单位显示时间：

Size:   100000   1000000Second answer by Armin Rigo:     634         ?By Armin Rigo, optimized:         64     >5000O(M^2) algorithm:      53      2940O(M^2*L) algorithm:     7       711