Настроить вложенную петлю в Scala

Question

Мне было интересно, смогу ли я настроить следующий код Scala:

def removeDuplicates(listOfTuple: List[(Class1,Class2)]): List[(Class1,Class2)] = {
           var listNoDuplicates: List[(Class1, Class2)] = Nil
           for (outerIndex <- 0 until listOfTuple.size) {
             if (outerIndex != listOfTuple.size - 1)
               for (innerIndex <- outerIndex + 1 until listOfTuple.size) {
                 if (listOfTuple(i)._1.flag.equals(listOfTuple(j)._1.flag))
                   listNoDuplicates = listOfTuple(i) :: listNoDuplicates
               }
           }
           listNoDuplicates
         }

Answer 1

Обычно, если у вас есть что-то похожее:

var accumulator: A = new A
for( b <- collection ) {
    accumulator = update(accumulator, b)
}
val result = accumulator

можно преобразовать во что-то вроде:

val result = collection.foldLeft( new A ){ (acc,b) => update( acc, b ) }

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

val result = listOfTuples.foldLeft( Map[F,(ClassA,ClassB)] ){
            ( map, tuple ) => map + ( tuple._1.flag -> tuple )
          }

Затем оставшиеся кортежи могут быть извлечены из карты и преобразованы в список:

val uniqList = map.values.toList

Он сохранит последний принятый кортеж,если вы хотите сохранить первое, замените foldLeft на foldRight, а инвертируйте аргумент лямбды .

Пример:

case class ClassA( flag: Int )
case class ClassB( value: Int )

val listOfTuples = 
  List( (ClassA(1),ClassB(2)), (ClassA(3),ClassB(4)), (ClassA(1),ClassB(-1)) )

val result = listOfTuples.foldRight( Map[Int,(ClassA,ClassB)]() ) {
  ( tuple, map ) => map + ( tuple._1.flag -> tuple )
}

val uniqList = result.values.toList

//uniqList: List((ClassA(1),ClassB(2)), (ClassA(3),ClassB(4)))

Редактировать: Если вам нужно сохранить порядок первоначального списка, используйте вместо этого:

val uniqList = listOfTuples.filter( result.values.toSet )

Answer 2

Это компилируется, но, поскольку я не могу проверить это, трудно сказать, если он делает "Правильное" (тм):

def removeDuplicates(listOfTuple: List[(Class1,Class2)]): List[(Class1,Class2)] = 
  (for {outerIndex <- 0 until listOfTuple.size
     if outerIndex != listOfTuple.size - 1
     innerIndex <- outerIndex + 1 until listOfTuple.size
     if listOfTuple(i)._1.flag == listOfTuple(j)._1.flag
  } yield listOfTuple(i)).reverse.toList

Обратите внимание, что вы можете использовать == вместо equals (используйте eq, если вам нужно ссылочное равенство).

Кстати: https://codereview.stackexchange.com/ лучше подходит для этого типа вопроса.

Answer 3

Не использовать индекс со списками (например, listOfTuple(i)). Индекс в списках имеет очень паршивую производительность. Итак, несколько способов ...

Самый простой:

def removeDuplicates(listOfTuple: List[(Class1,Class2)]): List[(Class1,Class2)] =
  SortedSet(listOfTuple: _*)(Ordering by (_._1.flag)).toList

Это сохранит последний элемент списка. Если вы хотите, чтобы он сохранил первый элемент, передайте вместо него listOfTuple.reverse. Из-за сортировки производительность в лучшем случае составляет O(nlogn). Итак, вот более быстрый способ, используя изменяемый HashSet:

def removeDuplicates(listOfTuple: List[(Class1,Class2)]): List[(Class1,Class2)] = {
  // Produce a hash map to find the duplicates
  import scala.collection.mutable.HashSet
  val seen = HashSet[Flag]()

  // now fold
  listOfTuple.foldLeft(Nil: List[(Class1,Class2)]) {
    case (acc, el) =>
      val result = if (seen(el._1.flag)) acc else el :: acc
      seen += el._1.flag
      result
  }.reverse
}

Можно не использовать mutable HashSet двумя способами:

1. Сделать seen переменной, чтобы ее можно было обновлять.

2. Передайте набор вместе со списком, который создается в сгибе. Дело становится:

   case ((seen, acc), el) =>