Scala vector splicing (поддерживая отсортированную последовательность)

Мне нужно поддерживать отсортированную последовательность (изменяемую или неизменяемую - мне все равно), динамически вставляя элементы в середину (сортировать) и удаляя их аналогично (так , случайный доступ по индексу имеет решающее значение).Scala vector splicing (поддерживая отсортированную последовательность)

Самое лучшее, что я пришел на это с использованием вектора и scala.collections.Searching из 2.11, а затем:

var vector: Vector[Ordered] 
... 
val ip = vector.search(element)

Вставка:

vector = (vector.take(ip.insertionPoint) :+ element) ++ vector.drop(ip.insertionPoint)

Удаление:

vector.patch(from = ip.insertionPoint, patch = Nil, replaced = 1)

Не выглядит элегантно для меня, и я подозреваю проблемы с производительностью. Есть ли способ лучше? Последовательности сращивания для меня очень важны, но я не могу найти изящное решение.

источник

2014-12-19 Alexander Temerev

"динамически вставляя элементы в середину (чтобы их сортировать)", но чтобы знать, куда его поместить, вам все равно нужно пройти список до этой точки. Это делает список не таким уж плохим для этой операции (или вы можете бинарную отбивку или что-то в этом роде, но в любом случае это не операция O (1)). Когда вы удаляете, удаляете ли вы индекс, или по значению, или что-то еще? –

Кроме того, 'vector.take' ..' vector.drop' является '.splitAt'. Но вы, вероятно, хотели '.span (_ <= element)' –

@Paul Бинарный поиск O (log N), что тоже хорошо. Не требуется обход. scala.collection.Searching использует двоичный поиск. Удаление по индексу. –

Вы должны использовать SortedSet. Реализация по умолчанию SortedSet - immutable red-black tree. Существует также mutable implementation.

SortedSet[Int]() + 5 + 3 + 4 + 7 + 1 
// SortedSet[Int] = TreeSet(1, 3, 4, 5, 7)

Set не содержит повторяющихся элементов. Если вы хотите подсчитать повторяющиеся элементы, вы можете использовать SortedMap[Key, Int] с элементами в качестве ключей и считать значениями. См. this answer для MultiSet эмуляция с использованием Map.

источник

2014-12-19 12:50:24 senia

Я бы хотел, но мне нужно иметь возможность добавлять несколько равных элементов и не терять их, итерации по последовательности. Могу ли я сделать это с помощью SortedSet? –

@AlexanderTemerev: см. Обновление. – senia

Scala vector splicing (поддерживая отсортированную последовательность)

ответ

Смежные вопросы