Long-running averages, without the sum of preceding values

Here’s a little lunch-time diversionary math.  Suppose you want a function that takes a number, and returns the average of all the numbers it’s been called with so far.  Handy for continuously updated displays, that kind of thing. Here’s a method that will return this averaging function.

private static Func MakeAverager()
{
    float sum = 0;
    int count = 0;
    return delegate(float x)
    {
        sum += x;
        count += 1;
        return sum/count;
    };
}

It creates sum and count variables for the function to close over.  The function takes a number, x, and adds it to sum.  It increments count, and divides.  Pretty standard.

Now, let’s get crazy, and pretend this code is going on Voyager, and it’ll be running for ever.  sum will get pretty high, right?  We’ll blow through 231, the upper-bound for .Net 32-bit ints.  Sure, we could make it a long, and go up to 263, but that’s not the point.  The point is, it’ll eventually run out, because sum is too high.

I’ve been chewing on this brain-teaser for a while.  I knew there must be a way to calculate a long-running average without storing the sum and the count; it seems the average so far, and the count, should be enough, but I don’t want to resort to ((average * count) + x) / count++, because that’s the exact same problem. (Of course, count could still get so high it overflows, but that’s somewhat less likely. Hush, you.)

I finally sat down and figured it out.  The trick is, each successive x tugs your average up or down — first by a lot, but by less over time.  With each x, the average gets harder to move:  the effect each new x has on the average is inversely proportionate to the count.  We can put it like this:

average += (x - average) / count

We tug average by x - average, the distance between them, scaled down by count.  Then, add that on to average (of course, if x < average, then x – average is negative, so it’ll tug the average down).

Let’s make a new averager.

private static Func MakeNewAverager()
{
    float average = 0;
    int count = 0;
    return delegate(float x)
    {
        average += (x - average) / ++count;
        return average;
    };
}

It works the same, but it’ll take a lot longer for count to overflow than sum.

For the record, here’s the ruby I used to sketch this idea out.  Of course, in ruby, this problem is even more bogus, because ruby’s Bignum can handle any number that your machine has enough free RAM to store.  But still.

def make_averager
    sum, count = 0, 0
    lambda { |x|
        sum += x
        count += 1
        sum.to_f / count
    }
end

def make_sum_free_averager
    avg = 0.0
    count = 0
    lambda { |x|
        count += 1
        avg += (x - avg) / count
    }
end
Advertisements

Constructor Inheritance in C# and Ruby

This morning: “Surprise!  Want to conduct a job interview?”  I’ve been here a little over 3 months, but um, sure!  “Great.  He’s in the conference room right now.”  Wow, we move quick.

So, without much time to gather my thoughts for good tech-y interview questions, I printed out the resume, and I winged it.  In the middle of the interview, I flipped over his resume, and scribbled out short-hand C# like this:

class A {
public A() {
Console.WriteLine(“in A”);
}
}
class B : A {
public B() {
Console.WriteLine(“in B”);
}
}
class C : B {
public C() {
Console.WriteLine(“in C”);
}
}
new C();

I asked, “What does this print out?” You know, see if he knows which order constructor inheritance goes in. I wanted to hear, “in A, in B, in C”, but not “in C, in B, in A”.

I forget exactly what the candidate’s answer was, but it stirred up a bit of discussion, because the three of us interviewing him disagreed on the answer: one of us said it would only print “in C,” because you need to stick : base() on the B and C constructors for the inheritance to work; I agreed with the third interviewer, who said it would print “in A, in B, in C”, because constructor inheritance is automatic (with no-arg constructors). We fudged around it, laughed a bit, and the interview moved on. (Update: here’s the answer.)

Back at my desk, I had to try it out. I didn’t want to bother with a whole Visual Studio .sln and all that nonsense, so I tried it in Ruby:

class A
def initialize
puts “in A”
end
end
class B < A def initialize puts "in B" end end class C < B def initialize puts "in C" end end C.new [/sourcecode] And the output is..."in C"! Huh? That can't be right...I was sure constructors were inherited automatically! Then I realized, of course! I’m working in Ruby, and you have to explicitly call superclass methods, constructors included:

class A
def initialize
super # <- call the superclass' constructor  puts "in A" end end class B < A def initialize super # <- call the superclass' constructor puts "in B" end end class C < B def initialize super # <- call the superclass' constructor puts "in C" end end C.new [/sourcecode] Stupid Ruby! Did I find a case where C# actually works nicer than Ruby? But then I realized, this also means Ruby lets you change the order of the constructor inheritance: you can go bottom-up, if you want, or even stranger: [sourcecode language='ruby'] class A def initialize super puts "in A" end end class B < A def initialize super puts "in B" end end class C < B def initialize puts "in C" super # <- call up the chain AFTER we're done end end C.new [/sourcecode] That one prints out "in C, in A, in B". The nice thing? No rule to memorize, and more control. The down-side? More to type. But given how compact Ruby already is, I think the added control is worth it here. What do you think?
(Update: I eventually did fire up Visual Studio, and the code above printed “in A, in B, in C”, without me typing out : base(). C# inherits constructors automatically, and the superclass constructors run before subclass constructors.)