in reply to Search a hash for closest match

Hashes don't help with finding nearest, only exact matches.

You would be better using a HoAs rather than a HoHs:

$hash{ 1 } = [ 15, 49, 51, 79 ];

[download]

And then use a binary search to find the closest position.

More information about the details of your data might lead to a more efficient solution.

Ie. What is the range of the positions? How many chr/pos pairs in your hash? How many lookups do you need to do?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: Search a hash for closest match
by aquinom (Sexton) on Nov 01, 2011 at 17:40 UTC
    Okay, I'll use a HoA instead I wasn't thinking about the data structure as I was hung up on thinking about how to make an efficient algorithm to do this. I was also thinking about doing a binary search as you suggested.

    The range of positions is going to be quite large(between 1-250M for large chromosomes, 25 chromosomes) for the eQTL set but only 928,000 positions in total. My query list will be probably in the dozens at most. I will need to do a lookup for each item in my query list.

[reply]

      Given small number of searches and the ~40k values per search, you may well find that a simple linear search using List::MoreUtils::firstidx() is more than adequate for your needs.

      Indeed, you may well find that as the linear search is coded in C, that it beats a binary search in Perl.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

In Section Seekers of Perl Wisdom