лучший способ удалить элемент из списка в мультикарте - PullRequest
Новая
       52

лучший способ удалить элемент из списка в мультикарте

0 голосов
/ 07 апреля 2020

теперь он просто перебирает списки и, если список содержит значение, удаляет его из

В Scala: 

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). как улучшить сложность алгоритма?

Ответы [ 2 ]

0 голосов
/ 07 апреля 2020

Вместо удаления элемента из 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)
    }
}

Надеюсь, это поможет!

0 голосов
/ 07 апреля 2020

Вы можете уменьшить сложность времени до O(log n) (где n - количество значений в дереве), используя Красно-черное дерево . То же самое делает c ++ в его реализации std::multimap.

В примечании стороны O(n^2) может быть не совсем точным. Если у вас есть n ключей, каждый из которых содержит не более m элементов в массиве значений, ваша временная сложность составляет O(n * m). 

public void remove(V value) {
  for (List<V> list: map.values()) { // O(n)
    list.removeIf(element -> element.equals(value)); // O(m)
  }
}

Вы можете переключиться на Map<K, HashSet<V>>, что приведет вас к O(n) ... но это не удовлетворяет требованию multiset, разрешающему дублирование значений под одним ключом: 

public void remove(V value) {
  for (HashSet<V> set: map.values()) { // O(n)
    set.remove(value); // O(1)
  }
}
...