如果我有一个单词向量，例如 ["john" "said"... "john" "walked"...] 并且我想制作每个单词的哈希映射以及下一个单词的出现次数，例如{“约翰”{“说”1“走”1“踢”3}}
我想出的最佳解决方案是按索引递归遍历列表并使用 assoc 不断更新哈希映射，但这看起来真的很混乱。有没有更惯用的方式来做到这一点？
问问题
324 次
2 回答
6
给定你的话：
(def words ["john" "said" "lara" "chased" "john" "walked" "lara" "chased"])
使用这个转换-fn
(defn transform
[words]
(->> words
(partition 2 1)
(reduce (fn [acc [w next-w]]
;; could be shortened to #(update-in %1 %2 (fnil inc 0))
(update-in acc
[w next-w]
(fnil inc 0)))
{})))
(transform words)
;; {"walked" {"lara" 1}, "chased" {"john" 1}, "lara" {"chased" 2}, "said" {"lara" 1}, "john" {"walked" 1, "said" 1}}
编辑：您可以使用像这样的瞬态哈希映射来获得性能：
(defn transform-fast
[words]
(->> (map vector words (next words))
(reduce (fn [acc [w1 w2]]
(let [c-map (get acc w1 (transient {}))]
(assoc! acc w1 (assoc! c-map w2
(inc (get c-map w2 0))))))
(transient {}))
persistent!
(reduce-kv (fn [acc w1 c-map]
(assoc! acc w1 (persistent! c-map)))
(transient {}))
persistent!))
显然，生成的源代码看起来不太好，只有在关键时才应该进行这种优化。
（Criterium 说它在李尔王上的速度大约是 Michał Marczykstransform*的两倍）。
于 2013-11-25T21:45:45.010 回答
5
（更新：见下文用于中间产品的解决方案——最终结果仍然完全持久——这是迄今为止最快的，比李尔王基准测试java.util.HashMap有 2.35 倍的优势。）transform-fast
merge-with基于解决方案
这是一个更快的解决方案，取自李尔王（King Lear）的单词大约是 1.7 倍（具体方法见下文），几乎是样本的 3 倍words：
(defn transform* [words]
(apply merge-with
#(merge-with + %1 %2)
(map (fn [w nw] {w {nw 1}})
words
(next words))))
传递给的函数map也可以写成
#(array-map %1 (array-map %2 1)),
尽管这种方法的时机不太好。（我仍然将此版本包含在下面的基准测试中transform**。）
首先，健全性检查：
;; same input
(def words ["john" "said" "lara" "chased" "john"
"walked" "lara" "chased"])
(= (transform words) (transform* words) (transform** words))
;= true
使用测试输入的标准基准（OpenJDK 1.7 with ）-XX:+UseConcMarkSweepGC：
(do (c/bench (transform words))
(flush)
(c/bench (transform* words))
(flush)
(c/bench (transform** words)))
Evaluation count : 4345080 in 60 samples of 72418 calls.
Execution time mean : 13.945669 µs
Execution time std-deviation : 158.808075 ns
Execution time lower quantile : 13.696874 µs ( 2.5%)
Execution time upper quantile : 14.295440 µs (97.5%)
Overhead used : 1.612143 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 2 (3.3333 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 12998220 in 60 samples of 216637 calls.
Execution time mean : 4.705608 µs
Execution time std-deviation : 63.133406 ns
Execution time lower quantile : 4.605234 µs ( 2.5%)
Execution time upper quantile : 4.830540 µs (97.5%)
Overhead used : 1.612143 ns
Found 1 outliers in 60 samples (1.6667 %)
low-severe 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 10847220 in 60 samples of 180787 calls.
Execution time mean : 5.706852 µs
Execution time std-deviation : 73.589941 ns
Execution time lower quantile : 5.560404 µs ( 2.5%)
Execution time upper quantile : 5.828209 µs (97.5%)
Overhead used : 1.612143 ns
最后，在 Project Gutenberg 中发现的使用 King Lear 的更有趣的基准测试（在处理之前不必费心去除法律声明等）：
(def king-lear (slurp (io/file "/path/to/pg1128.txt")))
(def king-lear-words
(-> king-lear
(string/lower-case)
(string/replace #"[^a-z]" " ")
(string/trim)
(string/split #"\s+")))
(do (c/bench (transform king-lear-words))
(flush)
(c/bench (transform* king-lear-words))
(flush)
(c/bench (transform** king-lear-words)))
Evaluation count : 720 in 60 samples of 12 calls.
Execution time mean : 87.012898 ms
Execution time std-deviation : 833.381589 µs
Execution time lower quantile : 85.772832 ms ( 2.5%)
Execution time upper quantile : 88.585741 ms (97.5%)
Overhead used : 1.612143 ns
Evaluation count : 1200 in 60 samples of 20 calls.
Execution time mean : 51.786860 ms
Execution time std-deviation : 587.029829 µs
Execution time lower quantile : 50.854355 ms ( 2.5%)
Execution time upper quantile : 52.940274 ms (97.5%)
Overhead used : 1.612143 ns
Evaluation count : 1020 in 60 samples of 17 calls.
Execution time mean : 61.287369 ms
Execution time std-deviation : 720.816107 µs
Execution time lower quantile : 60.131219 ms ( 2.5%)
Execution time upper quantile : 62.960647 ms (97.5%)
Overhead used : 1.612143 ns
java.util.HashMap基于解决方案
全力以赴，使用可变散列映射作为中间状态和loop/recur以避免在循环单词对时使用 consing 可能会做得更好：
(defn t9 [words]
(let [m (java.util.HashMap.)]
(loop [ws words
nws (next words)]
(if nws
(let [w (first ws)
nw (first nws)]
(if-let [im ^java.util.HashMap (.get m w)]
(.put im nw (inc (or (.get im nw) 0)))
(let [im (java.util.HashMap.)]
(.put im nw 1)
(.put m w im)))
(recur (next ws) (next nws)))
(persistent!
(reduce (fn [out k]
(assoc! out k
(clojure.lang.PersistentHashMap/create
^java.util.HashMap (.get m k))))
(transient {})
(iterator-seq (.iterator (.keySet m)))))))))
clojure.lang.PersistentHashMap/create是PHM类中的静态方法，并且公认是实现细节。（但在不久的将来不太可能改变——目前在 Clojure 中为内置地图类型创建的所有地图都通过像这样的静态方法。）
完整性检查：
(= (transform king-lear-words) (t9 king-lear-words))
;= true
基准测试结果：
(c/bench (transform-fast king-lear-words))
Evaluation count : 2100 in 60 samples of 35 calls.
Execution time mean : 28.560527 ms
Execution time std-deviation : 262.483916 µs
Execution time lower quantile : 28.117982 ms ( 2.5%)
Execution time upper quantile : 29.104784 ms (97.5%)
Overhead used : 1.898836 ns
(c/bench (t9 king-lear-words))
Evaluation count : 4980 in 60 samples of 83 calls.
Execution time mean : 12.153898 ms
Execution time std-deviation : 119.028100 µs
Execution time lower quantile : 11.953013 ms ( 2.5%)
Execution time upper quantile : 12.411588 ms (97.5%)
Overhead used : 1.898836 ns
Found 1 outliers in 60 samples (1.6667 %)
low-severe 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
于 2013-11-26T05:57:25.460 回答