core language - Implementing key-value associations in Mathematica 9 with inexact numbers for keys

I'm not sure of what type of problem my issue falls into, so I haven't been able to search forums with any success. If this has already been solved then my apologies!

Essentially I'm trying to set a list equal to a calculated value then call that list back.

-15*0.1 + 6*0.1

(* -0.9 *)


-15*0.1 + 6*0.1 == -0.9

(* True *)

a[-15*0.1 + 6*0.1] = 5

(* 5 *)

a[-0.9]


(* a[-0.9] *)

a[-0.8999999999999999`]

(* 5 *)

I've reset Mathematica 9.0.1.0 according to this guide http://support.wolfram.com/kb/3274 to no avail.

Answer

It would seem from the title that the OP is asking not only why the scheme does not work but also how to implement it. Three solutions, each with drawbacks, are given below.

An obstruction

Others have given an explanation why it doesn't work. I would add that it is also pointed out in the documentation for Equal in the Details section and under Possible Issues that the tolerance for Equal in comparing approximate machine numbers is the last seven bits ($MachineEpsilon affects the last bit in 1.):

1. == 1. + 2^6 $MachineEpsilon
1. == 1. + (2^6 + 1) $MachineEpsilon
(*
  True
  False
*)

The solution to the OP's problem would be to create a mapping key from machine reals to a set of keys satifying the condition that x == y if, and only if, MatchQ[key[x], key[y]] returns true. But I don't think this is possible. There is no way to assign keys to 1., 1.000000000000014, and 1.000000000000015 to meet the condition, since Equal is not transitive:

1.000000000000014 == 1.

1.000000000000015 == 1.
1.000000000000014 == 1.000000000000015
(*
  True
  False
  True
*)

Near solutions

Requirements: The first two solutions depend on the keys being far apart, enough so that Equal is effectively transitive, and the third does not have this requirement. The first one is somewhat slow but easy to understand. The second is fairly quick but has a potentially serious drawback. For the third, the keys do not have to be far apart but all the data needs to be known at once; to add key/value pairs requires recomputing the whole dictionary. It's somewhat fast to recompute, so if this not done very often, it may be a practical solution.

Note well, though, that in any solution, the potential for round-off error to land a number closer to the wrong key is always a concern.

A good-enough solution - Use `Condition` and `Equal`

Here is the easiest solution to understand:

a[x_ /; x == key] = value

For a dictionary of 10^4 elements,

SeedRandom[1];
keys = RandomReal[1, 10^4];
values = RandomInteger[{1, 10}, {10^4, 2}];

it takes over a minute to initialize all the values for a. In accessing a[x], Mathematica basically does a linear search through the 10^4 downvalues of a. Here's the timing for the last one, which is about the same time it takes to look up a key for which a is undefined:

a[keys[[-1]]] // AbsoluteTiming
(*
  {0.006379, {10, 8}}
*)

On average, assuming only defined values are looked up, the expected time would be half that or 0.00319 sec. If a[x] is executed for a lot of undefined keys x, then the average time would increase.

Faster - `Round` off the keys

One can use Round (or Floor etc.) to map a real x onto a key. The function associated with the option value for "KeyFunction" does this. One potential issue is that a function such as Round segments the real numbers into intervals. Two input data may be very close but on opposite sides of the boundary.

ClearAll[setupdict, associate];

Options[setupdict] = {
   Tolerance     -> 2^6 $MachineEpsilon, 
   "KeyFunction" -> Function[{x, tol}, Round[x, 2^Ceiling@Log2[Abs[x] tol]]]};
setupdict[a_Symbol, OptionsPattern[]] := (
   ClearAll[a];
   Options[a] = {
     Tolerance     -> OptionValue[Tolerance],
     "KeyFunction" -> (Evaluate[OptionValue["KeyFunction"][#, OptionValue[Tolerance]]] &)};
   With[{keyfn = OptionValue[a, "KeyFunction"]}, 
    a[x_?NumericQ] := With[{key = keyfn[x]},

      a[key] /; ! MatchQ[x, key]
      ]
    ]
   );
associate[a_, x_?NumericQ, value_] :=
 With[{key = OptionValue[a, "KeyFunction"][x]},
  a[key] = value
  ]

It's much faster on 10^4 elements.

setupdict[a];
MapThread[
   associate[a, ##] &,
   {keys, values}
   ]; // AbsoluteTiming

{0.142925, Null}

The access time is roughly constant and the average time is low:

First@AbsoluteTiming[a /@ keys;] / 10^4

(*
  0.0000119601
*)

OP's example:

setupdict[a];
associate[a, -15*0.1 + 6*0.1, {"my", "list"}]
(*
  {"my", "list"}
*)


a[-0.9]
(*
  {"my", "list"}
*)

However, some day a key being on the boundary of Round will cause an error.

Faster, if all data is known - Use `Nearest`

If all the data is known at the beginning, one can use Nearest to construct a look-up function is that is very fast.

ClearAll[setupdict];

Options[setupdict] = {Tolerance -> 2^6 $MachineEpsilon};
setupdict[a_Symbol, data_, OptionsPattern[]] := (
   ClearAll[a];
   Options[a] = {Tolerance -> OptionValue[Tolerance],
     "Dictionary" -> Nearest[data]};
   With[{dictfn = OptionValue[a, "Dictionary"]}, 
    a[x_?NumericQ] := dictfn[x, {1, OptionValue[Tolerance]}]
    ]
   );

Example

ClearAll[a];
setupdict[a, keys -> values]; // AbsoluteTiming
(*
  {0.011551, Null}
*)

Example

a[keys[[1]]]
a[keys[[1]] + 2^6 $MachineEpsilon]

(*
  {{6, 8}}
  {{6, 8}}
*)

Undefined at 0.1 returns an empty list:

a[0.1]
(*
  {}
*)

Timing -- quite fast:

First@AbsoluteTiming[a /@ keys] / 10^4
(*
  5.1667*10^-6
*)

Blog

Search This Blog