My first quick take is that you would be served well by creating your own data structure that wraps a priority queue for efficient access by minimum value, and a sorted map for efficient access by key, including subseq's of keys.
That combination won't give you subseq's on values, but you could toss in a sorted set with [<value> <key>] pairs (the key present in there to serve as a tie-breaker for key,value pairs with equal value, otherwise the sorted map would only keep one pair per value). Come to think of it, that should give you efficient access to the minimum value entry all by itself, so the priority queue would be unnecessary then. These suggestions are off the cuff, and intended to maximize reuse of existing code with least amount of new code required. It wouldn't necessarily minimize the memory required. Andy On Fri, Apr 7, 2017 at 8:49 PM, Brian Beckman <bc.beck...@gmail.com> wrote: > I have found a few data types in Clojure that support search and priority > queues. In particular, I found > > Priority Map https://github.com/clojure/data.priority-map > PSQ https://goo.gl/Dw4gkV > data.avl https://goo.gl/e07q7H > > I would be grateful for a few clarifying words on whether any of these can > meet my requirements out-of-the-box before I begin a deep-dive. Forgive me > for being a bit lazy (actually, just in a hurry), but I thought I'd check > whether someone knows an answer for me off-the-cuff. > > I need collections of [k v] pairs supporting efficient peek, pop, get, and > subseq-style search on either the key space or on the value space. I need > all operations on just one of the two spaces. > > Priority map supports efficient peek and pop of the value space on its API > surface, but I don't see a get subseq (or rsubseq) or other way to quickly > search the value space on the API surface. The comments in the source > suggest that there is an auxiliary inverse sorted map from values to keys. > The supported "get" operation seems to operate on the key space, but I > could use one on the value space (see line 313 of https://goo.gl/qhfXKL). > Perhaps that inverse map easy to get at, in which case I'll be done. > > PSQ supports peek and pop on values, and efficient search on keys, > according to its documentation. Do I read that correctly? > > I have not read the documentation for data.avl deeply enough to know > whether it will do my job out-of-the box. But I am sure I could build what > I need on top of AVL trees, RB trees, 2-3 trees, splay trees, etc. I'm just > looking to save myself work (and use tested software). > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
