1

次のシグネチャを使用してメソッドを作成しようとしています。 

def buildSumMap(minInterval:Int, mappes:SortedMap[Int, Long]):SortedMap[Int, Long] = {...}

(key:Int,value:Long)メソッド内で、 「マップ」の各ペアに次の疑似コードを適用して、新しいマップを返したいと考えています 。

If(key + minInterval > nextKey) {
    value += nextValue
}
else {
    //Forget previous key(s) and return current key with sum of all previous values
    return (key, value)
}

例: ソース Map が((10 -> 5000), (20 -> 5000), (25 -> 7000), (40 -> 13000))あり、minInterval を 10 に定義した場合、結果の Map は次のようになります。
((10 -> 5000), (25 -> 12000), (40 -> 13000))

キーと値を個別にフィルタリングするキーと値を変換する例はたくさん見つかりましたが、値を保持しながらキーを削除する例は今のところありません。

4

6 に答える 6

2

このソリューションはList、中間構造として使用します。マップを左から右にトラバースし、間隔が十分に大きい場合はキーと値のペアをリストに追加します。それ以外の場合は、リストの先頭を新しいキーと値のペアに置き換えます。TreeMapファクトリーメトッドは最後にリストを逆にします。 

import collection.immutable._

def buildSumMap(minInterval:Int, mappes:SortedMap[Int, Long]):SortedMap[Int, Long] = 
  TreeMap(
    mappes.foldLeft[List[(Int, Long)]] (Nil) { 
      case (Nil, nextKV) => nextKV :: Nil
      case (acc @ (key, value) :: accTail, nextKV @ (nextKey, nextValue)) =>
        if (nextKey - key < minInterval)
          (nextKey -> (value + nextValue)) :: accTail
        else
          nextKV :: acc
    } : _*
  )
于 2012-08-06T12:48:37.773 に答える
1

質問に答えるために、要件が単純ではないため、基本的にこれを行うための完全に単純な方法はありません。隣接する要素を比較しながら、SortedMapを何とか繰り返して、新しいマップを作成する必要があります。それを行うにはいくつかの方法があります。

  1. fold / reduce / scan / groupBy高階関数を使用する：一般的に推奨される方法であり、最も簡潔です
  2. 再帰（多くの例についてはhttp://aperiodic.net/phil/scala/s-99/を参照）：高階関数の使用が複雑になりすぎたり、必要な正確な関数が存在しない場合に頼る方法。関数を使用するよりも高速な場合があります。
  3. ビルダー-可変土地への簡単な進出を表す良い用語です。最高のパフォーマンス; 多くの場合、式典なしの再帰バージョンと同等です

これが私の試みscanLeftです：

def buildSumMap(minInterval: Int, mappes: SortedMap[Int, Long]) = 
  SortedMap.empty[Int, Long] ++ mappes.toSeq.tail.scanLeft(mappes.head){
    case ((k1, v1), (k2, v2)) => if (k2 - k1 > minInterval) (k2,v2) else (k1,v2)
  }.groupBy(_._1).mapValues(_.map(_._2).sum)

複雑に見えますが、実際には、何をして何をするかを理解すればscanLeft、groupBy他の場所で調べることができます。基本的に、左からシーケンスをスキャンしてキーを比較し、ギャップが小さすぎる場合は左のキーを使用して、キーに従ってタプルをグループ化します。

TLDR：重要なのは、コレクションライブラリに組み込まれている関数を学ぶことです。これにはある程度の練習が必要ですが、とても楽しいです。

于 2012-08-06T13:00:33.767 に答える
1

私はアルゴリズムの部分を分割しようとしました:

import scala.collection._

val myMap = SortedMap((10 -> 5000), (20 -> 5000), (25 -> 7000), (40 -> 13000)).mapValues(_.toLong)


def filterInterval(minInterval: Int, it: Iterable[Int]):List[Int] = {
    val list = it.toList
    val jumpMap = list.map(x => (x, list.filter( _ > x + minInterval))).toMap.
        filter(_._2.nonEmpty).mapValues(_.min)

    def jump(n:Int): Stream[Int] = jumpMap.get(n).map(j => Stream.cons(j, jump(j))).getOrElse(Stream.empty)

    list.min :: jump(list.min).toList
}


def buildSumMap(minInterval:Int, mappes:Map[Int, Long]):Map[Int,Long] = {
    val filteredKeys: List[Int] =  filterInterval(minInterval, mappes.keys)

    val agg:List[(Int, Long)] = filteredKeys.map(finalkey => 
        (finalkey,mappes.filterKeys(_ <= finalkey).values.sum)
    ).sort(_._1 < _._1)

    agg.zip((filteredKeys.min, 0L) :: agg ).map(st => (st._1._1, st._1._2 - st._2._2)).toMap
}

     buildSumMap(10, myMap)
于 2012-08-06T12:43:39.900 に答える
1 
import scala.collection.SortedMap

def buildSumMap(minInterval:Int, mappes:SortedMap[Int, Long]):SortedMap[Int, Long] = {
  def _buildSumMap(map: List[(Int, Long)], buffer: List[(Int, Long)], result:SortedMap[Int, Long]): SortedMap[Int, Long] = {
    def mergeBufferWithResult = {
        val res = buffer.headOption.map { case (k, v) =>
            (k, buffer.map(_._2).sum)
          }
        res.map(result + _).getOrElse(result)
    }

    map match {
        case entry :: other =>
          if(buffer.headOption.exists(entry._1 - _._1 < minInterval)) {
            _buildSumMap(other, entry :: buffer, result)
          } else {
            _buildSumMap(other, entry :: Nil, mergeBufferWithResult)
          }
        case Nil =>
          mergeBufferWithResult
    }
  }
  _buildSumMap(mappes.toList, List.empty, SortedMap.empty)
}

val result = buildSumMap(10 , SortedMap(10 -> 5000L, 20 -> 5000L, 25 -> 7000L,  40 -> 13000L))

println(result)

//Map(10 -> 5000, 25 -> 12000, 40 -> 13000)

于 2012-08-06T11:47:55.110 に答える
0

Scalaz 7 の を使用した (私の最初の試みよりも) はるかにクリーンなソリューションStateとList、計算の状態を保存するための です。を使用すると、各ステップでリストListの を効率的に検査し、必要に応じて変更できます。head

def f2(minInterval: Int): ((Int, Int)) => State[List[(Int, Int)], Unit] = {
  case (k, v) => State {
    case (floor, acc) :: tail if (floor + minInterval) > k =>
      ((k, acc + v) :: tail) -> ()
    case state => ((k, v) :: state) -> ()
  }
}

scala> mappes.toList traverseS f2(10) execZero
res1: scalaz.Id.Id[List[(Int, Int)]] = List((40,13000), (25,12000), (10,5000))
于 2012-08-06T14:12:01.103 に答える
0

別の見方を次に示します。

def buildSumMap(map: SortedMap[Int, Int], diff: Int) = 
  map.drop(1).foldLeft(map.take(1)) { case (m, (k, v)) =>
    val (_k, _v) = m.last
    if (k - _k < diff) (m - _k) + (k -> (v + _v))
    else m + (k -> v)
  }
于 2012-08-06T13:58:57.850 に答える