(F#) 在二维数组中查找元素的索引

Question

我目前有一些问题，无法在2D数组中找到特定元素的索引。我知道标准数组可以使用下面所示的findIndex。

let wantedElemented = 5
let index = Array.findIndex(fun x -> x = wantedElemented) array

我的问题是，如何将这个应用到一个二维数组（矩形）。有比迭代整个数组并比较每个元素更有效的方法吗？

for row in 0 .. max do
        for col in 0 .. max do
            if array.[row,col] = wantedElement then 
            let index = (row,col)
            index
            else (-1,-1)

如果我必须遍历整个数组，又不想使用选项类型，那么如何处理else条件语句呢？

- Code Guy

---

如果你想要“提前停止”语义，你必须使它递归。 - Fyodor Soikin

你如何在二维数组中实现这个功能？据我所知，数组不支持头尾模式匹配。 - Code Guy

Answer 1

作为对你的留言的回应：是的，数组不能像列表一样使用头和尾进行匹配。但是它们确实有索引！:-)

递归函数不一定要对数据结构进行递归。递归路径可以由其他东西定义。例如：为什么我们不从零到最大（或相反）递归数组索引呢？

let find2D needle (arr: int [,]) = 
    let rec go x y =
          if   y >= arr.GetLength 1 then None
          elif x >= arr.GetLength 0 then go 0 (y+1)
          elif arr.[x,y] = needle   then Some (x,y)
          else go (x+1) y
    go 0 0

上述解决方案将按行扫描数组，直到找到 needle，此时将立即返回。

或者，您可以生成一个可选索引的序列，然后使用 Seq.tryPick 选择该序列中第一个不是 None 的元素：

let find2D needle (arr: int [,]) = Seq.tryPick id <| seq {
    for i in 0..(arr.GetLength 0 - 1) do
        for j in 0..(arr.GetLength 1 - 1) do
            if arr.[i,j] = needle 
                then yield Some (i,j) 
                else yield None
}

由于序列的工作方式（它们是懒惰的），这将只迭代到第一个Some被找到，然后停止。这个方案比上面的纯递归解决方案稍微更加直接（就可读性而言），但也稍微不如上面的方案高效，因为在此处我们会产生创建和维护序列的开销。

- Fyodor Soikin

---

如 https://dev59.com/eKrka4cB1Zd3GeqPhrO1#49890136 所述，如果您在非内联函数中对通用类型使用“=”运算符，则可能会导致性能下降。对于标准类型和引用类型来说没问题，但它会将非标准值类型装箱，因此建议按照先前提到的链接使用谓词函数实现代码。 - Paul Westcott

@PaulWestcott 这不是问题的关键。当提问者似乎是新手时，我会尽量避免在我的回答中添加无关的细节。 - Fyodor Soikin

Answer 2

Fyodor Soikin提到的是类似于...的东西。

module Array2D =
    let findIndex f (array:'a[,]) =
        let xStart = array.GetLowerBound 0
        let xEnd   = array.GetUpperBound 0
        let yStart = array.GetLowerBound 1
        let yEnd   = array.GetUpperBound 1
        let rec iterate i j =
            if   f array.[i,j] then Some (i, j)
            elif j < yEnd      then iterate i (j+1)
            elif i < xEnd      then iterate (i+1) yStart
                               else None
        iterate xStart yStart

[<EntryPoint>]
let main argv =
    let testArray = Array2D.init 20 20 (fun _ _ -> 0)
    testArray.[13,12] <- 1

    match testArray |> Array2D.findIndex (fun x -> x = 1) with
    | Some (x,y) -> printfn "found at (%d,%d)" x y
    | None -> printfn "not found"

    0

此外，使用谓词函数而不是寻找特定值的原因是由于F#进行相等性检查的方式（否则，如果您要替换为元素比较，则建议将函数标记为“内联”）。

- Paul Westcott

Answer 3

另一个想法是创建一个函数，它能够懒惰地枚举二维数组的每一行，并尝试查找这些行中的元素：

let rows arr2D =
    seq {
        for i in Array2D.base1 arr2D .. Array2D.length1 arr2D - 1 -> arr2D.[i, *]
    }

let find2D arr2D elem =
    arr2D
    |> rows 
    |> Seq.mapi (fun i arr ->
        Array.tryFindIndex ((=) elem) arr 
        |> Option.map (fun j -> i, j)) 
    |> Seq.pick id

或者，如果该元素可以在多个位置找到，并且您想要列出所有这些位置的列表:

let findAll2D arr2D elem =
    arr2D
    |> rows 
    |> Seq.mapi (fun i arr ->
        Array.tryFindIndex ((=) elem) arr 
        |> Option.map (fun j -> i, j)) 
    |> Seq.choose id

- Lars

---

使用序列是实现惰性计算的好方法，但它并不够彻底：创建所有这些中间数组会浪费大量内存和循环。更加优雅的方法是创建一个迭代单个单元格的序列。 - Fyodor Soikin

Answer 4

使用标准 F# 库，您可以实现以下针对 Array2D 的通用索引查找函数：

let findIndexes f (aa: 'a[,]) =
    let mutable found = None
    aa |> Array2D.iteri (fun x y a -> if found.IsNone && (f a) then found <- Some(x,y))
    found

并将其用作

findIndexes ((=)soughtValue) yourArray

这个实现显然使用Array2D.iteri扫描整个数组，但在第一次匹配后的比较中，可以通过比较表达式上的短路稍微优化。

最后，我建议通过惯用的Option<int,int>返回搜索结果。如果出于某种原因，您想要在不使用选项的情况下返回搜索结果，则可以使用一些“不可能”的索引对，如(-1,-1)作为初始found值和搜索失败的指示器，或者像Array.findIndex一样在搜索失败时抛出异常。

- Gene Belitski

---

有特定的原因会投反对吗？ - Gene Belitski