F# Array.tryFindIndex从一个索引开始搜索

Question

我想知道是否有一种廉价（性能方面）的选择，可以从一个索引开始搜索满足某些条件的数组元素的索引？

Array.tryFindIndex方法没有startIndex参数。我可以使用Array.skip(n)，然后在那里搜索，但似乎为了搜索而创建一个数组开销太大了。我该怎么办呢？

我查看了List，也没有这个参数。我必须使用while ... do吗？有更好的方法吗？

- user1325696

Answer 1

基础库尝试为您提供方便的函数，但它们不可能预先考虑到所有用例。如果需要，编写自己的函数没有问题。

module Array =
    let tryFindIndexFrom i p (a : _ []) =
        let rec loop k =
            if k >= a.Length then None
            elif p a.[k] then Some k
            else loop (k + 1)
        if i < 0 then None else loop i

编辑：p是用于测试数组元素的谓词。 tryFindIndexFrom的签名与tryFindIndex相同，但将起始索引添加为第一个参数。 编辑2：为了防止错误使用，添加了对k < 0的测试。 编辑3：将对k < 0的测试移出循环，因为只需要检查一次。

- dumetrulo

---

也许可以解释一下，'p' 表示谓词，即某个返回 true 或 false 的函数。这是我的猜测。 - sashang

@sashang：确实，“p”是测试数组元素的谓词。 “tryFindIndexFrom”与“tryFindIndex”的签名相同，但在第一个参数中添加了起始索引。 - dumetrulo

如果在 let 后面添加 inline，F# 编译器有时可以内联谓词，从而避免虚拟调用。此外，有时使用 ValueOption<_> 可以避免 GC 压力。因为 OP 谈到了性能便宜的问题。 - Just another metaprogrammer

Answer 2

以下是使用数组索引的惰性序列实现的方法：

最初的回答

let input = [| 'a' .. 'z' |]

seq { 4 .. input.Length - 1 }
|> Seq.tryFind (fun i -> input |> Array.tryItem i = Some 'x')

我会把这个转化成一个帮助函数的工作留给你，如果你认为有必要的话。

当前形式的好处在于它非常灵活。你可以轻松地更改最大索引或向后搜索，例如：seq { input.Length - 1 .. -1 .. 4 }。

最初的回答

- TheQuickBrownFox

Answer 3

跟随你的直觉。虽然考虑使用Array.skip，但明显会浪费分配第二个数组的资源，因此可以更进一步地将其推广到惰性求值的Seq.skip，并将其与标准的Seq.tryFindIndex函数组合，并在适用时添加偏移量。

最初的回答：考虑使用Array.skip，但可能会浪费资源。建议使用Seq.skip进行惰性求值，并与Seq.tryFindIndex函数结合使用，如有必要，请添加偏移量。

let tryFindIndexMin n p =
    Seq.skip n
    >> Seq.tryFindIndex p
    >> Option.map ((+) n)
// val tryFindIndexMin : n:int -> p:('a -> bool) -> (seq<'a> -> int option)

[ for i in 0..3 ->
    [|"a"; "b"; "a"; "b"|]
    |> tryFindIndexMin i ((=) "a") ]
// val it : int option list = [Some 0; Some 2; Some 2; null]

- kaefer

---

这个方法不必分配一个中间数组，但仍然必须迭代遍历 n 个序列项，这可能是较慢的部分。 - TheQuickBrownFox