查找列表中的一个点是最接近另一点

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