Список Clojure 2d для хэш-карты

Чтобы быть ленивым, компьютер должен будет выполнять линейное сканирование входной последовательности каждый раз, когда запрашивается ключ, по крайней мере, если ключ выходит за рамки того, что было просканировано до сих пор. Наивное решение — просто каждый раз сканировать последовательность, например так:

(defn get-val [coll k]
  (some (fn [[a b]] (when (= k a) b)) coll))

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

Чуть менее наивным решением было бы использовать memoize для кэширования результатов get-val, хотя это все равно будет сканировать входную последовательность больше, чем это необходимо. Более агрессивным решением для кэширования было бы использование атома (как это делает memoize внутри) для кэширования каждой пары по мере ее появления, тем самым потребляя больше входной последовательности только тогда, когда поиск требует чего-то еще не видимого.

Несмотря на это, я бы не рекомендовал оборачивать это в API хэш-карты, так как это подразумевает эффективные неизменяемые «обновления», которые, вероятно, не понадобятся, но которые будет сложно реализовать. Я бы также вообще не рекомендовал использовать ключевые слова для ключей.

Проблема в том, что хеш-карты не могут быть ни бесконечными, ни ленивыми. Они предназначены для быстрого доступа к ключу-значению. Итак, если у вас есть хэш-карта, вы сможете выполнить быстрый поиск ключа. Ключ-значение — основная идея хэш-карт, но это делает невозможным создание ленивой бесконечной хэш-карты.

Предположим, у нас есть бесконечный 2d-список, тогда вы можете просто использовать into для создания хэш-карты:

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

Но нет способа сделать эту хэш-карту бесконечной. Таким образом, единственным решением для вас является создание собственной хэш-карты, например Предложил Чоузер. В этом случае у вас будет бесконечная 2D-последовательность и функция для выполнения ленивого поиска в ней.

Собственно, его решение можно немного улучшить:

(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

Если вы сгладите его до списка (k v k v k v k v) с помощью flatten, вы можете использовать apply для вызова hash-map с этим списком в качестве аргументов, которые дадут вам список, который вы ищете.

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

хотя он не использует ключевое слово для первого аргумента.

По крайней мере, в clojure последнее значение, связанное с ключом, считается значением для этого ключа. Если это не так, вы не можете создать новую карту с другим значением для ключа, который уже есть в карте, потому что первый (и теперь затененный ключ) будет возвращен функцией поиска. Если функция поиска ищет до конца, то она не ленива. Вы можете решить эту проблему, написав собственную реализацию карты, которая использует списки ассоциаций, хотя ей не хватит гарантий производительности карт Clojure на основе trei, потому что в худшем случае она перейдет к линейному времени.

Я не уверен, что сохранение ленивой входной последовательности даст желаемые результаты.

Чтобы сделать хэш-карту из вашей последовательности, вы можете попробовать:

(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}

Вы можете преобразовать эту структуру в хэш-карту позже таким образом.

(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}