在可能的情况下使用transients结合select-keys

Question

问题：当前select-keys使用conj来添加条目。如果map是可编辑的，可以使用conj!来提高select-keys性能。

此外，keyseq被作为seq遍历，但可以通过reduce遍历，这可能更快。

方法1：使用transient map和conj!，保持loop/recur
方法2：重新实现select-keys以使用reduce而不是loop/recur
方法3：结合方法和二

|选择键大小 | loop/recur | transient | reduce | transient + reduce |
| :-- | :-- | :-- | :-- | :-- | :-- |
|1 | 243 ns | 256 ns | 161 ns | 188 ns |
|7 | 1.1 ms | - | 885 ns | 454 ns |

从这些数据中，选择了方法三。

注意：为了以reduce的形式实现select-keys，需要将select-keys移动到reduce定义之后。这强制使用(declare select-keys)，因为它在reduce定义之前被使用。

补丁：（链接：https://dev.clojure.org/jira/secure/attachment/17392/0001-CLJ-1789-Use-transients-and-reduce-with-select-keys.patch 文件名：0001-CLJ-1789-Use-transients-and-reduce-with-select-keys.patch）

Answer 1

_由slipset发表的评论

标准的Clojure select-keys

 (bench (clojure.core/select-keys {:a "b" :c "d"} [:a]))
评估计数：在4106374次调用中的60个样本为246382440。
             平均执行时间：243.245536 ns
    执行时间标准差：2.714803 ns
   执行时间的最小四分位数：238.473675 ns (2.5%)
   执行时间的最大四分位数：248.544255 ns (97.5%)
                   使用的开销：1.845047 ns


使用transients

 (bench (select-keys {:a "b" :c "d"} [:a]))
评估计数：在3878787次调用中的60个样本为232727220。
             平均执行时间：256.937568 ns
    执行时间标准差：10.025123 ns
   执行时间下四分位数：249.951872 纳秒 (2.5%)
   执行时间上四分位数：276.251590 纳秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现5个异常值（8.3333%）
   轻度严重     3 (5.0000%)
   轻度轻微     2 (3.3333%)
 异常值引起的方差：25.4503% 异常值略微增加了方差


减少后

 (bench (select-keys {:a "b" :c "d"} [:a]))
评估次数：365807860 次在60个样本中的6080131次调用。
             执行时间平均值：161.582833 纳秒
    执行时间标准差：2.212659 纳秒
   执行时间下四分位数：158.027524 纳秒 (2.5%)
   执行时间上四分位数：167.673682 纳秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现3个异常值（5.0000%）
   轻度严重     3 (5.0000%)
 异常值引起的方差：1.6389% 异常值略微增加了方差

添加transient后

 (bench (select-keys {:a "b" :c "d"} [:a]))
评估次数：318075720 次在60个样本中的5301262次调用。
             执行时间平均值：188.656164 纳秒
    执行时间标准差：3.024952 纳秒
   执行时间下四分位数：183.867285 纳秒 (2.5%)
   执行时间上四分位数：195.466784 纳秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现4个异常值（6.6667%）
   轻度严重     4 (6.6667%)
 异常值引起的方差：1.6389% 异常值略微增加了方差


在更大的映射/选择上

(bench (clojure.core/select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：56147160 次在60个样本中的935786次调用。
             执行时间平均值：1.104653 微秒
    执行时间标准差：36.366516 纳秒
   执行时间下四分位数：1.048257 微秒 (2.5%)
   执行时间上四分位数：1.142031 微秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现5个异常值（8.3333%）
   轻度严重     4 (6.6667%)
   轻度轻微     1 (1.6667%)
 异常值引起的方差：19.0389% 异常值略微增加了方差

reduce

(bench (select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：67723500 次在60个样本中的1128725次调用。
             执行时间平均值：885.840664 纳秒
    执行时间标准差：11.503115 纳秒
   执行时间下四分位数：864.403495 纳秒 (2.5%)
   执行时间上四分位数：905.721942 纳秒 (97.5%)
                   使用的开销：1.845047 ns

添加transient + reduce

(bench (select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：134119380 次在60个样本中的2235323次调用。
             执行时间平均值：454.587795 纳秒
    执行时间标准差：15.681611 纳秒
   执行时间下四分位数：439.822498 纳秒 (2.5%)
   执行时间上四分位数：485.797378 纳秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现3个异常值（5.0000%）
   轻度严重     3 (5.0000%)
 异常值引起的方差：20.6393% 异常值略微增加了方差


所附补丁同时使用transient和reduce

Answer 2

评论者：alexmiller

该提案对我来说看起来不错。描述需要更好地反映已考虑和选择的内容。

Answer 3

参考： https://clojure.atlassian.net/browse/CLJ-1789（由 alexmiller 报告）