diff; egyéb program összehasonlításra

Algoritmusok

Szasztok!

Van egy elég nagy problémám - méret ügyileg is ;o). Gondoltam közzé teszem, hátha van valakinek jó ötlete a megoldásra.
Jelenleg betöltöm egy Oracle alá és ott hasonlítom össze a dolgokat, de iszonyat mennyiségű adatról van szó.

Tehát a probléma:
- Adott két fájl. Az egyik T0 időpontban jön létre, a másik T1.
- A fájlok felépítése formátum ügyileg a következő:
"99999", "ADAT1", "ADAT2", "ADAT3"
"99999", "ADAT4"
"99999", "ADAT4"
"99999", "ADAT4"
"99999", "ADAT5", "ADAT6", "ADAT7", "ADAT8"
"99999", "ADAT5", "ADAT6", "ADAT7", "ADAT8"

"99991", "ADAT1", "ADAT2", "ADAT3"
"99991", "ADAT4"
"99991", "ADAT4"
"99991", "ADAT4"
"99991", "ADAT5", "ADAT6", "ADAT7", "ADAT8"
"99991", "ADAT5", "ADAT6", "ADAT7", "ADAT8"

Az első oszlop egy "csoport azonosító". A csoport azonosító csak egy fájlon belüli
csoport azonosítára megfelelő. Tehát a T0 fájlban lehet azonos adatcsoport a T1
fájlal kapcsolatban, de a csoport azonosítójuk eltérő lehet (eltérő és kész).

Azon csoportokat akarom T1-ből, ami nem szerepel T0-ban vagy változott T0-hoz képest.
Eltérés lehet az is, ha pl. ADAT4 változik. Tehát az egész halmazt kell vizsgálni.

Fincsi, mi?

Van valakinek ötlete hozzá?

  • 1414 megtekintés

( imp | 2007. 01. 12., p – 15:27 )

honnan tudod, hogy egy t0-beli csoportot melyik t1-beli csoporttal kell összehasonlítani?

( asch v | 2007. 01. 12., p – 16:06 )

És Oracle alatt túl sokáig tart a művelet?

Én így csinálnám kb (algoritmus szintjén leírva, hogy milyen eszközökkel, azt még nem tudom, akár adatbázis is szóba jöhetne).
1. Csinálnék a csoportnak egy "kanonikus" leírást. Amiben leírva ugyanúgy néznek ki bitről bitre az egyenlőnek mondottak. (pl ha a sorrend nem számít a csoporton belül, vagy akárhol, akkor a sorait rendezném). Ezen leírás formátumára konvertálnám a bemenetet a T0-st és a T1-st is.
2. Definiálnék egy rendezést a csoportokra is, olyat, ami lehetőleg gyors (pl először hash összehasonlítás, és ha az egyenlő, akkor utána lexikografikusan)
3. Rendezném a két listát
4. összefésülve (párhozamosan olvasva kiszedném a keresett sorokat)

Ennyit szarakodni vele csak akkor éri meg, ha tényleg nagyon sok érték van, és nagyon kell az eredmény...
Ezzel ugye a rendezés n*log n, a többi lépés n nagyságrendű. Kivéve, ha a csoportok adatai nincsenek egymás mellett. Akkor a csoportok összegyűjtése sem feltétlen triviális, de ezzel most nem fogltalkoztam.

Végül egy ehhez hasonló megoldásra jutottam én is:
Egy egy ID-hez tartozó adatokat egyetlen folttá alakítottam, ezzel elveszítette az ID-jét és már csak az adattartalomra kellett koncentrálnom. Az adattartalmak szerencsére egyediek. Egyenlőre az a helyzet, hogy quicksorttal rendezem az egyiket és binárisan keresek bennük. Azon elemeket, melyeket megtaláltam T0-ban, törlöm T0-ból ezzel is gyorsítva a keresést.

Egyébként köszi a hozzászólást!

Még valami. Elfelejtettem mondani, hogy oracle alá még be is kell pakolni az adatokat és csak utána kezdődhet az összehasonlítást. Amennyiben szűz táblákat használok, nincs rajta se kulcs, se index és ezeket az importálás után hozom létre, akkor is kb. öt-hat órát vesz igénybe az adatbetöltés. (Pufferelt olvasás text fájlból, csak én használom a szervert ebben az esetben.) Ezt az időt is szeretném megtakarítani.