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

Question

我想知道是否有一个便宜的（性能方面的）选项来搜索从索引开始满足特定条件的数组元素的索引？

Array.tryFindIndex 方法没有参数 startIndex。我可以执行 Array.skip(n) 然后在那里搜索，但创建一个仅用于搜索的数组似乎很昂贵。我该怎么做？

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

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

的测试移出了循环，因为它只需要检查一次。

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 }

。

Answer 3

跟随你的直觉。考虑到

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]

Answer 4

例如，我正在从某个 startIndex 索引开始的字节数组中搜索 LF 字符。我有一些不同函数 f 的类，我在其中放置函数 find10:

module Main =
  type f =
   static member find10(bytes:inref<byte[]>,startIndex:int)=
      if i<=bytes.Length then
        if bytes[]<>b10 then f.find10(&bytes,i+m1) |> ignore
      i

常量 m1 为 1，b10 为字节 10。现在您可以像这样参考您的代码：

let i=f.find10(&bytes,startIndex)