Scala PriorityQueue для Array [Int] проблема производительности со сложной функцией сравнения (требуется кэширование)

Question

Проблема заключается в производительности Scala PriorityQueue [Array [Int]] для большого набора данных.Необходимы следующие операции: постановка в очередь, удаление из очереди и фильтрация.В настоящее время моя реализация выглядит следующим образом:

Для каждого элемента типа Array [Int] существует сложная функция оценки: (Я не уверен, как написать ее более эффективным способом, поскольку она исключаетпозиция 0)

def eval_fun(a : Array[Int]) =
  if(a.size < 2) 3
  else {
    var ret = 0
    var i = 1
    while(i < a.size) {
      if((a(i) & 0x3) == 1) ret += 1
      else if((a(i) & 0x3) == 3) ret += 3
      i += 1
    }
    ret / a.size
  }

Порядок с функцией сравнения основан на функции оценки: ( Перевернутый , порядок по убыванию)

val arr_ord = new Ordering[Array[Int]] {
  def compare(a : Array[Int], b : Array[Int]) = eval_fun(b) compare eval_fun(a) }

ПриоритетQueueопределяется как:

val pq: scala.collection.mutable.PriorityQueue[Array[Int]] = PriorityQueue()

Вопрос:

1. Существует ли более элегантный и эффективный способ написания такой функции оценки?Я думаю об использовании сгиба, но сгиб не может исключить позицию 0.
2. Существует ли структура данных для генерации очереди приоритетов с уникальными элементами?Применение операции фильтра после каждой операции постановки в очередь не эффективно.
3. Существует ли метод кэширования для уменьшения вычислений при оценке?Поскольку при добавлении нового элемента в очередь каждый элемент может нуждаться в повторной оценке eval_fun, что не является необходимым, если оцененное значение каждого элемента может быть кэшировано.Кроме того, я должен отметить, что два различных элемента могут иметь одинаковое оценочное значение.
4. Существует ли более эффективная структура данных без , использующая универсальный тип?Потому что, если размер элементов достигает 10000, а размер достигает 1000, производительность очень низкая.

Спасибо.

Answer 1

(1) Если вам нужна максимальная производительность, я бы придерживался цикла while, даже если он не очень элегантный.В противном случае, если вы используете view в массиве, вы можете легко отбросить первый элемент перед переходом в fold:

a.view.drop(1).foldLeft(0)( (sum, a) => sum + ((a & 0x03) match {
   case 0x01 => 1
   case 0x03 => 3
   case _    => 0
})) / a.size

(2) Вы можете поддерживать две структуры: очередь с приоритетами имножество.Оба вместе дают вам отсортированный набор ... Таким образом, вы можете использовать collection.immutable.SortedSet, но в стандартной библиотеке нет изменяемого варианта.Хотите равенства на основе функции приоритета или фактического содержимого массива?Потому что в последнем случае вы не сможете обойти сравнение элементов массива за элементом для каждой вставки, отменив эффект кэширования значения функции приоритета.

(3) Просто поместите вычисленный приоритет вместе с массивом вочередь.Т.е.

implicit val ord = Ordering.by[(Int, Array[Int]), Int](_._1)
val pq = new collection.mutable.PriorityQueue[(Int, Array[Int])]
pq += eval_fun(a) -> a

Answer 2

Ну, вы можете использовать хвостовую рекурсивную петлю (как правило, они более "идиоматичны":

def eval(a: Array[Int]): Int =
  if (a.size < 2) 3
  else {
    @annotation.tailrec
    def loop(ret: Int = 0, i: Int = 1): Int =
      if (i >= a.size) ret / a.size
      else {
        val mod3 = (a(i) & 0x3)
        if (mod3 == 1) loop(ret + 1, i + 1)
        else if (mod3 == 3) loop(ret + 3, i + 1)
        else loop(ret, i + 1)
      }
    loop()
  }

Затем вы можете использовать это для инициализации кэшированного значения приоритета:

case class PriorityArray(a: Array[Int]) {
  lazy val priority = if (a.size < 2) 3 else {
    @annotation.tailrec
    def loop(ret: Int = 0, i: Int = 1): Int =
      if (i >= a.size) ret / a.size
      else {
        val mod3 = (a(i) & 0x3)
        if (mod3 == 2) loop(ret, i + 1)
        else loop(ret + mod3, i + 1)
      }
    loop()
  }
}

Вы также можете заметить, что я удалил избыточный & op и у меня есть только одно условное условие (для случая, когда оно равно 2, а не две проверки для 1 && 3) - это должно иметь некоторый минимальный эффект.

Между предложением 0 __, которое только что пришло, нет большой разницы.

Answer 3

Мои ответы:

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

2. Нет, нет, но вы можете приблизиться к нему, просто изменив операцию удаления очереди:

   def DifferentDequeue [T] (q: PriorityQueue [T]): T = { val result = q.dequeue while (q.head == результат) q.dequeue результат }

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

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

1. Как и предложено 0__, поместите стоимость в приоритетную очередь. Но вы можете также сохранить кеш в функции, если это будет полезно. Я бы попробовал что-то вроде этого:

   val evalMap = scala.collection.mutable.HashMapWrappedArray [Int], Int def eval_fun (a: Array [Int]) = если (a.size

   import scala.math.Ordering.Implicits._ val pq = new collection.mutable.PriorityQueue [(Int, WrappedArray [Int])] pq + = eval_fun (a) -> (a: WrappedArray [Int])

Обратите внимание, что я не создал специальный Ordering - я использую стандарт Ordering, чтобы WrappedArray разорвал связи. Обернуть Array не составит большого труда, и вы получите обратно с .array, но, с другой стороны, вы получите следующее:

1. Связи будут разорваны при сравнении самого массива. Если в стоимости не так много связей, этого должно быть достаточно. Если есть, добавьте что-то еще в кортеж, чтобы помочь разорвать связи, не сравнивая массивы.

2. Это означает, что все равные элементы будут сохранены вместе, что позволит вам удалить все из них одновременно, создавая впечатление, что вы сохранили только один.

3. И это equals будет на самом деле работать, потому что WrappedArray сравнивать, как это делают последовательности Scala.

Я не понимаю, что вы имеете в виду под этим четвертым пунктом.