CODEWITHSUNDEEP
c#real-timeaggregation
toasteroven
toasteroven

Reputation: 2790

algorithm to update an aggregated value when an element changes

(I'm using C# but this isn't necessarily platform-specific)

Say I have a table of values, which are indexed by a triplet of keys (A, B, C). The values in the table are streaming in from an outside source at sporadic intervals. I want to publish aggregates over various sets of keys, e.g. calculate a sum over all values where B = b1.

This is trivial to do if I just iterate over the entire table each time, but obviously that's not efficient. What I'm wondering is, is there a particularly good way to design such a thing so that I only update sum(B = b1) when a value in the table changes that would affect this sum? It seems like I would need to create some sort of Aggregation object that maintains a list of every value that is included in that aggregation, but I feel like there might be a more elegant way that's escaping me. Something like a "real time" LINQ query...

Upvotes: 1

Views: 220

Answers (2)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86015

Use a Dictionary<TypeOfB, int>. Everytime you add a new b, do

dictionary[b] += value;

If a value changes, do

dictionary[b] += (newValue - oldValue)

Upvotes: 1

jason
jason

Reputation: 241641

Well, for the simple example that you presented, why not have an event, say, OnValueChanging that signals the value that is about to change? Then you can record the current value, say, x. Then fire another event OnValueChanged and record the new value, say, y. Then the sum that you want to update is currentSum - x + y.

Upvotes: 0

Related Questions