В продолжение вашей идеи использовать целые числа для представления битовых наборов. Вы используете фактический оператор по модулю? Вы также можете использовать битовые маски, чтобы проверить, есть ли какое-то число в битах. (Обратите внимание, что на JVM они оба являются одной инструкцией, так что кто знает, что там происходит?)
Другое потенциальное значительное улучшение заключается в том, что, поскольку ваша работа с диапазоном карт является ассоциативной, вы можете сохранять вычисления, повторно используя предыдущие. Например, если вы объединяете A,B,C, но уже скомбинировали, скажем, A,C в AC, например, вы можете просто объединить B с AC.
Следующий код реализует обе идеи:
type MapT = Map[String,Int] // for conciseness later
@scala.annotation.tailrec
def pow2(i : Int, acc : Int = 1) : Int = {
// for reasonably sized ints...
if(i <= 0) acc else pow2(i - 1, 2 * acc)
}
// initial set of maps
val maps = List(
Map("x" -> 1, "y" -> 2),
Map("x" -> 1, "a" -> 4),
Map("x" -> 1, "b" -> 5)
)
val num = maps.size
// any 'op' that's commutative will do
def combine(m1 : MapT, m2 : MapT)(op : (Int,Int)=>Int) : MapT =
((m1.keySet intersect m2.keySet).map(k => (k -> op(m1(k), m2(k))))).toMap
val numCombs = pow2(num)
// precomputes all required powers of two
val masks : Array[Int] = (0 until num).map(pow2(_)).toArray
// this array will be filled, à la Dynamic Algorithm
val results : Array[MapT] = Array.fill(numCombs)(Map.empty)
// fill in the results for "combinations" of one map
for((m,i) <- maps.zipWithIndex) { results(masks(i)) = m }
val zeroUntilNum = (0 until num).toList
for(n <- 2 to num; (x :: xs) <- zeroUntilNum.combinations(n)) {
// The trick here is that we already know the result of combining the maps
// indexed by xs, we just need to compute the corresponding bitmask and get
// the result from the array later.
val known = xs.foldLeft(0)((a,i) => a | masks(i))
val xm = masks(x)
results(known | xm) = combine(results(known), results(xm))(_ + _)
}
Если вы напечатаете полученный массив, вы получите:
0 -> Map()
1 -> Map(x -> 1, y -> 2)
2 -> Map(x -> 1, a -> 4)
3 -> Map(x -> 2)
4 -> Map(x -> 1, b -> 5)
5 -> Map(x -> 2)
6 -> Map(x -> 2)
7 -> Map(x -> 3)
Конечно, как и все остальные, он со временем взорвется, когда количество входных карт увеличится.