Beispiele für Max

Beim Testen verschiedener Arten von Servern ist es manchmal notwendig, nur eine bestimmte Anzahl von Clients zu bedienen, bevor der Server beendet wird, was zu Code wie dem folgenden führt:

count = 5

def counts(stop):
    i = 0
    while i < stop:
        yield i
        i += 1

for client_number in counts(count):
    handle_one_client()

Wenn Max als Wert zugewiesen wird, der für die Anzahl (count) verwendet wird, wird unser Testserver mit minimalem Aufwand zu einem Produktionsserver.

Als weiteres Beispiel im Dijkstra-Algorithmus für den kürzesten Pfad in einem Graphen mit gewichteten Kanten (alle positiv).

1. Setze die Abstände zu jedem Knoten im Graphen auf Unendlich.
2. Setze den Abstand zum Startknoten auf Null.
3. Setze besuchte Knoten als leere Zuordnung.
4. Solange der kürzeste Abstand eines noch nicht besuchten Knotens kleiner als Unendlich ist und das Ziel noch nicht besucht wurde.
   1. Hole den Knoten mit dem kürzesten Abstand.
   2. Besuche den Knoten.
   3. Aktualisiere Nachbarknotenabstände und Elternzeiger bei Bedarf für Nachbarknoten, die noch nicht besucht wurden.
5. Wenn das Ziel besucht wurde, gehe die Elternzeiger rückwärts durch, um den umgekehrten Pfad zu finden, der genommen werden soll.

Unten ist ein Beispiel für den Dijkstra-Algorithmus für den kürzesten Pfad in einem Graphen mit gewichteten Kanten, der eine Tabelle verwendet (eine schnellere Version, die einen Heap verwendet, ist verfügbar, aber diese Version wird aufgrund ihrer Ähnlichkeit mit der obigen Beschreibung angeboten, die Heap-Version ist über ältere Versionen dieses Dokuments verfügbar).

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
        table[node] = (0, Max, node, None)                     #1
    table[S] = (0, 0, S, None)                                 #2
    cur = min(table.values())                                  #4a
    while (not cur[0]) and cur[1] < Max:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child][0] and ndist < table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
        cur = min(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

Die Leser sollten beachten, dass das Ersetzen von Max im obigen Code durch eine beliebig große Zahl nicht garantiert, dass der kürzeste Pfad zu einem Knoten diese Zahl niemals überschreitet. Nun, mit einer Einschränkung: Man könnte sicherlich die Gewichte jeder Kante im Graphen aufsummieren und die „beliebig große Zahl“ auf diese Summe setzen. Dies macht den Algorithmus jedoch nicht einfacher zu verstehen und birgt potenzielle Probleme mit numerischen Überläufen.

Gustavo Niemeyer [7] weist darauf hin, dass die Verwendung einer Python-tauglicheren Datenstruktur als Tupel zur Speicherung von Informationen über Knotendistanzen die Lesbarkeit erhöht. Zwei äquivalente Knotenstrukturen (eine mit None, die andere mit Max) und ihre Verwendung in einem entsprechend modifizierten Dijkstra-Algorithmus für den kürzesten Pfad sind unten aufgeführt.

class SuperNode:
    def __init__(self, node, parent, distance, visited):
        self.node = node
        self.parent = parent
        self.distance = distance
        self.visited = visited

class MaxNode(SuperNode):
    def __init__(self, node, parent=None, distance=Max,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        return cmp((self.visited, self.distance),
                   (other.visited, other.distance))

class NoneNode(SuperNode):
    def __init__(self, node, parent=None, distance=None,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        pair = ((self.visited, self.distance),
                (other.visited, other.distance))
        if None in (self.distance, other.distance):
            return -cmp(*pair)
        return cmp(*pair)

def DijkstraSP_table_node(graph, S, T, Node):
    table = {}                                                 #3
    for node in graph.iterkeys():
        table[node] = Node(node)                               #1
    table[S] = Node(S, distance=0)                             #2
    cur = min(table.values())                                  #4a
    sentinel = Node(None).distance
    while not cur.visited and cur.distance != sentinel:        #4
        cur.visited = True                                     #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child].visited and\                   #|
               ndist < table[child].distance:                  #|
                table[child].distance = ndist                  #|_
        cur = min(table.values())                              #4a
    if not table[T].visited:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur].parent is not None:                       #|
        path.append(table[cur].parent)                         #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

Im obigen Fall wäre die Übergabe von entweder NoneNode oder MaxNode ausreichend, um entweder None oder Max für die Knotendistanz „Unendlich“ zu verwenden. Beachten Sie den zusätzlichen Sonderfall, der für die Verwendung von None als Sentinel in NoneNode in der __cmp__-Methode erforderlich ist.

Dieses Beispiel hebt die Sonderfallbehandlung hervor, bei der None als Sentinelwert für Höchstwerte „in freier Wildbahn“ verwendet wird, obwohl None selbst kleiner als jedes andere Objekt in der Standarddistribution verglichen wird.

Nebenbei bemerkt der Autor nicht, dass die Verwendung von Knoten als Ersatz für Tupel die Lesbarkeit signifikant, wenn überhaupt, erhöht hat.

Ein Min-Beispiel

Ein Anwendungsbeispiel für Min ist ein Algorithmus, der das folgende Problem löst [5]

Angenommen, Sie erhalten einen gerichteten Graphen, der ein Kommunikationsnetzwerk darstellt. Die Knoten sind die Punkte im Netzwerk, und jede Kante ist ein Kommunikationskanal. Jede Kante (u, v) hat einen zugeordneten Wert r(u, v), mit 0 <= r(u, v) <= 1, der die Zuverlässigkeit des Kanals von u nach v darstellt (d. h. die Wahrscheinlichkeit, dass der Kanal von u nach v nicht ausfällt). Angenommen, die Zuverlässigkeitswahrscheinlichkeiten der Kanäle sind unabhängig. (Dies impliziert, dass die Zuverlässigkeit eines Pfades das Produkt der Zuverlässigkeit der Kanten entlang des Pfades ist.) Nun nehmen Sie zwei Knoten im Graphen, A und B.

Ein solcher Algorithmus ist eine 7-zeilige Modifikation des obigen DijkstraSP_table-Algorithmus (modifizierte Zeilen mit * gekennzeichnet)

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
*       table[node] = (0, Min, node, None)                     #1
*   table[S] = (0, 1, S, None)                                 #2
*   cur = max(table.values())                                  #4a
*   while (not cur[0]) and cur[1] > Min:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
*           ndist = distance*cdist                             #|
*           if not table[child][0] and ndist > table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
*       cur = max(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

Beachten Sie, dass es eine Möglichkeit gibt, den Graphen so zu übersetzen, dass er unverändert an den ursprünglichen DijkstraSP_table-Algorithmus übergeben werden kann. Es gibt auch eine Handvoll einfacher Methoden zur Erstellung von Knotenobjekten, die mit DijkstraSP_table_node funktionieren würden. Solche Übersetzungen werden dem Leser als Übung überlassen.

Andere Beispiele

Andrew P. Lentvorski, Jr. [6] hat darauf hingewiesen, dass verschiedene Datenstrukturen, die Bereichssuche beinhalten, unmittelbaren Nutzen für Max und Min Werte haben. Genauer gesagt: Segmentbäume, Bereichsbäume, k-d-Bäume und Datenbank-Schlüssel.

…Das Problem ist, dass ein Bereich auf einer Seite offen sein kann und nicht immer einen initialisierten Fall hat.

Die von mir gesehenen Lösungen sind entweder die Überladung von None als Extremwert oder die Verwendung einer beliebigen Zahl mit großem Betrag. Die Überladung von None bedeutet, dass die eingebauten Funktionen nicht wirklich ohne spezielle Fallprüfungen verwendet werden können, um die undefinierte (oder „falsch definierte“) Ordnung von None zu umgehen. Diese Prüfungen neigen dazu, die gute Leistung von eingebauten Funktionen wie max() und min() zu beeinträchtigen.

Die Wahl einer Zahl mit großem Betrag verzichtet auf die Fähigkeit von Python, mit beliebig großen Ganzzahlen umzugehen, und führt eine potenzielle Quelle für Überlauf-/Unterlauf-Fehler ein.

Weitere Anwendungsbeispiele für Max und Min finden sich im Bereich der Graphenalgorithmen, Bereichssuchalgorithmen, algorithmischen Geometriealgorithmen und anderen.

Unabhängige Implementierungen?

Unabhängige Implementierungen des Min/Max-Konzepts durch Benutzer, die eine solche Funktionalität wünschen, werden wahrscheinlich nicht kompatibel sein und sicherlich inkonsistente Reihenfolgen erzeugen. Die folgenden Beispiele sollen zeigen, wie inkonsistent sie sein können.

• Nehmen wir an, wir hätten ordnungsgemäße separate Implementierungen von MyMax, MyMin, YourMax und YourMin mit demselben Code wie in der Beispielimplementierung erstellt (mit einigen geringfügigen Umbenennungen).

  >>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
  YourMax, MyMax]
  >>> lst.sort()
  >>> lst
  [YourMin, YourMin, MyMin, MyMin, YourMin, MyMax, MyMax, YourMax,
  MyMax]
  

  Beachten Sie, dass, obwohl alle „Min“-Werte vor den „Max“-Werten stehen, keine Garantie besteht, dass alle Instanzen von YourMin vor MyMin kommen, die Umgekehrte, oder die entsprechenden MyMax und YourMax.

• Das Problem zeigt sich auch bei der Verwendung des heapq-Moduls.

  >>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
  YourMax, MyMax]
  >>> heapq.heapify(lst)  #not needed, but it can't hurt
  >>> while lst: print heapq.heappop(lst),
  ...
  YourMin MyMin YourMin YourMin MyMin MyMax MyMax YourMax MyMax
  

• Darüber hinaus könnten der findmin_Max-Code und beide Versionen von Dijkstra zu falschen Ausgaben führen, indem sekundäre Versionen von Max übergeben werden.

Es wurde darauf hingewiesen [7], dass die nachstehende Referenzimplementierung nicht mit unabhängigen Implementierungen von Max/Min kompatibel wäre. Der Sinn dieser PEP ist die Einführung von „The One True Implementation“ des „The One True Maximum“ und „The One True Minimum“. Benutzerdefinierte Implementierungen von Max und Min Objekten würden somit entmutigt und die Verwendung von „The One True Implementation“ offensichtlich gefördert. Mehrdeutiges Verhalten, das sich aus der Vermischung von benutzerdefinierten Implementierungen von Max und Min mit „The One True Implementation“ ergibt, sollte durch Variablen- und/oder Quellcode-Introspektion leicht erkennbar sein.