Как отсортировать RDD в Scala Spark?

Чтение метода Spark sortByKey:

sortByKey([ascending], [numTasks])   When called on a dataset of (K, V) pairs where K implements Ordered, returns a dataset of (K, V) pairs sorted by keys in ascending or descending order, as specified in the boolean ascending argument.

Можно ли вернуть только количество результатов "N". Поэтому вместо того, чтобы возвращать все результаты, просто верните первую десятку. Я мог бы преобразовать отсортированную коллекцию в Array и использовать метод take, но поскольку это операция O (N), существует более эффективный метод?

Ответы

Ответ 1

Скорее всего, вы уже изучили исходный код:

  class OrderedRDDFunctions {
   // <snip>
  def sortByKey(ascending: Boolean = true, numPartitions: Int = self.partitions.size): RDD[P] = {
    val part = new RangePartitioner(numPartitions, self, ascending)
    val shuffled = new ShuffledRDD[K, V, P](self, part)
    shuffled.mapPartitions(iter => {
      val buf = iter.toArray
      if (ascending) {
        buf.sortWith((x, y) => x._1 < y._1).iterator
      } else {
        buf.sortWith((x, y) => x._1 > y._1).iterator
      }
    }, preservesPartitioning = true)
  }

И, как вы говорите, данные целые должны пройти этап тасования - как видно из фрагмента.

Однако ваша озабоченность по поводу последующего вызова take (K) может быть не столь точным. Эта операция НЕ выполняет цикл по всем N элементам:

  /**
   * Take the first num elements of the RDD. It works by first scanning one partition, and use the
   * results from that partition to estimate the number of additional partitions needed to satisfy
   * the limit.
   */
  def take(num: Int): Array[T] = {

Итак, казалось бы:

O (myRdd.take(K)) < O (myRdd.sortByKey()) ~ = O (myRdd.sortByKey.take(k)) (по меньшей мере, для малых K) O (myRdd.sortByKey(). Собирать()

Ответ 2

Если вам нужны только 10 лучших, используйте rdd.top(10). Он избегает сортировки, поэтому он быстрее.

rdd.top делает один параллельный проход через данные, собирая верхнюю N в каждом разделе в куче, а затем объединяет кучи. Это операция O (rdd.count). Сортировка будет O (rdd.count log rdd.count) и будет нести большую передачу данных - она перемещается, поэтому все данные будут передаваться по сети.

Ответ 3

Другим вариантом, по крайней мере, от PySpark 1.2.0, является использование takeOrdered.

В порядке возрастания:

rdd.takeOrdered(10)

В порядке убывания:

rdd.takeOrdered(10, lambda x: -x)

Верхние значения k для k, v пар:

rdd.takeOrdered(10, lambda (k, v): -v)