时间戳

首页 > 解决方案 > Clojure Set 与 Map Lookup 性能差异

clojure - Clojure Set 与 Map Lookup 性能差异

问题描述

我有一个 uid 列表，想检查一个 uid 是否是这个列表的成员

实现它的自然方法是创建一组 ( clojure.set) uid 并在该列表中搜索该成员

我发现映射键查找要快得多 - 我使用以下代码段对这两种方法进行基准测试：

(def uids #{:a :b :c :d :e :f :g :h :i :j :k :l :m :n :o :p :a1 :b1 :c1 :d1 :e1 :f1 :h1 :i1 :j1 :k1 :l1 :m1 :n1 :o1 :p1})
(def uids-map (reduce (fn [acc v] (assoc acc v true)) {} uids))
(time (dotimes [i 1000000] (:o1 uids)))
;user=> "Elapsed time: 191.076266 msecs"
(time (dotimes [i 1000000] (:o1 uids-map)))
;user=> "Elapsed time: 38.159388 msecs"

结果在调用中非常一致 - 地图查找大约占集合查找的 1/5

那么对于键查找来说设置不是最优的还是我使用错误的方式？

另外，这些基准的差异的原因是什么？

我的印象是在 clojure 中将集合实现为类似于向量的关联数据结构 - 那么为什么键查找比简单映射慢得多？

标签： clojure

解决方案

我从来没有进入 clojure 的源代码，但从我看到的 set 实现实际上在里面使用了一个地图：

protected APersistentSet(IPersistentMap impl){
    this.impl = impl;
}

它还将invoke调用委托给内部映射。

在APersistentSet 中：

public Object invoke(Object arg1) {
    return get(arg1);
}

// ....

public Object get(Object key){
    return impl.valAt(key);
}

在APersistentMap 中：

public Object invoke(Object arg1) {
    return valAt(arg1);
}

public Object invoke(Object arg1, Object notFound) {
    return valAt(arg1, notFound);
}

所以这无法解释差异。

正如@cgrand的评论中所提到的，当我们反转参数时它会更快（并且大致相同，因为我们invoke立即调用 set）。所以我查找了Keyword的invoke可能用于(:k obj)：

final public Object invoke(Object obj, Object notFound) {
    if(obj instanceof ILookup)
        return ((ILookup)obj).valAt(this,notFound);
    return RT.get(obj, this, notFound);
}

需要注意的重要一点是，它ILookup是在APersistentMap（通过Associative）中实现的，而不是在APersistentSet. 您还可以在 clojure 中进行验证：

(instance? clojure.lang.ILookup #{}) ;; false
(instance? clojure.lang.ILookup {})  ;; true

所以地图通过“快乐路径”并设置最终RT.get我认为是运行时。

让我们看一下运行时。

它最初尝试做与关键字几乎相同的事情：

static public Object get(Object coll, Object key){
    if(coll instanceof ILookup)
        return ((ILookup) coll).valAt(key);
    return getFrom(coll, key);
}

但是由于我们知道集合没有实现ILookup，我们知道它们会去RT.getFrom：

static Object getFrom(Object coll, Object key){
    if(coll == null)
        return null;
    else if(coll instanceof Map) {
        Map m = (Map) coll;
        return m.get(key);
    }
    else if(coll instanceof IPersistentSet) {
        IPersistentSet set = (IPersistentSet) coll;
        return set.get(key);
    }
    else if(key instanceof Number && (coll instanceof String || coll.getClass().isArray())) {
        int n = ((Number) key).intValue();
        if(n >= 0 && n < count(coll))
            return nth(coll, n);
        return null;
    }
    else if(coll instanceof ITransientSet) {
        ITransientSet set = (ITransientSet) coll;
        return set.get(key);
    }

    return null;
}

这使我相信主要区别在于instanceof由于未实施的集合而导致的额外代表团和呼叫ILookup。

作为奖励，我在一个集合上添加了一个测试，该集合立即（使用）实现ILookup并委托valAt给内部映射proxy，这稍微缩小了差距：

(def uids #{:a :b :c :d :e :f :g :h :i :j :k :l :m :n :o :p :a1 :b1 :c1 :d1 :e1 :f1 :h1 :i1 :j1 :k1 :l1 :m1 :n1 :o1 :p1})
(def uids-map (into {} (for [k uids] [k k])))
(def lookupable-set (proxy [clojure.lang.APersistentSet clojure.lang.ILookup] [uids-map]
                      (valAt [k] (get uids-map k))))

;; verify
(instance? clojure.lang.APersistentSet lookupable-set) ;; true
(instance? clojure.lang.ILookup lookupable-set) ;; true

(time (dotimes [i 1000000] (:o1 uids))) ;; 134.703101 msecs
(time (dotimes [i 1000000] (:o1 lookupable-set))) ;; 63.187353 msecs  <-- faster
(time (dotimes [i 1000000] (:o1 uids-map))) ;; 35.802762 msecs <-- still fastest

总结：性能很重要——在(#{...} k)不通过关键字的情况下调用集合(k #{...})与映射一样快。

但我可能是错的:)

推荐阅读