Finite Function (Follow up)
- To: mathgroup at yoda.physics.unc.edu
- Subject: Finite Function (Follow up)
- From: roger at isy.liu.se (Roger Germundsson)
- Date: Mon, 30 Sep 91 13:51:21 +0100
This is a followup to my previous posting
about finite functions:
Does anyone out there know of a good way of handling
finite functions in Mathematica?
One obvious way would be to use:
f[x1] = y1; f[x2] = y2; ...
Then you would have make f a global variable (!!!)
This approach is implemented in BuildFunction[] below.
Another obvious choice would be to use lists as follows
{{x1, y1}, {x2, y2}, ... }
and then search this list. This is implemented in
Lookup[] below. However this will run at least one
order of magnitude slower than the first approach.
What I think is really needed is something like Maples
table construct which build a list representation, but
packs a hashing function along with that (This is probably
the way Mathematica has implemented the approach
f[x1] = y1, ... ). This would enable you to send such
objects as arguments to functions and also receive those.
See below for implementation and experimental data:
***** Stuff deleted *****
// Roger Germundsson (roger at isy.liu.se)
Thanks everyone (R.Maeder, Bill MacGregor, pkatula at wri.com)
for your responses.
Summary:
(R.Maeder) One can use the first approach above without the
pitfalls of global variables by making them unique.
This can be done in the Module[ ] construct
of V2.0 or as below in V1.2.
(Bill MacGregor)Another way to get the speed of the first approach
above and still not have to use global variables
is to view a function as a list of rules and
then use Dispatch[] to pack the hashing function
along with that. (Or whatever optimazition is
performed). Note: Dispatch[] is used automatically
if the first approach is taken.
(pkatula at wri.com) Basically that the first approach can be used and
that contexts can be used to ensure the global
symbols to be unique.
See, below for revised implementation and result:
(For those who want to know this is V1.2 on a Sparc2 16MB)
// Roger Germundsson (roger at isy.liu.se)
(*
These functions assume that fun looks like:
{ { x1, f[x1] }, ... ,{ xn, f[xn] } }
*)
Lookup[ fun:{{_,_}...}, key_ ] :=
Block[{pos},
(* Assume only one match .. since function *)
pos = Flatten[ Position[ fun, {key,_}] ];
Last[ Last[ fun[[ pos ]] ] ]
]
BuildGlobalFunction[ fun:{{_,_}...}, fname_ ] :=
(
Apply[ (fname[#1] = #2)&, fun, {1} ];
fname
)
BuildUniqueFunction[data:{{_, _}...}] :=
Block[{sym = Unique[], key = Unique[]},
Apply[ (sym[#1] = #2)&, data, {1} ];
Function[Release[key],Release[ sym[key] ]]
]
flist = Table[ {i,Random[Integer,{0,10}]}, {i,1,100}];
TLook[k_] :=
Timing[
Do[ Lookup[flist, Random[Integer,{1,100}] ], {k} ];
][[1]]/Second
TGlobFun[k_] :=
Timing[
(
Clear[F];
BuildGlobalFunction[flist,F];
Do[ F[ Random[ Integer, {1,100}] ], {k} ];
)
][[1]]/Second
TUniFun[k_] :=
Timing[
(
Clear[F];
F = BuildUniqueFunction[flist];
Do[ F[ Random[ Integer, {1, 100} ] ], {k} ];
)
][[1]]/Second
(* Results:
Mathematica (sun4) 1.2 (June 13, 1990) [With pre-loaded data]
by S. Wolfram, D. Grayson, R. Maeder, H. Cejtin,
S. Omohundro, D. Ballman and J. Keiper
with I. Rivin and D. Withoff
Copyright 1988,1989,1990 Wolfram Research Inc.
-- X11 windows graphics initialized --
In[1]:= <<FiniteFunction1.m
In[2]:= tunifun = Table[ TUniFun[ k ], {k, 1000, 10000, 1000} ]
Out[2]= {0.633333, 1.15, 1.61667, 2.16667, 2.71667, 3.23333, 3.61667,
> 4.11667, 4.73333, 5.23333}
In[3]:= tglobfun = Table[ TGlobFun[ k ], {k, 1000, 10000, 1000} ]
Out[3]= {0.583333, 0.933333, 1.36667, 1.78333, 2.2, 2.65, 3.06667,
> 3.45, 3.86667, 4.28333}
In[4]:= tlook = Table[ TLook[ k ], {k, 1000, 10000, 1000} ]
Out[4]= {9.51667, 19.6667, 29.4333, 39.3333, 49.4, 59.0833, 68.9667,
> 78.8, 88.4167, 98.5333}
*)