AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python

Overview

A note about AtCoder ABC155 Problem D Pairs.

I measured the speed of Python and NumPy for "sorting" and "dichotomy". Before the implementation, both processes expected NumPy to win overwhelmingly. Sorting is about 10 times faster with NumPy. The dichotomy shows that NumPy is faster when giving a large number of thresholds as a list, but Python is faster than NumPy when calling a function for one threshold. It's quite surprising.

Background

Continuation of AtCoder ABC155 Problem D Pairs Review Note 1. It was observed that the reason why I couldn't get out of TLE with this problem seems to be that Python is slower than NumPy. So I wrote a test program to compare Python and NumPy and measured the speed.

result

(The program used for the measurement is at the bottom)

sort I compared the execution times of sorted (Python) and numpy.sort (NumPy) when I changed the size of List (Python) and Array (NumPy) from 1024 to 1048576. The vertical axis of the graph is the execution time (seconds), and the horizontal axis is the List or Array size.

Each measurement was performed 16 times, and the graph shows the average, maximum, and minimum elapsed times. LIST：Python sorted() ARRAY: NumPy numpy.sort() From the result, it can be seen that the processing of Array (NumPy) is almost 10 times faster than the processing of List (Python).

Dichotomy

I compared the execution times of bisect.bisect_left (Python) and numpy.searchsorted (NumPy) when changing the size of List (Python) and Array (NumPy) from 1024 to 1048576. The vertical axis of the graph is the execution time (seconds), and the horizontal axis is the List or Array size. If this function is a problem of the same size, it finishes in a much shorter time than sorting and there is a problem with the measurement system, so 1. Call it 1024 times with a for statement or 2. Give a threshold with 1024 times LIST 1 The implementation time is plotted when the dichotomy is repeated 1024 times per trial.

LIST: Python bisect.bisect_left () Called 1024 times with for statement ARRAY: Call 1024 times with NumPy numpy.searchsorted () for statement ARRAY2: NumPy numpy.searchsorted () Call once with a list of size 1024 passed as the second argument

Each measurement was performed 16 times, and the graph shows the average, maximum, and minimum elapsed times. The Array uses a for statement to call numpy.searchsorted () 1024 times per attempt. Array2 performs the same processing per trial by giving a list of size 1024 to the second argument of numpy.searchsorted ().

From the result, the performance is better in the order of Array2 (NumPy), List (Python), Array (NumPy). The performance difference tends to shrink as the size increases. However, even with size 1048576, Array2 (NumPy) is several times better than others. It was a bit surprising that Python bisect.bisect_left () seemed to perform better than NumPy numpy.searchsorted () when no list was used as the second argument.

Impressions

From this speed difference, I couldn't TLE my program in AtCoder ABC155 Problem D Pairs because I didn't use NumPy. It is inferred that. There are many things I have to remember. I would like to try a C ++ test with the same question for practice if I have the opportunity.

Appedix Program used for testing

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