将从可变映射中删除的元素收集到第二个可变映射中的惯用方法

Question

我正在为 Scala 中缺少 Java 的 Iterator.remove() 而苦恼。特别是，我想在一次遍历大型可变映射时，删除满足谓词的元素并将它们收集到另一个可变映射中。

这是我正在尝试做的事情：

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
}

出于某些合理的原因，Scala 的 Iterator，即使在可变集合上，也没有实现 remove()。

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

不用担心第二遍的成本，使用 filter() 然后 --= 删除过滤的条目：

val 结果 = map.filter(p)

地图--=result.keys
使用分区并将新映射重新分配给旧变量：

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

我运行一些测试。正如预期的那样，第一个解决方案实际上更快，在删除条目的数量与原始地图的大小相比较小的情况下。拐点，其中两个解决方案运行大致相同的时间是谓词将原始地图分成两半的时候。第二种解决方案似乎不依赖于此，但第一种显然依赖于此。两者都是 O(n)，所以也许我在这里太挑剔了。我希望我可以在两个答案之间拆分复选标记。多亏了 Don B运行儿子和 rogue-one.

Answer 1

一种惯用的方法是使用 filterNot() / filter():

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

  val removed = map.filterNot(_._2 > 1)
  val newMap = map.filter(_._2 > 1)
}

但是，这两个调用可以合并为一个分区调用：

val (newMap, removed) = map.partition(_._2 > 1)

归根结底，更新可变集合是将过程惯用语应用到函数式语言上，并为某些类型的错误打开了大门。返回新的、不可变的集合在功能上更符合惯用语。

感谢 rogue-one 呼唤 partition() 作为一个选项。

Answer 2

如果您可以返回新的 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)

Answer 3

尝试对谓词进行 groupBy，您将得到一个包含两个键的映射：对于应该保留的键为 true，对于应该删除的键为 false。

  val p: ((String, Int)) =>  Boolean = (_._2>1)
  private val booleanToStringToInt = Map[String, Int]("one" -> 1, "two" -> 2).groupBy(p)
  val remain =  booleanToStringToInt(true)
  val removed = booleanToStringToInt(false)

将从可变映射中删除的元素收集到第二个可变映射中的惯用方法

Idiomatic way to collect elements removed from a mutable map into a second mutable map

scala

scala-collections