1) Если вы хотите использовать библиотеки Scala, то вы не можете сделать гораздо лучше, чем это. Scala уже пытается сортировать вашу коллекцию наиболее эффективным способом. SeqLike определяет def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f), который вызывает эту реализацию:
def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
val len = this.length
val arr = new ArraySeq[A](len)
var i = 0
for (x <- this.seq) {
arr(i) = x
i += 1
}
java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
val b = newBuilder
b.sizeHint(len)
for (x <- arr) b += x
b.result
}
Это то, что ваш код будет звонить. Как вы можете видеть, он уже использует массивы для сортировки данных на месте. Согласно javadoc из public static void sort(Object[] a) в:
Примечание реализации: Эта реализация является устойчивой, адаптивной, итеративным слиянием, что требует гораздо меньше, чем п LG (N) сравнений , когда массив ввода частично сортируются, в то время предлагая Производительность традиционного объединения, когда входной массив случайным образом упорядочен. Если входной массив почти отсортирован, реализация требует приблизительно n сравнений.
2) Если вы пытаетесь оптимизировать вставляя результаты вашего дифф непосредственно в отсортированный структуру как бинарное дерево, как вы производите их поэлементно, вы все равно будете платить ту же цену: средняя стоимость вставки log(n)n Элементы = n log(n) - то же, что и любой алгоритм быстрой сортировки, такой как сортировка слияния.
3) Таким образом, вы не можете оптимизировать этот случай в общем случае, если вы не оптимизируете его в своем конкретном прецеденте.
3a) Например, ListBuffer может быть заменен Set и diff должны быть гораздо быстрее. На самом деле он реализован как:
def diff(that: GenSet[A]): This = this -- that
который использует -, который в свою очередь должен быть быстрее, чем diff на Seq, который должен сначала построить карту:
def diff[B >: A](that: GenSeq[B]): Repr = {
val occ = occCounts(that.seq)
val b = newBuilder
for (x <- this)
if (occ(x) == 0) b += x
else occ(x) -= 1
b.result
}
3b) Вы также можете избежать сортировки используя _3 как индекс в массиве. Если вы вставляете этот индекс, ваш массив будет отсортирован. Это будет работать, только если ваши данные достаточно плотные, или вы счастливы иметь дело с разреженным массивом впоследствии. Один индекс может также иметь несколько значений, сопоставляющих его, вам также придется иметь дело с этим. Эффективно вы строите отсортированную карту.Вы можете использовать Map для этого, но HashMap не будет сортироваться, а TreeMap потребует log(n) для дополнительной операции добавления.
Проконсультируйтесь с Scala Collections Performance Characteristics, чтобы понять, что вы можете получить на основе вашего дела.
4) Как бы то ни было, на современных компьютерах действительно очень быстро сортировать. Сделайте некоторые бенчмаркинга, чтобы убедиться, что вы преждевременно не оптимизируете его.
Резюмируя сложности для различных сценариев ...
Ваш текущий случай:
- дифференциал для
SeqLike: n создать карту из that + n перебрать this (карта поиска фактически постоянная время (C)) = 2n или O(n)
- sort -
O(n log(n))
- всего =
O(n) + O(n log(n)) = O(n log(n)), точнее: 2n + nlog(n)
Если вы используете Set вместо SeqLike:
- дифференциал для
Set: n итерировать (поиск является C) = O(n)
- рода - такой же
- итого - такой же:
O(n) + O(n log(n)) = O(n log(n)), более точно: n + nlog(n)
Если вы используете Set и массив для вставки:
- диф - такой же, как для набора
- сортировки - 0 - массив отсортирован по построению
- всего:
O(n) + O(0) = O(n), а точнее: n. Не может быть очень практичным для разреженных данных.
Похоже, что в великой схеме вещей это не имеет значения, если у вас нет уникального случая, который приносит пользу из последней опции (массива).
Если у вас есть ListBuffer[Int], а не ListBuffer[(Int, Int, Int)], я бы предложил сначала отсортировать обе коллекции, а затем выполнить diff, выполнив один проход через оба из них в одно и то же время. Это будет O(nlog(n)). В вашем случае сортировка по _3 не является достаточной, чтобы гарантировать точный порядок в обеих коллекциях. Вы можете сортировать по всем трем полям кортежа, но это изменит первоначальный порядок. Если вы в порядке с этим и написав свой собственный diff, то это может быть самый быстрый вариант.