Recursive Sum «
»


Code: ,
1 comment

In #ruby on Freenode, platzhirsch asked about how to total an array of Transactions when the Transactions may have parents. The two obvious approaches have pitfalls when there are a lot of Transactions, and he said he expects to have 23 million that may be deeply nested. Here’s his sample code:


class Transaction
attr_accessor :amount, :parent

def initialize(amount, parent)
self.amount = amount
self.parent = parent
end
end

t1 = Transaction.new(100, nil)
t2 = Transaction.new(250, t1)
t3 = Transaction.new(300, t2)

current = t3
all = []
while current != nil
all << current current = current.parent end total = all.inject(0) { |total, transaction| total + transaction.amount }

Spoiler warning: last chance to solve it for yourself before I dig into the solutions.

This code sample expressed the first obvious solution: build a list of all the transactions. The problem is that you'll spend RAM and time building a data structure you expect to use once.

One person offered an addition to Transaction to solve it recursively, the second obvious approach:


class Transaction
def total_amount
(parent ? parent.total_amount : 0) + amount
end
end

This pitfall is that this risks blowing the stack when Transactions are deeply nested: recurse too many times and you'll run out of RAM. It's also super-specialized, if you want to do anything else with every Transaction you'll have to write another custom method. And despite the specialization, you might end up writing this logic again if you have a collection of child transactions:


t4 = Transaction.new(400, nil)

total = [t3, t4].inject(0) { |sum, t| sum + t.amount }

Here's my approach:


# because Transaction doesn't have any logic, I made a shorter version:
Transaction = Struct.new(:amount, :parent)

# And I like using powers of two when testing recursion, because the sum
# will come out obviously different for different combinations of items:
t1 = Transaction.new 1, nil
t2 = Transaction.new 2, t1
t3 = Transaction.new 4, t2
t4 = Transaction.new 8, nil

TransactionEnumerator = Struct.new(:collection) do
include Enumerable

def each
collection.each do |t|
yield t
yield t while t = t.parent
end
end
end

ts = TransactionEnumerator.new [t3, t4]
total = ts.inject(0) { |total, transaction| total + transaction.amount }

This little wrapper doesn't recurse, doesn't duplicate Transactions, and doesn't build a data structure. It can work on any collection of Transactions that exposes each, the sum logic is expressed only once and separately from the control flow, and it provides the powerful Ruby Enumerable interface.

Hope you enjoyed this little puzzle! If you had an alternate solution, please wrap it in <code></code> tags below.

And let me tag on my own fun exercise: add an ID field to Transaction and implement TransactionEnumerator#uniq yield the transactions exactly once, so this returns true (Array has #uniq, but you shouldn't assume the collection is an Array):


TransactionEnumerator.new([t1, t1]).uniq == [t1]


Comments

  1. I would do a running sum, just loads maximum 2 transactions at a time.


    current = t3
    total = current.amount
    while current != nil
    current = current.parent
    total += current.amount
    end

    This is not very rubyesque, so first I wrap it:


    class Transaction
    def total
    current = this
    sum = current.amount

    while current != nil
    current = current.parent
    sum += current.amount
    end

    sum
    end
    end

    Then I simplify:


    class Transaction
    def total
    sum = amount
    current = this
    sum += current.amount while current = current.parent
    sum
    end
    end

Leave a Reply

Your email address will not be published.