Hogyan lehetne tovább optimalizálni ezt a megoldást?
Az a feladat, hogy tömbben kell megkeresni a legtöbbször előforduló elemet. A nyelv igazából mindegy, Pythonban írtam, de megértek mást is.
A tömbnek ilyen tulajdonságai vannak:
- minimum 3 elemű, maximum 10 000 elemű
- az elemek a [0, tömb mérete[ intervallumból vehetnek fel értékeket, tehát 100 elemű tömbben például 0-99 elemek lehetnek, 5000 eleműben 0-4999 stb.
- mindig van jó megoldás és mindig csak egy jó megoldás van, tehát a legtöbbször előforduló elemen kívül minden más elem kevesebbszer fordul elő
Példa és megoldás:
[4, 0, 0, 3, 1] - 0 (kétszer fordul elő)
[4, 0, 9, 2, 4, 4, 9, 0, 3, 7] - 4 (háromszor fordul elő)
[1, 1, 2] - 1 (kétszer fordul elő)
A megoldásom 2 körös, első körben végig megyek a tömbön és dictben (más nyelvekben hashmap, hashtable) letárolom az elemeket az előfordulásukkal.
A második kör pedig egy maximum keresés a dictben, tehát megkeresem a legnagyobb előfordulást és visszaadom az ahhoz tartozó elemet.
Lehet ezen a megoldáson javítani valahogy?
Ha jól gondolom ez O(n) idő és O(n) tár komplexitás ebben a formában (mert minden elemen végig kell menni, a dictbe pedig legrosszabb esetben tömb mérete - 1 elem kerül).
Nem feltétlenül kódra vagyok kíváncsi, ötletekre főleg.
"i = val % n
helyett val & 0xffff"
Írtam egy gyors tesztet erre Pythonban, egymilliószor lefuttattam mindkét verziót n = 1..100000-re és átlagot néztem, a modulo verzió nálam egyértelműen gyorsabb.
Mikroszekundumban mértem a futásidőt.
De lehet a benchmarkom rossz, te milyen kóddal méred és milyen nyelven? Kipróbálom úgy.
válasza:C#-ban:
private static void ModTest(int val)
{
var sw = Stopwatch.StartNew();
for (int i = 1; i < 100000000; i++)
{
int a = val % i;
}
Console.WriteLine(sw.ElapsedMilliseconds);
}
private static void AndTest(int val)
{
var sw = Stopwatch.StartNew();
for (int i = 1; i < 100000000; i++)
{
int a = val & 0xffff;
}
Console.WriteLine(sw.ElapsedMilliseconds);
}
Majd meghívom 2x:
ModTest(1);
AndTest(1);
ModTest(6487);
AndTest(6487);
Az és-elés egyértelműen 10x gyorsabb. Eredmény:
249
27
249
27
De mint említettem a Pythont nem igazán ismerem, lehet ott az & is lassú:)
Csak kíváncsiságból 100ezer elemre neked mennyi idő alatt futott le? Én azért 100 millióval próbáltam, mert egyébként 0 idő volt.
válasza: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!