Listaösszefűzés
Sziasztok!
Egy olyan problémába ütköztem, hogy van két listám amiben időrendben adatok vannak, de a másodperc a legkisebb egység, amiben rögzíteni lehet, és előfordul, hogy egy másodpercen belül több adat is van. Példa:
2010.02.28 23:23:10,1.36269,1.36302
2010.02.28 23:23:10,1.3627,1.36301
2010.02.28 23:23:10,1.36271,1.36302
2010.02.28 23:23:10,1.3627,1.36301
És van két listám, amikben a fenti módon több 10'000 sor van egyenként.
Három lehetőség van egy másodperc vizsgálatakor:
1. csak az "a" listában van az adott másodpercről adat
2. csak a "b" listában van az adott másodpercről adat
3. mindkét listában van az adott másodpercben adat
A negyedik eset, mikor egyikben sincs, nem kezelődik le, így azal nem foglalkozom.
Naszóval, az 1. és a 2. pontot le tudom könnyen kezelni, viszont a 3. pontban mindkét lista elemeit összefűzve kell lekezelnem az alábbi példa alapján:
az "a" listában van 3 adat, a "b" listában 7.
A scriptnek a következőképpen kell lefutnia:
a(ab)a(ab)a(ab)a
(A zárójelben levők egyszerre futnak le.)
Vagyis amit szeretnék. Mivel nem tudom, hogy valóságban hogy követték egymást az adatok, így szeretném azt az elérhető legkisebb időegységben (mp) szétnyújtani annyira, hogy közel megfeleljen a valóságnak.
Tehát az elméletem:
1. ha azonos a másodpercen belüli elemszám, akkor egyszerűen párhuzamosan lefuttatom azokat
2. ha alistáknak nem azonos az elemszáma, akkor a nagyobbik a virtuális másorperc elejétől a végéig egyenletesen oszlik el, úgy, hogy az első a 0 ezredmásodpercnél, az utolsó a 999. ezredmásodpercnél legyen.
Mellette a kisebb darabszámú lista úgy helyezkedjen el, hogy az elejére és a végére felveszünk még fél egységet (ezáltal a példabeli 3-ból 4 lesz, és az értékek minden fél értéknél lesznek), és ezt nyújtjuk szét a másodpercben.
Összevonva tehát megkapnánk a feldolgozási sorrendet:
Ez pontosn az, mint amit fentebb írtam.
Namármost a problémám hogy ezt az elméletet hogy tudnám gyakorlatba átültetni. Már gondoltam arra, hogy egy 1000 elemű tömbbe belepakolom a megfelelő helyre, majd végigfuttatnám létező adatokon, de akkor két ilyen tömb kéne, mivel amint a példa is mutatja, azonos helyen is lehet adat. De ez a módszer nem biztos, hogy jó lenne, mivel nagyon nagy adatmennyiség esetén az amúgy is hosszú kalkulációt még jobban meghosszabítaná. Ha ti sem tudtok jobb ötletet (amit kétlek, ismerve ezt a közösséget), akkor marad ez.
A segítséget előre is köszönöm: Needback
Ui.: Azért nem írtam nyelvet, mert egyrészt nem akartam leszűkíteni a válaszadók körét, másrészt jobb szeretem a tiszta elméletből átdolgozni saját kódra. |
Az biztos, hogy ha a lista n elemet tartalmaz, akkor b lista (n-1)-t? Mert ha nem, akkor már a 0,5 egységes eltolásos móka sem játszik. Én inkább összeadnám a és b lista elemeinek számát az adott mp-ben és eloszlatnám egyenletesen.
Mindenképpen rendezett listával kellene dolgozni.
Ha nincs túl sok "luk" a mintában (olyan időpont, amikor egyik listában sincs adat), akkor én léptetném az időt, kigyűjteném mindkét listából az adatokat (a követelménynek megfelelő sorrendben) egy c listába, majd ezt megszámolva, elosztva tolnám egy d listába, ami a végeredményt adja (ezek után c megszűnik).
Ha sok az olyan időpont, amikor nincs mérési eredmény, akkor a következő időpontot a listák soron következő eleme alapján venném (megnézem a következő elemet a listában, ha a b lista következő elem ennél kisebb, akkor az a mérvadó, ha nagyobb vagy egyenlő, akkor az a lista eleme kell).
Nyelvet ugyen nem írtál, de biztosan nem tömbökkel oldanám meg, inkább láncolt listával. |
2 mélység:
--->másodperc
|
|
|
V
rows
2010.02.28 23:23:10,1.36269,1.36302 [0]
2010.02.28 23:23:10,1.3627,1.36301 [1]
2010.02.28 23:23:10,1.36271,1.36302 [2]
2010.02.28 23:23:10,1.3627,1.36301 [3]
vagyis
date[date][row] |
no, átrágva magamat a nagyobbik listán, az egy másodpercen belüli sorok száma maximum nyolt lehet.
A darabszámot ha úgy tetszik, random értékekkel is tekinthetjük, vagyis lehetséges a 8:1 arányú adatsortartalom.
A feles eltolás azért kell, mert a legperiférikusabb esetben 1-gyel tér el a két adatmennyiség egymástól, példázva:
"a" 8 elemű, "b" 7 elemű
0 999
a a a a a a a a
b b b b b b b
0 999
Míg 8:1 esetében:
0 999
a a a a a a a a
b
0 999
Sajna az adatok már rögzültek, és a rendszer, amivel rögzítve lettek, nem kezeli az ezredmásodperceket, így csak az elméleti legpontosabb sorrend kikövetkeztetését végezhetem el, amihez az ilyen módú összefűzés áll a legközelebb.
Az, hogy melyik adat pontosan melyik ezredmásodpercben van, teljesen lényegtelen, az egymáshoz viszonyított sorrendjük a fontos, ráadásul olyan is van (mint egy szinttel feljebb a másodperceknél), hogy egyszerre van két adat, és azt teljesen máshogy kell feldolgozni, mint az egymás után jövőket.
Példa:
1. mp |2. mp |3. mp |4. mp |5. mp |6. mp
a a a| | a |a a a a a|a a a a a|
|b b b b| b b b |b b b b b|b b b b
A fenti példa minden lehetőséget ábrázol:
1. mp: csak az "a" liatában van adat: ebben az esetben az adatokon sorbamegyek(FxA függvénnyel), és lépek a következő mp-re
2. mp: egyik listában sincs adat: lépek a következőre
3. mp: mindkét listában van adat, és a "b" listában van a több: ebben az esetben megyek "időben" sorba, és lefuttatom a megfelelő függvényeket (FxB, FxB, FxA, FxB, FxB), majd lépek a következő mp-re
4. mp: mindkét listában van adat, és az "a" listában van a több: ugyanúgy, mint az előbb, de itt van egy időpont, amikor találkoznak a sorok az elméleti idősíkon, ezért a föggvények sorrendje a következő lesz: FxA, FcB, FxA, FxAB, FxA, FxB, FxA
5. mp: mindkét listából van adat, és ugyanannyi: ebben viszont annyiszor futtatom le a közös függvényt, ahányszor szerepelnek az adatbárok
6. mp: csak a "b" listából van adat: FxB függvény futtatása minden adatsoron
Tehát valahogy nagyon függök a fenti megoldástól, főleg, mivel a rendszer, amibe építem, megköveteli mindhárom függvény lefutását, mi a valóságban is megtörténik.
No, remélem ezzel most nem kavartam össze senkit.
Változó, hogy a 2. mp-s állapot milyen gyakori.
Jelenleg a következőképpen oldom meg:
aindex=0 | bindex=0
ciklus eleje
ha alista aindex-edik eleme < blista bindex-edik eleme (vagyis az "a" listaelem időben régebbi)
FxA az aktuális "a" listaelemen, aindex növelése, ugrás ciklus elejére
ha alista aindex-edik eleme > blista bindex-edik eleme (vagyis a "b" listaelem időben régebbi)
FxB az aktuális "b" listaelemen, bindex növelése, ugrás ciklus elejére
és itt vagyok bajban, mert itt jönne az egyenlőség esetén történő feldolgozás. |
| Asszem félreértettél... az egymáshoz képesti sorrendet tudom, azt a lista adja, nekem a két lista elemeinek egymáshoz viszonyított sorrendje kell oly módon, ahogy azt fentebb leírtam. |
Szerintem létre kellene hoznod egy harmadik listát, amiben már ezredmásodpercek is szerepelnek. Az ezredmásodperceket az alapján számolod ki, hogy adott listában adott másodpercben mennyi mérés történt, függetlenül attól, hogy mi van a másik listában.
Tehát végiglépkedsz a listán, megszámolod az egy mp-en belüli elemeket, ezt arányosan elosztod a mp-en belül. Akár ebbe a listába is visszajavíthatod az időket és nem kell új lista. Ugyan ezt megteszed b-vel is. Majd a kettőt szépen összefűzöd egy c listába. Ebben már az összes elem megvan - függetlenül attól, hogy eredetileg melyik listában szerepeltek.
Tehát:
[a] lista első elemének kiolvasása és elmentése [akt]-ba
ciklus amíg [akt] nem mutat túl a listán
ciklus amíg az idő nem változik
[n] számláló növelése
mutató vissza az [akt]-ra
ciklus [n]-szer
dátum módosítása = dátum + 1000/[n] ezredmásodperc
[akt] átállítása a lista következő elemére
Ugyan ez [ b] listával is
Ezek után végiglépkedsz a és b listán - hasonlóan mint a mostani elgondolásod szerint - és az egyes elemeket kigyűjtöd egy [c] listába. Persze azt is lehet, hogy ömlesztve teszed ezt, majd sorba rendezed. Esetleg már röptében is lehetne a fenti ciklusok közben gyűjteni [c] elemeit, majd sorba rendezni. |
Igen, ez pont az 1000 elemű tömb elméletem, és úgy látszik, nincs jobb megoldás, vagy számítás a dologra.
Mivel idővel nem vagyok eleresztve, ezért elfogadom a megerősítésed.
Szóval véglegesítve az elméletet a következőt teszem:
létrehozok két tömbböt 0-tól 999-ig.
majd a szabályaim szerint a megfelelő pozícióba belerakom az "a" értékeit arányosan elnyújtva (a példa kedvéért az "a" a nagyobb elemszámú lista). Pl.: 5 elem esetén 0-nál, 250-nél, 500-nál, 750-nél, és 999-nél.
"a" tömb
0 -> 1. érték
250 -> 2. érték
500 -> 3. érték
750 -> 4. érték
999 -> 5. érték
Ezek után egy másik tömbbe berakom a "b" (kisebb elemszámú) lista elemeit fél-fél értékű eltolással. Pl.: 2 elem esetén 250-nél és 750-nél
"b" tömb
250 -> 1. érték
750 -> 2. érték
és végig megyek mind az 1000 soron, és ahol csak az "a" tömbben van érték, ott az FxA függvényt futtatom le, ahol csak a "b" tömbben van érték, ott az FxB függvényt futtatom le, és ahol mindkettőben, ott az FxAB függvényt.
0 -> csak "a" -> FxA
250 -> mindkettő -> FxAB
500 -> csak "a" -> FxA
750 -> mindkettő -> FxAB
999 -> csak "a" -> FxA
és így végülis megoldottam a dolgot, bár optimalizáció szempontjából nem a legtökéletesebb.
Köszönöm a segítséget. |
Szerintem nem ugyan az, de ahogy gondolod.
Továbbra is kérdés, hogy miért tömb és miért nem lista? |
| a lista azért nem jó, mert előre nem meghatározható a mérete, viszont előre nem tudom az egyik listaszámból, hogy a másik milyen arányban fog belekerülni, valamint van adat a kisebb elemszámúból, ami a nagyobb elemszámúak közé ékelődik, és van, ami mellé kerül. ezt listával nem tudom megoldani, hacsak nem indexelem a listákat, ami ugyanúgy tömböt jelent. |
Akkor szerintem konkretizáld a nyelvet.
Merthogy láncolt lista, collection, hashtable, stb. - nyelv föggően szóba jöhet. Nagy előnye, hogy nem foglal feleslegesen memóriát csak annyit amennyi eleme van. |
Delphi.
Igazából nem is a memóriával lenne a gond, mert két 1000 elemű string tömb nem foglal sokat, hanem a bejárása minden duplaadatú másodperc elemzésekor vinne el nagyon sok időt. |
|
