Блог

Главная - Вопросы по программированию - функция комбинаций scala, влияющая на накладные расходы GC

функция комбинаций scala, влияющая на накладные расходы GC

#scala #apache-spark

#скала #apache-искра #scala #apache-spark

Вопрос:

У меня есть следующий процесс, который принимает список строк и генерирует их комбинации:

 val a = List(("a","a"),("a","b"),("a","c"),("b","a"),("b","b"),("b","c"),("c","a"),("c","b"),("c","c"));

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

Так, например, результат, который я ожидаю, будет примерно таким:

 List(("a","a"),("b","b"),("c","c"))

но это не может быть что-то вроде:

 List (("a","a"),("b","a"),("a","c"))

итак, я написал следующее:

 val res = a
  .combinations(3)
  .toList
  .filter(x =>
    x.map(y => y._1).distinct.size == 3
    amp;amp;  x.map(y => y._2).distinct.size == 3 
  )

который генерирует правильный набор ответов:

 List((a,a), (b,b), (c,c))
List((a,a), (b,c), (c,b))
List((a,b), (b,a), (c,c))
List((a,b), (b,c), (c,a))
List((a,c), (b,a), (c,b))
List((a,c), (b,b), (c,a))

но когда я увеличиваю размер a вместе с количеством комбинаций, я получаю накладные расходы GC. Мне было интересно, есть ли способ сделать то, что я хочу, без использования функции combination или более эффективным способом? Я использую Spark, так что я мог бы использовать любую функцию Spark и для этого, хотя я не думаю, что таковая существует.

Комментарии:

1. вы знаете, что ничего из этого не делаете с Spark? вы передаете результат вашего (локального) вычисления в sc.parallelize , а затем ничего не делаете с созданным параллельным набором данных (RDD)… Таким образом, Spark фактически не выполняет никакой работы в этом коде

2. @TzachZohar да, я знаю — на самом деле я собираю их для мастера, чтобы использовать функцию combination в scala, поскольку spark этого не делает. Я мог бы создать комбинации из 2, используя cartesian но это не относится к вопросу. Если у вас есть способ сделать это в Spark на RDD, я бы с радостью принял этот ответ 🙂

3. toList убьет вас, если ваш ввод станет большим. Попробуйте потоковые комбинации, а не создавать гигантский список заранее.

4. если вы собираете данные для использования combinations , вы предполагаете, что набор данных не будет слишком большим для обработки вашим драйвером одного процесса; Если это так — зачем использовать Spark для начала?

5. @BrianPendleton хммм, это правда, попробую.

Ответ №1:

Ну, действительно, у Spark нет combinations функции, но вы можете имитировать ее, используя последовательные вызовы cartesian . Это может быть не слишком эффективно с точки зрения производительности, но это должно предотвратить проблемы с памятью, с которыми вы столкнулись, и устранить необходимость collect (которая имеет свои собственные затраты на производительность):

 val values: RDD[(String, String)] = sc.parallelize(a)
val combinationSize = 3 // can be increased

// mimic Scala's "combination" by repeating RDD.cartesian N times:
val combinations: RDD[Set[(String, String)]] = (1 until combinationSize)
  .foldLeft(values.map(Set(_))) {
    case (rdd, index) => rdd.cartesian(values).map { case (set, t2) => set   t2 }.distinct
  }

// removing "illegal" combinations - since we're using sets we don't need to call "distinct": 
val res = combinations
  .filter(_.map(_._1).size == combinationSize)
  .filter(_.map(_._2).size == combinationSize)