AtCoder ABC155 Problème D Pairs Review Note 2 NumPy et Python

Aperçu

Une note sur AtCoder ABC155 Problem D Pairs.

J'ai mesuré la vitesse de Python et NumPy pour "sort" et "dichotomie". Avant la mise en œuvre, les deux processus s'attendaient à ce que NumPy gagne massivement. Le tri est environ 10 fois plus rapide dans NumPy. Les résultats de la dichotomie montrent que NumPy est plus rapide en donnant un grand nombre de seuils sous forme de liste, mais Python est plus rapide que NumPy lors de l'appel d'une fonction pour un seuil. C'est assez surprenant.

Contexte

Poursuite de AtCoder ABC155 Problème D Pairs Review Note 1. Il a été observé que la raison pour laquelle TLE ne pouvait pas sortir de ce problème était que Python était plus lent que NumPy. J'ai donc écrit un programme de test pour comparer Python et NumPy et mesuré la vitesse.

résultat

(Le programme utilisé pour la mesure est en bas)

Trier J'ai comparé les temps d'exécution de tri (Python) et numpy.sort (NumPy) lorsque les tailles de List (Python) et Array (NumPy) ont été modifiées de 1024 à 1048576. L'axe vertical du graphique correspond au temps d'exécution (en secondes) et l'axe horizontal correspond à la taille de la liste ou du tableau.

Chaque mesure a été effectuée 16 fois, et le graphique montre les temps écoulés moyen, maximum et minimum. LIST：Python sorted() ARRAY: NumPy numpy.sort() D'après les résultats, on peut voir que le traitement de Array (NumPy) est presque 10 fois plus rapide que le traitement de List (Python).

Dichotomie

J'ai comparé les temps d'exécution de bisect.bisect_left (Python) et numpy.searchsorted (NumPy) lorsque la taille de List (Python) et Array (NumPy) a été modifiée de 1024 à 1048576. L'axe vertical du graphique correspond au temps d'exécution (en secondes) et l'axe horizontal correspond à la taille de la liste ou du tableau. Si cette fonction est un problème de même taille, elle sera complétée dans un temps beaucoup plus court que le tri et il y a un problème avec le système de mesure, donc 1. Appelez-la 1024 fois avec une instruction for ou 2. Donnez un seuil avec 1024 fois LIST 1 Le temps d'exécution lorsque la dichotomie est répétée 1024 fois par essai est tracé.

LISTE: Appelé 1024 fois avec Python bisect.bisect_left () pour instruction ARRAY: appelé 1024 fois avec NumPy numpy.searchsorted () pour instruction ARRAY2: NumPy numpy.searchsorted () Appel une fois avec une liste de taille 1024 passée comme deuxième argument

Chaque mesure a été effectuée 16 fois, et le graphique montre les temps écoulés moyen, maximum et minimum. Le tableau utilise l'instruction for pour appeler numpy.searchsorted () 1024 fois par tentative. Pour Array2, le même traitement est effectué par essai en donnant une liste de taille 1024 au deuxième argument de numpy.searchsorted ().

D'après le résultat, les performances sont meilleures dans l'ordre Array2 (NumPy), List (Python), Array (NumPy). La différence de performance a tendance à se réduire à mesure que la taille augmente. Cependant, même avec la taille 1048576, Array2 (NumPy) a des performances plusieurs fois meilleures que les autres. C'était un peu surprenant que Python bisect.bisect_left () semblait mieux performer que NumPy numpy.searchsorted () lorsqu'aucune liste n'était utilisée comme deuxième argument.

Impressions

À partir de cette différence de vitesse, la raison pour laquelle mon programme n'a pas pu TLE dans AtCoder ABC155 Problem D Pairs est que je n'ai pas utilisé NumPy. C'est déduit. Il y a beaucoup de choses dont je dois me souvenir. Je voudrais essayer un test C ++ avec la même question pour la pratique si j'en ai l'occasion.

Appedix Programme utilisé pour les tests

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