Идиоматический способ собрать элементы, удаленные с изменяемой карты, во вторую изменяемую карту - PullRequest
Новая
       5

Идиоматический способ собрать элементы, удаленные с изменяемой карты, во вторую изменяемую карту

0 голосов
/ 01 мая 2018

Я борюсь с отсутствием Java в Iterator.remove() в Scala. В частности, я хочу за один проход по большой изменяемой карте удалить элементы, которые удовлетворяют предикату, и собрать их в другую изменяемую карту.

Вот что я пытаюсь сделать: 

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().

Редактировать Ниже представлены два решения:

  1. Не беспокойтесь о стоимости второго прохода и используйте filter (), а затем --=, чтобы удалить отфильтрованные записи:

    val результат = map.filter (p)

    карта - = result.keys

  2. Используйте раздел и переназначьте новую карту старой переменной:

    (результат, newMap) = map.partition ({case (k, v) => ...})

Я провел несколько тестов. Как и ожидалось, первое решение на самом деле быстрее, в случаях, когда количество удаленных записей меньше по сравнению с размером исходной карты. Точка перегиба, где два решения работают примерно в одно и то же время, - это когда предикат разделяет исходную карту примерно пополам. Второе решение, кажется, не зависит от этого, но, очевидно, первое. Оба O (n), так что, возможно, я здесь слишком разборчив. Я хотел бы разделить галочку между двумя ответами. Спасибо и Дону Брэнсону, и мошеннику.

Ответы [ 3 ]

0 голосов
/ 01 мая 2018

ниже работает, если вы в порядке с возвращением нового объекта карты. Решение использует 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)
0 голосов
/ 01 мая 2018

Попробуйте сгруппировать по предикату, у вас будет карта из двух ключей: 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)
0 голосов
/ 01 мая 2018

Идиоматический способ сделать это - использовать 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() в качестве опции.

...