Wydajność długich (str) kluczy w słowniku Pythona

Question

Parsuję niektóre xml (z pewnym kodem Pythona 3.4) i chcę pobrać zarówno tekst z węzła, jak i jego atrybut id. Przykład: <li id="12345"> Some text here </li> Mój obecny kod jest uporządkowany tylko wokół tekstu (teraz dodam identyfikator, ale wcześniej tego nie potrzebowałem). Przeszukuję listę tekstu/zdań, a następnie wykonuję kilka czynności. Więc pomyślałem o stworzeniu słownika z tekstem/zdaniem jako kluczem i tym atrybutem id jako wartością.

Jednak nie jest to bardzo skuteczne. Tekst może być całością akapitu, co czyni ten klucz bardzo długim. Natomiast id zawsze ma dość ograniczoną długość (ale nadal typu type, np. Niektóre znaki alfy, po których następuje kilka cyfr). Ale sprawienie, że identyfikator jest kluczem, a tekst wartością, wymaga przepisania kodu. Wszystko to nie jest bardzo problematyczne, ale to tylko mnie zastanowiło: Jak nieskuteczne byłoby, aby tekst (potencjalnie cały akapit) był kluczowy, w porównaniu do identyfikatora takiego jak "ulp_887362487687678" jako klucza?

Potrafię utworzyć dwa słowniki zwrotne (jeden o id jako klucz, a drugi z tekstem jako klucz) i porównać konstrukcję i wyszukiwanie oraz wszystkie. Znalazłem także kilka tematów dotyczących klucza długości limitu (Do Dictionaries have a key length limit?). Ale zastanawiam się tylko, jakie są twoje myśli na ten temat. Czy posiadanie tak długich kluczy w dyktafonie jest czymś, czego na pewno chcesz uniknąć, czy też nie jest to wielka sprawa? Jeśli mógłbyś podzielić się z innymi profesjonalistami/profesjonalistami, byłoby wspaniale!

Answer 1

Nie, długość łańcucha w Pythonie prawie nie ma wpływu na wydajność słownika. Jedyny wpływ, jaki długość łańcucha może mieć na funkcję hash(), polega na odwzorowaniu klucza na szczelinę tabeli mieszania.

długość String ma bardzo niewielki wpływ na wydajność hash():

>>> import random 
>>> from timeit import timeit 
>>> from string import ascii_letters 
>>> generate_text = lambda len: ''.join([random.choice(ascii_letters) for _ in xrange(len)]) 
>>> for i in range(8): 
...  length = 10 + 10 ** i 
...  testword = generate_text(length) 
...  timing = timeit('hash(t)', 'from __main__ import testword as t') 
...  print 'Length: {}, timing: {}'.format(length, timing) 
... 
Length: 11, timing: 0.061537027359 
Length: 20, timing: 0.0796310901642 
Length: 110, timing: 0.0631730556488 
Length: 1010, timing: 0.0606122016907 
Length: 10010, timing: 0.0613977909088 
Length: 100010, timing: 0.0607581138611 
Length: 1000010, timing: 0.0672461986542 
Length: 10000010, timing: 0.080118894577 

zatrzymałem się generując ciąg 10 milionów znaków, bo nie może być jedno, czekając na mój laptop, aby wygenerować 100 milionów łańcuch znaków.

Czasy są prawie stałe, ponieważ wartość jest faktycznie buforowana na obiekcie napisów po obliczeniu.