Vergleich mit unendlich, wenn geprüft wird, ob ein Punkt über einer Linie liegt

  • Ich habe eine Funktion, die in einer engen Schleife aufgerufen wird. Ich habe meinen Code profiliert und hier liegt mein größter Engpass. Die Funktion ist ziemlich einfach: Sie prüft, ob ein Punkt in (x, y) über einer Linie in (Steigung, Schnittpunkt) liegt.

    Das Problem ist, es muss sich auch mit dem Fall befassen, bei dem die Steigung eine positive Unendlichkeit ist und der Abschnitt den x-Achsenabschnitt ergibt. In diesem Fall sollte die Funktion True zurückgeben, wenn sich der Punkt rechts von der Linie befindet.

    Hier wird die Funktion so geschrieben, wie sie war, als ich den Engpass bemerkte:

     def point_over(point, line):
        """Return true if the point is above the line.
        """
        slope, intercept = line
        if slope != float("inf"):
            return point[0] * slope + intercept < point[1]
        else:
            return point[0] > intercept
     

    Auf meinem Rechner läuft das so schnell:

     >>> timeit("point_over((2.412412,3.123213), (-1.1234,9.1234))", 
               "from __main__ import point_over", number = 1000000)
    1.116534522825532
     

    Da diese Funktion häufig aufgerufen wird, habe ich sie eingebettet, um den Funktionsaufruf-Overhead zu vermeiden. Die eingebettete Version ist ziemlich einfach:

     point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]
     

    Und funktioniert ähnlich in timeit:

     >>> timeit("point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]", 
               "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
    0.9410096389594945
     

    Allerdings beansprucht diese eine Codezeile immer noch den größten Teil der Ausführungszeit in meinem Code, selbst nachdem sie inline ist.

    Warum dauert der Vergleich mit float('inf') länger als einige Berechnungen sowie ein Vergleich? Gibt es eine Möglichkeit, dies schneller zu machen?

    Als Beispiel für das, was ich behaupte, sind hier die Geschwindigkeiten zweier Teile meiner ternären Aussage getrennt und zeitlich festgelegt:

     >>> timeit("line[0] != float('inf')", 
               "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
    0.528602410095175
    >>> timeit("point[0] * line[0] + line[1] < point[1]", 
               "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
    0.48756339706397966
     

    Meine primäre Frage ist, warum der Vergleich mit Unendlich so lange dauert. Zweitens gibt es Tipps, wie man diese beschleunigen kann. Idealerweise gibt es einen magischen (wenn auch unglaublich hackigen) Weg, um die Hälfte der Ausführungszeit dieser Zeile zu halbieren, ohne auf C zu fallen. Andernfalls sagen Sie mir, ich müsste auf C zurückfallen.

    14 November 2014
    200_successAsik
3 answers
  • Andere haben math.isinf() erwähnt. Dies ist jedoch wahrscheinlich schneller, da eine Namenssuche und ein Funktionsaufruf vermieden wird:

     def point_over(point, line, infinity=float("inf")):
        slope, intercept = line
        if slope == infinity:
            return point[0] > intercept
        return point[0] * slope + intercept < point[1]
     

    Im Prinzip stattdessen Bei der Auswertung von float("inf") wird die Funktion bei jedem Funktionsaufruf einmalig zur Funktionsdefinitionszeit ausgewertet und in einer lokalen Variablen gespeichert, indem Sie sie als Argument default deklarieren. (Auf lokale Variablen kann schneller zugegriffen werden als auf globale Variablen.)

    15 November 2011
    Jamie
  • Der langsame Teil von if slope != float("inf") ist zweifellos das Konvertieren der Zeichenfolge in einen Float. Es wäre einfacher, stattdessen einfach if not math.isinf(slope) zu verwenden. Natürlich müssen Sie import math, um dies zu erreichen.

    15 November 2011
    kenny
  • Wenn Sie den Wert von float("inf") in einer Variablen zwischenspeichern, ist dies noch schneller (durch das Vermeiden von Funktionsaufrufen):

     >>> def floatcall():
    ...     return 1.0 == float("inf")
    ... 
    >>> def mathcall():
    ...     return math.isinf(1.0)
    ... 
    >>> inf = float("inf")
    >>> def nocall():
    ...     return 1.0 == inf
    ... 
    >>> timeit.timeit("floatcall()", "from __main__ import floatcall", number=1000000)
    0.37178993225097656
    >>> timeit.timeit("mathcall()", "import math; from __main__ import math call", number=1000000)
    0.22630906105041504
    >>> timeit.timeit("nocall()", "from __main__ import inf, nocall", number=1000000)
    0.17772412300109863
     
    15 November 2011
    dcrosta