Beefy Boxes and Bandwidth Generously Provided by pair Networks
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??


in reply to calculate average from range of hash values (optimize)

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

    Updates:

    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.
    2. Added aristotles new variant.


    ---
    demerphq

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

Log In?
Username:
Password:

What's my password?
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?