find_bal.rb

#Given an array of numbers i.e. [1,2,3...1000], find out all possible combinations that add up to any given number i.e. 51437

#start with empty db
# start with 1st transaction -> write {key = 1, value => 1 }
# for the second transaction write { key => 1.2 => value => 3 }
#                                  { key = 2, value => 3 }
# for the third transaction write { key => 1.2.3 => value => 6 }
#                                  { key = 1.3, value => 4 }
#                                  { key = 2.3, value => 5 }
#                                  { key = 3, value => 3 }

# and so on ..
# i.e. each time a transaction is received, 
#     take all the keys in the DB and make a copy of them
#     add the latest transaction id to each new key
#     and increment the value by the value of the transaction.

# recording each new transaction is in O(n) time

# Then it's a simple search for the right total which is very fast.
# Compute on write works well for such situations.

# Redis is just an example. Can use mongo if RAM is a problem.

# below is pseudo ruby i.e. it runs, but uses serially incrementing keys instead

require 'redis'

r = Redis.new
r.flushdb
bals = ([1,2,3,4,5,6,7,8,9,10] * 100).flatten
puts bals.count
bals.each_with_index do |b,i|
  t = Time.now
  max_key = r.keys.max || 0
  r.keys.each_with_index do |k,j|
    new_key = max_key.to_i + j + 1
    r[new_key] = r[k].to_i + b
  end
  insert_key = (r.keys.max || 0).to_i + 1
  r[insert_key] = b
  puts "item no #{i} done in #{(Time.now - t).round(2)} secs"
end