Git Product home page Git Product logo

range_hash's Introduction

range_hash

##Problem

Given a list of ranges, how do you effectively find if an element exist in any of them?

##Solution

[sudo] gem install range_hash

##Example

Simple

require 'range_hash'
ranges = RangeHash.new
ranges[1..3] = 'a'
ranges[10..15] = 'b'
ranges[27...30] = 'c'
ranges[7..10] = 'd'

ranges[2] #=> 'a'
ranges[15] #=> 'b'
ranges[100] #=> nil

Callbacks

require 'range_hash'
ranges = RangeHash.new
ranges.add_callback(1..13) do |elem|
  puts "#{elem} is between 1 and 3"
end
ranges.add_callback(10..15) do |elem|
  puts "#{elem} is between 10 and 15!"
end
ranges.add_callback(27...30) do |elem|
  puts "#{elem} is between 27 and 29!"
end
ranges.add_callback(7..10) do |elem|
  puts "#{elem} is between 7 and 10!"
end
ranges.add_callback(:default) do |elem|
  puts "Couldn't find a range for #{elem}"
end

ranges.call(2) #=> 2 is between 1 and 3!
ranges.call(15) #=> 15 is between 10 and 15!
ranges.call(100) #=> Couldn't find a range of 100

##Wait ... why?

Because O(log n) is better than O(N). RangeHash keeps an internal sorted array that uses a binary search to find your range. This allows you to achieve (log n) search. Another option would be to store a dense hash that stores all possible elements within the ranges, however this isn't efficient in terms of memory usage. This is great happy medium.

On-top of that, RangeHash provides some awesome functionality such as callbacks.

##Notes

  • Tested against 1.8.7, 1.9.2, 1.9.3
  • Currently does not support ranges that overlap one another.

range_hash's People

Contributors

mikelewis avatar

Stargazers

 avatar Richard Hess avatar

Watchers

 avatar James Cloos avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.