时间戳

首页 > 解决方案 > 从多图列表中删除元素的最佳方法

java - 从多图列表中删除元素的最佳方法

问题描述

现在它只是遍历列表，如果列表包含该值，则将其从

在斯卡拉：

trait MultiMap[K, V] {

  final val map: mutable.Map[K, ArrayBuffer[V] = ...


  def values(): Seq[V] = ...

  def remove(value: V) = 
    for {
      (_, buff) <- map if buff.contains(value)
    } 
      buff -= value
}

在 Java 中：


class MultiMap<K, V> {

    private final Map<K, ArrayList<V>> map = ...;

    public void remove(V value) {
        for (ArrayList<V> list: map.values()) {
            if (list.contains(value)) {
                list.remove(value);
                list.trimToSize();
            } 
        }
    }

}

这两种方法都有 O(n^2) 复杂度。如何提高算法的复杂度？

标签： javascalaperformancemultimap

解决方案

您可以尝试使用操作ArrayBuffer，而不是在检查项目是否存在后将其删除：filter

trait MultiMap[K, V] {
    private final val map: mutable.Map[K, ArrayBuffer[V]] = mutable.Map.empty[K, ArrayBuffer[V]]
    def values(): Seq[V] = map.values.flatten.toSeq
    def remove(value: V): Unit = map.values.foreach(_.filter(_ != value))
}

它不会是O(N^2)值N的总数，而是因为filter每次都会创建新的缓冲区实例，这可能是另一个性能下降。

更新

另一种选择，为了几乎O(1)或更精确地O(M)实现M值重复的地方，是创建另一个索引或映射，但对于它们所在的值和信息（主映射中的键和缓冲区中的索引）：

import scala.collection.mutable._

trait MultiMap[K, V] {
    private final val map: Map[K, ArrayBuffer[V]] = Map.empty
    private final val valuesIndex: Map[V, ArrayBuffer[(K, Int)]] = Map.empty

    def add(key: K, value: V): Unit = {
      map += key -> map.get(key).fold(ArrayBuffer(value))(_ += value)
      valuesIndex += value -> valuesIndex.get(value).fold(ArrayBuffer(key -> 0))(_ += (key -> (map(key).length - 1)))
    }

    def remove(value: V): Unit = {
      valuesIndex.getOrElse(value, ArrayBuffer.empty).foreach {
        case (key, index) => map(key).remove(index)
      }
      valuesIndex.remove(value)
    }
}

希望这可以帮助！

推荐阅读