最长等距子序列

Question

我按排序顺序有一百万个整数,我想找到连续对之间差异相等的最长子序列.例如

1, 4, 5, 7, 8, 12

有一个子序列

   4,       8, 12

我天真的方法是贪婪的,只是检查你可以从每个点扩展一个子序列的距离.这O(n²)看起来每点需要时间.

有没有更快的方法来解决这个问题？

更新.我会尽快测试答案中给出的代码(谢谢).但是很明显,使用n ^ 2内存将无法正常工作.到目前为止,没有代码以输入结束[random.randint(0,100000) for r in xrange(200000)].

计时. 我在32位系统上测试了以下输入数据.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()

• ZelluX的动态编程方法使用1.6G的RAM,需要2分14秒.使用pypy只需9秒!但是,它在大输入时因内存错误而崩溃.
• Armin的O(nd)时间方法用pypy花了9秒,但只有20MB的RAM.当然,如果范围更大,情况会更糟.低内存使用率意味着我也可以用一个= [random.randint(0,100000)来测试它,对于x inrange(200000)中的r,但是在我用pypy给它的几分钟内它没有完成.

为了能够测试Kluev的方法,我重申了

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

粗略地列出一个长度列表20000.与pypy的所有时间

• ZelluX,9秒
• Kluev,20秒
• 阿明,52秒

似乎如果ZelluX方法可以成为线性空间,它将是明显的赢家.

Answer 1

O(n*m)通过适应您的需求,我们可以及时获得非常少的内存需求的解决方案.这n是给定输入数字序列中的项目数,并且m是范围,即最高数字减去最低数字.

调用A所有输入数字的序列(并使用预先计算set()的答案在恒定时间内问题"是A中的这个数字？").调用d 我们正在寻找的子序列的步骤(这个子序列的两个数字之间的差异).对于d的每个可能值,对所有输入数进行以下线性扫描:对于A中每个数字n的递增顺序,如果尚未看到数字,则在A中查找从n开始的序列长度步骤d.然后标记已经看到的那个序列中的所有项目,这样我们就可以避免再次从它们中搜索相同的d.因此,复杂性仅O(n)适用于d的每个值.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

更新:

• 如果你只对相对较小的d值感兴趣,那么这个解决方案可能就足够了; 例如,如果获得最佳结果d <= 1000就足够了.然后复杂性下降到O(n*1000).这使得算法具有近似性,但实际上可以运行n=1000000.(使用CPython在400-500秒测量,使用PyPy测量80-90秒,随机数字在0到10'000'000之间.)

• 如果您仍想搜索整个范围,并且如果常见情况是存在长序列,则只要d太大而无法找到更长的序列,就会停止显着的改进.

Answer 2

更新:我发现了一个关于这个问题的论文,你可以在这里下载.

这是一个基于动态编程的解决方案.它需要O(n ^ 2)时间复杂度和O(n ^ 2)空间复杂度,并且不使用散列.

我们假设所有数字都a按升序保存在数组中,并n保存其长度.2D数组l[i][j]定义以a[i]和结束的最长等间隔子序列的长度a[j],并且l[j][k]= = l[i][j]+ 1 if a[j]- a[i]= a[k]- a[j](i <j <k).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

Answer 3

更新:这里描述的第一个算法被Armin Rigo的第二个答案淘汰,这个答案更简单,更有效.但这两种方法都有一个缺点.他们需要很多小时才能找到100万个整数的结果.所以我尝试了另外两个变体(参见本答案的后半部分),其中输入整数的范围被假定为有限.这种限制允许更快的算法.我还尝试优化Armin Rigo的代码.最后查看我的基准测试结果.

这是使用O(N)存储器的算法的概念.时间复杂度为O(N ² log N),但可以降低到O(N ²).

算法使用以下数据结构:

1. prev:指向前一个(可能不完整的)子序列元素的索引数组.
2. hash:hashmap with key =子序列中连续对之间的差异,value =两个其他散列图.对于这些其他散列图: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. 从第2步继续,而pq不是空的.

该算法分别更新O(N)个O(N)个元素prev.并且每个更新可能需要添加新的"差异" pq.如果我们使用简单的堆实现,所有这些意味着O(N ² log N)的时间复杂度pq.要将其减少到O(N ²),我们可能会使用更高级的优先级队列实现.此页面列出了一些可能性:优先级队列.

请参阅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 lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

如果源数据(M)中的整数范围很小,则可以使用O(M ²)时间和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 best


print(findLESS([1, 4, 5, 7, 8, 12]))

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

如果不使用布尔数组,我们使用比特集数据结构和按位运算来并行处理数据,则可以改进先前的算法.下面显示的代码将bitset实现为内置的Python整数.它具有相同的假设:没有重复,最小输入值是非负的并且接近于零.时间复杂度为O(M ²*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   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711