(F #) Finde den Index des Elements im 2D-Array

Question

Ich habe derzeit einige Probleme beim Finden des Index eines bestimmten Elements in einem 2D-Array. Ich weiß, dass ein Standardarray findIndex wie unten gezeigt verwenden kann.

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

Meine Frage ist, wie Sie dies auf ein 2D-Array (rechteckig) anwenden. Gibt es eine effizientere Möglichkeit, als das gesamte Array zu durchlaufen und jedes Element zu vergleichen?

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)

Wenn ich das gesamte Array durchlaufen muss, wie würde ich mit der Bedingung else umgehen, ohne Optionstypen zu verwenden?

arrays multidimensional-array f#

4

Code Guy 18 Apr. 2018 im 02:28

Answer 1

Antwort auf Ihren Kommentar: Ja, Arrays können nicht mit Listen wie Kopf und Schwanz abgeglichen werden. Aber sie haben Hinweise! :-)

Eine rekursive Funktion muss nicht über die Datenstruktur rekursiv sein. Der rekursive Pfad kann durch etwas anderes definiert sein. Zum Beispiel: Warum rekursieren wir nicht über die Array-Anzeigen von Null bis Max (oder zurück)?

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

Die obige Lösung scannt das Array in Zeilen, bis es das needle findet. An diesem Punkt wird es sofort zurückgegeben.

Alternativ können Sie selbst eine Sequenz optionaler Indizes erstellen und dann mit Seq.tryPick das erste Element dieser Sequenz auswählen, das nicht None ist:

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
}

Aufgrund der Funktionsweise von Sequenzen (sie sind faul) wird dies nur wiederholt, bis das erste Some gefunden wurde, und dann gestoppt. Dies ist etwas einfacher (was die Lesbarkeit betrifft), aber auch etwas weniger performant als die oben beschriebene einfache rekursive Lösung, da hier der Aufwand für das Erstellen und Verwalten der Sequenz anfällt.

4

Fyodor Soikin 18 Apr. 2018 im 15:03

Answer 2

Fjodor Soikin bezog sich auf etwas wie ...

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

Der Grund dafür, dass eine Prädikatfunktion verwendet wird, anstatt nach dem spezifischen Wert zu suchen, liegt in der Art und Weise, wie f # Gleichheitsprüfungen durchführt (andernfalls würde ich empfehlen, die Funktion als "inline" zu markieren, wenn Sie sie durch einen Elementvergleich ersetzen würden ")

2

Paul Westcott 18 Apr. 2018 im 02:16

Answer 3

Eine andere Idee ist eine Funktion, die die einzelnen Zeilen des 2d-Arrays träge auflistet und dann versucht, das Element dieser Zeilen zu finden:

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

Oder wenn sich das Element an mehreren Stellen befindet und Sie eine Liste aller Elemente wünschen:

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

1

Lars 18 Apr. 2018 im 11:02

Answer 4

Mit Standard-F # -Bibliotheken können Sie die folgenden generischen Indexsuchfunktionen für Array2D implementieren:

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

Und benutze es als

findIndexes ((=)soughtValue) yourArray

Diese Implementierung scannt anscheinend das gesamte Array mit Array2D.iteri, aber der Vergleich nach der ersten Übereinstimmung kann durch Kurzschließen im obigen Vergleichsausdruck leicht optimiert werden.

Und schließlich würde ich mich daran halten, das Suchergebnis über idiomatisch Option<int,int> zurückzugeben. Wenn Sie aus irgendeinem Grund das Suchergebnis ohne Verwendung der Option zurückgeben möchten, reicht ein int*int -Tupel aus, wenn Sie ein "unmögliches" Indexpaar wie (-1, -1) als anfänglichen found -Wert und verwenden Indikator für Suchfehler oder Auslösen einer Ausnahme bei Suchfehlern wie bei Array.findIndex.

0

Gene Belitski 18 Apr. 2018 im 04:06

(F #) Finde den Index des Elements im 2D-Array

4 Antworten

Verwandte Fragen

Neue Fragen

arrays