0

我有一个这样的无限列表：
((1 1)(3 9)(5 17)...)
我想从中制作一个哈希图：
{:1 1 :3 9 :5 17 ... )

基本上“内部”列表的第一个元素是关键字，而第二个元素是值。我不确定在创建时是否更容易创建我使用的列表：

(迭代 (fn [[ab]] [(计算 a) (计算 b)]) [1 1])

(b) 的计算需要 (a)，所以我相信在这一点上 (a) 不能是关键字……重点是可以很容易地访问给定 (a) 的值 (b)。

任何想法将不胜感激......

--EDIT--
好的，所以我想通了：

(def my-map (into {} (map #(hash-map (keyword (str (first %))) (first (rest %))) my-list)))

问题是：它似乎并不懒惰......即使我没有消费它，它也会永远存在。有没有办法让它变得懒惰？

4

5 回答 5

3

问题是哈希映射既不是无限的也不是惰性的。他们设计用于快速键值访问。因此，如果您有一个哈希映射，您将能够执行快速键查找。键值访问是 hash-map 的核心思想，但它使得惰性无限 hash-map 的创建变得不可能。

假设，我们有一个无限的 2d 列表，那么您可以使用它into来创建 hash-map：

(into {} (vec (map vec my-list)))

但是没有办法使这个哈希映射无限。因此，您唯一的解决方案是创建自己的哈希映射，就像Chouser 建议的那样。在这种情况下，您将拥有一个无限的二维序列和一个在其中执行惰性键查找的函数。

实际上，他的解决方案可以稍微改进一下：

(def my-map (atom {}))

(def my-seq (atom (partition 2 (range))))

(defn build-map [stop]
  (when-let [[k v] (first @my-seq)]
    (swap! my-seq rest)
    (swap! my-map #(assoc % k v))
    (if (= k stop)
        v
        (recur stop))))

(defn get-val [k]
  (if-let [v (@my-map k)]
    v
    (build-map k)))

my-map在我的示例中，存储当前的哈希映射并my-seq存储尚未处理的元素的序列。get-val函数执行惰性查找，使用已处理的元素my-map来提高其性能：

(get-val 4)
=> 5
@my-map
=> {4 5, 2 3, 0 1}

和加速：

(time (get-val 1000))
=> Elapsed time: 7.592444 msecs
(time (get-val 1000))
=> Elapsed time: 0.048192 msecs
于 2013-04-09T06:56:18.460 回答
1

如果您使用 flatten 将其展平为 (kvkvkvkv) 列表，那么您可以使用 apply 使用该列表调用 hash-map，因为它的参数将为您提供您寻找的列表。

user> (apply hash-map (flatten '((1 1)(3 9)(5 17))))
{1 1, 3 9, 5 17}

尽管它没有对第一个参数进行关键字化。

至少在 clojure中，与键关联的最后一个值被称为该键的值。如果不是这种情况，那么您不能为已经在映射中的键生成具有不同值的新映射，因为查找函数将返回第一个（现在是阴影键）。如果查找函数搜索到最后，那么它不是懒惰的。您可以通过编写自己的使用关联列表的地图实现来解决这个问题，尽管它会缺乏 Clojure 基于 Trei 的地图的性能保证，因为在最坏的情况下它会退化为线性时间。

我不确定保持输入序列惰性会产生预期的结果。

于 2013-04-09T00:59:15.850 回答
1

为了变得懒惰，每次请求一个键时，计算机都必须对输入序列进行线性扫描，至少如果该键超出了目前已扫描的范围。一个简单的解决方案是每次都扫描序列，如下所示：

(defn get-val [coll k]
  (一些 (fn [[ab]] (当 (= ka) b)) coll))

(get-val '((1 1)(3 9)(5 17))
         3)
;=> 9

一个稍微不那么天真的解决方案是用来memoize缓存 的结果get-val，尽管这仍然会扫描输入序列而不是严格必要的。一个更积极的缓存解决方案是使用一个原子（就像memoize内部一样）来缓存每对所看到的，从而仅在查找需要尚未看到的内容时消耗更多的输入序列。

无论如何，我不建议将其包装在哈希映射 API 中，因为这意味着可能不需要但难以实现的高效不可变“更新”。我通常也不建议对键进行关键字化。

于 2013-04-09T06:01:24.487 回答
0

要从您的序列中制作哈希图，您可以尝试：

(defn to-map [s] (zipmap (map (comp keyword str first) s) (map second s)))

=> (to-map '((1 1)(3 9)(5 17)))
=> {:5 17, :3 9, :1 1}
于 2013-04-09T00:59:05.730 回答
0

您可以稍后通过这种方式将该结构转换为哈希映射

(def it #(iterate (fn [[a b]] [(+ a 1) (+ b 1)]) [1 1])) 
(apply hash-map (apply concat (take 3 (it))))
=> {1 1, 2 2, 3 3}
于 2013-04-09T01:00:41.703 回答