想象一下List[Int]Scala 中的以下內容：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
我想對其應用一種動態過濾器，以便與串列中間相比，對頭/尾過濾的資料更少：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
_ ____ __________ ___________ ______ __
[0, 1, 3, 7, 11, 13] // result
為此，索引從兩端增加下一個 2的冪，從中間開始，2 的冪再次減少：
0, 0 2**0 = 1, 1 2**1 = 3, 3 2^2 = 7等。
為了通過命令式方法實作這一點，可以使用與此類似的代碼：
var log = 0
var idx = 0
val mask: ListBuffer[Int] = mutable.ListBuffer()
while (idx < buffer.size) {
mask = idx
if (idx (2 ** log) < buffer.size / 2) {
idx = 2 ** log
log = 1
} else {
idx = buffer.size - (2 ** log) 1
log -= 1
}
}
這會產生一個掩碼陣列，然后可以用來過濾原始串列，例如mask.flatMap(list.lift)
有人可以幫助我以更簡潔、更實用的方式做到這一點嗎？我基本上需要的是一種使用外部變化狀態來過濾串列的方法。
提前致謝。
uj5u.com熱心網友回復：
使用狀態進行迭代的常用方法是尾遞回（或者您經常reduceLeft使用足夠簡單的情況做同樣的事情）。
這比其他答案更好，因為它是線性的（按索引訪問串列元素會使整個事情成為二次方），并且是尾遞回的（堆疊上沒有額外的空間）。另外，我認為，另一個版本顛倒了過濾元素的順序。
您可以一次遞回地完成它（這比另一個答案更好，因為它是尾遞回的，并且是線性的（通過索引訪問串列元素使實作成為二次方）。
我沒有檢查邏輯，另一個答案建議是不正確的，只是從你的代碼片段中使用它，但這是這個想法：
@tailrec
def filter(
in: List[Int],
midpoint: Int,
out: List[Int]=Nil,
idx: Int = 0,
next: Int = 0,
log: Int = 0
): List[Int] = in match {
case Nil => out.reverse
case head::tail if (idx == next) =>
filter(tail, midpoint, head::out, idx 1, idx pow(2, log).toInt, if (idx < midpoint) log 1 else log-1)
case head::tail => filter(tail, midpoint, out, idx 1, next, log)
}
請注意，這似乎比您的“掩碼”想法效率低，因為它查看串列中的每個元素，而不是跳過被過濾掉的索引，但實際上，只要您使用List，它實際上更有效：首先，無論如何，你的（至少）是 O(N)，因為你必須遍歷整個串列才能確定大小，其次，list.lift(idx)是 O(idx)，所以在串列的末尾，這將是必需的幾乎整個串列的多次遍歷。
現在，如果你有一個索引容器而不是一個串列，那么整個“屏蔽”的想法確實會改善一些事情：
def filter(list: IndexedSeq[Int]) = {
val size = list.size
Iterator.iterate((0, 0)) { case (idx, log) =>
(idx math.pow(2, log).toInt, if idx < size/2 log 1 else log-1)
}.map(_._1).takeWhile(_ < size).map(list)
}
uj5u.com熱心網友回復：
您的代碼片段效果不佳，我不得不對其進行一些調整以使其輸出您想要的結果：
var log = 0
var idx = 0
val resultList: mutable.ListBuffer[Int] = mutable.ListBuffer()
// Fill the result until the middle, increasing the jump size
while (idx < list.size / 2) {
resultList = list(idx)
idx = math.pow(2, log).toInt
log = 1
}
// Fill the result from the middle until the end, decreasing the jump size again
while (idx < list.size && log >= 0) {
resultList = list(idx)
log -= 1
idx = math.pow(2, log).toInt
}
使用您的示例，它可以作業：
val list = (0 to 13).toList -> ListBuffer(0, 1, 3, 7, 11, 13)
但是，通過另一個示例，我得到了：
val list = (0 to 22).toList -> ListBuffer(0, 1, 3, 7, 15)
我不認為這真的是你想要的，是嗎？
無論如何，這是一個更實用的版本：
def filter(list: List[Int]) = {
// recursive function to traverse the list
def recursive(l: List[Int], log: Int, idx: Int, size: Int, halfSize: Int): List[Int] = {
if (idx >= l.size || log < 0) // terminal case: end of the list
Nil
else if (idx < l.size / 2) // first half of the list: increase the jump size
l(idx) :: recursive(l, log 1, idx math.pow(2, log).toInt, size, halfSize)
else // second half of the list: decrease the jump size
l(idx) :: recursive(l, log - 1, idx math.pow(2, log-1).toInt, size, halfSize)
}
// call the recursive function with initial parameters
recursive(list, 0, 0, list.size, list.size / 2)
}
但是，如果 2 過于激進，則按次冪跳躍。如果您靠近串列的中間，則下一次跳躍將在最后結束，您將無法獲得漸進式跳躍衰減。
另一種解決方案是每次將跳轉大小增加一個，而不是使用 2 的冪。當您靠近串列中間時，您還可以保持一個恒定的跳轉大小，以避免在開始前的后半部分跳過太多值減少跳躍大小：
def filter2(list: List[Int]) = {
def recursive(l: List[Int], jumpsize: Int, idx: Int, size: Int, halfSize: Int): List[Int] = {
if (idx >= l.size) // terminal case: end of the list
Nil
else if (idx jumpsize < l.size/2) // first half of the list: increase the jump size
l(idx) :: recursive(l, jumpsize 1, idx jumpsize, size, halfSize)
else if (idx < l.size/2) // around the middle of the list: keep the jump size
l(idx) :: recursive(l, jumpsize, idx jumpsize, size, halfSize)
else { // second half of the list: decrease the jump size
val nextJumpSize = jumpsize - 1
l(idx) :: recursive(l, nextJumpSize, idx nextJumpSize, size, halfSize)
}
}
// call the recursive function with initial parameters
recursive(list, 1, 0, list.size, list.size / 2)
}
在我看來，這個版本的結果要好一些：
val list = (0 to 22).toList -> List(0, 1, 3, 6, 10, 15, 19, 22)
uj5u.com熱心網友回復：
對于某些極端情況，您的問題不是很清楚，這是我的解決方案：
scala> def filter[A](seq: Seq[A], n: Int = 1): Seq[A] = seq match {
| case Nil => Nil
| case Seq(x) => Seq(x)
| case _ => seq.head : filter(seq.drop(n).dropRight(2*n), 2*n) : seq.last
| }
def filter[A](seq: Seq[A], n: Int): Seq[A]
scala> filter(0 to 13)
val res0: Seq[Int] = List(0, 1, 3, 7, 11, 13)
scala> filter(0 to 100)
val res1: Seq[Int] = List(0, 1, 3, 7, 15, 31, 38, 70, 86, 94, 98, 100) // I am not sure if 38 should in the result
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463275.html