het vinden van gaten in een numerieke lijst.

[Uhmmie]

Ik zit al een tijdje te puzzelen met het volgende probleem.

Ik heb een array met hierin timstamps. Al deze timestamps staan op volgorde dus iets als:

10023103, 10023104, 10023105, 10023107, etc, etc

Nu wil ik alle gaten zien te vinden binnen deze lijst (met de mogelijkheid om te zoeken op een bepaalde minimale grote).

De makkelijkste manier is om er gewoon doorheen te loopen en elke keer als ik een gat aan tref te gaan tellen.. Maar als ik een paar miljoen stamps heb begint dat toch wel traag te worden..

Nu dacht ik dit wel met de native php array functies op te lossen, maar hierin loop ik helaas toch redelijk vast .. Eventueel een oplossing via SQL zou ook goed (misschien zelfs beter zijn).

Iemand hier toevallig een tip voor?

[ Voor 5% gewijzigd door Uhmmie op 11-06-2012 18:52 ]

[P_de_B]

Een tabel vullen met alle timestamps en dan left-joinen met deze tabel?

[Gomez12]

Pak hoogste, trek daar de laagste vanaf.
Dump het hele zaakje in een list of array oid en tel het aantal elementen.

Verschil tussen deze 2 getallen is je verschil.

Wil je het snel hebben voor miljoenen records dan is het puur afhankelijk waar de data vandaan komt (miljoenen records in een list/array stoppen kost ook tijd)

[Uhmmie]

De timestamps komen uit een database tabel. Hierbij wil ik opzoek gaan naar de plekken waar er bijvoorbeeld minimaal 5 minuten lang geen timestamps zijn ingevoerd..

Het aanmaken van een tabel met alle mogelijke timestamps zou wel een lompe manier zijn aangezien ik dan gewoon alle mogelijke timestamps in zou moeten voeren ..

Ik verbaas me er echt over hoe lastig dit eigenlijk wel niet is of ik kijk echt ergens enorm overheen.

Maar ik wil dus echt de gate aan kunnen wijzen, niet alleen kunnen zeggen dat er 3 gaten zijn.

[ Voor 10% gewijzigd door Uhmmie op 11-06-2012 19:08 ]

[pedorus]

Je kunt toch gewoon een self-join doen en dan de gaten teruggeven? Gaten van minimale grootte x wordt dan iets als:

SQL:

select distinct A.time from tablename as A left join tablename as B 
     on A.time < B.time and (A.time + x) > B.time
where B.time is null

[Jap_]

Dus dit is te traag?

PHP:

for($i=0; $i<count($t)-1; $i++) {
    $t1 = $t[$i];
    $t2 = $t[$i+1];
    if ($t2 - $t1 > 300) 
        $gaten[] = $t1 . '-' $t2;
}

In principe moet je toch elke gat checken. Er zijn n-1 mogelijke gaten. Dus je hebt ook n-1 vergelijkingen nodig. Het kost je gewoon O(n) tijd.

Je kan daarnaast nog algoritmische truukjes toepassen. Daarvoor moet je echter wel extra eisen aan je data stellen.

Zo kan je een recursieve functie opstellen die checkt of een range timestamps een gat kán bevatten. Als dat niet zo is kan je die range uitsluiten. De eis aan je data is daarvoor wel dat elke timestamp maximaal 1 keer voor kan komen.
Door die eis is bij een volledige dichte timestamp-range (elke timestamp komt precies 1 keer voor) de lengte van de range gelijk aan het bereik (het verschil tussen het eind en het begin). Als er echter een gat tussen twee timestamps zit is het bereik groter dan de lengte. Als het verschil tussen bereik en lengte groter is dan de minimale grootte van je grote gat is er dus de kans dat er zo'n gat in je range zit (of veel kleine gaten). Als dat zo is kan je de range opsplitsen in twee ranges en die beiden op dezelfde manier checken. Een range waarbij het verschil kleiner is dan je gatgrootte kan geen groot gat bevatten en hoef je niet verder uit te pluizen (winst!)

Voorbeeld:

index 0  1  2  3  4  5  6  7
value 10 15 16 17 19 20 21 23

Je zoekt voor een gat > 4.
23 - 10 >= 7-0 + 4 Dus er kan een gat in de array zitten
Recursief range 0-3 en 4-7
17-10 >= 3-0 + 4 Wel gat mogelijkheid
23-19 !>= 7-4 + 4 Geen gat mogelijkheid
Recursief 0-1 en 2-3
15-10 >= 1-0 + 4 Dus gat!
17-16 !>= 3-2 + 4 Dus geen gat

Dit algoritme heeft worst case O(n log n). Dus log n keer trager dan het bovenste. Dat is wanneer alle timestamps grote gaten tussen zich hebben. Gebruik het dus niet als je een veel gaten per timestamp verwacht.

Dit is slechts een voorbeeld, door goed naar je data te kijken kan je zelf misschien nog andere algoritmes verzinnen of bovenstaande verbeteren .

[Ventieldopje]

Gomez12 schreef op maandag 11 juni 2012 @ 19:03:
Pak hoogste, trek daar de laagste vanaf.
Dump het hele zaakje in een list of array oid en tel het aantal elementen.

Verschil tussen deze 2 getallen is je verschil.

Wil je het snel hebben voor miljoenen records dan is het puur afhankelijk waar de data vandaan komt (miljoenen records in een list/array stoppen kost ook tijd)

Dit zou je zelfs in blokken kunnen doen, 100 per keer bijvoorbeeld en als er in dat blok geen verschil is pak je het volgende blok, scheelt je heel wat loops

[dusty]

Als je de recursieve oplossing gebruikt die Jap_ voorstelt; werk dan wel met pointers en ga niet elke keer de gehele lijst (of een gedeelte daarvan) doorspelen naar de volgende stap.

[Uhmmie]

Thnx voor de adviezen.. De timestamps zelf zijn inderdaad uniek. Dus het zoeken in blokken is inderdaad misschien nog wel de beste oplossing, zodat ik niet door alles heen hoef te loepen ..

Ik ga der meteen mee aan de gang .

[Shezzie]

Ik weet niet op welke hardware je deze controles wilt gaan draaien, maar dit probleem is iets wat bij uitstek geschikt is om parallel op te lossen. Definieer subsets, stop ze in objecten die de controles voor je kunnen doen laat ze op afzonderelijke threads draaien. Waar je dan wel op moet letten is dat je niet duizend subsets tegelijk laat lopen maar dat je een load-balancing mechanisme inbouwt.

[martennis]

Kun je het niet oplossen met een subquery?
Bijvoorbeeld zoiets als:

code:

select *
from timestamp_table AS t1
where not exists ( select null from timestamp_table AS t2 where t2.timestamp between t1.timestamp and DATEADD(t1.timestamp, MI, 5) )

Deze selecteert dan alle timestamps waarvan er de volgende 5 minuten geen timestamp is gevonden.

Nu weet ik niet direct of de DATEADD op een timestamp werkt etc, maar daar is vast voor jou specifieke database wel iets voor te verzinnen.

Heb je hier iets aan?

[Nic]

In SQL server zou ik het zo doen:

code:

with testtabel (volgnr,timestamp) as (
    select rank() over (order by timestamp),timestamp from tabel
)
select * from testtabel c1 inner join testtabel c2 on c1.volgnr=c2.volgnr+1
where c1.timestamp-c2.timestamp>5

Even getest op een tabel met 30 miljoen records: 2301 gaten gevonden in 1 minuut en 14 seconden.

Uitleg: 'testtabel' is een tijdelijke tabel met een volgnummer (rank) en de timestamp:

code:

volgnr  timestamp
1     1
2     2
3     4
4     5
5     7

en vervolgens een JOIN met zichzelf, waarbij je naar het volgende volgnummer kijkt. Dan hoef je alleen nog maar via een WHERE te checken of het gat groot genoeg is. Sim-pel. :-)
Performed prima, want alles is te indexeren (alleen het joinen met volgnr+1 is suboptimaal...) en je hoeft zelf geen loopjes te programmeren. Je database-server is daar veel beter in. :-)

[ Voor 42% gewijzigd door Nic op 13-06-2012 13:56 ]

[Zoijar]

Uhmmie schreef op maandag 11 juni 2012 @ 18:50:
De makkelijkste manier is om er gewoon doorheen te loopen en elke keer als ik een gat aan tref te gaan tellen.. Maar als ik een paar miljoen stamps heb begint dat toch wel traag te worden..

Denk je dat, of wordt het dat ook echt? ik kan me namelijk niet voorstellen dat dat lang duurt. O(n) op miljoenen records zou vrijwel meteen klaar moeten zijn. Of voor je dit ook weer miljoenen keren opnieuw uit? Als het 1 keer moet doen, gewoon makkelijk er doorheen lopen. Zonde om allemaal moeilijke mogelijke optimalisaties te doen.

[Rotterdammertje]

In SQL Server 2012 en Oracle heb je ook de beschikking over de analytic function "LAG", waarmee je de waarde van een vorig record kan opvragen. Hiermee wordt het wel heel erg eenvoudig:

SQL:

with testtabel (timestamp, prev_timestamp) as (
    select timestamp, lag(timestamp) over (order by timestamp) from tabel
)
select * from testtabel c1 where timestamp-prev_timestamp > 5