Hogyan lehetne tovább optimalizálni ezt a megoldást?

#20 Azt hiszem értem mit akar az úriember mondani, csak rettenetesen fogalmazza meg.

Az algoritmus noha nem foglal le új tömböt, de a működése érdekében az eredeti tömb elemeinek el kell tudnia tárolni a tömb elemszámának négyzetét. 16 biten a 10 000 elfér, de a 100 000 000 már nem, tehát 32 bites intekre van szükséged hogy az algoritmus biztosan működjön. Így ugyanaz a memóriaigénye, mintha két 16 bites integerekből álló tömböd lenne.

A readonly megjegyzése pedig arra vonatkozik, hogy nem minden esetben megengedhető, hogy az eredeti tömböt módosítgasd, bár ennél a példánál könnyen visszaállítható az eredeti tömb. Őszintén szólva ez mindegy is, mert ez az algoritmus amilyen elmés, olyannyira undorító, és valós életbeli szituációkban úgysem használna senki ilyet, max olyan szituációkban, ahol az utolsó bitet is ki kell optimalizálni belőle (noha mint kiderült ebben a formában semmit nem spórolsz vele).

Az a lényeg, hogy a #10-es kódja az állításával ellentétben nem O(1) space.

Kevesebb lesz a memória használat?

Valószínűleg igen. Pythont nem ismerem, hogy mikor szabadítja fel a memóriát, hisz ott minden objektum. Egy 32 bites szám is 12/24 byte (32/64 bites verziótól függően). Tehát eleve nem hatékony.

Más nyelveken (C/C++/C#/Java) biztosan kevesebb lesz a memória használat az említett feltételekkel.

Gyorsabb lesz? Biztosan nem, sőt lassabb, hiszen egy moduló számítás extraként van minden lépésben.

Az a gond, hogy nagyon sok "programozó" észre sem veszi a trükköt és jön a követelmény módosítás, hogy 10000 helyett legyen 100000 elem. Látják, hogy mindenhol (tfh. nem Python kód) 32 bites számokat használnak, mi baj lehet? Aztán nem fog működni egyes esetekben (elég ritka esetben, amikor sok egyforma szám van)

Állásinterjún valóban előny lehet egy trükkös kód.. de szerintem nem az itteni, hanem amikor ténylegesen olyan módot találunk hogy az aktuális értelmezési tartományban is elférjenek a számok. Mint pl. a klasszikus hogyan cseréljünk fel 2 számot ideiglenes változó nélkül.

Versenyeken pont a kis korlát miatt ez nem lesz előny, hiszen nem lényegesen kisebb a memória foglalás, de lassabb a kód... és ott általában a sebességet mérik addig amíg a memória használat egy észerű korlátok között van.

Ha megemeljük a korlátot, akkor persze Pythonban működni fog a kód, viszont nagy számokra (több mint 64 bites) már ott is igaz, hogy a szám négyzete kb. 2x annyi memóriát foglal mint maga a szám.

Typically, we consider space complexity in terms of Turing machines with:

one read-only input tape

one write-only output tape

however many read-write working tapes you want.

The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted. (See, e.g., Section 2.5 of Papadimitriou.)

Forrás:

C.H. Papadimitriou, Computational Complexity. Addison–Wesley, 1992.

M. Sipser, Introduction to the Theory of Computation (3rd edition). Cengage Learning, 2013.

Alternatívaként még szokták úgy megadni, hogy az algoritmus teljes memóriahasználatát számolják az input és output paraméterekkel együtt, de így egy sima bubble sort is O(n) space.

Nem azt mondom, hogy nem jobb a megadott algoritmus, csak hogy nem O(1).

Egyébként ha gyorsabb kódot szeretnél érdemes lenne a

i = val % n

helyett val & 0xffff -et írni.

És persze a

arr[i] += n

helyett

arr[i] += 0x10000 -t.

Az osztás és ezzel együtt a modulo számítás nagyon költséges művelet.

A fenti kódsorok nem (biztos, hogy) Pythonban vannak. Nem tudom ott hogy mennek a bit műveletek.