# 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.

-
Closely related: (1072) – Mr.Wizard Jul 5 '14 at 16:59

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];
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
*)

-

You need to use InputForm to see the actual value of the numbers.

  x = -15*0.1 + 6*0.1;
InputForm[x]


Now when you wrote

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


Now 5 is actually stored in a[-0.8999999999999999] and not in a[-0.9], this is why a[-0.9] does not return the value 5 you expected. But when you wrote a[-0.8999999999999999] it did.

Now, as to why -15*0.1 + 6*0.1 == -0.9 returned True and not False, then I think this is a numerical issue. The difference was so small, that == returned true.

You can see this:

  y = -0.9;
Abs[x - y] <= \$MachineEpsilon
(*True*)

-
Hi, thanks for the answer. So if I have a Table construct to store variables, how then do I call them? – Andrew Stewart Jul 5 '14 at 1:05

Your problem arises from the way a[-0.9] is evaluated.

When you evaluate a[-0.9], Mathematica searches the down-values of a for a match to the internally stored value of -15*0.1 + 6*0.1, which as Nasser points out, is 0.8999999999999999. By "match" I mean that

MatchQ[-0.9, -15*0.1 + 6*0.1]


would have to return True, but it does not, even though

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


does.

-