XP is just a number PerlMonks

### Re: calculate average from range of hash values (optimize)(reply)

by demerphq (Chancellor)
 on Jul 27, 2003 at 14:58 UTC ( #278228=note: print w/replies, xml ) Need Help??

Hmm, well this happens to be very similar to a problem that I have been working on. With respect to this node the primary difference btween our problems is that I cant simply return undef if start_pos is not in the hash. In other words my problem would be to find the average of the values where the keys are within a range, regardless of whether the first and last actually exists.

Of the solutions posted here the Zaxo/aristotle(1)/browseruk(1) variant fits. For reasons decribed in the reply to Aristotle I've ruled his second one out, and Ive ruled browserUk's second out because my data set isn't contiguous at all. Likewise I didn't include the two variants that take arrays as arguments as they don't scale well for scattered data sets. (IMO, they are welcome and encouraged to adjust their code and add it to the benchmark.)

My initial reaction to this node and your code was that it was way more complex that it seemed to need to be. And for this reason I put it in the benchmark even though it violates my rule by returning undef if the start pos doesnt exist. One might guess that this requirement would make your code infinitely fast in this case, (as does browseruks variant) but even then its one of the slowest in my benchmark, furthermore, as far as I can tell this code is incorrect, in that the sort statement does a lexicographical sort and not a numerical sort and thus would include 11 in the average of 1..3 in a data set containing 1..11. (Your test case happens to hide this, a good example of the difficulties in doing a really good comparative benchmark.)

My first solution was dem1. Its a naive single pass through the data set, filtering out keys whose value ar out of range, and keeping a count and sum for the final calculation. The second solution I did was dem2 which uses the sum() routine from List::Util. The third solution I did was a perl algorithm written to be easily translatable to C. It uses caching to speed itself up, using binsearch and a linear walk to do its business. The fourth version is the third translated as directly to C as possible. For these version I normally would use a class (or a tie) to handle the cache, thus being able to spoil the cache when an insert occurs. Instead the code currently has a fourth parameter to force a cache reset.

When you benchmark the dataset you test against is critical. Does it represent your actual data? Have you tested the behaviour as it changes? For instance in the results I will show below, the cached c/perl versions massively outperform the others. However this would almost certainly would not be true if the \$data hash was changing regularly. Again, the behaviour of ari1 over the different test sets is interesting as it shows how subject it is to the spareness of the data set involved. Which just goes to show that truly optimizing this will require far more information about typical data involved. Is the data sparse? Dense? Does it change often in between lookups, will really govern optimizing this code. It would be nice to know a bit more about the usage pattern. Anyway, ive attempted to allow for a decent range of behaviour testing in my version of the benchmark. Although I havent touched the spoiled cache aspect.

In order to make this easier to read ill post the final result her and ill put the code and overall results in two replies with readmores. Heres the overall benchmark, of the average of the keys (1..100,10000 .. 30000,100000..150000) with the range 1..150000.

```Testing 1 - 150000
ari1  = 0.500910
orig  = 0.500190
demc  = 0.500910
ofix  = 0.500910
buk   = 0.500910
dem1  = 0.500910
demcp = 0.500910
dem2  = 0.500910
Benchmark: running ari1, buk, dem1, dem2, demc, demcp, ofix, orig,
each for at least 2 CPU seconds...
ari1:  2 wc secs ( 2.16 usr +  0.00 sys =  2.16 CPU) @  3.70/s (
+n=8)
buk:  2 wc secs ( 2.18 usr +  0.00 sys =  2.18 CPU) @  3.66/s (
+n=8)
dem1:  2 wc secs ( 2.03 usr +  0.00 sys =  2.03 CPU) @  5.41/s (
+n=11)
dem2:  3 wc secs ( 2.24 usr +  0.00 sys =  2.24 CPU) @  3.57/s (
+n=8)
demc:  2 wc secs ( 2.03 usr +  0.00 sys =  2.03 CPU) @ 1424.99/s
+ (n=2897)
demcp:  2 wc secs ( 2.09 usr +  0.00 sys =  2.09 CPU) @ 14.33/s (
+n=30)
ofix:  2 wc secs ( 2.20 usr +  0.00 sys =  2.20 CPU) @  3.18/s (
+n=7)
orig:  2 wc secs ( 2.06 usr +  0.00 sys =  2.06 CPU) @  3.39/s (
+n=7)
Rate   ofix   orig   dem2    buk   ari1   dem1  demcp   demc
ofix  3.18/s     --    -6%   -11%   -13%   -14%   -41%   -78%  -100%
orig  3.39/s     7%     --    -5%    -7%    -8%   -37%   -76%  -100%
dem2  3.57/s    12%     5%     --    -3%    -4%   -34%   -75%  -100%
buk   3.66/s    15%     8%     3%     --    -1%   -32%   -74%  -100%
ari1  3.70/s    16%     9%     4%     1%     --   -32%   -74%  -100%
dem1  5.41/s    70%    59%    52%    48%    46%     --   -62%  -100%
demcp 14.3/s   351%   322%   302%   291%   288%   165%     --   -99%
demc  1425/s 44746% 41896% 39853% 38784% 38428% 26236%  9842%     --

Anyway, this was fun. :-)

---
demerphq

<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

Replies are listed 'Best First'.
Re: calculate average from range of hash values (optimize)(results)
by demerphq (Chancellor) on Jul 27, 2003 at 20:00 UTC

Here are the results of the benchmark code contained in the sister node to this one. As I state there the primary difference between this node and the parent is that the values involed are not random numbers from 0 to 1, but rather the value of the key. This makes error checking and proving easier.

## Test Set:

```( 0 .. 100, 10000 .. 30000, 100000 .. 150000 )

## Testing 0 - 150000

RoutineAverage
ari1 94862.56
orig 114752.28
demc 94862.56
ari3 94862.56
ofix 94862.56
buk 94862.56
dem1 94862.56
demcp94862.56
dem2 94862.56

Benchmark: running ari1, ari3, buk, dem1, dem2, demc, demcp, ofix, orig, each for at least 10 CPU seconds...

TestWallclock SecsUsrSysCUsrCSysCPUN/secN
ari110.0010.01 0.00 0.00 0.0010.01 3.3033
ari311.0010.27 0.00 0.00 0.0010.27 1.8519
buk10.0010.09 0.00 0.00 0.0010.09 3.4735
dem110.0010.07 0.00 0.00 0.0010.07 5.1652
dem210.0010.20 0.00 0.00 0.0010.20 2.3524
demc11.0010.51 0.00 0.00 0.0010.511432.5215063
demcp11.0010.52 0.00 0.00 0.0010.5213.03137
ofix10.0010.10 0.00 0.00 0.0010.10 2.0821
orig10.0010.08 0.00 0.00 0.0010.08 3.3734

Comparative Results

Rateari3ofixdem2ari1origbukdem1demcpdemc
ari31.85/s---11%-21%-44%-45%-47%-64%-86%-100%
ofix2.08/s12%---12%-37%-38%-40%-60%-84%-100%
dem22.35/s27%13%---29%-30%-32%-54%-82%-100%
ari13.30/s78%59%40%---2%-5%-36%-75%-100%
orig3.37/s82%62%43%2%---3%-35%-74%-100%
buk3.47/s87%67%47%5%3%---33%-73%-100%
dem15.16/s179%148%119%57%53%49%---60%-100%
demcp13.0/s604%527%454%295%286%276%152%---99%
demc1433/s77294%68825%60806%43371%42349%41218%27655%10895%--

---
demerphq

<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
Re: calculate average from range of hash values (optimize)(the code)
by demerphq (Chancellor) on Jul 27, 2003 at 18:40 UTC

The code for the benchmark. I happen to have a hacked Benchmark.pm that includes support for HTML benchmarks (er, I do now anyway, thats why the code took so long to follow, I sort of got distracted :-), so this was written with that in mind. However as posted it should run just fine on your system. (Assuming you have a C compiler and etc.)

1. I forgot to point out that I changed the way the values are set in the test set from rand() to being the same as the key. This makes spotting errors and proving correctness much easier.

---
demerphq

<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

Create A New User
Node Status?
node history
Node Type: note [id://278228]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2019-12-15 08:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?