Имеет ли смысл лень для clojure hash-карт? - PullRequest
3 голосов
/ 24 февраля 2012

Мне нужно вернуть последовательность, число и хэш-карту из моей функции (все обернутые в вектор), чтобы напечатанное возвращаемое значение выглядело так:

[ ([:c :a] [:e :c] [:f :e] [:d :e] [:g :f] [:b :a])  15
  {:g :c, :f :a, :c :e, :d :a, :b :a, :c :a} ]

Поскольку мои входные данные моглибыть большим, я хотел бы вернуть ленивые последовательности / объекты из моей функции.Последовательность пар (первый объект в моем возвращаемом векторе) была достаточно простой, чтобы сделать ее ленивой, обернув 'lazy-seq' вокруг вызовов вызовов, которые ее создают.

Хеш-карта (3-й объект в моем векторе возврата и потенциально очень большой, как моя последовательность) создается (с использованием вызовов Assoc) в том же блоке loop-recur, что и последовательность.Хэш-карта - это дополнительная информация, которую некоторые из моих абонентов будут использовать, но если последовательность пар возвращается как ленивая, то мне интересно, имеет ли смысл отправлять обратно потенциально огромную хэш-карту с помощью (эффективного) lazy-seqдаже если я сделаю это необязательным возвращаемым значением.Записи в хэш-карте связаны с парами в ленивой последовательности.

Итак, вот мой новый вопрос: есть ли смысл отправлять ленивую последовательность MapEntry вместо большого HashMap?То есть, предполагая, что пользователь возьмет кусок ленивого seq MapEntrys, преобразует его в hashmap, чтобы выполнить поиск ..., в противном случае он получит следующий кусок, и так далее.Это разумный способ лениво использовать ассоциативные данные?Существуют ли идиоматические способы возврата / управления большими ассоциативными данными в Clojure?Буду признателен за любые идеи о том, что мои варианты.Заранее спасибо за помощь.

Ответы [ 3 ]

6 голосов
/ 24 февраля 2012

Нет, дать им ленивую карту невозможно.Ленивая последовательность MapEntries возможна, но не очень полезна.Однако есть ряд других опций, которые могут иметь смысл, которые похожи.

  • Вы говорите, что вызывающему абоненту карта вообще может не понадобиться: так что верните задержку карты, которую они могут вызвать, если она понадобится.
  • Если ключи дешевы для вычисления, но значения дороги, вы можете вернуть полную карту с правильными ключами и значениями, каждое из которых задерживается;вызывающая сторона может принудительно устанавливать только те значения, которые им нужны.

Вы все равно можете вернуть ленивый-последовательность векторов (я бы не стал делать их MapEntries), но в принципе вызывающая сторона не будетв состоянии рассматривать это как ленивую карту.Либо они хотят только искать фиксированный набор уже известных ключей (в этом случае они просто лениво фильтруют записи, никогда не делая это картой), либо они хотят искать записи произвольно, в этом случае они будутпосле поиска первой записи необходимо сохранить все записи в памяти, чтобы они все еще могли искать вторую, и чтобы они могли просто выбросить все это на полностью реализованную карту.

1 голос
/ 24 февраля 2012

Нет, у Clojure нет ленивых карт.

Кроме того, если вы создаете последовательность, используя loop / recur, я не верю, что попытка сделать ее ленивой приводит к чему-либо (если генерация каждого элемента не медленная).

Посмотрите на эти две функции:

(defn bad-lazy-range [begin end]
  (loop [i (dec end) lst nil]
    (if (>= i begin)
      (recur (dec i) (lazy-seq (cons i lst)))
      lst)))

(defn good-lazy-range [begin end]
  (if (>= begin end)
    nil
    (lazy-seq (cons begin (good-lazy-range (inc begin) end)))))

bad-lazy-range будет повторяться begin-end раз, генерируя thunk (ленивая ссылка последовательности) каждый раз, а затем возвращать самый внешний thunk. Этот блок должен содержать ссылку на следующий блок, который требует ссылку на третий блок и т. Д. Вы выполняете всю работу немедленно и генерируете псевдосвязанный список блоков, который занимает больше места, чем обычный список.

good-lazy-range, однако, немедленно возвращается без повторения больше - рекурсивный вызов скрыт внутри thunk и не будет оцениваться до тех пор, пока не будет необходим. Это также предотвращает исключение переполнения стека - без вызова lazy-seq это может сгенерировать исключение переполнения стека, но на каждом шаге он оценивает один вызов good-lazy-range и возвращает. Затем вызывающий абонент может оценить следующий вызов, но на этом этапе кадр стека от первого вызова давно пропал.

В общем, используйте lazy-seq, только если вы можете обернуть его вокруг значительного объема вычислений. В первой функции она заключена только в вызов cons, который в любом случае быстро вернется. Однако во второй функции она обернута вокруг вызова cons и рекурсивного вызова, что означает, что она задерживает стоящее количество вычислений.

Если ваш код использует ленивость правильно и использует loop / recur, пожалуйста, опубликуйте его - мне было бы интересно посмотреть, как вы это сделали.

0 голосов
/ 24 февраля 2012

Из примера, который вы привели, зачем возвращать карту вообще, вызывающий может просто построить карту из последовательности, используя (в {} s)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...