Подсчитайте, сколько раз числа из списка встречаются в списке кортежных интервалов в Scala.

Скажем, у меня есть список кортежей:

 val ranges= List((1,4), (5,8), (9,10))

и список номеров

val nums = List(2,2,3,7,8,9)

Я хочу сделать карту из кортежа в диапазонах до того, сколько раз заданное число из nums попадает в интервал этого кортежа.

Выход:

Map ((1,4) -> 3, (5,8) -> 2, (9,10) -> 1)

Как лучше всего это сделать в Scala

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

С уважением


tuples scala accumulator
person Arun Shyam    schedule 18.01.2019    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Что-то вроде этого:

val ranges = List((1, 4), (5, 8), (9, 10))
val nums = List(2, 2, 3, 7, 8, 9)

val occurences = ranges.map { case (l, r) => nums.count((l to r) contains _) }
val map = (ranges zip occurences).toMap

println(map) // Map((1,4) -> 3, (5,8) -> 2, (9,10) -> 1)

Обычно он сначала вычисляет количество вхождений, [3, 2, 1]. Оттуда легко построить карту. И способ вычисления вхождений:

  • пройтись по списку диапазонов
  • transform each range into number of occurrences for that range, which is done like this :
    • how many numbers from the list nums are contained in that range?

РЕДАКТИРОВАТЬ: Не уверен, почему этот ответ отклоняется, возможно, я как-то неправильно понял вопрос.

person slouc    schedule 18.01.2019
comment
Я не знаю, кто вас проголосовал против, это хороший ответ и очень скала. - person Etienne Herlaut; 18.01.2019
comment
Нет, вы правильно поняли, я считаю, что в большом диапазоне (l, r) содержит может быть узким местом. Но я сам поправил. Это было определенно правильно - person Arun Shyam; 18.01.2019
comment
@Arun Shyam: Да, это неэффективно, но я хотел указать вам, в каком направлении нужно думать о решении по-другому. Кстати, если вы получите такой вопрос о чем-то вроде HackerRank, это может быть даже вне временных ограничений, и в этом случае вы будете вынуждены использовать итеративный подход с циклами и счетчиками. Но по мере возможности я предпочитаю решения FP. - person slouc; 19.01.2019

arrow_upward
3
arrow_downward

Вот эффективное однопроходное решение:

ranges
  .map(r => r -> nums.count(n => n >= r._1 && n <= r._2))
  .toMap

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

Это версия, в которой используется больше функций Scala, но она слишком навороченная:

(for {
  r <- ranges
  range = r._1 to r._2
} yield r -> nums.count(range.contains)
).toMap

Это также менее эффективно, поскольку contains должно допускать диапазоны со значением шага и, следовательно, является более сложным.

А вот еще более эффективная версия, в которой отсутствуют какие-либо временные структуры данных:

val result: Map[(Int, Int), Int] =
  ranges.map(r => r -> nums.count(n => n >= r._1 && n <= r._2))(collection.breakOut)

См. Это объяснение breakOut, если вы с ним не знакомы. Использование breakOut означает, что вызов map будет строить Map напрямую, а не создавать List, который нужно преобразовать в Map с помощью toMap.

person Tim    schedule 18.01.2019