6

すべて同じキー (1 から 20) を持つ Map[Int, Int] のリストがあり、それらの内容を単一の Map[Int, Int] にマージしたいと考えています。

scalaz ライブラリから使用するマップのマージに関するスタック オーバーフローに関する別の投稿を読みました。|+|

私は次の解決策を思いつきましたが、私には不格好に思えます。

val defaultMap = (2 to ceiling).map((_,0)).toMap
val factors: Map[Int, Int] = (2 to ceiling). map(primeFactors(_)).
        foldRight(defaultMap)(mergeMaps(_, _))

def mergeMaps(xm: Map[Int, Int], ym: Map[Int, Int]): Map[Int,Int] = {
    def iter(acc: Map[Int,Int], other: Map[Int,Int], i: Int): Map[Int,Int] = {
      if (other.isEmpty) acc
      else iter(acc - i + (i -> math.max(acc(i), other(i))), other - i, i + 1)
    }
    iter(xm, ym, 2)
  }

def primeFactors(number: Int): Map[Int, Int] = {
  def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = {
    if (i > number) factors
    else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i)
    else iter(factors, rem, i + 1)
  }
  iter((2 to ceiling).map((_,0)).toMap, number, 2)
}

説明: val factors2 から 20 までの数の素因数をそれぞれ表すマップのリストを作成します。次に、これらの 18 のマップは、各キーの最大値を含む 1 つのマップに折り畳まれます。

アップデート

@folone の提案を使用して、次のコードで終了します (元のバージョンよりも確実に改善されており、Maps を HashMaps に変更する必要はありません)。

import scalaz._
import Scalaz._
import Tags._

/**
 * Smallest Multiple
 *
 * 2520 is the smallest number that can be divided by each of the numbers 
 * from 1 to 10 without any remainder. What is the smallest positive number 
 * that is evenly divisible by all of the numbers from 1 to 20?
 *
 * User: Alexandros Bantis
 * Date: 1/29/13
 * Time: 8:07 PM
 */
object Problem005 {

  def findSmallestMultiple(ceiling: Int): Int = {
    val factors = (2 to ceiling).map(primeFactors(_).mapValues(MaxVal)).reduce(_ |+| _)
    (1 /: factors.map(m => intPow(m._1, m._2)))(_ * _)
  }

  private def primeFactors(number: Int): Map[Int, Int] = {
    def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = {
      if (i > number) factors.filter(_._2 > 0).mapValues(MaxVal)
      else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i)
      else iter(factors, rem, i + 1)
    }
    iter((2 to number).map((_,0)).toMap, number, 2)
  }

  private def intPow(x: Int, y: Int): Int = {
    def iter(acc: Int, rem: Int): Int = {
      if (rem == 0) acc
      else iter(acc * x, rem -1)
    }
    if (y == 0) 1 else iter(1, y)
  }
}
4

3 に答える 3

6

この解決策は一般的なMaps では機能しませんが、 s を使用している場合は、次の方法immutable.HashMapを検討できます。merged

def merged[B1 >: B](that: HashMap[A, B1])(mergef: ((A, B1), (A, B1)) ⇒ (A, B1)): HashMap[A, B1]

this と引数のハッシュ マップをマージした新しいマップを作成します。

2 つのキーが同じ場合、指定された衝突解決関数を使用します。衝突解決関数は、常にこのハッシュ マップから最初の引数を取得し、それから 2 番目の引数を取得します。

マージされたメソッドは、トラバーサルを実行して新しい不変ハッシュ マップをゼロから再構築するよりも、平均してパフォーマンスが向上します。

使用事例：

val m1 = immutable.HashMap[Int, Int](1 -> 2, 2 -> 3)
val m2 = immutable.HashMap[Int, Int](1 -> 3, 4 -> 5)
m1.merged(m2) {
  case ((k1, v1), (k2, v2)) => ((k1, math.max(v1, v2)))
}
于 2013-02-27T19:32:47.150 に答える