許多整數之間的成對距離的分佈

Question

我們在1和N之間有M個唯一整數。在現實生活中，N是幾百萬，M是在N/10和N/3之間。我需要計算M個整數之間的成對距離分佈。

問題的蠻力複雜度是M^2，但輸出只是N個數字。所以自然的問題是是否有更快的算法。即使像N * sqrt（M）那樣快的算法也足以滿足我們的需求。

該問題作爲以下問題的一個子集出現。我們有一個大的虛擬平方對稱矩陣，幾百萬到幾百萬個元素。矩陣的一些行和列被屏蔽掉。我們需要找出矩陣的每個對角線中有多少蒙版元素。人們可以很容易地計算出每個對角線有多少個被遮蓋的區域相交。但是經常被遮住的行和列將在對角線上正好相交，從而僅掩蓋一個箱。爲避免重複計算這些數據，我們需要成對的分隔列之間的距離。

Answer 1

您可以使用傅里葉變換在O（NlogN）中執行此操作。

這個想法是，你首先計算你的M個整數的直方圖H（x），其中H（x）是值x在你的輸入中出現的次數（如果所有M都是0或1不同 - 但這不是必需的）。

然後你想要計算的是A（d），其中A（d）定義爲完全分開的整數對數。

這可以被計算爲A（d）=總和（H（X）* H（X + d）對於所有x）

這種類型的功能被稱爲卷積並且可以通過利用被有效計算傅立葉變換，將輸出與自身相乘，然後計算逆變換。需要注意適當填充，例如參見question。

如果您使用Python，這很容易，因爲您可以撥打scipy.signal.fftconvolve來執行此操作。