查找列表中的一個點是最接近另一點

Question

介紹

說你要確定哪一個列表裏面點是最接近另一個指定點。函數應該返回點本身和距離。

例如用這樣的數據：

(def pts [[2 4] [1 9] [9 4] [2 8]]) 
(def p [7 6]) 

首先，需要一些輔助功能：

(def abs js/Math.abs) 
(def pow js/Math.pow) 
(def sqrt js/Math.sqrt) 
(def pow2 #(pow % 2)) 

(defn distance [p1 p2] 
    (sqrt (+ (pow2 (abs (- (p1 0) (p2 0)))) 
      (pow2 (abs (- (p1 1) (p2 1))))))) 

---

兩個提案

我的第一種方法是以下：

(defn find-closest [p pts] 
    (->> (map #(vector (distance p %) %) pts) 
     (reduce (fn [m v] 
       (if (< (v 0) (m 0)) 
        v 
        m))))) 

(find-closest p pts) 
=> [2.8284271247461903 [9 4]] ;; this is a correct result 

通過努力使功能更加perfomant我想出了這個第二個版本：

(defn find-closest2 [p pts] 
    (let [init (first pts)] 
    (reduce (fn [m v] 
       (let [d (distance p v)] 
       (if (< d (m 0)) 
        [d v] 
        m))) 
      [(distance p init) init] 
      (rest pts)))) 

事實上，後來的功能被證明是相當快（在鉻瀏覽器49測試）：

=> (time (dotimes [_ 100000] (find-closest p pts))) 
"Elapsed time: 445.720000 msecs" 
=> (time (dotimes [_ 100000] (find-closest2 p pts))) 
"Elapsed time: 248.900000 msecs" 

的說明旁白：沒有任何人有一個提示，爲什麼同樣的功能是Clojure中的方法要慢：？

user> (time (dotimes [_ 100000] (find-closest p pts))) 
"Elapsed time: 6886.850965 msecs"                                
user> (time (dotimes [_ 100000] (find-closest2 p pts))) 
"Elapsed time: 6574.486679 msecs" 

這會慢10倍以上，我覺得很難相信。

問題

不管怎麼說，因爲我需要一個ClojureScript項目的功能，這裏是我的問題：你會如何解決這個問題？ find-closest看起來對我好，但更快的版本find-closest2看起來有點混亂。有沒有更好的方法來做到這一點？

Answer 1

與所有基於微基準決策的情況一樣，值得使用基準庫（如criterium）來確保您看到具有統計意義的結果。

在這種情況下，區別在於計算立即丟棄的中間惰性序列。 map正在生成所有潛在答案的序列，併爲每個答案分配內存。由於您對使用中間結果不感興趣，因此這次浪費了，並且您的僅限於降低版本的速度更快。

直到最近Clojure程序不得不在使用map reduce filter等的簡單和可組合之間進行選擇，並且通過不產生中間結果來快速選擇。 這已修復trannsducers所以現在您可以使用地圖版本而不介紹中間結果，並且可以以非常一般和適應性的方式進行操作。

user> (import '[java.lang.Math]) 
nil 
user> (def pow2 #(Math/pow % 2)) 
     (defn distance [p1 p2] 
     (Math/sqrt (+ (pow2 (Math/abs (- (p1 0) (p2 0)))) 
        (pow2 (Math/abs (- (p1 1) (p2 1))))))) 
#'user/pow2 
#'user/distance 
user> (defn closer-point 
     ([] [Long/MAX_VALUE [Long/MAX_VALUE Long/MAX_VALUE]]) 
     ([p1] p1) 
     ([[distance1 point1 :as p1] 
      [distance2 point2 :as p2]] 
     (if (< distance1 distance2) 
      p1 
      p2))) 
#'user/closer-point 
user> (transduce (map #(vector (distance p %) %)) 
       closer-point 
       pts) 
[2.8284271247461903 [9 4]] 

Answer 2

min-key功能是專爲這個問題而設計的。這是JVM版本。請注意，我們只是儘量減少平方距離也懶得計算的實際距離與Math/sqrt：

(ns clj.core 
    (:use tupelo.core) 
    (:require [clojure.core  :as clj] 
      [schema.core  :as s] 
      [tupelo.types  :as tt] 
      [tupelo.schema  :as ts] 
      [criterium.core  :as crit] 
)) 

; Prismatic Schema type definitions 
(s/set-fn-validation! true) ; #todo add to Schema docs 

(def pts [[2 4] [1 9] [9 4] [2 8]]) 
(def p [7 6]) 

(defn square [x] (* x x)) 

(defn dist2 [p1 p2] 
    (+ (square (- (p1 0) (p2 0))) 
    (square (- (p1 1) (p2 1))))) 

(doseq [curr-p pts] 
    (println "curr-p: " curr-p " -> " (dist2 p curr-p))) 

(newline) 
(spyx (apply min-key #(dist2 p %) pts)) 

(newline) 
(crit/quick-bench (apply min-key #(dist2 p %) pts)) 

(defn -main []) 

我不會太擔心代碼的不成熟的優化，才使得它簡單易懂第一。使用內置函數幾乎總是一個好的開始（因爲當您不需要平方根時，只需最小化數量的平方的舊技巧）。請注意，自(square ...)自動執行此操作後，我還擺脫了(abs ...)呼叫。

下面是運行結果：

curr-p: [2 4] -> 29 
curr-p: [1 9] -> 45 
curr-p: [9 4] -> 8 
curr-p: [2 8] -> 29 

(apply min-key (fn* [p1__8701#] (dist2 p p1__8701#)) pts) => [9 4] 

WARNING: Final GC required 7.5524163302816705 % of runtime 
Evaluation count : 1132842 in 6 samples of 188807 calls. 
      Execution time mean : 527.711887 ns 
    Execution time std-deviation : 3.437558 ns 
    Execution time lower quantile : 524.840276 ns (2.5%) 
    Execution time upper quantile : 531.911280 ns (97.5%) 
        Overhead used : 1.534138 ns