Re: binary search trees & binning

FROM : John Stiles
DATE : Wed Apr 16 18:25:11 2008

I never thought of using a hash function to do binning. Interesting
approach.


Army Research Lab wrote:
> Have you looked at hash_multimap
> (http://www.sgi.com/tech/stl/hash_multimap.html)?  Note that the following
> code was beaten out in entourage, without compiling, testing, etc.
>
> struct eqdouble
> {
>  bool operator()(const double d1, const double d2) const
>  {
>    double diff = d1 - d2;
>    if (diff < 0.0)
>        diff = -diff;
>    return diff < 0.00001; // Or whatever other epsilon you want.
>  }
> };
>
> struct hashfunc
> {
>    // This operator hashes numbers into bins of differing ranges.
>    // If all your bins are the same size, use divide.
>    size_t operator()(const double &d) const
>    {
>        if (d < 1.0)
>            return 1.0;
>        if (d < 3.0)
>            return 2.0;
>        if (d < 35.0987)
>            return 3.0;
>        return 4.0;
>    }
> };
>
> typedef hash_multimap<double, double, hashfunc, eqdouble> map_type;
>
> void lookup(const map_type& Map, const double d)
> {
>  cout << d << ": ";
>  pair<map_type::const_iterator, map_type::const_iterator> p =
>    Map.equal_range(d);
>  for (map_type::const_iterator i = p.first; i != p.second; ++i)
>    cout << (*i).second << " ";
>  cout << endl;
> }
>
> int main()
> {
>  map_type M;
>  M.insert(map_type::value_type(1.0, 1.0));
>  M.insert(map_type::value_type(2.0, 2.0));
>  M.insert(map_type::value_type(2.0, 12.0));
>  M.insert(map_type::value_type(2.0, 13.0));
>  M.insert(map_type::value_type(3.0, 16.0));
>  M.insert(map_type::value_type(35.0, 17.0));
>  M.insert(map_type::value_type(-56.9, 18.0));
>  M.insert(map_type::value_type(42.0, 127.0));
>
>  lookup(M, 1.0);
>  lookup(M, 2.0);
>  lookup(M, 35.0);
> }
>
> Thanks,
> Cem Karan
>
> _______________________________________________
>
> Cocoa-dev mailing list (<email_removed>)
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/<email_removed>
>
> This email sent to <email_removed>
>