Как удалить каждый n-й элемент из списка Scala?

Question

Есть ли способ быть в наличии, чтобы удалить все n th element от Scala List?

Надеюсь, мы сможем сделать это внутри метода filter и вернуть другой список, написав логику. Но эффективный ли это способ?

Answer 1

Просто:

list.zipWithIndex 
    .filter { case (_, i) => (i + 1) % n != 0 } 
    .map { case (e, _) => e } 

Answer 2

Простейшее до сих пор, я думаю

def removeNth[A](myList: List[A], n: Int): List[A] = 
    myList.zipWithIndex collect { case (x,i) if (i + 1) % n != 0 => x } 

collect является часто забыт драгоценным камнем, который занимает частичной функции в качестве второго аргумента, отображает элементы с этой функцией и игнорирует те, которые не входят в его область.

Answer 3

подход без индексации, путем измельчения списка на куски длиной nth каждый

xs.grouped(nth).flatMap(_.take(nth-1)).toList 

Из каждого куска поставляемого grouped мы принимаем до nth-1 пунктов.

Этот другой подход не является эффективным (примечание комментарий от @ Алексей Романов), с использованием для понимания, которое desugars в flatMap и (фильтр ленивым) в withFilter,

for (i <- 0 until xs.size if i % nth != nth-1) yield xs(i) 

Answer 4

Вот рекурсивный реализация без индексации.

def drop[A](n: Int, lst: List[A]): List[A] = { 
    def dropN(i: Int, lst: List[A]): List[A] = (i, lst) match { 
     case (0, _ :: xs) => dropN(n, xs) 
     case (_, x :: xs) => x :: dropN(i - 1, xs) 
     case (_, x) => x 
    } 
    dropN(n, lst) 
    } 

Answer 5

еще одна альтернатива, близко к @ ответ Elm, но принимая во внимание, что drop(1) гораздо быстрее списков, чем take ING почти весь список:

def remove[A](xs: List[A], n: Int) = { 
    val (firstPart, rest) = xs.splitAt(n - 1) 
    firstPart ++ rest.grouped(n).flatMap(_.drop(1)) 
} 

Answer 6

Вот хвостовой рекурсией реализация для списка с помощью аккумулятора:

import scala.annotation.tailrec 
    def dropNth[A](lst: List[A], n: Int): List[A] = { 
    @tailrec 
    def dropRec(i: Int, lst: List[A], acc: List[A]): List[A] = (i, lst) match { 
     case (_, Nil) => acc 
     case (1, x :: xs) => dropRec(n, xs, acc) 
     case (i, x :: xs) => dropRec(i - 1, xs, x :: acc) 
    } 
    dropRec(n, lst, Nil).reverse 
    } 

---

Обновление: Как отмечалось в комментариях, я пробовал другие решения здесь на большом входе (1 to 5000000).toList. Те, у кого zipWithIndex filter/collect выходят из строя на OutOfMemoryError, и (не-хвост) рекурсивный сбой на StackOverflowError. Шахта, использующая список cons (::) и tailrec, хорошо работает.

Это потому, что индекс zping-with-index создает новый ListBuffer и добавляет кортежи, что приводит к OOM. И рекурсивный просто имеет 5 миллионов уровней рекурсии, что слишком много для стека.

Рекурсивный хвост не создает ненужных объектов и эффективно создает две копии ввода (то есть 2 * 5 миллионов экземпляров ::), как в O(n).Во-первых, это создание фильтрованных элементов, которые находятся в обратном порядке, потому что выход добавляется x :: acc (в O(1), а добавление List - O(n)). Второй - это просто обратный рекурсивный вывод.

Answer 7

Простейшее решение

scala> def dropNth[T](list:List[T], n:Int) :List[T] = { 
    | list.take(n-1):::list.drop(n) 
    | } 

Answer 8

Еще один подход: сделать функцию для списка, который делает именно то, что вам нужно. Это делает то же самое, как функции dropNth Мартина, но не нуждается в О (п) reverse:

import scala.collection.mutable.ListBuffer 

    implicit class improvedList[A](xs: List[A]) { 
     def filterAllWhereIndex(n: Int): List[A] = { 
     var i = 1 
     var these = xs 
     val b = new ListBuffer[A] 
     while (these.nonEmpty) { 
      if (i != n) { 
      b += these.head 
      i += 1 
      } else i = 1 
      these = these.tail 
     } 
     b.result 
     } 
    } 

    (1 to 5000000).toList filterAllWhereIndex 3 

Если вы хотите эффективным это делает трюк. Плюс он может использоваться как оператор infix, как показано выше. Это хороший образец, чтобы знать, чтобы избежать использования zipWithIndex, который кажется немного тяжелым, как на время, так и в пространстве.