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

У меня есть список scala, содержащий строку и список целых чисел. Я хотел отфильтровать только те, которые имеют наибольший размер списка целых чисел. Обычный способ сортировки от наибольшего к наименьшему, а затем взятие n строк, имеет один недостаток.

var qq = List[(String,List[Int])]()

Скажем, например, список длиной 10, есть 6 списков размером 65, а остальные 5 имеют размеры меньше 65. Теперь мне нужно получить все 6 списков из вектора.

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

var max = qq.sortWith(_._2.size>_._2.size).head._2.size //get maximum size
var filList = qq.filter(p=>p._2.size>=max) //filter them

Мой вопрос: есть ли другой быстрый и эффективный способ сделать это в scala? Поскольку я бы проделал этот процесс около 10 000-20 000 раз с большим размером списка.


list scala scala-collections
person Balaram26    schedule 10.04.2014    source источник
comment
Можете ли вы переключить внутренние списки на коллекцию с поиском длины O (1)? Вектор, например.   -  person dmitry    schedule 11.04.2014

Ответы (2)


arrow_upward
2
arrow_downward

Для производительности вам не следует сортировать весь список, если вы просто хотите макс.

Во-вторых, в Scala очень легко сделать многопоточный код:

  val data = List(("a", List(1, 2, 3)), ("b", List(4, 5)), ("c", List(45, 3, 2)))
  val maxListSize = data.par.map(_._2.size).max
  val largestLists = data.par.filter(_._2.size == maxListSize)
  println(largestLists)

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

person toto2    schedule 10.04.2014
comment
Ну и даст ускорение, не превышающее количество доступных ядер. Или, как говорят рекламщики, До бла-бла-бла! (включая ноль…). - person Randall Schulz; 10.04.2014
comment
Я не знаю, прочитал ли я весь мой пост, но я упоминаю, что для небольших списков это может на самом деле замедлить работу. Если список очень большой, он предложит коэффициент ускорения, который асимптотически близок к количеству ядер. К чему сарказм по поводу многопоточного кода? - person toto2; 10.04.2014
comment
Сарказм был направлен только на рекламный язык, но ваше утверждение было неточным в ответе (количество ядер…), хотя в комментарии, где вы говорите асимптотически близко, вы гораздо точнее. - person Randall Schulz; 11.04.2014

arrow_upward
1
arrow_downward

Я предлагаю

val sorted = qq.sortBy(_._2.size)
val thresh = sorted.head._2.size  // assume qq is non-empty
val retain = sorted.takeWhile(_._2.size == thresh)

Производительность в любом случае связана с процедурой сортировки (конечно, хуже, чем O(N)).

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

Как это:

type A = (String,List[Int])

((0, List.empty[A]) /: qq) { case (prev @ (bestLen, res), entry @ (_, list)) =>
  val eLen = list.size
  if      (eLen <  bestLen) prev
  else if (eLen == bestLen) (bestLen, entry :: res)
  else                      (eLen, entry :: Nil)
}

Производительность будет O(N), насколько это возможно.

person 0__    schedule 10.04.2014
comment
@ toto2 - правильно, несмотря на распараллеливание. Но если мы предположим, что C = количество ядер является константой, это все еще O (N) :) - person 0__; 10.04.2014
comment
Истинный. Нотация Big-O не заботится о константах. :-‹ - person toto2; 10.04.2014