Эффективный способ преобразования Scala массива в уникальный отсортированный список

Ответ 1

Эта простая строка является одним из самых быстрых кодов:

someArray.toList.filter (_ > 0).sortWith (_ > _).distinct

но явный победитель до сих пор - из-за моего измерения - Джед Уэсли-Смит. Возможно, если код Рекса исправлен, он выглядит иначе.

Типичный отказ от ответственности 1 + 2:

• Я изменил коды, чтобы принять массив и вернуть список.
• Типичные ориентиры:
  • Это были случайные данные, одинаково распределенные. Для 1 миллиона элементов я создал массив размером в 1 миллион от 0 до 1 миллиона. Таким образом, с более или менее нулями и более или менее дублирующими, это может различаться.
  • Это может зависеть от машины и т.д. Я использовал одноядерный процессор Intel-Linux-32bit, jdk-1.6, scala 2.9.0.1

Ниже приведен базовый codecoat-код и конкретный код для создания графика (gnuplot). Ось Y: время в секундах. Ось X: от 100 000 до 1 000 000 элементов в массиве.

обновление:

После обнаружения проблемы с кодом Рекса его код работает так же быстро, как Jed-код, но последняя операция - это преобразование его массива в список (для полного заполнения моего тестового интерфейса). Используя var result = List [Int], и result = someArray (i) :: result ускоряет его код, так что он примерно в два раза быстрее, чем Jed-Code.

Другим, может быть, интересным, является: если я изменил свой код в порядке фильтра /sort/distinct (fsd) = > (dsf, dfs, fsd,...), все 6 возможностей существенно не отличаются,

Ответ 2

Я не измерил, но я с Дунканом, соберите на месте, затем используйте что-то вроде:

util.Sorting.quickSort(array)
array.foldRight(List.empty[Int]){ 
  case (a, b) => 
    if (!b.isEmpty && b(0) == a) 
      b 
    else 
      a :: b 
}

В теории это должно быть довольно эффективно.

Ответ 3

Без бенчмаркинга я не могу быть уверен, но я думаю, что следующее довольно эффективно:

val list = collection.SortedSet(someArray.filter(_>0) :_*).toList

Также попробуйте добавить .par после someArray в вашей версии. Не гарантировано, что это будет быстрее, возможно, это может быть. Вы должны запустить тест и эксперимент.

sort устарел. Вместо этого используйте .sortWith(_ > _).

Ответ 4

Бокс-примитивы собираются дать вам 10-30-кратное снижение производительности. Поэтому, если вы действительно ограничены в производительности, вам нужно будет работать с исходными примитивными массивами:

def arrayDistinctInts(someArray: Array[Int]) = {    
  java.util.Arrays.sort(someArray)
  var overzero = 0
  var ndiff = 0
  var last = 0
  var i = 0
  while (i < someArray.length) {
    if (someArray(i)<=0) overzero = i+1
    else if (someArray(i)>last) {
      last = someArray(i)
      ndiff += 1
    }
    i += 1
  }
  val result = new Array[Int](ndiff)
  var j = 0
  i = overzero
  last = 0
  while (i < someArray.length) {
    if (someArray(i) > last) {
      result(j) = someArray(i)
      last = someArray(i)
      j += 1
    }
    i += 1
  }
  result
}

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

Изменить (в дополнение к исправлению предыдущего кода, чтобы он действительно работал):

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

def listDistinctInts(someArray: Array[Int]): List[Int] = {
  if (someArray.length == 0 || someArray(someArray.length-1) <= 0) List[Int]()
  else {
    java.util.Arrays.sort(someArray)
    var last = someArray(someArray.length-1)
    var list = last :: Nil
    var i = someArray.length-2
    while (i >= 0) {
      if (someArray(i) < last) {
        last = someArray(i)
        if (last <= 0) return list;
        list = last :: list
      }
      i -= 1
    }
    list
  }
}

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

И имейте в виду, что существуют специальные решения, которые намного быстрее, но в зависимости от характера данных. Например, если вы знаете, что у вас длинный массив, но числа будут в небольшом диапазоне (например, от -100 до 100), вы можете использовать битовый набор для отслеживания тех, с которыми вы столкнулись.

Ответ 5

Для эффективности, в зависимости от вашего значения:

val a = someArray.toSet.filter(_>0).toArray
java.util.Arrays.sort(a) // quicksort, mutable data structures bad :-)
res15: Array[Int] = Array(1, 2, 4, 5, 6, 9)

Обратите внимание, что это делает сортировку с использованием qsort в распакованном массиве.

Ответ 6

Я не в состоянии измерить, но еще несколько предложений...

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

Ответ 7

Как добавить все в отсортированный набор?

val a = scala.collection.immutable.SortedSet(someArray filter (0 !=): _*)

Конечно, вы должны проверить код, чтобы проверить, что быстрее, и, что более важно, что это действительно горячая точка.