哪个更快?映射或减少条件fn或get-in

Question

我正在使用monger，并使用find-maps从我的mongo nosql数据库获取批处理。它返回一个数组，我计划将其用作函数调用链下游的数据存储参数(引用)。在这些未来的函数调用中，我将有权访问相应的id。我希望使用这个id作为查找，以便在我的数据存储中获取，这样我就不必进行另一个monger调用。数组形式的数据存储似乎不是通过id ....访问对象的最快方式但我不确定。

如果我需要从这个数据存储数组派生一个对象，那么我需要使用这样的函数(必须对每个元素进行log(n))

(defn fetchObjFromArray [fetch_id inputarray]
    (reduce (fn [reduced_obj element_obj]
                (if (= fetch_id (get-in element_obj [:_id]))
                    element_obj ;; ignoring duplicates for conversation
                    reduced_obj 
                )    
            )
            {}
            inputarray
    )
)

相反，如果在初始的monger调用之后，我使用如下函数创建了一个键/值哈希对象:

(defn createReportFromObjArray [inputarray]
    (reduce (fn [returnobj elementobj]
                (let [_id (get-in elementobj [:_id])
                      keyword (keyword _id)]
                    (assoc returnobj keyword elementobj)
                ) ;; ignoring duplicates for conversation
            )
            {}
            inputarray)
)

那么也许我的后续调用可以使用get-in，这会更快，因为我将按键抓取?

我很困惑，因为:当我使用get-in时，它不需要迭代key/val对象中的每个键，直到它找到键和fetch_id之间的匹配:

(let [report (createReportFromObjArray inputarray)
      target_val (get-in report [(keyword fetch_id)])]

为什么每个键的get-in不需要log(n) ?也许它更快是因为它可以在找到第一个"匹配"时停止，而map/reduction必须经过整个log(n)?这如何比必须迭代数组中的每个元素并检查id是否匹配fetch_id更快?

我非常感谢你提供的帮助。

Answer 1

在第二个代码示例中，您正在线性时间内构建Clojure哈希映射。通过get和衍生，它们的查找性能为O(log32(N))。

在第一个示例中，您扫描整个输入并返回与ID或空散列映射匹配的最后一个元素，这可能是无意的。

_

我建议使用(group-by :_id)代替第二个代码示例。我还建议使用(first (filter (comp #{fetch_id} :_id) inputarray))来代替第一个例子。

避免通过keyword强制转换为关键字——Clojure关键字通常应该在编译时就知道。映射支持任意数据类型作为键