Scala: наиболее эффективно сортируйте ListBuffer of (Int, Int, Int) по третьему значению

Я хочу отсортироватьListBuffer(Int, Int, Int) по третьему значению наиболее эффективно. Это то, что у меня есть сейчас. Я используюsortBy . Примечаниеy а такжеz обаListBuffer[(Int, Int, Int)] , которую я сначала беру на заметку. Моя цель - оптимизировать это и выполнить эту операцию (используя разницу между двумя списками и сортировку по третьему элементу) наиболее эффективно. Я предполагаюdiff часть не может быть оптимизирована, но sortBy может, поэтому я ищу эффективный способ сделать часть сортировки. Я нашел сообщения о сортировке массивов, но я работаю с ListBuffer, и преобразование в массив добавляет накладные расходы, поэтому я предпочитаю не преобразовывать свой ListBuffer.

val x = (y diff z).sortBy(i => i._3)
# sorting listbuffer
Источник
Codelisting
за 5 против
Лучший ответ

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
  }

Это то, что будет вызывать ваш код. Как видите, он уже использует массивы для сортировки данных на месте. Согласноjavadocpublic static void sort(Object[] a) :

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

2) Если вы попытаетесь оптимизировать, вставив результаты вашего сравнения непосредственно в отсортированную структуру, такую как двоичное дерево, когда вы создаете их поэлементно, вы все равно будете платить ту же цену: средняя стоимость вставки составляетlog(n) разn элементы= n log(n) - так же, как любой алгоритм быстрой сортировки, такой как сортировка слиянием.

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

3а) Например,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, чтобы понять, что вы можете получить в зависимости от конкретного случая.

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

Подводя итог сложности для различных сценариев ...

Ваш текущий случай:

  • diff дляSeqLike :n создать карту изthat +n перебиратьthis (поиск по карте - это фактически постоянное время (C)) =2n илиO(n)
  • Сортировать -O(n log(n))
  • итого =O(n) + O(n log(n)) знак равноO(n log(n)) , точнее:2n + nlog(n)

Если вы используетеSet вместо тогоSeqLike :

  • diff дляSet :n для итерации (поиск - C) =O(n)
  • сорт - такой же
  • итого - то же:O(n) + O(n log(n)) знак равноO(n log(n)) , точнее:n + nlog(n)

Если вы используетеSet и массив для вставки:

  • diff - то же, что и для Set
  • sort - 0 - массив сортируется по построению
  • общий:O(n) + O(0) знак равноO(n) , точнее:n . Может быть не очень практично для разреженных данных.

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

Если бы у вас былListBuffer[Int] скорее, чемListBuffer[(Int, Int, Int)] Я бы посоветовал сначала отсортировать обе коллекции, а затем провести сравнение, выполнив один проход через обе коллекции одновременно. Это было быO(nlog(n)) . В вашем случае сортировка по_3 недостаточно, чтобы гарантировать точный порядок в обеих коллекциях. Вы можете сортировать по всем трем полям кортежа, но это изменит исходный порядок. Если вас это устраивает и вы пишете свой собственный diff, это может быть самым быстрым вариантом.

Codelisting
Популярные категории
На заметку программисту