Clojure中的碰撞檢查如何在時間n^2/2中完成？

我對檢測碰撞不感興趣。Clojure中的碰撞檢查如何在時間n^2/2中完成？

我用具有用於用java環路像這樣兩個兩個計數器的方法：

第一環路解析過的所有對象，幷包含所述第二回路。它的計數器是當前對象被檢查所有其他對象的索引。

第二個for循環解析所有未檢查的對象。它的計數器是當前正在對第一個循環查看的對象進行檢查的未檢查對象的索引。

僞代碼：

for(i++) 
    for(int j = i, j++) 
    collides(objects[i], objects[j)

這是如何用Clojure實現的？

我非常習慣於使用像map那樣沒有計數器的命令，我想知道這種方法是否真的需要一個計數器。如果有辦法做到這一點，沒有一個可取的櫃檯。

我也想表明，我不希望執行時間爲n^2。相反，我想有時間n^2/2方法，只檢查未經檢查的對象的衝突。

來源

2016-12-21 Jason Basanese

請注意，在大O符號中，'/ 2'被丟棄，因此您剩下'O（N^2）' – Max

對，我會如何強調我關心那個細節？我會刪除O嗎？我會把'n^2/2'嗎？ –

很難做到這一點，因爲計算事物花費多少時間的方法有點可變。有時候設置變量可能需要不同的時間來說明檢查條件。我認爲你寫這個的方式是最好的。 – Max

您可以通過爲做同樣的代碼：

(for [i (range (count objs)) 
     j (range i (count objs)) 
     :when (collide? (nth objs i) (nth objs j))] 
    ...do stuff...)

如果使用loop但它可能不會那麼好這將運行得更快。

來源

2016-12-21 19:11:34

//，它看起來不錯。仍然櫃檯 –

要選擇所有不使用計數器碰撞對：

(defn select-pairs [collide? objects] 
    (for [tail (iterate rest objects) :while (seq tail) 
     :let [x (first tail)], y tail :when (collide? x y)] 
    [x y]))

例如，

(select-pairs < (range 4)) 
;([0 1] [0 2] [0 3] [1 2] [1 3] [2 3])

這將在任何序列，甚至是無盡的工作之一。
collide?只是選擇對的標準的名稱。

來源

2016-12-22 11:39:03 Thumbnail

幹得好，沒有櫃檯。我一定會嘗試一下。 –

Clojure中的碰撞檢查如何在時間n^2/2中完成？

回答

相關問題