Scala TreeSet

У меня есть большой набор целых чисел, которые я использую для хранения TreeSet. Моя задача - найти два числа меньше входного числа.

Например, Set(1, 5, 8, 9) и input = 6 должны возвращать (1, 5) input = 8 должны возвращать (5, 8)

То, что у меня есть до сих пор с точки зрения кода, следующее:

treeSet.to(inputNumber).takeRight(2)

Насколько я понимаю, .to() возвращает проекцию элементов меньше, чем ввод в logN времени. Мне интересно, в чем сложность дополнительного takeRight. Я не могу понять из документов.

Я пытаюсь сделать это максимально эффективным, поскольку мой список ввода содержит миллионы чисел.


scala data-structures treeset
person frodo    schedule 30.01.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Иногда проще посмотреть исходный код, даже не просматривая документы.

In TreeSet:

override def takeRight(n: Int) = drop(size - math.max(n, 0))

override def drop(n: Int) = {
  if (n <= 0) this
  else if (n >= size) empty
  else newSet(RB.drop(tree, n))
}

In RedBlackTree:

def drop[A: Ordering, B](tree: Tree[A, B], n: Int): Tree[A, B] = blacken(doDrop(tree, n))

Удаление в RBtree равно O(log n), поэтому takeRight в Scala TreeSet, поддерживаемом RBtree, также равно O(log n).

person Aivean    schedule 30.01.2018