Python feladat jó megoldás?
Bit műveleteket tanulunk és olyan metódust kell írnom aminek egy tömböt átadva visszaadja 2 szám legnagyobb XOR értékét a tömbből.
Pl ha [3, 1, 2] a tömb:
3 XOR 1 = 2
3 XOR 2 = 1
1 XOR 2 = 3 <- ez a legnagyobb XOR érték tehát 3 a megoldás.
Így csináltam és elvileg működik is:
De nem tudom ez jó megoldás-e mert például minden számot XOR-ol saját magával is ami mindig 0 lesz tehát azt feleslegesnek tűnik ellenőrizni.
Hogyan kéne ezt jobban megcsinálni?
válasza:Igen, nem mindenre jó. Egyébként meg így szerintem gyorsabb lenne:
max([a^b for a in array for b in array])
válasza:Csináltam kíváncsiságból pár mérést.
A: a 2 loopos megoldás
B: a max([a ^ b for a in arr for b in arr]) (11. válaszoló kódja)
C: lineáris megoldás
50 elemű tömb:
A: < 1 ms
B: < 1 ms
C: < 1 ms
500 elemű tömb:
A: 78 ms
B: 46 ms
C: 15 ms
1 000 elemű tömb:
A: 265 ms
B: 140 ms
C: 31 ms
5 000 elemű tömb:
A: 5 609 ms
B: 3 359 ms
C: 125 ms
10 000 elemű tömb:
A: 28 812 ms
B: MemoryError
C: 234 ms
Nem rendes benchmark, csak párszor lefuttattam őket, de nagyságrendileg stimmel szerintem.
Érdekes hogy a B ennyivel gyorsabb az A-nál pedig ha jól értem akkor végülis ugyanazt csinálja.
A MemoryError oka meg gondolom az hogy minden kombinációt berak egy tömbbe.
válasza:A belső ciklushoz nem jó az enumerate sem szerintem de a külsőhöz igen.
#12 megmutatod a lineáris megoldásodat?
#16 Ez nekem nem ad jó eredményt.
Legalábbis ha jól értem akkor a következő sort kéne csak átírni:
sum = sum + idsum
Erre:
sum = max(sum, idsum)
Vagy rosszul gondolom?
válasza:#12 megmutatod a lineáris megoldásodat?
Trie-vel kísérleteztem csak, végül ez lett a leggyorsabb verzió:
válasza:Hastebin szerintem lehalt (vagy csak nálam nem jó), feldobtam pastebinre:
https://pastebin pont com/xkdsQvS1
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!