Status of bounded search on sorted-map?

[Rob Lachlan]

About a year and a half ago, there was some discussion about having a
function that would enable some kind of bounded search on a sorted
map:

http://groups.google.com/group/clojure/browse_thread/thread/949cae6c085d3d39/65b4082085c19a60?q=

Does this exist, currently? I haven't looked at the gory details of
PersistentTreeMap, so I don't know how difficult this would be to do.
Intuitively though, since we have the keys are in a sorted tree, I
thought that it would be possible to have a bounded search in
something like O(log n).

Rob

p.s. I asked a related question on stackoverflow:

http://stackoverflow.com/questions/1981859/finding-keys-closest-to-a-given-value-for-clojure-sorted-maps

[Sean Devlin]

Use a combination of take-while & key

(take-while (comp your-pred key) sorted-map)

You could also use drop while as needed.

I've got a blog post where I use this to solve the knapsack problem:

http://fulldisclojure.blogspot.com/2009/12/uses-for-takedrop-while.html

I've got some other stuff, too. Send me a note if you need more than
this.

Sean

On Dec 30, 5:37 pm, Rob Lachlan <robertlach...@gmail.com> wrote:
> About a year and a half ago, there was some discussion about having a
> function that would enable some kind of bounded search on a sorted
> map:
>

> http://groups.google.com/group/clojure/browse_thread/thread/949cae6c0...

>
> Does this exist, currently?  I haven't looked at the gory details of
> PersistentTreeMap, so I don't know how difficult this would be to do.
> Intuitively though, since we have the keys are in a sorted tree, I
> thought that it would be possible to have a bounded search in
> something like O(log n).
>
> Rob
>
> p.s.  I asked a related question on stackoverflow:
>

> http://stackoverflow.com/questions/1981859/finding-keys-closest-to-a-...

[Rob Lachlan]

This would work, but would require iterating over the keys, for
something like O(n) performance. I'm hoping that we can do better,
since the keys are already in an ordered collection.

[Rob Lachlan]

I should have said: since the keys are already in a tree. If they
were in a linked list, I'd expect to have to iterate over most of the
list.

[Sean Devlin]

Do you need persistence? There's a solution in java.util in Java 6.

[Rob Lachlan]

Thanks for the pointer. I had a feeling that java world had something
like this, but I'd much prefer to be able to do this from clojure.
Appreciate the info, though.

[Timothy Pratley]

2009/12/31 Rob Lachlan <robert...@gmail.com>:

> About a year and a half ago, there was some discussion about having a
> function that would enable some kind of bounded search on a sorted

> Does this exist, currently?  I haven't looked at the gory details of

subseq and rsubseq provide efficient bounded searching.
I don't see the need for find or seek as that is really just (first (subseq sm))

For your particular problem (find closest) a combination of first
subseq >= and first rsubseq <= will find you the two best candidates
on either side, and thus which is closest. However this is slightly
more work than if you could just do one efficient search and then
access the key to the other side of the test... which is a different
proposition all together than bounded search but if it is useful
sounds easy enough to expose. Currently you can access the tree itself
(.tree sm) works, but you can't find out what's to the left or right
because those are private. Do you want to navigate the tree, or would
a left and right search suffice?

Regards,
Tim.

[Rob Lachlan]

Thanks very much, that makes a lot of sense. I looked through the
java code for PersistentTreeMap, and indeed those methods are private.

I think that I'll be happy with subseq and rsubseq. Being a noob, it
hadn't occured to me that I could do that.

On Dec 30, 8:04 pm, Timothy Pratley <timothyprat...@gmail.com> wrote:
> 2009/12/31 Rob Lachlan <robertlach...@gmail.com>: