Удалить лишние записи, scala way

Question

Редактировать: добавлен тот факт, что список отсортирован, а реализация «дубликата» вводит в заблуждение, заменив его на «избыточный» в заголовке. У меня есть отсортированный список записей, в которых указана производственная стоимость за указанный интервал. Записи с указанием того же значения в более позднее время не добавляют никакой информации и могут быть безопасно пропущены.

case class Entry(minute:Int, production:Double)
val entries = List(Entry(0, 100.0), Entry(5, 100.0), Entry(10, 100.0), Entry(20, 120.0), Entry(30, 100.0), Entry(180, 0.0))

Экспериментируя с функциями коллекции scala 2.8, пока у меня есть эта рабочая реализация:

entries.foldRight(List[Entry]()) {
  (entry, list) => list match {
    case head :: tail if (entry.production == head.production) => entry :: tail
    case head :: tail => entry :: list
    case List() => entry :: List()
  }
}
res0: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0))

Есть комментарии? Я пропускаю магию скалы?

Answer 1

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

Ниже я беру первую запись из списка и использую collect, чтобы одновременно отфильтровывать пары, где производство не изменилось, а для остальных пар карта e2. (collect является новым в Scala 2.8, и некоторое время назывался partialMap)

scala> entries.head :: ((entries zip entries.tail).collect { 
           case (Entry(_, p1), e2@Entry(_, p2)) if p1 != p2 => e2 
       })
res13: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0))

ОБНОВЛЕНИЕ Для простоты предполагается, что записи не пусты.

Answer 2

Существует новый метод zipped с Tuple2, который более эффективен (и более ленив), чем zip в списках для некоторых операций. Вы можете попробовать это на своем тесте - я не знаю, действительно ли он быстрее, но он, безусловно, может быть (и это определенно намного короче):

entries.take(1) :::
(entries,entries.drop(1)).zipped.filter(_.production != _.production)._2

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

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

Answer 3

Вместо поиска дубликатов для каждого элемента, который является O (n ^ 2), или zip, который является n ^ 2 в памяти, используйте карту [Double, Int]. Затем просто добавьте элементы с «production» в качестве ключа и «minute» в качестве значения. Карта обеспечит уникальные значения для «производства». Вы можете загрузить карту естественным образом в другом месте вашего кода, но даже если вам придется начать со списка, как указано выше, загрузка карты линейна в списке и только O (n log (n)) на карте.

Карта будет заменена, когда вы добавите «mymap + = production -> minute», чтобы сохранить первое значение, переверните список перед тем, как вставлять или использовать защиту «содержит (ключ)». Проверки будут O (log (n)), поэтому общий алгоритм будет O (n log (n)).

Кстати, вы можете использовать карту [Double, Entry], чтобы отобразить производственные значения непосредственно в ваши структуры Entry. Затем вы можете легко получить список, если нужно, извлекая значения карты непосредственно из карты и сортируя по любому элементу записи (при необходимости).