Ближайшие ключи в SortedMap

Ответ 1

Глядя на исходный код для 2.9.0, следующий код кажется лучшим, что вы можете сделать

def getLessOrEqual[A,B](sm: SortedMap[A,B], bound: A): B = {
  val key = sm.to(x).lastKey
  sm(key)
}

Я не знаю точно, как работает расщепление дерева RedBlack, но я предполагаю, что это похоже на обход дерева (log n) дерева/конструкции новых элементов, а затем балансировку, предположительно также O (log n). Затем вам нужно снова спуститься по новому дереву, чтобы получить последний ключ. К сожалению, вы не можете получить значение за один проход. Поэтому вам нужно снова спуститься, чтобы получить значение.

Кроме того, lastKey может генерировать исключение и не существует аналогичного метода, который возвращает Option.

Я жду исправлений.

Редактировать и личный комментарий

Область SortedMap в std lib, по-видимому, немного игнорируется. Я также пропускаю измененную SortedMap. И, просматривая источники, я заметил, что некоторые важные методы отсутствуют (например, тот, который запрашивает OP, или те, которые указаны в моем ответе), а также некоторые из них имеют плохую реализацию, например "last", которая определяется TraversableLike и идет через полное дерево от первого до последнего, чтобы получить последний элемент.

Изменить 2

Теперь вопрос переформулирован, мой ответ уже недействителен (ну это было не раньше). Я думаю, вы должны сделать то, что я описываю дважды, для lessOrEqual и moreOrEqual. Ну, вы можете взять ярлык, если найдете равный элемент.

Ответ 2

Scala SortedSet trait не имеет метода, который даст вам ближайший элемент к другому элементу.

В настоящее время он реализован с помощью TreeSet, который основан на RedBlack. Дерево RedBlack не видно с помощью методов на TreeSet, но защищенный метод tree защищен. К сожалению, это в основном бесполезно. Вам придется переопределить методы, возвращающие TreeSet, чтобы вернуть ваш подкласс, но большинство из них основано на newSet, который является приватным.

Итак, в конце концов, вам придется дублировать большую часть TreeSet. С другой стороны, это не так много кода.

Как только у вас будет доступ к RedBlack, вам нужно будет реализовать нечто похожее на RedBlack.Tree lookup, поэтому у вас будет производительность O(logn). Это на самом деле такая же сложность range, хотя она, безусловно, будет работать меньше.

В качестве альтернативы вы создадите застежку-молнию для дерева, чтобы вы могли фактически перемещаться по множеству в постоянное время. Конечно, было бы намного больше работать.

Ответ 3

Похоже, я должен подать билет, чтобы добавить методы fromIterator и toIterator к признаку 'Sorted'.

Ответ 4

Ну, один вариант, безусловно, использует java.util.TreeMap.

У него есть методы lowerKey и higherKey, которые действительно делают то, что вы хотите.

Ответ 5

К сожалению, библиотека Scala позволяет эффективно выполнять этот тип запроса:

а также наименьший ключ n, который больше или равен k.

val n = TreeMap(...).keyIteratorFrom(k).next

Вы можете взломать это, сохранив две структуры: одну с обычными клавишами и одну с отрицательными клавишами. Затем вы можете использовать другую структуру для создания второго типа запроса.

val n = - TreeMap(...).keyIteratorFrom(-k).next

Ответ 6

Используя Scala 2.11.7, следующее даст то, что вы хотите:

scala> val set = SortedSet('a', 'f', 'j', 'z')
set: scala.collection.SortedSet[Char] = TreeSet(a, f, j, z)

scala> val beforeH = set.to('h').last
beforeH: Char = f

scala> val afterH = set.from('h').head
afterH: Char = j

Как правило, вы должны использовать lastOption и headOption, поскольку указанные элементы могут не существовать. Если вы хотите сжать немного больше эффективности, вы можете попробовать заменить from(...).head на keysIteratorFrom(...).head

Ответ 7

У меня была аналогичная проблема: я хотел найти ближайший элемент к заданному ключу в SortedMap. Я помню ответ на этот вопрос: "Вы должны взломать TreeSet", поэтому, когда мне пришлось реализовать его для проекта, я нашел способ обернуть TreeSet, не входя в его внутренности.

Я не видел ответ jazmit, который более точно отвечает на исходный вопрос с минимальным шумом (два вызова метода). Тем не менее, эти вызовы методов делают больше работы, чем необходимо для этого приложения (несколько обходов дерева), и мое решение обеспечивает множество перехватов, когда другие пользователи могут модифицировать его в соответствии с их собственными потребностями.

Вот он:

import scala.collection.immutable.TreeSet
import scala.collection.SortedMap

// generalize the idea of an Ordering to metric sets
trait MetricOrdering[T] extends Ordering[T] {
  def distance(x: T, y: T): Double
  def compare(x: T, y: T) = {
    val d = distance(x, y)
    if (d > 0.0) 1
    else if (d < 0.0) -1
    else 0
  }
}

class MetricSortedMap[A, B]
  (elems: (A, B)*)
  (implicit val ordering: MetricOrdering[A])
  extends SortedMap[A, B] {

  // while TreeSet searches for an element, keep track of the best it finds
  // with *thread-safe* mutable state, of course
  private val best = new java.lang.ThreadLocal[(Double, A, B)]
  best.set((-1.0, null.asInstanceOf[A], null.asInstanceOf[B]))

  private val ord = new MetricOrdering[(A, B)] {
    def distance(x: (A, B), y: (A, B)) = {
      val diff = ordering.distance(x._1, y._1)
      val absdiff = Math.abs(diff)

      // the "to" position is a key-null pair; the object of interest
      // is the other one
      if (absdiff < best.get._1)
        (x, y) match {
          // in practice, TreeSet always picks this first case, but that's
          // insider knowledge
          case ((to, null), (pos, obj)) =>
            best.set((absdiff, pos, obj))

          case ((pos, obj), (to, null)) =>
            best.set((absdiff, pos, obj))

          case _ =>
        }

      diff
    }
  }

  // use a TreeSet as a backing (not TreeMap because we need to get
  // the whole pair back when we query it)
  private val treeSet = TreeSet[(A, B)](elems: _*)(ord)

  // find the closest key and return:
  // (distance to key, the key, its associated value)
  def closest(to: A): (Double, A, B) = {
    treeSet.headOption match {
      case Some((pos, obj)) =>
        best.set((ordering.distance(to, pos), pos, obj))
      case None =>
        throw new java.util.NoSuchElementException(
          "SortedMap has no elements, and hence no closest element")
    }

    treeSet((to, null.asInstanceOf[B]))  // called for side effects

    best.get
  }

  // satisfy the contract (or throw UnsupportedOperationException)
  def +[B1 >: B](kv: (A, B1)): SortedMap[A, B1] =
    new MetricSortedMap[A, B](
      elems :+ (kv._1, kv._2.asInstanceOf[B]): _*)
  def -(key: A): SortedMap[A, B] =
    new MetricSortedMap[A, B](elems.filter(_._1 != key): _*)
  def get(key: A): Option[B] = treeSet.find(_._1 == key).map(_._2)
  def iterator: Iterator[(A, B)] = treeSet.iterator
  def rangeImpl(from: Option[A], until: Option[A]): SortedMap[A, B] =
    new MetricSortedMap[A, B](treeSet.rangeImpl(
      from.map((_, null.asInstanceOf[B])),
      until.map((_, null.asInstanceOf[B]))).toSeq: _*)
}

// test it with A = Double
implicit val doubleOrdering =
  new MetricOrdering[Double] {
    def distance(x: Double, y: Double) = x - y
  }

// and B = String
val stuff = new MetricSortedMap[Double, String](
  3.3 -> "three",
  1.1 -> "one",
  5.5 -> "five",
  4.4 -> "four",
  2.2 -> "two")

println(stuff.iterator.toList)

println(stuff.closest(1.5))
println(stuff.closest(1000))
println(stuff.closest(-1000))
println(stuff.closest(3.3))
println(stuff.closest(3.4))
println(stuff.closest(3.2))

Ответ 8

Я делаю:

val m = SortedMap(myMap.toSeq:_*)
val offsetMap = (m.toSeq zip m.keys.toSeq.drop(1)).map {
  case ( (k,v),newKey) => (newKey,v)
}.toMap

Когда я хочу, чтобы результаты моей карты были отключены одним ключом. Я также ищу лучший способ, желательно, не сохраняя дополнительную карту.