Re: Fastest way to normalize doubles and convert to float?
On Mar 6, 8:56 pm, Seungbeom Kim <musip...@bawi.org> wrote:
k04j...@gmail.com wrote:
I have a huge array of doubles. I want to normalize them to the range
-1 to 1 converting them to floats in the process. Is there a 'best' /
fastest way to do this? Does C++ provide a way out of the box?
Some of the previous answers don't normalize to [-1, +1] as specified.
class normalizer
{
double min_, max_;
public:
normalizer(double min, double max) : min_(min), max_(max) { }
double operator()(double x) const {
return (2 * x - max_ - min_) / (max_ - min_);
}
};
// use case: std::transform(begin, end, out, normalizer(min, max))
#include <algorithm>
#include <iterator>
#include <ostream>
#include <iostream>
int main()
{
double array[] = { +0.1139, +1.0668, +0.0593, -0.0956, -0.8323 };
double* array_end = array + sizeof(array) / sizeof(*array);
std::ostream_iterator<double> osi(std::cout, " ");
std::copy(array, array_end, osi);
std::cout << '\n';
double* min = std::min_element(array, array_end);
double* max = std::max_element(array, array_end);
std::transform(array, array_end, array, normalizer(*min, *max));
std::copy(array, array_end, osi);
std::cout << '\n';
}
.... and /this/ doesn't convert to float as specified.
The other thing that the OP may want to worry about is memory (and
cache) accesses. For a sufficiently huge array ( greater than
sizeof(L2 cache); which for a 1MB cache is only 128k doubles ), the
time to perform this operation is going to be dominated by the memory
accesses.
As such
a) it will definitely be worth acquiring the min and the max in a
single pass through the array (rather than the two loops implied by
min_element and max_element).
b) it may be worth copying the double array to the float array on the /
first/ loop (which finds the min and the max). That works by halving
the number of memory accesses in the second loop (because a cache line
holds twice as many doubles as floats). This will of course fail
horribly if the input values are outside the range (approx +/- 1E38
from memory) of a float. It wouldn't even surprise me to find that
making the loops be:
flt[i] := ln( dbl[i] );
and
flt[i] := 2*(max-min)( exp(flt[i]) - min - 1 )
was faster (particularly if one could get the compiler to switch off
infinity and NaN handling, and just use the floating point
instructions)
c) it may be worth making one of the loops run backwards (from high
memory to low memory). This has the advantage that the second loop
will end up re-using the cache that has just been filled by the first
loop. This is particularly effective if the array is just larger than
the cache (it means that the second loop almost entirely runs in cache
rather than thrashing the cache). On the other hand, running
backwards may well defeat any attempt by the system to prefill the
cache (which will probably assume that most arrays run forward), and
thus will be slower if the array is significantly larger than cache.
As always with performance optimizations the rules are:
1. Don't do it.
2. (for experts only) Don't do it yet.
3. PROFILE
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]