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. graph-sort-elapsedtime.png

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.

graph-bisect-elapsedtime.png

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: ")

Recommended Posts

AtCoder ABC155 Problem D Pairs Review Note 2 NumPy und Python
AtCoder ABC155 Problem D Pairs Review Note 1
AtCoder ABC 182 Python (A ~ D)
Lösen mit Ruby und Python AtCoder ABC178 D Dynamische Planungsmethode
Lösen mit Ruby und Python AtCoder ABC151 D Suche nach Breitenpriorität
Lösen mit Ruby und Python AtCoder ABC133 D Kumulative Summe
AtCoder ABC151 Problem D Geschwindigkeitsvergleich in C ++ / Python / PyPy
AtCoder ABC156 Problem D Berechnung und Reihenfolge der Bouquet-Mods usw.
Lösen mit Ruby und Python AtCoder ABC138 D Benachbarte Liste
Lösen in Ruby, Python und Java AtCoder ABC141 D Priority Queue
Lösen mit Ruby, Python und numpy AtCoder ABC054 B Matrixberechnung
Lösen mit Ruby, Python und networkx AtCoder ABC168 D Benachbarte Liste
Python-Anfänger Atcoder memo @ Keyence 2020, ABC-Problem
[AtCoder] Löse ABC1 ~ 100 Ein Problem mit Python
Löse AtCoder ABC168 mit Python (A ~ D)
AtCoder ABC 174 Python
AtCoder ABC 175 Python
AtCoder ABC130 D Kumulative Summen-Dichotomie, gelöst durch Ruby und Python
AtCoder ABC 165 D Bodenfunktion in Ruby, Perl, Java und Python gelöst
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 131 D Sortieren von Arrays
[AtCoder] Lösen Sie ein Problem von ABC101 ~ 169 mit Python
Fordern Sie AtCoder (ABC) 164 mit Python heraus! A ~ C Problem
Lösen mit Ruby und Python AtCoder ABC084 D Kumulative Summe der Primzahlen
Python- und Numpy-Tipps
AtCoder ARC080 D Simulation mit Ruby und Python gelöst
Überprüfung des Atcoders ABC158 bis Frage E (Python)
AtCoder ABC 177 Python (A ~ E)
Löse AtCoder ABC166 mit Python
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
Python-Eingabehinweis in AtCoder
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D in Python
Lösen mit Ruby und Python AtCoder AISING2020 D Iterative Square-Methode
Löse ABC175 D in Python
Atcoder ABC165 A-D in Python
Lösen mit Ruby und Python AtCoder ABC011 C Dynamische Planungsmethode
Lösen mit Ruby und Python AtCoder ABC153 E Dynamische Planungsmethode
Atcoder ABC166 A-E in Python
[AtCoder] ABC165C Persönliche Notiz [Python]
AtCoder ABC168 Ein in Ruby und Python gelöster Fallausdruck
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D mit Python
[AtCoder-Kommentar] Gewinnen Sie mit Python das ABC165 C-Problem "Many Requirements"!
Ich wollte das ABC164 A ~ D-Problem mit Python lösen
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 065 C-te Potenz
[Hinweis] Project Euler in Python (Problem 1-22)
Löse ABC166 A ~ D mit Python
ABC166 in Python A ~ C Problem
Löse den Atcoder ABC169 A-D mit Python
AtCoder ABC 114 C-755 mit Python3 gelöst
Vorlage AtCoder ABC 179 Python (A ~ E)
AtCoder Anfängerwettbewerb 174 C Problem (Python)
Lösen mit Ruby und Python AtCoder ABC057 C Zerlegung des Primfaktors Bit vollständige Suche
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 107 B String-Manipulation