用于收集从可变地图中移除的元素到第二个可变地图的惯用方法

Question

我正在努力解决Iterator.remove()Scala 缺少Java的问题.特别是,我希望在一个大的可变映射的单个传递中删除满足谓词的元素并将它们收集在另一个可变映射中.

这是我想要做的:

def main(args: Array[String]) {
  val map = new TrieMap[String, Integer]();
  map += "one" -> 1
  map += "two" -> 2

  // Remove all elems whose value is > 1 and put them in val removed.
  val removed = removeIf(map, _._2 > 1) 
}

def removeIf(
    map: mutable.Map[String, Integer], 
    p: ((String, Integer)) =>  Boolean): mutable.Map[String, Integer] = {

  val result = mutable.Map[String, Integer]()
  val iter = map.iterator
  while (iter.hasNext) {
    val elem = iter.next()
    if ( p(elem) ) {
      iter.remove()  // Error
      result += elem
    }
  }
  result
}

出于一些合理的原因,Iterator即使是在可变集合上,Scala 也没有实现remove().

编辑 以下提供的两个解决方案是

1. 不要担心第二次传递的成本并使用filter()然后--=删除过滤的条目:

   val result = map.filter(p)

   map - = result.keys

2. 使用分区并将新映射重新分配给旧变量:

   (result,newMap)= map.partition({case(k,v)=> ...})

我做了一些测试.正如预期的那样,当删除的条目数量与原始地图的大小相比较小时,第一种解决方案实际上更快.两个解决方案大致同时运行的拐点是谓词将原始地图分成两半.第二个解决方案似乎并不依赖于此,但第一个解决方案显然确实如此.两者都是O(n),所以也许我在这里太挑剔了.我希望我可以分开两个答案之间的复选标记.多亏了唐·布兰森和流氓一人.

Answer 1

如果您可以返回新的Map对象,则以下情况有效.该解决方案使用partition集合方法,仅使用一次传递.

scala> val map = TrieMap[String, Integer]("one" -> 1, "two" -> 2)
map: scala.collection.concurrent.TrieMap[String,Integer] = TrieMap(two -> 2, one -> 1)

scala> val (newMap, removed) = map.partition({case(_, x) => x > 1})
newMap: scala.collection.concurrent.TrieMap[String,Integer] = TrieMap(two -> 2)
removed: scala.collection.concurrent.TrieMap[String,Integer] = TrieMap(one -> 1)