Counting of direct-neighbor peaks can be a performance-relevant task and the list of implementations is getting longer. Good reasons to compare the runtime. In a first run, I decided to go for one test set only. Obviously, the different implementations may reveal their strength at different lengths of lists. For instance, the optimal implementation of border value handling seems to be a candidate that depends on the list length.
Output:
count_peaks_schwobaseggl: elapsed time 1.44 s
count_peaks_sahasrara62: elapsed time 1.50 s
count_peaks_saikat: elapsed time 2.27 s
count_peaks_tom_wojcik: elapsed time 4.11 s
count_peaks_igian: elapsed time 3.65 s
count_peaks_cloud_balancing: elapsed time 1.86 s
Implementation:
import random
import time
from typing import List
def measure_runtime_in_s(func, test_lists):
start = time.time()
results = []
for test_list in test_lists:
max_cnt = func(test_list)
results.append(max_cnt)
return time.time() - start, results
def run_experiment(funcs, nlists=1000, len_range=(20, 10000), num_range=(-100, 100)):
assert len(funcs) > 0
# generate test data
test_lists = [[random.randint(*num_range) for _ in range(random.randint(*len_range))]
for _ in range(nlists)]
# run it for all implementations and check results
_, ref_results = measure_runtime_in_s(funcs[0], test_lists)
for func in funcs:
failed = False
time_in_s, results = measure_runtime_in_s(func, test_lists)
if not all(result == ref_result for result, ref_result in zip(results, ref_results)):
failed = True
print(
f"{func.__name__}: elapsed time {time_in_s:.2f} s"
+ (" (FAILED TESTS!)" if failed else ""))
def count_peaks_schwobaseggl(lst):
lst = [float("-inf")] + lst + [float("-inf")]
return sum(a < b > c for a, b, c in zip(lst, lst[1:], lst[2:]))
def count_peaks_sahasrara62(array):
if len(array) < 2:
return 0
array2 = [array[1]] + array + [array[-2]]
count = sum([1 for i in range(len(array2) - 2) if array2[i + 2] < array2[i + 1] > array2[i]])
return count
def count_peaks_saikat(lst):
num = 0
leni = len(lst)
for i in range(leni):
if i == 0:
if lst[i] > lst[i + 1]:
num = num + 1
elif i == leni - 1:
if lst[i] > lst[i - 1]:
num = num + 1
else:
if lst[i] > lst[i - 1] and lst[i] > lst[i + 1]:
num = num + 1
return num
def count_peaks_igian(ls):
res = [ls[0] > ls[1], ls[-1] > ls[-2]]
for n in range(len(ls)-2):
a, b, c = ls[n:n+3]
res.insert(-1, b > max([a, c]))
return sum(res) # < modified
def count_peaks_tom_wojcik(lst: List[int]):
found = 0
for i, current_value in enumerate(lst):
is_first_object = i == 0
is_last_object = i == len(lst) - 1
if is_first_object:
previous_val = None
else:
previous_val = lst[i-1]
if is_last_object:
next_val = None
else:
next_val = lst[i+1]
if is_first_object and not is_last_object:
found += 1 if current_value > next_val else 0
elif is_last_object and not is_first_object:
found += 1 if current_value > previous_val else 0
elif not is_last_object and not is_last_object:
found += 1 if previous_val < current_value > next_val else 0
return found
def count_peaks_cloud_balancing(lst):
lst_len = len(lst)
hits = 0
for i in range(1, lst_len - 1):
num_to_test = lst[i]
before = lst[i - 1]
after = lst[i + 1]
if num_to_test > before and num_to_test > after:
hits += 1
# This is for the case lst contains only 1 member and you want to count it as 1
if lst_len == 1:
hits += 1
# For checking the edges
if lst_len > 1:
if lst[0] > lst[1]:
hits += 1
if lst[lst_len - 1] > lst[lst_len - 2]:
hits += 1
return hits
if __name__ == "__main__":
run_experiment([
count_peaks_schwobaseggl,
count_peaks_sahasrara62,
count_peaks_saikat,
count_peaks_tom_wojcik,
count_peaks_igian,
count_peaks_cloud_balancing,
])
