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?
4 Antworten
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.
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 ")
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
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
.
Verwandte Fragen
Neue Fragen
arrays
Ein Array ist eine geordnete lineare Datenstruktur, die aus einer Sammlung von Elementen (Werten, Variablen oder Referenzen) besteht, die jeweils durch einen oder mehrere Indizes gekennzeichnet sind. Wenn Sie nach bestimmten Varianten von Arrays fragen, verwenden Sie stattdessen die zugehörigen Tags: [vector], [arraylist], [matrix]. Wenn Sie dieses Tag verwenden, kennzeichnen Sie die Frage in einer für eine Programmiersprache spezifischen Frage mit der verwendeten Programmiersprache.