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)
}

示例：如果我有源地图((10 -> 5000), (20 -> 5000), (25 -> 7000), (40 -> 13000))并将 minInterval 定义为 10，我希望得到的地图：
((10 -> 5000), (25 -> 12000), (40 -> 13000))

我发现了很多单独转换过滤键和值的键和值的示例，但到目前为止还没有一个用于删除键同时保留值的示例。

4

6 回答 6

2

该解决方案List用作中间结构。它从左到右遍历 map，如果间隔足够大，则将键值对附加到列表中，否则将列表的头部替换为新的键值对。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 
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)

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

于 2012-08-06T11:47:55.110 回答
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

要回答这个问题，基本上没有完全简单的方法可以做到这一点，因为要求并不简单。您需要在比较相邻元素并构建新地图时以某种方式遍历 SortedMap。有几种方法可以做到：

  1. 使用 fold / reduce / scan / groupBy 高阶函数：通常是首选方式，也是最简洁的方式
  2. 递归（有关大量示例，请参见http://aperiodic.net/phil/scala/s-99/）：如果使用高阶函数变得过于复杂，或者您需要的确切函数不存在，您会采取什么措施。可能比使用函数更快。
  3. Builders - 一个不错的术语，用于短暂涉足可变领域。最棒的表演; 通常相当于没有仪式的递归版本

这是我使用的尝试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 回答
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 回答
0

一个使用 Scalaz 7 的更清洁（比我的第一次尝试）的解决方案State，以及一个List存储计算状态的解决方案。使用 a可以有效地检查每个步骤中的列表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 回答