如何根據點列表高效地計算間隔列表？

所以我有間隔的列表，讓我們真正的線說，如何根據點列表高效地計算間隔列表？

let intervals = [(1, 12), (2, 5), (3, 24), (7, 8)]

需要注意的是，因爲我將它們存儲爲成對我只用括號，間隔實際上是包容性（關閉）。

而且我點的列表，

let points = [13, 2, 7, 3, 14]

我試圖計算落入每個間隔點的數量，這應該是一個[Integer]有長度length intervals，

counts == [3, 2, 4, 1]

現在問題是在現實中intervals和points都是真的是長，所以使用迭代算法，需要O(length intervals * length points)會採取預測呃。因此我考慮使用某種分段樹來製作O(log (length intervals) * length points)。目前我在看包SegmentTree。然而，我有限的Haskell知識不足以讓我想出一個完整的解決方案。

我明白，如果目標是計算覆蓋每一個點，然後間隔的號碼，然後解決方法是直截了當：

import qualified Data.SegmentTree as S 
map (S.countingQuery $ S.fromList intervals) points

但我不能想辦法做相反。對我來說，爲了有效地做到這一點，必須使用可變數據結構，而這只是打開一個潘多拉魔盒。

什麼是解決方案？

來源

2015-09-15 trVoldemort

如果您可以先對點列表進行排序，您可以快速完成：對於每個區間，在其下限和上限的點列表中找到索引，然後減去。這就出現了類似於'O（log（nPoints）* max（nPoints，nRanges））'的情況，這有點更好。線性時間很難想象，但也許我錯過了一個聰明的解決方案。 – amalloy

我猜想有效的碰撞檢測算法的研究將在這裏相關。但是你應該說明你實際知道你的點和間隔的分佈情況：如果終點是在實際的某個區間內均勻分佈的，那麼我們可以說出重疊區間的概率。相反，如果我們說他們是隨機分佈在實際線上的，那麼......我想這可能是不合適的，或者我們得到的重疊概率爲0. – jberryman

考慮我們可以編寫一個平凡的算法，所有的間隔都精確地重疊。 – jberryman

如果您可以先對點列表進行排序，那麼可以很快完成：對於每個間隔，在其下限和上限的點列表中找到索引，然後進行相減。這些查找需要記錄（nPoints）時間，並且您正在做nRanges，因此整體性能將由初始排序（n log n）或查找（m log n）來控制。

這出來O(log(nPoints) * max(nPoints, nRanges))，這當然好於二次時間。這與我期望能夠得到的一樣好：我沒有看到任何聰明的方法來達到線性時間，並且對數因子非常小。

其主要缺點是它需要一次將所有點列表存儲在內存中，而您可以想象一個懶惰的解決方案可能會佔用較少的空間。

來源

2015-09-15 00:26:25 amalloy

Haskell中是否存在預定義的二進制搜索函數，還是我必須實現它？另外二分搜索需要隨機訪問，這是否意味着我需要切換到「矢量」？ – trVoldemort

我唯一能找到的就是'Data.Vector.Algorithms.Search.binarySearch'，它在'MVector'上運行。 – trVoldemort

您不需*隨機訪問使用二進制搜索，您可以在對點列表進行排序後構建一個平衡的二叉搜索樹。不過，數組的常數因子會更好。 –

如何根據點列表高效地計算間隔列表？

回答

相關問題