多くの整数間の対の距離の分布

Question

私たちは1とNとの間にM個の固有の整数を持ちます。実際の生活では、Nは数百万であり、MはN/10とN/3の間です。私は、M個の整数間の対の距離の分布を計算する必要があります。

問題のブルートフォースの複雑さはM^2ですが、出力はN個の数字に過ぎません。だから自然な問題は、より速いアルゴリズムがあるかどうかです。私たちの目的にはN * sqrt（M）のアルゴリズムでも十分であるはずです。

この問題は、次の問題のサブセットとして発生しました。私たちは、数百万から数百万の要素で構成される、大きな仮想正方形の対称行列を持っています。行列のいくつかの行と列はマスクされています。行列の各対角にどれだけのマスクされた要素があるかを調べる必要があります。各対角線と交差するマスクされたビンの数を簡単に計算できます。しかし、多くの場合、マスクされた行と列は対角線上で右に交差し、したがって1つのビンのみがマスクされます。これらを二重にカウントしないようにするには、マスクされた列の間に距離のペアごとの分布が必要です。

Answer 1

これは、フーリエ変換を使用してO（NlogN）で実行できます。

考えられるのは、M個の整数のヒストグラムH（x）を計算するという考え方です。ここでH（x）は入力xの値の数です（Mがすべての場合は0または1になります）。明白ですが、これは必須ではありません）。

あなたが計算したいのはA（d）です。ここで、A（d）は、正確にd離れた整数の組の数として定義されます。

この

は（d）のように計算することができる=合計（すべてのxに対してH（X）* H（X + D））を

関数このタイプのコンボリューションと呼ばれ、効率的にとることによって計算することができます。フーリエ変換、それ自体の出力の乗算、および逆変換の計算を含む。適切にパッドするように注意する必要があります。たとえば、questionを参照してください。

Pythonを使用している場合は、この操作を行うためにscipy.signal.fftconvolveに電話すると特に簡単です。