@Finn_h: Mal so ganz allgemein sind da ein paar Ecken die komisch sind.
Beispielsweise die Ausführung. Das sieht so aus, als wenn das von einem anderen Modul aus ausgeführt wird in dem es importiert wird und sich dann aus diesem oder einem weiteren Modul die Werte auf denen es operiert wiederum per Import holt. Das ist sehr sehr sehr falsch!
Auf Modulebene sollte nur Code stehen der Konstanten, Funktionen, und Klassen definiert. Kein Code der irgendwelche Ergebnisse berechnet. So etwas gehört in eine Funktion. Und alles was Funktionen und Methoden ausser Konstanten benötigen, bekommen sie als Argument(e) übergeben. Man verwendet keine globalen Variablen. Weder in dem man auf Modulebene Datenstrukturen anlegt und manipuliert, und schon gar nicht per ``global``. Falls Du ``global`` irgendwo verwendest, dann vergiss sofort, dass es das gibt, und schreib den Code sauber ohne globalen Zustand.
`find_neigbors()` fügt beispielsweise Elemente an die globale `neighbours`-Liste an *und* gibt die als Ergebnis zurück. Das ist verwirrend. Entweder übergibt man `neighbours` und das wird in der Funktion verändert und *nicht* zurückgegeben, denn wenn es als Argument übergeben wurde, hat der Aufrufer das Objekt ja bereits. Oder man erstellt in `find_neigbors()` eine neue Liste und gibt die dann an den Aufrufer zurück. Das wäre die sauberere, übersichtlichere Lösung.
Geunddatentypen wie `list` haben nichts in Namen zu suchen. Man ändert den Typ während der Entwicklung gerne mal und dann hat man entweder falsche, irreführende Namen im Quelltext, oder man muss die immer überall anpassen.
Namen sollten auch nicht abgekürzt werden oder kryptische Prä- und/oder Postfixe enthalten. Wenn man `coordinates` meint, sollte man bitte nicht `koos` schreiben.
Da sind ein paar überflüssige Semikolons im Quelltext. Das ist Python, kein C, C#, C++, Java, oder was auch immer, wo Anweisungen mit einem Semikolon abgeschlossen werden. ``pass`` in eiem Block der davor Code enthält macht auch keinen Sinn.
``for i in range(len(sequence)):`` nur um dann mit dem `i` auf ein Element in `sequence` zuzugreifen ist in Python ein „anti pattern“. Man kann direkt über die Elemente von `sequence` iterieren, ohne den Umweg über einen unnötigen Laufindex. Hör auf in irgendeiner anderen Programmiersprache zu programmieren, schreibe echtes Python. Oder nimm halt tatsächlich die Programmiersprache in der Du eigentlich programmieren willst.
Es gibt da Listen mit Koordinaten und Listen mit Indexwerten in andere Listen und man kann den Unterschied nicht an den Namen erkennen. Das ist verwirrend. Die sollte man passend benennen.
Das nächste was den Code fehleranfällig und ”unsauber” macht ist die Verwendung von `list.clear()`. Das verwendet man nur wenn man tatsächlich eine vorhandene Liste leeren muss die irgendwo anders im Code verwendet wird wo es wichtig ist, das diese Änderung sichtbar ist. Ansonsten verwendet man das nicht, weil das eben auch irgendwo anders im Code Auswirkungen haben kann mit denen man nicht rechnet und die dann zu schwer zu findenen Fehlern führen. Wenn man eine leere Liste braucht, dann erstellt man einfach eine leere Liste. Du kannst Dir dann auch die beiden `tuple()`-Aufrufe sparen, die den Listeninhalt von so einer mit `clear()` wiederverwendeten kopieren, weil das wiederverwenden sonst Probleme macht.
Der Code wird dann auch einfacher weil man nicht mehr überall mit `append()` arbeiten muss, sondern an bestimmten Stellen auch einfach gleich eine literale Liste mit den entsprechenden Werten hinschreiben kann.
Die erste Funktion schrumpft damit auf das hier zusammen:
Code: Alles auswählen
def find_neigbors_indices(pixels_coordinates):
neighbor_indices = list()
for x, y in pixels_coordinates:
pixel_neighbor_indices = list()
for potential_neighbor in [(x + 1, y), (x - 1, y), (x, y + 1)]:
if potential_neighbor in pixels_coordinates:
pixel_neighbor_indices.append(
pixels_coordinates.index(potential_neighbor)
)
neighbor_indices.append(pixel_neighbor_indices)
return neighbor_indices
Davon die innere Schleife in eine „list comprehension“ umgeschrieben:
Code: Alles auswählen
def find_neigbors_indices(pixels_coordinates):
neighbor_indices = list()
for x, y in pixels_coordinates:
neighbor_indices.append(
[
pixels_coordinates.index(potential_neighbor)
for potential_neighbor in [(x + 1, y), (x - 1, y), (x, y + 1)]
if potential_neighbor in pixels_coordinates
]
)
return neighbor_indices
Und dann die äussere Schleife:
Code: Alles auswählen
def find_neigbors_indices(pixels_coordinates):
return [
[
pixels_coordinates.index(potential_neighbor)
for potential_neighbor in [(x + 1, y), (x - 1, y), (x, y + 1)]
if potential_neighbor in pixels_coordinates
]
for x, y in pixels_coordinates
]
`startpoints()` ist kein guter Funktionsname weil der keine Tätigkeit beschreibt und weil so der Name `startpoints` für eine Objekt das Startpunkte repräsentiert, verloren ist. Die Mehrzahl in dem Namen ist ausserdem falsch, weil da nur *ein* Startpunkt ermittelt wird. Also `get_start_point()`.
Das kleinste `x` lässt sich leichter mit einer `min()` und einem Generatorausdruck ermitteln.
Wobei die Funktion gar nicht wirklich sicherstellt, dass es die Koordinate die am Ende heraus kommt, auch tatsächlich in den Übergebenen Koordinaten der Pixel gibt. Soll das so, oder ist das ein Fehler?
In `search_for_neighbor()` kann der Programmfluss am Ende der Funktion ankommen und da steht dann gar kein explizites ``return`` mehr. Da fragt sich der Leser ob das ein Fehler ist oder ob die Funktion noch nicht zuende ausprogrammiert wurde. Erst wenn man die Stelle sieht, wo die Funktion aufgerufen wird, sieht man, dass sich hier auf das implizite `None` verlassen wird. Das sollte explizit in der Funktion stehen.
`coordinates_work_list` hiesse vom Inhalt her besser `remaining_pixels_coordinates`, dann weiss der Leser gleich, was die Werte darin für eine Bedeutung haben. Und man kann die ``while`` Bedingung der ersten ``while``-Schleife auch kürzer formulieren, nämlich einfach ``while remaining_pixels_coordinates:``. Die Art wie diese Liste am Ende von jedem Schleifendurchlauf erstellt wird ist übrigens was die Laufzeit angeht ziemlich pervers. Das tut schon fast körperlich weh das zu lesen.
Wenn man bei `used_coordinates` darauf verzichtet auf das letzte Element mit ``…[-1]`` zuzugreifen, ist man nicht mehr daran gebunden, dass das eine Liste sein muss, und damit könnte man die ``in``-Operation zumindest schon mal beschleunigen, in dem man daraus eine Menge macht (`set`).
`round()` verwendet man nur wenn man mit gerundeten Zwischenergebnissen weiterrechnen will. Für die Ausgabe von einer begrenzten Anzahl von Nachkommastellen verwendet man die Möglichkeiten der Zeichenkettenformatierung.
Zwischenstand (ungetestet):
Code: Alles auswählen
import time
def find_neigbors_indices(pixels_coordinates):
return [
[
pixels_coordinates.index(potential_neighbor)
for potential_neighbor in [(x + 1, y), (x - 1, y), (x, y + 1)]
if potential_neighbor in pixels_coordinates
]
for x, y in pixels_coordinates
]
def get_start_point(pixels_coordinates, height, width):
potential_startpoints = list()
smallest_y = height
for pixel_coordinates in pixels_coordinates:
y = pixel_coordinates[1]
if y < smallest_y:
smallest_y = y
potential_startpoints = [pixel_coordinates]
elif y == smallest_y:
potential_startpoints.append(pixel_coordinates)
smallest_x = min((x for x, _ in potential_startpoints), default=width)
return (smallest_x, smallest_y)
def search_for_neighbor_index(neigbor_indices, used_coordinates_indices):
for index in neigbor_indices:
if index not in used_coordinates_indices:
return index
return None
def find_path(pixels_coordinates, height, width):
start = time.perf_counter()
print("Ab hier beginnt der pathfinder")
pixels_neighbors_indices = find_neigbors_indices(pixels_coordinates)
used_coordinates_indices = set()
path = list()
remaining_pixels_coordinates = pixels_coordinates
while remaining_pixels_coordinates:
start_point = get_start_point(
remaining_pixels_coordinates, height, width
)
point_index = pixels_coordinates.index(start_point)
used_coordinates_indices.add(point_index)
path_segment_indices = [point_index]
while True:
point_index = search_for_neighbor_index(
pixels_neighbors_indices[point_index], used_coordinates_indices
)
if point_index is None:
break
used_coordinates_indices.add(point_index)
path_segment_indices.append(point_index)
path.append(path_segment_indices)
#
# XXX Butt ugly inefficient!
#
remaining_pixels_coordinates = [
pixels_coordinates[i]
for i in range((len(pixels_coordinates)))
if i not in used_coordinates_indices
]
print(path)
finish = time.perf_counter()
print(f"abgeschlossen in {finish - start:.2f} Sekunden")
Das ist jetzt erst einmal nur (fast) genau das was Dein Quelltext gemacht hat, nur etwas mehr in Python. Das sieht aber immer noch sehr danach aus wie etwas das eigentlich in C geschrieben werden wollte.
Was hier nämlich immer noch kein Python ist, sind die Listen die für *alles* verwendet werden und das herumgehampel mit Indexwerten. Das sollte man ohne die undurchsichtigen Indirektionen über Indexwerte lösen, in dem man die Koordinaten selbst verwendet. Und nicht alles muss eine Liste sein. Es gibt auch Mengen und Wörterbücher. Wenn die Koordinaten Tupel (oder was ähnlich ”hashbares”) sind, dann kann man die Koordinaten in Mengen als Elemente nutzen und in Wörterbüchern als Schlüssel. Zum Beispiel um eine Abbildung von Koordinaten auf alle Nachbarn zu erstellen, in der man direkt über die Koordinaten an die Koordinaten der Nachbarn kommen kann. ``in`` und ``index()`` in Listen sind hier ziemliche Performance-Killer, weil beides linear vom Anfang der Liste sucht und alle Elemente anschaut bis zu dem was gesucht wird. Oder wirklich alle, wenn das gesuchte Element gar nicht enthalten ist.
