scala - 在 Scala 中表达有状态过滤器的功能方法

Question

想象一下 Scala 中的以下 List[Int]:

[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)

有人可以帮助我以一种更简洁、实用的方式来做到这一点吗？我基本上需要的是一种使用外部变化的状态来过滤列表的方法。

提前致谢。

Answer 1

使用状态进行迭代的常用方法是尾递归(或者您经常在足够简单的情况下使用 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)
}