Nieuws:

Welkom, Gast. Alsjeblieft inloggen of registreren.
Heb je de activerings-mail niet ontvangen?

Auteur Topic: Python tellen van overlappende tuples  (gelezen 1360 keer)

Offline MKe

  • Lid
Python tellen van overlappende tuples
« Gepost op: 2013/07/01, 16:18:58 »
Hoi,

ik heb twee lijsten van tuples met elk een begin- en een eindwaarde. Voor de duidelijkheid een lijst ziet er dus zo uit:
a = [(1,5),(10,13),(20,25)]
b=[(4,8),(30,33),(41,50),(15,20)]
In werkelijkheid gaat het hier om lijsten met enkele honderdduizenden tuples. Nu wil ik tellen hoeveel tuples van de tweede lijst overlap heeft met de eerste. Dus (4,8) heeft overlap met (1,5) in de eerste lijst, dus dat is er een etc.
Ik kan van elk item in een list een set maken en dan isdisjoint uitvoeren:
a = [(1,5),(10,13),(20,25)]
b=[(4,8),(30,33),(41,50),(15,20)]
teller = 0
for aitem in a:
    for bitem in b:
        if not set(range(aitem[0],aitem[1])).isdisjoint(set(range(bitem[0],bitem[1]))):
            teller += 1
Maar dit wordt erg inefficiënt als het gaat om 10.000 of zelfs 1.000.000 items per list. Het kan natuurlijk iets efficiënter door de set functie buiten de loop te houden, waardoor ik wat milliseconden kan winnen. Maar het schaalt nog steeds n*n.
Weet iemand een efficiëntere methode?

Re: Python tellen van overlappende tuples
« Reactie #1 Gepost op: 2013/07/01, 19:21:59 »
teller = sum(1 if (x[0][0] < x[0][1] < x[1][0]) || (x[1][0] < x[0][0] < x[1][1]) else 0 for x in zip(a,b))

Disclaimer: ik ken niets van Python.
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Re: Python tellen van overlappende tuples
« Reactie #2 Gepost op: 2013/07/01, 21:14:46 »
Heb je misschien een lange lijst om mee te testen?
[edit]Ik heb al wat om mee te spelen ;)[/edit]
« Laatst bewerkt op: 2013/07/01, 21:26:30 door FreeTheBee »

Re: Python tellen van overlappende tuples
« Reactie #3 Gepost op: 2013/07/01, 23:18:00 »
Ik heb wat me numpy slicing zitten spelen,

from numpy import array

def MKe3(a, b):
    teller = 0
    a = array(a)
    b = array(b)
    for bitem in b:
        for aitem in a[(a[:,1] >= bitem[0]) & (a[:,0] <= bitem[1])]:
            if not set(range(aitem[0],aitem[1])).isdisjoint(set(range(bitem[0],bitem[1]))):
                teller += 1
    return teller

Als aitem[1] < bitem[0], dan ligt aitem in zijn geheel negatief van bitem en is er geen overlap. Als aitem[0] > bitem[1]  ligt aitem positief van bitem. In de binnenste loop slice ik a, zodat alleen items die hier niet aan voldoen meegenomen worden.

Ik kon alleen testen met wat lijsten die ik zelf gegenereerd heb, dus ik hoop dat er geen stomme fout in zit ;)

Als je die disjoint actie doet, zou je dan niet range(x, y+1) moeten gebruiken, aangezien range tot de  y waarde loopt en niet tot en met?



Re: Python tellen van overlappende tuples
« Reactie #4 Gepost op: 2013/07/02, 09:13:45 »
Mij lijkt het dat die range/set functies een hele hoop geheugen gaan alloceren, iets wat je ook met een eenvoudige if-test kan doen.

Als b[0] of b[1] tussen a[0] en a[1] ligt, is er een overlap.

Verder kan je wat optimalizeren door sum() te gebruiken (wat native loops gebruikt ipv Python loops):

def overlap(a, b):
    return a[0] < b[0] < a[1] || a[0] < b[1] < b[2]

for aitem in a:
    teller += sum(1 if overlap(aitem, bitem) else 0 for bitem in b)

Mocht dat nog te traag zijn, kan je eens kijken naar numpy, of de boel in C(++) implementeren:

vector<pair<int,int>> a = {{1,5},{10,13},{20,25}};
vector<pair<int,int>> b= {{4,8},{30,33},{41,50},{15,20}}

auto _overlap = [](const pair<int,int>& p1, const pair<int,int>& p2) {
    return (a[0] < b[0] && b[0] < a[1]) || (a[0] < b[1] && b[1] < b[2]);
};

unsigned counter = 0;

for(auto& aitem : a) {
    counter += count_if(b.begin(), b.end(), [&](const pair<int,int>& bitem) { return _overlap(aitem, bitem); });
}

Je kan dat laatste ook eenvoudig parallelizeren (hier over 4 threads):

for(auto it = a.begin(); it != a.end(); ++it) {
    auto f1 = async(launch::async, [&] {
        return count_if(b.begin(), b.end(), [&](const pair<int,int>& bitem) {
            return _overlap(*a++, bitem);
        });
    });

    auto f2 = async(launch::async, [&] {
        return count_if(b.begin(), b.end(), [&](const pair<int,int>& bitem) {
            return _overlap(*a++, bitem);
        });
    });

    auto f3 = async(launch::async, [&] {
        return count_if(b.begin(), b.end(), [&](const pair<int,int>& bitem) {
            return _overlap(*a++, bitem);
        });
    });

    auto f4 = async(launch::async, [&] {
        return count_if(b.begin(), b.end(), [&](const pair<int,int>& bitem) {
            return _overlap(*a++, bitem);
        });
    });

    counter += f1.get() + f2.get() + f3.get() + f4.get();
}
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline MKe

  • Lid
Re: Python tellen van overlappende tuples
« Reactie #5 Gepost op: 2013/07/02, 09:16:05 »
Mij lijkt het dat die range/set functies een hele hoop geheugen gaan alloceren, iets wat je ook met een eenvoudige if-test kan doen.

Als b[0] of b[1] tussen a[0] en a[1] ligt, is er een overlap.

Bijna, het kan ook andersom, a[0] en a[1] kunnen ook binnen b[0] en b[1] liggen, Maar het zou kunnen dat dit de boel sneller maakt, ga ik eens proberen.

Re: Python tellen van overlappende tuples
« Reactie #6 Gepost op: 2013/07/02, 10:54:42 »
Met numpy slicing doe ik er 1e6 in 52 seconden, maar dan is ie al aardig aan het opblazen (3e5 gaat nog in 5s).  Ik heb nog wat zitten prutsen, maar al m'n verdere testjes gaan trager.

Misschien dat je hier nog iets mee kan,
https://en.wikipedia.org/wiki/Interval_tree#Overlap_test

gevonden op,
http://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals

Offline MKe

  • Lid
Re: Python tellen van overlappende tuples
« Reactie #7 Gepost op: 2013/07/02, 14:11:56 »
Ik heb wat me numpy slicing zitten spelen,

from numpy import array

def MKe3(a, b):
    teller = 0
    a = array(a)
    b = array(b)
    for bitem in b:
        for aitem in a[(a[:,1] >= bitem[0]) & (a[:,0] <= bitem[1])]:
            if not set(range(aitem[0],aitem[1])).isdisjoint(set(range(bitem[0],bitem[1]))):
                teller += 1
    return teller

Als aitem[1] < bitem[0], dan ligt aitem in zijn geheel negatief van bitem en is er geen overlap. Als aitem[0] > bitem[1]  ligt aitem positief van bitem. In de binnenste loop slice ik a, zodat alleen items die hier niet aan voldoen meegenomen worden.

Ik kon alleen testen met wat lijsten die ik zelf gegenereerd heb, dus ik hoop dat er geen stomme fout in zit ;)

Als je die disjoint actie doet, zou je dan niet range(x, y+1) moeten gebruiken, aangezien range tot de  y waarde loopt en niet tot en met?
Als je op deze manier sliced (in de te loop) kun je dan niet gewoon die lijst gebuiken? Volgens mij is het if statement in die loop altijd waar. Of snap ik de syntax niet?
Volgens mij werkt de volgende functie op dezelfde manier:
def MKe3(a, b):
     teller = 0
     a = array(a)
     b = array(b)
     for bitem in b:
         teller += len(a[(a[:,1] >= bitem[0]) & (a[:,0] <= bitem[1])])
     return teller
Trouwens, als ik dit run op bovenstaande twee kleine lijstjes werkt het prima, maar bij echte lijsten werkt het niet. Lijst a heeft 98547 items, toch vind hij 150721 items met overlap ? Zal me nog eens beter verdiepen in die matrix functies. Numpy is voor mij nieuw.

Offline MKe

  • Lid
Re: Python tellen van overlappende tuples
« Reactie #8 Gepost op: 2013/07/02, 14:38:25 »
Mij lijkt het dat die range/set functies een hele hoop geheugen gaan alloceren, iets wat je ook met een eenvoudige if-test kan doen.

Als b[0] of b[1] tussen a[0] en a[1] ligt, is er een overlap.

Verder kan je wat optimalizeren door sum() te gebruiken (wat native loops gebruikt ipv Python loops):

def overlap(a, b):
    return a[0] < b[0] < a[1] || a[0] < b[1] < b[2]

for aitem in a:
    teller += sum(1 if overlap(aitem, bitem) else 0 for bitem in b)

Mocht dat nog te traag zijn, kan je eens kijken naar numpy, of de boel in C(++) implementeren:
de if vergelijking scheelt 16 seconden op 5m46s runtijd. Dat scheelt dus inderdaad wel iets maar niet heel veel. De numpy versie runt in 30 seconden ongeveer, is dus veel sneller, maar geeft foutieve antwoorden, zoals ik hierboven aangaf.

Re: Python tellen van overlappende tuples
« Reactie #9 Gepost op: 2013/07/02, 15:08:15 »
...
Als je op deze manier sliced (in de te loop) kun je dan niet gewoon die lijst gebuiken? Volgens mij is het if statement in die loop altijd waar. Of snap ik de syntax niet?
Volgens mij werkt de volgende functie op dezelfde manier:
...
Dat dacht ik eerlijk gezegd ook, maar met testen met wat zelf gegenereerde data kreeg ik andere antwoorden dan met jouw functie. De versie zoals ik hem postte gaf bij mij wel dezelfde resultaten als bij jouw. Het zou echter goed kunnen dat de data zoals ik die genereerde om te testen niet ideaal was. Als je een voorbeeldlijst post om mee te spelen, kan ik vanavond nog wel wat prutsen.

Re: Python tellen van overlappende tuples
« Reactie #10 Gepost op: 2013/07/02, 15:16:11 »
Mocht het nog te traag gaan, kan je een interval tree gebruiken, dat zou O(n log n) duren in plaats van O(n²). (Je originele implementatie met sets was O(n³)).

Maar als je zo een snelheidswinst maakt met numpy, is het misschien een idee om een native implementatie te doen (zoals ik eerder zei)?
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline MKe

  • Lid
Re: Python tellen van overlappende tuples
« Reactie #11 Gepost op: 2013/07/02, 16:03:57 »
Mocht het nog te traag gaan, kan je een interval tree gebruiken, dat zou O(n log n) duren in plaats van O(n²). (Je originele implementatie met sets was O(n³)).

Maar als je zo een snelheidswinst maakt met numpy, is het misschien een idee om een native implementatie te doen (zoals ik eerder zei)?
Native is ook een optie, maar gezien mijn onwetendheid wat betreft C heb ik de voorkeur voor python. Trouwens een intervalTree werkt uitstekend. Ik heb de volgende class gevonden: http://blog.nextgenetics.net/demo/entry0045/intervalTree.txt
Als ik die gebruik dan breng ik de runtime van bijna 6 minuten terug naar 25 seconden.