Home > Archive > Fortran > July 2006 > caching of function values: design patterns?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
caching of function values: design patterns?
|
|
| Daniel Franke 2006-07-27, 8:00 am |
|
Hi all.
I have to evaluate a continuous function at a number of discrete points. The
computation of the functions value will be quite expensive in terms of wall
clock time. (Since I'm still in the planning phase, I don't have any
timings yet, but the formula to be computed is a rather long and
complicated one.)
Due to the calling algorithm, it is known that
a) the actual number of evaluation points is finite (i.e. small)
b) the same argument will be evaluated several times
My conclusion: instead of re-evaluating the function every time, I could
cache the results and look them up afterwards. There will be a slight
overhead at the beginning, but when each argument was called at least once,
only a single cache lookup is needed.
My question: are there any recommended ways or design patterns one could
employ here? My idea (making this up as I go along):
MODULE cached_function
IMPLICIT NONE
PRIVATE
TYPE :: cache_value
REAL :: x, f_x
END TYPE
TYPE(cache_value), DIMENSION(:), POINTER :: cache
INTEGER :: nentries, nreserved
CONTAINS:
REAL function f(x)
REAL, INTENT(IN) :: x
IF (.NOT. associated(cache)) THEN
! init chache
END IF
! use a binary search function here
IF ("x in cache") THEN
! return function value
ENDIF
IF (nentries .EQ. nreserved) THEN
! increase cache size
ENDIF
! compute function
! insert into cache (sorted by x)
END MODULE
Thanks for your suggestions.
Daniel
| |
| Gordon Sande 2006-07-27, 8:00 am |
| On 2006-07-27 10:15:55 -0300, Daniel Franke <nospam@nowhere.com> said:
>
> Hi all.
>
> I have to evaluate a continuous function at a number of discrete points. The
> computation of the functions value will be quite expensive in terms of wall
> clock time. (Since I'm still in the planning phase, I don't have any
> timings yet, but the formula to be computed is a rather long and
> complicated one.)
>
> Due to the calling algorithm, it is known that a) the actual number
> of evaluation points is finite (i.e. small)
> b) the same argument will be evaluated several times
>
> My conclusion: instead of re-evaluating the function every time, I could
> cache the results and look them up afterwards. There will be a slight
> overhead at the beginning, but when each argument was called at least once,
> only a single cache lookup is needed.
>
> My question: are there any recommended ways or design patterns one could
> employ here? My idea (making this up as I go along):
>
> MODULE cached_function
> IMPLICIT NONE
> PRIVATE
>
> TYPE :: cache_value
> REAL :: x, f_x
> END TYPE
>
> TYPE(cache_value), DIMENSION(:), POINTER :: cache
> INTEGER :: nentries, nreserved
>
> CONTAINS:
> REAL function f(x)
> REAL, INTENT(IN) :: x
>
> IF (.NOT. associated(cache)) THEN
> ! init chache
> END IF
>
> ! use a binary search function here
> IF ("x in cache") THEN
> ! return function value
> ENDIF
>
> IF (nentries .EQ. nreserved) THEN
> ! increase cache size
> ENDIF
>
> ! compute function
> ! insert into cache (sorted by x)
>
> END MODULE
>
>
> Thanks for your suggestions.
>
> Daniel
The usual scheme would be a hash table, also known as a scatter store or
even an associative store. Assumes exact match on the "argument" which
may not be quite true for continuous values resulting from computation.
If you know the finite value then use it from the beginning. Hash tables
like to have adequate space, and resizing is a nuisance. For that matter
why not just table the finitely many case as part of the startup? (You
may not know them. Etc. Lots of good reasons.)
Sorting assumes that "x" is one dimensional. Otherwise use a hash table
as above or one of the multidimensional nearest neighbour schemes. Start
with k-d trees and work forward. Google is your friend.
Before others make a fuss over it you should initialize cache to NULL
as associated will not work as intended. Easy error to make on the fly
but it is a Fortran awkwardness. (one of the F95 fixes.)
| |
| Daniel Franke 2006-07-27, 7:00 pm |
| Gordon Sande wrote:
> On 2006-07-27 10:15:55 -0300, Daniel Franke said:
[color=darkred]
> The usual scheme would be a hash table, also known as a scatter store or
> even an associative store.
I thought about an associative store (e.g. a map) as well. Unfortunately, as
far as I know, in fortran I would have to come up with an implementation
myself. I can not reuse any existing implementations (reuse not in terms of
copy-and-paste and find-and-replace), correct?
> If you know the finite value then use it from the beginning. Hash tables
> like to have adequate space, and resizing is a nuisance. For that matter
> why not just table the finitely many case as part of the startup? (You
> may not know them. Etc. Lots of good reasons.)
Forgot to mention this. I do not explicitly know it, but of course I could
compute this - and the full table while I am at it - beforehand.
Good point. Thanks.
> Before others make a fuss over it you should initialize cache to NULL
> as associated will not work as intended. Easy error to make on the fly
> but it is a Fortran awkwardness. (one of the F95 fixes.)
Noted =)
To rephrase my point from above: are there any implementations of trees,
tables, maps ... available for fortran that allow to use them with any
type? That is, without using a bunch of type specific
copy-paste-implementations and a generic interface to cover them?
If, for example, there is another function I would like to cache (slightly
different argument and return types), I would have to reimplement the
caching logic again. And again. I really would like to avoid this, the
thought alone makes my skin crawl.
| |
| Steven G. Kargl 2006-07-27, 7:00 pm |
| In article <eaaefq$498ia$1@claire.desy.de>,
Daniel Franke <nospam@nowhere.com> writes:
>
> Hi all.
>
> I have to evaluate a continuous function at a number of discrete points. The
> computation of the functions value will be quite expensive in terms of wall
> clock time. (Since I'm still in the planning phase, I don't have any
> timings yet, but the formula to be computed is a rather long and
> complicated one.)
>
> Due to the calling algorithm, it is known that
> a) the actual number of evaluation points is finite (i.e. small)
> b) the same argument will be evaluated several times
>
> My conclusion: instead of re-evaluating the function every time, I could
> cache the results and look them up afterwards. There will be a slight
> overhead at the beginning, but when each argument was called at least once,
> only a single cache lookup is needed.
Have you considered a minmax polynominal approximation?
You can also approximate the complicated function via a
linear combination of Chebyshev polynominals. This usually
isn't a minmax polynominal, but it's pretty darn close.
--
Steve
http://troutmask.apl.washington.edu/~kargl/
| |
| Daniel Franke 2006-07-28, 4:00 am |
| Steven G. Kargl wrote:
> Daniel Franke writes:
>
> Have you considered a minmax polynominal approximation?
>
> You can also approximate the complicated function via a
> linear combination of Chebyshev polynominals. This usually
> isn't a minmax polynominal, but it's pretty darn close.
Not yet. Don't think it would have occurred to me, a valueable suggestion.
Thanks Steve. I think, I'll try both, the formula as is and an approximation
as suggested. Let's see.
Daniel
|
|
|
|
|