Program milyen rendezéssel kezeljen fájlban lévő nagylétszámú rekordokat? (bővebben lent)
Elméletben foglalkoztat ez a téma: nagy létszámú rekordok esetén célszerű adatbázist használni, vagy bármilyen programozási nyelven, algoritmussal megoldható a feladat?
Ha létrehozásra kerülne például egy program által nagy számú rekordot tartalmazó fájl, milyen algoritmussal célszerű rendezni, hogy a rendezési sebresség ne vegyen el túl sok időt?
Például: az adatok: név, telefonszám. Tegyük fel, hogy telefonszám szerint kerül rendezésre.
Ilyenkor azt érdemes tenni, hogy minden törlésnél-módosításnál-beszúrásnál újrarendezzni az egész fájlt és keresni olyan algoritmust, amely rendezett adatokon gyors?
Rendezni úgy érdemes hogy például egy pár tízezer, rekordokból álló tömböt definiálni, majd ebbe olvasgatni az adatokat, míg meg nem telik, aztán kiírni stb, vagy egyesével olvasni/írni a fájlba a rekordokat?
válasza:1. Adatbázist mindig használsz.
2. Mégis, miféle rendezésre gondoltál? Csak mert ahány féle, annyi célú. Előbb kéne ismerni a célt és az adatok mennyiségét.
3. Rendezni és file-ba kiírni akkor érdemes, ha kevés a memória és sok az adat. Amúgy jobb előbb rendezni és a rendezett tömböt kiírni, már ha van erre igény és az adatforrást nem kell biztosítani.
Gondoltam a gyorsrendezésre, beszúrásos rendezésre, buborékos rendezésre például.
Lenne mondjuk többszázezer adat, vagy akár milliós nagyságrendű, ekkor bármilyen elem miatti újrarendezés elejétől végéig végigrohan a fájlon. A feladat pont e zért foglalkoztat: miképp lehet valamit úgy megírni, hogy ne legyen észrevehető sebesség-csökkenés.
válasza:Az adatok jellege, felhasználásuk módja és a számuk. Ez az ami a rendezési vagy keresési algoritmust is meghatározza.
Az nem egészen úgy van, hogy végigrohan.
Létezik osztott adatbázis. Akár a te példád okán betűrendes, minden betű saját file-ban kerül letárolásra, vagy a..f, stb.
Ekkor elég a teljes adatmennyiség kisebb részét benyalni a memóriába és azzal műveleteket végezni.
A mai gépek sebessége - ha PC-ről van szó - olyan, hogy akár egy millió [név,telszám] rekord buborék-rendezése is lefut 1 sec. alatt vagy max. 1-3 sec. időigénnyel.
Az akármekkora rekordszámú, file-ban tárolt adattömeg is adatbázis. Amire te gondoltál, az talán az adatbázis kezelő.
Amúgy, ilyen egyszerű [név,cím,telszám] rekordszerkezet esetén nem célszerű semmiféle adatbáziskezelőt használni, mert nem éri meg.
válasza:"A mai gépek sebessége - ha PC-ről van szó - olyan, hogy akár egy millió [név,telszám] rekord buborék-rendezése is lefut 1 sec. alatt vagy max. 1-3 sec. időigénnyel."
Mirol beszelsz te bohoc? Quantum PC-rol? :D
válasza:Bináris keresésnek azt a módját ismerem, ahol rendezett adatokon történő kereséskor mindig felezi az intervallumot, míg az adott elemet vagy megtalálja, vagy nyilvánvalóvá válik, hogy nincs benne.
A sima 1000000 tömbös rendezéssel kapcsolatos időket még nem tudom ide másolni, mert nem akar gyorsan lefutni a teszt.
válasza:Akkor számolgass:
- 1 M integer
- Intel Core i7 5960X 238,310 MIPS at 3.0 GHz
- bubble műveletigény - O/n ~ n2/
A művelet által elkivánt utasítások ciklusidejét meg kinézegeted a táblázatból. Jó szórakozást.
válasza:Ok.
10^6 int upper boundot tekintve ugye 10^12 nagysagrend lesz a negyzetes komplexitas miatt.
Ha 1db instructionnel szamolunk osszehasonlitasonkent, akkor lesz 1 000 000 000 000 / 238 310 000 000 = 4.2 masodperc az eredmeny. Ez mar tobb, mint az altalad hazudott 1-3, de nyilvan nem 1db instruction van osszehasonlitasonkent, hiszen meg egy sima swap is minimum 4db. Ez igy also hangon 16 masodperc. Es meg csak intekrol beszeltunk, stringek osszehasonlitasa pl. nyilvan karakterenkent tortenik, tehat mar 2 karakter hosszu stringek eseteben is minimum duplazodik ez az ido, te meg nevekrol beszelsz.
De normalis ember amugy lefuttat mondjuk csak 100 000 elemre egy buborekrendezest a gepen es mar latja, hogy fingod nincs mirol beszelsz :)
válasza:További 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!