Merkwürdige Leistungen für Mengenoperationen

Question

Alle diese Ergebnisse wurden mit CPython 3.5.2 erhalten.

Ich bemerkte seltsame Leistungen für einige Operationen der set Klasse.

Ich habe die Zeit gemessen, die benötigt wird, um die Vereinigung von zwei Mengen, die nur ganze Zahlen enthalten, durchzuführen. Diese Zeit hängt natürlich von den Größen der Sets ab. Überraschenderweise hängt es auch von der "Dichte" der ganzen Zahlen ab. Hier ist eine grafische Darstellung:

Die x-Achse ist die Summe der Umfänge der beiden Sätze (die voneinander unabhängig und zufällig ausgewählt wurden, für jede Erfahrung). Die y-Achse ist die Zeit in Sekunden (in logarithmischer Skala).

Eine Dichte d bedeutet, dass die Sätze instanziiert wurden, indem N ganze Zahlen von insgesamt N/d ganzen Zahlen genommen wurden. Mit anderen Worten, für eine Dichte von 0,5 nehmen wir die Hälfte der ganzen Zahlen eines Intervalls an, während wir für eine Dichte von 0,1 ein Zehntel der ganzen Zahlen eines (größeren) Intervalls nehmen.

Hier ist ein minimaler Code, um einige Ergebnisse zu erhalten (bei Bedarf kann ich den vollen Code, den ich für das Diagramm verwendet habe, aber es ist länger).

import time 
import random 
import numpy 

def get_values(size, density): 
    return set(random.sample(range(int(size/density)), size)) 

def perform_op(size, density): 
    values1 = get_values(size, density) 
    values2 = get_values(size, density) 
    t = time.time() 
    result = values1 | values2 
    return time.time()-t 

size = 10000000 
for density in [0.05, 0.1, 0.5, 0.99]: 
    times = [perform_op(size, density) for _ in range(10)] 
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times))) 

Union:

density: 0.05, time: 0.9846, standard deviation: 0.0440 
density: 0.10, time: 1.0141, standard deviation: 0.0204 
density: 0.50, time: 0.5477, standard deviation: 0.0059 
density: 0.99, time: 0.3440, standard deviation: 0.0020 

Es gibt etwa einen Faktor 3 für die Rechenzeit zwischen dem schnellsten und dem langsamsten, mit Sätzen eine gleiche Größe aufweisen. Es gibt auch viel mehr Variabilität für niedrige Dichten.

Eine lustige Sache ist, dass für die Kreuzung (ersetzen values1 | values2 durch values1 & values2 in perform_op-Funktion), haben wir auch nicht konstant Leistungen, aber das Muster ist anders:

density: 0.05, time: 0.3928, standard deviation: 0.0046 
density: 0.10, time: 0.4876, standard deviation: 0.0041 
density: 0.50, time: 0.5975, standard deviation: 0.0127 
density: 0.99, time: 0.3806, standard deviation: 0.0015 

ich nicht andere Set-Operationen testen habe .

Ich verstehe nicht, warum es solche Unterschiede gibt. Soweit ich weiß, werden Python-Sets mit Hash-Tabellen implementiert, so dass die Dichte der ganzen Zahlen keine Rolle spielt, solange ihre Hashes gut verteilt sind.

Woher kommen diese unterschiedlichen Leistungen?

Answer 1

Es gibt zwei wichtigsten Faktoren hier:

1. Sie sind unterschiedlicher Größe Ausgänge zu erzeugen; Bei dichten Eingaben überlappt sich die überwiegende Mehrheit der Werte, sodass Sie am Ende viel kleinere Ausgaben produzieren.
2. int hat einen sehr einfachen Hash-Code; es ist nur der Wert der int. Also hash(1234) == 1234. Bei dichten Eingaben bedeutet dies, dass Sie weitgehend zusammenhängende Hash-Codes ohne Überlappung haben, da die Werte immer kleiner sind als die Anzahl der Buckets (z. B. mit 100.000 Werten haben Sie 262.144 Buckets; bei dichten Werten Ihre Hash-Codes Bereich von 0 bis 101.010, so dass kein tatsächlicher Wraparound auftritt modulo 262,144).Darüber hinaus bedeuten die Hash-Codes, die weitgehend sequentiell sind, dass auf den Speicher in einem weitgehend sequentiellen Muster zugegriffen wird (Unterstützung von Cache-Cache-Abruf-Heuristiken). Für spärliche Eingaben gilt dies nicht; Sie haben viele ungleiche Werte, die auf denselben Bucket hashen (weil jeder der 2.000.000 Werte für den 0.05-Fall 7-8 verschiedene Werte hat, die bei 262.144 Buckets auf denselben Bucket hashen). Da Python geschlossenes Hashing verwendet (auch als offene Adressierung bezeichnet), wird bei einer Bucket-Kollision mit nicht gleichen Werten über den gesamten Speicher gesprungen (wodurch der CPU-Cache nicht mehr unterstützt wird), um einen Bucket für den neuen Wert zu finden.

den Eimer Kollision Problem zu demonstrieren:

>>> import random 
>>> vals = random.sample(xrange(int(100000/0.99)), 100000) 
>>> vals_sparse = random.sample(xrange(int(100000/0.05)), 100000) 

# Check the number of unique buckets hashed to for dense and sparse values 
>>> len({hash(v) % 262144 for v in vals}) 
100000 # No bucket overlap at all 
>>> len({hash(v) % 262144 for v in vals_sparse}) 
85002 # ~15% of all values generated produced a bucket collision 

Jeder dieser Werte, die um die set der Suche nach einem nicht besetzten Eimer, die dichten Werte kollidieren gar nicht, hüpfen muss kollidiert so Sie vermeiden diese Kosten vollständig.

Wenn Sie einen Test möchten, die beide Probleme behebt (während immer noch dicht und spärlich Eingänge), versuchen Sie es mit float s (die int Werte nicht gleichwertig sind, weil float Hashing versucht, eine int Äquivalent float zu der Hash gleicher Wert wie int). Um ungleiche Ebenen von tatsächlich gleichen Werten zu vermeiden, wählen Sie die Eingaben aus nicht überlappenden Werten aus, sodass die Größe der resultierenden Union nicht durch die Kombination "dünn" und "dicht" geändert wird. Dies ist der von mir verwendete Code, der unabhängig von der Dichte zu ziemlich gleichmäßigen Zeiten führt: