mboost-dp1
Python og Big O
Meget fin gennemgang. Men er lookup i en hash tabel virkelig O(1), jeg vil mene at der er en cost ved stigende antal keys.
Men, en novice kunne læse en sådan artikel og vurdere at dictionaries bare er bedst og bruge dem selv hvor man kunne have brugt en list. Det fremgår ikke at lists som jo er python's array, jo er en hel grundlæggende datastruktur som de andre bygger oven på, og hvis man kan nøjes med en list, er det bedst pga. mindre overhead.
Men, en novice kunne læse en sådan artikel og vurdere at dictionaries bare er bedst og bruge dem selv hvor man kunne have brugt en list. Det fremgår ikke at lists som jo er python's array, jo er en hel grundlæggende datastruktur som de andre bygger oven på, og hvis man kan nøjes med en list, er det bedst pga. mindre overhead.
larsp (2) skrev:
Meget fin gennemgang. Men er lookup i en hash tabel virkelig O(1), jeg vil mene at der er en cost ved stigende antal keys.
Hvis der ikke er for mange kollisioner så er lookup O(1).
At undgå kollisioner kræver:
- en fornuftig dimensionering af hash tabellen i forhold til antal elementer
- en god hash funktion
Med 100% kollisioner er lookup O(n).
Men problemstillingen har været kendt i mange år og p.g.a. den store betydning for performance så tror jeg godt vi kan regne med at Python har en rimelig god implementering.
Bemærk at udviklere kan stadig skyde sig selv i foden med en dårlig __hash__ metode.
#3
Følgende skulle gerne vise alt:
Følgende skulle gerne vise alt:
import time
class bc(object):
def __init__(self, k):
self.k = k
def __eq__(self, k):
return self.k == k
def __hash__(self):
return self.k.__hash__()
class cc(object):
def __init__(self, k):
self.k = k
def __eq__(self, k):
return self.k == k
def __hash__(self):
return 42
REP = 10000000
a = {}
b = {}
c = {}
def setup(n):
a.clear()
b.clear()
c.clear()
for i in range(n):
a[i] = '#' + str(i)
b[bc(i)] = '#' + str(i)
c[cc(i)] = '#' + str(i)
def test(lbl, ht, k):
t1 = time.time()
for j in range(REP):
if ht.get(k) is None:
raise Exception('Houston we have a problem')
t2 = time.time()
print(' %d lookup of %s key : %.3f s' % (REP, lbl, t2 - t1))
for n in [10, 100, 1000, 10000]:
print('%d elements:' % (n))
setup(n)
test('int', a, n // 2)
test('smart class', b, bc(n // 2))
test('dumb class', c, cc(n // 2))
#4
Ja, klart nok det er O(1). Jeg tænker python dynamisk udvider hashtabellen efter behov. Det er jo en balance mellem at undgå kollisioner og ikke svine med pladsen.
Jeg udvidede med en tilsvarende test af list lookups: ht[k] (og fjernede dumb class:
Hash tabellen med int er godt nok tæt på list. Jeg tænker der stadig køres en hash funktion på en int. Mon det bare er en modulo operator ...
10 elements:
10000000 lookup of int key : 0.279 s
10000000 lookup of smart class key : 1.570 s
10000000 lookup of dumb class key : 6.115 s
100 elements:
10000000 lookup of int key : 0.294 s
10000000 lookup of smart class key : 1.574 s
10000000 lookup of dumb class key : 41.244 s
1000 elements:
10000000 lookup of int key : 0.370 s
10000000 lookup of smart class key : 1.904 s
10000000 lookup of dumb class key : 410.445 s
10000 elements:
10000000 lookup of int key : 0.320 s
10000000 lookup of smart class key : 1.733 s
^C
Ja, klart nok det er O(1). Jeg tænker python dynamisk udvider hashtabellen efter behov. Det er jo en balance mellem at undgå kollisioner og ikke svine med pladsen.
Jeg udvidede med en tilsvarende test af list lookups: ht[k] (og fjernede dumb class:
10 elements:
10000000 lookup of int key : 0.276 s
10000000 lookup of smart class key : 1.570 s
10000000 list lookup of int : 0.192 s
100 elements:
10000000 lookup of int key : 0.278 s
10000000 lookup of smart class key : 1.582 s
10000000 list lookup of int : 0.214 s
1000 elements:
10000000 lookup of int key : 0.320 s
10000000 lookup of smart class key : 1.721 s
10000000 list lookup of int : 0.192 s
10000 elements:
10000000 lookup of int key : 0.323 s
10000000 lookup of smart class key : 1.760 s
10000000 list lookup of int : 0.192 s
Hash tabellen med int er godt nok tæt på list. Jeg tænker der stadig køres en hash funktion på en int. Mon det bare er en modulo operator ...
Tankevækkende at en sådan løkke som i testen ikke bliver bortoptimeret fuldstændig. Der slås op igen og igen det samme sted i noget data der ikke ændres. Det viser noget om pythons performance problemer / udfordringer. Mon ikke en dygtig JIT python kunne klare testen på mikrosekunder.
larsp (6) skrev:
Ja, klart nok det er O(1). Jeg tænker python dynamisk udvider hashtabellen efter behov. Det er jo en balance mellem at undgå kollisioner og ikke svine med pladsen.
Ja. Det gælder alle de dynamiske data strukturer (dict, list etc.) at de har en initial størrelese, der indsættes og på et tidspunkt skal datastrukturen udvides hvilket kræver en allokering af nyt + kopiering fra gammelt til nyt + deallokaring af gammelt.
Og det koster naturligvis.
I nogle sprog kan man angive en initial størrelse, så man kan udnytte at man eventuelt ved ca. hvor mange elementer man vil ende op med.
larsp (6) skrev:
Hash tabellen med int er godt nok tæt på list. Jeg tænker der stadig køres en hash funktion på en int. Mon det bare er en modulo operator ...
dict kalder formentligt bare __hash__() uanset hvilken data type det er.
Og bruger modulus til at skalere ned til hash tabellen regulære område størrelse.
Og hash af en int er meget simpel.
k = 2**61 - 1 # on 64 bit, 2**31 - 1 on 32 bit
v = 1
for i in range(50):
v = v * 10 + 17
print('+%080X' % (v))
print('+%080X' % (v.__hash__()))
print('+%080X' % (v % k))
v2 = -v
print('%081X' % (v2))
print('%081X' % (v2.__hash__()))
print('-%080X' % (-v2 % k))
arne_v (8) skrev:#7
Koden er svær at optimere. Den testes jo for None. Og hvis det var en multi-threaded kode, så kunne en anden tråd fjerne en værdi.
Og man skal vel også lige nærlæse Python specs for at se om spec garanterer at get kalder __hash__ og om det er tilladt at __hash__ kan have side effects. JA + JA vil gøre bortoptimering stort set umulig.
arne_v (8) skrev:#7
Koden er svær at optimere. Den testes jo for None. Og hvis det var en multi-threaded kode, så kunne en anden tråd fjerne en værdi.
Jeg testede lige med GraalPython. Den JIT compiler. Men den optimerer ikke løkken væk.
Iøvrigt er den lidt hurtigere med int key, meget hurtigere med smart class key og det samme med dumb class key.
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Tagwall
Gå til bund