AtCoder ABC155 Problem D Pairs Review Note 2 NumPy und Python

Überblick

Ein Hinweis zu AtCoder ABC155 Problem D Pairs.

Ich habe die Geschwindigkeit von Python und NumPy für "Sortieren" und "Dichotomie" gemessen. Vor der Implementierung erwarteten beide Prozesse, dass NumPy überwältigend gewinnen würde. Mit NumPy ist das Sortieren etwa zehnmal schneller. Die Dichotomieergebnisse zeigen, dass NumPy schneller ist, wenn eine große Anzahl von Schwellenwerten als Liste angegeben wird, Python jedoch schneller als NumPy, wenn eine Funktion für einen Schwellenwert aufgerufen wird. Es ist ziemlich überraschend.

Hintergrund

Fortsetzung von AtCoder ABC155 Problem D Pairs Review Note 1. Es wurde beobachtet, dass der Grund, warum TLE dieses Problem nicht lösen konnte, darin bestand, dass Python langsamer als NumPy war. Also schrieb ich ein Testprogramm, um Python und NumPy zu vergleichen und die Geschwindigkeit zu messen.

Ergebnis

(Das für die Messung verwendete Programm befindet sich unten)

Sortieren Ich habe die Ausführungszeiten von sortiert (Python) und numpy.sort (NumPy) verglichen, als die Größen von List (Python) und Array (NumPy) von 1024 auf 1048576 geändert wurden. Die vertikale Achse des Diagramms ist die Ausführungszeit (Sekunden) und die horizontale Achse ist die Listen- oder Arraygröße.

Jede Messung wurde 16 Mal durchgeführt, und die Grafik zeigt die durchschnittlichen, maximalen und minimalen verstrichenen Zeiten. LIST：Python sorted() ARRAY: NumPy numpy.sort() Aus den Ergebnissen ist ersichtlich, dass die Verarbeitung von Array (NumPy) fast zehnmal schneller ist als die Verarbeitung von List (Python).

Dichotomie

Ich habe die Ausführungszeiten von bisect.bisect_left (Python) und numpy.searchsorted (NumPy) verglichen, als die Größe von List (Python) und Array (NumPy) von 1024 auf 1048576 geändert wurde. Die vertikale Achse des Diagramms ist die Ausführungszeit (Sekunden) und die horizontale Achse ist die Listen- oder Arraygröße. Wenn es sich bei dieser Funktion um ein Problem gleicher Größe handelt, ist sie in viel kürzerer Zeit als beim Sortieren abgeschlossen und es liegt ein Problem mit dem Messsystem vor. 1. Rufen Sie sie 1024 Mal mit einer for-Anweisung auf oder 2. Geben Sie einen Schwellenwert mit 1024 mal LIST 1 an Die Ausführungszeit, wenn die Dichotomie 1024 Mal pro Versuch wiederholt wird, ist aufgetragen.

LIST: 1024-mal mit Python bisect.bisect_left () zur Anweisung aufgerufen ARRAY: 1024 Mal mit NumPy numpy.searchsorted () zur Anweisung aufgerufen ARRAY2: NumPy numpy.searchsorted () Einmal mit einer Liste der Größe 1024 aufrufen, die als zweites Argument übergeben wurde

Jede Messung wurde 16 Mal durchgeführt, und die Grafik zeigt die durchschnittlichen, maximalen und minimalen verstrichenen Zeiten. Das Array verwendet die for-Anweisung, um numpy.searchsorted () 1024 Mal pro Versuch aufzurufen. Für Array2 wird dieselbe Verarbeitung pro Versuch durchgeführt, indem dem zweiten Argument von numpy.searchsorted () eine Liste der Größe 1024 zugewiesen wird.

Aufgrund des Ergebnisses ist die Leistung in der Reihenfolge Array2 (NumPy), List (Python), Array (NumPy) besser. Der Leistungsunterschied nimmt mit zunehmender Größe tendenziell ab. Selbst mit der Größe 1048576 ist Array2 (NumPy) um ein Vielfaches besser als andere. Es war ein wenig überraschend, dass Python bisect.bisect_left () eine bessere Leistung zu erzielen schien als NumPy numpy.searchsorted (), wenn keine Liste als zweites Argument verwendet wurde.

Impressionen

Aufgrund dieses Geschwindigkeitsunterschieds konnte mein Programm in AtCoder ABC155 Problem D Pairs nicht TLE-fähig sein, weil ich NumPy nicht verwendet habe. Es wird gefolgert. Es gibt viele Dinge, an die ich mich erinnern muss. Ich würde gerne einen C ++ - Test mit der gleichen Frage zum Üben ausprobieren, wenn ich die Gelegenheit dazu habe.

Appedix Programm zum Testen verwendet

python:random.bisect.py

import math
import sys
import numpy as np
import random
import time
import bisect

args = sys.argv
stdin = sys.stdin
rangeMax = 2 ** 60
n_bisect_try = 1024
target = [random.randrange(0,rangeMax) for _ in range(n_bisect_try)]

print(rangeMax) 
N = int(args[1])

def start_time():
    global start
    start = time.time()

def end_time(header="Elapsed time: "):
    global start
    elapsed_time = time.time() - start
    print("{0}{1:0.7f}".format(header,elapsed_time))
    return elapsed_time

start_time()
s = [ random.randrange(0,rangeMax) for _ in range(N)]
end_time('Time Generate Random List: ')
# print(s)    

start_time()
sn = np.array(s)
end_time('Time Make Array: ')


start_time()
s_sort = sorted(s)
end_time("Time List Sort: ")
#print(s,s_sort)

start_time()
for t in target:
    i  = bisect.bisect_left(s_sort,t)
    #print("Result List Bisect:", i)
end_time("Time List Bisect: ")

start_time()
sn_sort = np.sort(sn)
end_time("Time Array Sort: ")
# print(sn,sn_sort)

start_time()
for t in target:
    i  = np.searchsorted(sn_sort,t)
    # print("Result List Bisect:", i)
end_time("Time Array Bisect: ")

start_time()
i_array  = np.searchsorted(sn_sort,target)
#print("Result List Bisect2:", i_array)
end_time("Time Array Bisect2: ")