Effizienteste Lösung für USACO: Triangles - Python

Oct 05 2020

Ich versuche dieses Problem mit Python 3.8 zu lösen . In meinem Code habe ich 3 verschachtelte for-Schleifen verwendet, um jeden einzelnen Punkt zu überprüfen und den größten Bereich mit jedem Satz von Punkten zu speichern. Dieses Programm funktioniert gut, aber es ist \$ O(n^3) \$Zeitkomplexität, und ich frage mich, ob es elegantere / effizientere Lösungen gibt. Gibt es einen effizienteren Algorithmus, der nicht jeden einzelnen Punkt durchläuft, oder ist das notwendig?

Mein Code:

with open("triangles.in", "r") as file_in:
  lines = [x.strip() for x in file_in.readlines()]
  n, points = lines[0], lines[1:]


def main(points):
  largest = 0

  for corner in points:
    cx, cy = corner.split()
    for leg in points:
      lx, ly = leg.split()
      for width in points:
        wx, wy = width.split()
        if lx == cx and wy == cy:
          area = abs(int(ly)-int(cy)) * abs(int(wx)-int(cx))
          
          if area > largest:
            largest = area

  return str(largest)

with open("triangles.out", "w+") as file_out:
  file_out.write(main(points))
  file_out.close()

Die Eingabedatei triangles.in:

Problemübersicht: Gegeben eine Reihe von \$ n \$verschiedene Punkte \$ (X_1, Y_1) \$zu \$ (X_n, Y_n) \$Finden Sie die Fläche des größten Dreiecks multipliziert mit 2, vorausgesetzt, das Dreieck ist ein rechtwinkliges Dreieck (eine der Linien des Dreiecks parallel zur x-Achse und eine andere parallel zur y-Achse).

Antworten

5 superbrain Oct 05 2020 at 18:43

Eine offensichtliche Verbesserung besteht darin, die Saiten nicht zu teilen und die Teile int immer wieder zu konvertieren . Mach es einmal am Anfang:

def main(points):
  points = [tuple(map(int, point.split())) for point in points]
  largest = 0

  for cx, cy in points:
    for lx, ly in points:
      for wx, wy in points:
        if lx == cx and wy == cy:
          area = abs(ly-cy) * abs(wx-cx)
          if area > largest:
            largest = area

  return str(largest)

Und es kann in O (n) gelöst werden. Für jede "Ecke", wie Sie sie nennen, gehen Sie alle Punktpaare durch. Schauen Sie stattdessen einfach den am weitesten entfernten Punkt auf derselben y-Koordinate und den am weitesten entfernten Punkt auf derselben x-Koordinate nach. Das kann in O (n) vorberechnet werden:

with open('triangles.in') as f:
    next(f)
    points = [tuple(map(int, line.split())) for line in f]

xmin, xmax, ymin, ymax = {}, {}, {}, {}
for x, y in points:
    xmin[y] = min(xmin.get(y, x), x)
    xmax[y] = max(xmax.get(y, x), x)
    ymin[x] = min(ymin.get(x, y), y)
    ymax[x] = max(ymax.get(x, y), y)

result = max(max(x - xmin[y], xmax[y] - x) * max(y - ymin[x], ymax[x] - y)
             for x, y in points)

with open('triangles.out', 'w') as f:
    print(result, file=f)

Beachten Sie, dass ich die Ausgabe auch etwas anders gemacht habe. Keine Notwendigkeit für closedich. Das Schließen der Datei für Sie ist der Grund, warum Sie sie withzuerst verwendet haben. Erinnern Sie sich? Und ich ziehe es printvor write, da ich dann nicht in einen String konvertieren muss und den Zeilenenden vertraue, damit sie für die Plattform geeignet sind (vielleicht kein Problem hier, da die Ausgabe nur eine Zeile ist und es ihnen anscheinend egal ist, wie es endet).

PS Diese verdammten ... sie sagten immer wieder, meine Lösung sei aufgrund eines "Laufzeitfehlers oder eines Speicherlimits überschritten" fehlgeschlagen, und ich brauchte eine Weile, um herauszufinden: Stattdessen hatte tuple(map(...))ich meine bevorzugte verwendet [*map(...)]. Aber sie verwenden unerklärlicherweise Python 3.4 und es gab es damals noch nicht. Das sollte aber ein Syntaxfehler sein. Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Dies wird der großartigen Antwort des großartigen Regens ziemlich ähnlich sein.

Schreibfunktionen

Mit Schreibfunktionen können Sie einfacher schreiben, um Code zu pflegen. Bei den algorithmischen Herausforderungen hilft es Ihnen außerdem, sich auf den Algorithmus selbst zu konzentrieren, anstatt sich mit Eingabe / Ausgabe zu befassen.

Schreiben Sie Tests

Sobald Sie eine Funktion haben, ist es einfacher, Tests zu schreiben. (Sie können die Tests auch vor der Funktion schreiben). Dies wird dazu beitragen, verschiedene Implementierungen zu testen, zu testen und zu vergleichen (sowohl in Bezug auf die Richtigkeit als auch in Bezug auf die Leistung).

Optimierungshinweise

Berechnen Sie so wenig wie möglich und stoppen Sie so schnell wie möglich.

Hier könnte dies bedeuten, dass lx == cxSie so schnell wie möglich prüfen und abs(ly-cy)nur einmal pro Tupel (ly, cy) rechnen.

def get_solution_naive_on_smaller_range(points):
    largest = 0
    for cx, cy in points:
        for lx, ly in points:
            if lx == cx:
                dy = abs(ly-cy)
                for wx, wy in points:
                    if wy == cy:
                        dx = abs(wx-cx)
                        area = dy * dx
                        if area > largest:
                            largest = area
    return largest

Berechnen Sie so viel wie möglich vor

Anstatt alle Punkte durchlaufen zu müssen, um die Punkte auf derselben Linie oder Spalte zu finden, die der betreffende Punkt berücksichtigt, könnten wir eine Vorberechnung durchführen, um schnell alle Punkte in derselben Linie (oder Spalte) wie den aktuellen Punkt zu finden.

def get_solution_using_dicts(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        for ly in by_x[cx]:
            dy = abs(ly-cy)
            for wx in by_y[cy]:
                dx = abs(wx - cx)
                area = dy * dx
                if area > largest:
                    largest = area
    return largest

Berechne so wenig wie möglich (wieder)

Für einen bestimmten Punkt müssen nicht alle anderen Punkte in derselben Linie und alle anderen Punkte in derselben Spalte berücksichtigt werden. Wir können nur diejenige betrachten, die vertikal oder horizontal am weitesten entfernt ist.