Jatszottam egy picit a problemaval. Az eredeti felvetesben meg nem szerepelt az, hogy millios a dict, ezert is irtam a listaba mentest (meg mert arra a legegyszerubb atirni az eredeti, nem mukodot). Termeszetesen ha tul nagy a dict, akkor az lesz a legjobb, ha kulon kigyujtjuk a rossz elemek kulcsait, es utana ezeket toroljuk.
Megirtam az otletek alapjan parat, amihez nem volt kod, a tobbit meg bemasoltam. A kodokat tobbszor lefuttatva nagyon mas szamokat kaptam (a seedet nem akartam fixalni, nem hiszem, hogy szamitananak a konkret szamok), de a torloalgoritmusok idejenek a sorrendje nagyjabol fix volt (kiveve persze, ahol kicsi volt a kulonbseg).
Az eredmenyek:
1_000_000 elem, 1% torlendovel (elsonel csak 10 teszt atlaga volt, utana 100):
306.48188 ms nullptr_lambda
226.72707 ms hory_comprehension
164.18201 ms YleGreg_none
178.61049 ms dumb_for_with_list
180.24219 ms dumb_for_with_tuple
162.95704 ms Raynes_pop
42.37052 ms collect_and_delete_tuple
40.80489 ms collect_and_delete_list_comprehension
innentol 100 teszt atlaga:
308.761951 ms nullptr_lambda
228.882706 ms hory_comprehension
181.400935 ms YleGreg_none
180.352806 ms dumb_for_with_list
180.965113 ms dumb_for_with_tuple
169.337919 ms Raynes_pop
43.717338 ms collect_and_delete_tuple
55.782222 ms collect_and_delete_list_comprehension
299.539108 ms nullptr_lambda
231.145582 ms hory_comprehension
164.153661 ms YleGreg_none
179.763108 ms dumb_for_with_list
185.511865 ms dumb_for_with_tuple
186.877396 ms Raynes_pop
50.006395 ms collect_and_delete_tuple
45.016147 ms collect_and_delete_list_comprehension
1_000_000 elem, 20% torlendo, 100 teszt:
280.340851 ms nullptr_lambda
217.177389 ms hory_comprehension
172.452924 ms YleGreg_none
209.975946 ms dumb_for_with_list
187.794945 ms dumb_for_with_tuple
210.398768 ms Raynes_pop
95.312606 ms collect_and_delete_tuple
89.21088 ms collect_and_delete_list_comprehension
255.113054 ms nullptr_lambda
235.54483 ms hory_comprehension
179.64522 ms YleGreg_none
190.935718 ms dumb_for_with_list
191.051743 ms dumb_for_with_tuple
212.003838 ms Raynes_pop
131.213676 ms collect_and_delete_tuple
106.744159 ms collect_and_delete_list_comprehension
1000-es dict, 1% torlendo, de 100 helyett 100_000 teszt:
0.14031875 ms nullptr_lambda
0.098073557 ms hory_comprehension
0.057327860999999994 ms YleGreg_none
0.055978737 ms dumb_for_with_list
0.053868858 ms dumb_for_with_tuple
0.061609896 ms Raynes_pop
0.038435756 ms collect_and_delete_tuple
0.039400389 ms collect_and_delete_list_comprehension
A kod, ha masnak is lenne kedve hozza:
from random import randint, choice
from time import perf_counter_ns
MAX_NUM = 1_000_000_000
DICT_SIZE = 1_000_000
PERCENTAGE = 1
# PERCENTAGE = 20
TEST_COUNT = 100
# DICT_SIZE = 1_000
# PERCENTAGE = 1
# TEST_COUNT = 100_000
def prepare_dict(n: int, percentage_of_1s) -> dict:
d = {randint(2, MAX_NUM): randint(2, MAX_NUM) for _ in range(n)}
number_of_1s_needed = (n * percentage_of_1s) // 100
keys = tuple(d.keys())
while number_of_1s_needed > 0:
key = choice(keys)
if d[key] != 1:
d[key] = 1
number_of_1s_needed -= 1
return d
def runner(func: callable, d: dict) -> None:
cumulated_time = 0
for _ in range(TEST_COUNT):
new_dict = dict(d)
start_time = perf_counter_ns()
func(new_dict)
end_time = perf_counter_ns()
cumulated_time += end_time - start_time
print(f"{cumulated_time / TEST_COUNT / 1_000_000.0} ms {func.__name__}")
def dumb_for_with_list(d: dict) -> dict:
for k in list(d.keys()):
if d[k] == 1:
del d[k]
return d
def dumb_for_with_tuple(d: dict) -> dict:
for k in tuple(d.keys()):
if d[k] == 1:
del d[k]
return d
def nullptr_lambda(d: dict) -> dict:
return dict(filter(lambda item: item[1] != 1, d.items()))
def hory_comprehension(d: dict) -> dict:
return {k: v for k, v in d.items() if v != 1}
def Raynes_pop(d: dict) -> dict:
for k, v in list(d.items()):
if v == 1:
d.pop(k)
return d
def YleGreg_none(d: dict) -> dict:
for k in d:
if d[k] == 1:
d[k] = None
return d
def collect_and_delete_list_comprehension(d: dict) -> dict:
for k in [k for k, v in d.items() if v == 1]:
del d[k]
return d
def collect_and_delete_tuple(d: dict) -> dict:
for k in tuple(k for k, v in d.items() if v == 1):
del d[k]
return d
def main():
d = prepare_dict(DICT_SIZE, PERCENTAGE)
runner(nullptr_lambda, d)
runner(hory_comprehension, d)
runner(YleGreg_none, d)
runner(dumb_for_with_list, d)
runner(dumb_for_with_tuple, d)
runner(Raynes_pop, d)
runner(collect_and_delete_tuple, d)
runner(collect_and_delete_list_comprehension, d)
if __name__ == '__main__':
main()
Meglepo, de annyira nem rossz a kulcsokat listaba/tuple-be gyujtos megoldas sem. A dict 0-rol felepitese viszont erezhetoen lassabb, fuggetlenul a filter+lambda, vagy dict comprehension megoldastol, bar utobbi picit gyorsabb annal.
szerk: A decoratorokat ismerem, viszont nem akartam bonyolitani, meg nem szerettem volna beszolasokat, hogy biztos amiatt lassabb egyik vagy masik megoldas.