Re: Priority Map with efficient search on values?

[Brian Beckman]

"Much appreciated" to all answerers. Looks like priority-map has maps in 
both directions that I can use quickly. I'll write a protocol with the API 
I need, implement it with priority-map's non-superficial features to get 
going, then investigate more advanced data structures if / when I need to.

On Friday, April 7, 2017 at 10:55:44 PM UTC-7, Brian Beckman wrote:
>
> I have found a few data types in Clojure that support search and priority 
> queues. In particular, I found 
>
> Priority Maphttps://github.com/clojure/data.priority-map
> PSQhttps://goo.gl/Dw4gkV
> data.avlhttps://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.

Re: Priority Map with efficient search on values?

[Erik Assum]

This is way out of my league, but have you had a look at Michals priority 
search queues?

https://github.com/michalmarczyk/psq.clj 


He had a presentation about them at Euroclojure in 2016

Priority Search Queues: 1.5 dimensional Tree Search - Michał Marczyk 


Erik.
> On 8 Apr 2017, at 05:49, Brian Beckman  wrote:
> 
> I have found a few data types in Clojure that support search and priority 
> queues. In particular, I found 
> 
> Priority Maphttps://github.com/clojure/data.priority-map
> PSQhttps://goo.gl/Dw4gkV
> data.avlhttps://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.

Re: Priority Map with efficient search on values?

[Mark Engelberg]

If you need to do subseq on the key space, you could do the following:
(def pm-empty (PersistentPriorityMap. (sorted-map) (sorted-map) {} nil))

This sets up the priority map to use sorted maps for both associating keys
to values and values to keys.

Use this as your base priority map to pour new key-value pairs into.  Then,
you can extract the underlying key-value sorted map with (.item->priority
pm) and call subseq on it to perform the subseq on keys.

Once you're using sorted maps for both the keys and values though, you
might want to look at the PSQ data structure you referred to which was
built with this kind of range searching on both keys and values as a
primary objective.

-- 
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.

Re: Priority Map with efficient search on values?

[Mark Engelberg]

On a priority map pm, (.priority->set-of-items pm) will return a sorted map
from priorities (i.e., the values in the priority-map) to sets of items
that have that priority (i.e., the keys in the priority-map).

With that sorted map you can look up specific priorities, or do various
subseq operations on it.

I've been waiting 7 years for the Clojure JIRA patch (
http://dev.clojure.org/jira/browse/CLJ-428) that will make it possible for
me to hook this behavior directly into Clojure's subseq when called on the
priority map.  Still waiting, so for now, you have to explicitly call
.priority->set-of-items on the priority map and work with that object.

--Mark


On Fri, Apr 7, 2017 at 8:49 PM, Brian Beckman  wrote:

> I have found a few data types in Clojure that support search and priority
> queues. In particular, I found
>
> Priority Maphttps://github.com/clojure/data.priority-map
> PSQhttps://goo.gl/Dw4gkV
> data.avlhttps://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.

Re: Priority Map with efficient search on values?

[Andy Fingerhut]

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 [ ] 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  wrote:

> I have found a few data types in Clojure that support search and priority
> queues. In particular, I found
>
> Priority Maphttps://github.com/clojure/data.priority-map
> PSQhttps://goo.gl/Dw4gkV
> data.avlhttps://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.

Priority Map with efficient search on values?

[Brian Beckman]

I have found a few data types in Clojure that support search and priority 
queues. In particular, I found 

Priority Maphttps://github.com/clojure/data.priority-map
PSQhttps://goo.gl/Dw4gkV
data.avlhttps://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.