等間隔に並んだ最長の部分配列

質問

100万個の整数をソートして、連続するペアの差が等しい最も長い部分列を見つけたい。例えば

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秒かかりましたが、RAMは20MBだけでした。もちろん、範囲がもっと大きければ、これはもっと悪くなります。 メモリ使用量が少ないので、a= [random.randint(0,100000) for r in xrange(200000)] でもテストできましたが、私が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方式をリニアな空間にすることができれば、明らかに勝者となるようです。

どのように解決するのですか？

更新しました。 ここで紹介した最初のアルゴリズムは Armin Rigoの2つ目の回答 の方がはるかにシンプルで効率的です。しかし、これらの方法には一つ欠点があります。100万個の整数の結果を見つけるのに何時間もかかるのです。そこで私は、入力される整数の範囲が限定されていると仮定した、さらに2つのバリエーション（この解答の後半を参照）を試してみました。このような制限を設けることで、より高速なアルゴリズムが可能になります。また、Armin Rigoのコードを最適化することも試みました。最後に私のベンチマーク結果をご覧ください。

O(N)メモリを使用したアルゴリズムのアイデアです。時間計算量はO(N ² log N)であるが、O(N)に減少する可能性がある。 ² ).

アルゴリズムは以下のデータ構造を使用します。

1. prev : (不完全な)部分配列の前の要素を指すインデックスの配列です。
2. hash : キー = 部分配列の連続するペアの差、値 = 他の2つのハッシュマップを持つハッシュマップ。これらの他のハッシュマップについて: key = 部分配列の開始/終了インデックス、value = (部分配列の長さ、部分配列の終了/開始インデックス)のペア。
3. pq に格納された部分配列のすべての可能な "difference" 値のための優先キューです。 prev と hash .

アルゴリズムです。

1. 初期化 prev インデックスを持つ i-1 . 更新 hash と pq で、このステップで見つかった全ての（不完全な）部分配列とその "差分"を登録することができます。
2. から最小の"difference"を取得（および削除）する。 pq . から対応するレコードを取得する。 hash から対応するレコードを取得し、第2レベルのハッシュマップの1つをスキャンする。このとき、与えられた "difference" を持つ全ての部分配列が完了する。もし第2レベルのハッシュマップにこれまで見つかったものより良い長さの部分配列があれば、最良の結果を更新する。
3. 配列の中で prev : 手順 2 で見つかった任意のシーケンスの各要素について、インデックスをデクリメントして hash を更新し、場合によっては pq . を更新している間 hash を更新する際に、長さ1の新しい部分列を追加する、既存の部分列を1つ増やす、既存の2つの部分列を結合する、などの操作を行うことができます。
4. 手順2で見つけたハッシュマップレコードを削除します。
5. ステップ #2 から続ける間 pq が空でない限り続けます。

このアルゴリズムでは、O(N)個の prev をそれぞれO(N)回更新します。そして、これらの更新のそれぞれは、新しい "差分" を pq . これらのことは、時間の複雑さが O(N ² log N)であることを意味します。 pq . これを O(N ² ) に減少させるために，より高度な優先度キュー実装を使用することができます．このページでは、その可能性をいくつか挙げています。 優先度キュー .

対応する 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氏による最初の方法と似ていますが、動的なデータ構造を一切使っていません。ソースデータには重複がないと仮定します。また、（コードをシンプルにするために）最小入力値が非負でゼロに近いと仮定します。

booleanの配列の代わりに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)])))

また、最速のアルゴリズムとして、以下のデータ（約10000個の整数）も使ってみました。

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