[JesperA]

Slängde ihop ett snabbtest, gjorde efter logiken i första inlägget utan optimerar & utan förbättringar, så testet har nästlade/stackade queries å loopar vilket resulterar i galen exec tid.

Här: http://www.jespera.se/temp/EventMatches.zip (skall flytta servern senare idag så kan komma att sluta fungera i 10-20 min)

Har ni inte PDO så fungerar inte exemplet, antingen byta ut till mysqli eller bara köra via dummydatan i SQL filen. Glöm inte ange lösenord & användarnamn till din server i index.php (nästan längst upp)


Iaf, tack vare nestlade querisarna så ökar exec tiden exponentiellt mot antalet deltagare i eventet, 1´000 personer klarar min dev-server att para ihop på runt 2´000ms, 4´000 personer tar dock nästan 60´000ms :S (vilket givetvis inte fungerar, lösningen bör kunna skalas hyfsat iaf)

Är inte supermycket kod i index.php men vissa saker kanske är lite otydliga så är något oklar så säg till så förklarar jag + uppdaterar exemplet.


Med 1´000 eventdeltagare kommer det ju inte kunna matchas exakt 500 par, oftast blir det runt 320 par, men resten kan jag bara slumpmässigt para ihop och meddela dessa personer att ingen exakt matchning skedde så exemplet behöver inte innehålla detta.

[lubic]

Om man tar bort syntax-felen i min fråga blir den som nedan:

select * from
(
select u.UserID userID1, u2.UserID userID2

from EventUsers eu
join Users u on u.UserID = eu.EventUserID

join EventUsers eu2 on eu2.EventUserID != eu.EventUserID
AND eu2.EventGender = u.UserGender AND eu2.EventCity = u.UserCity

join Users u2 on u2.UserID = eu2.EventUserID
AND u2.UserGender = eu.EventGender
AND u2.UserCity = eu.EventCity

order by RAND()
) q1 group by userID1

Dock så tänkte jag inte riktigt rätt i och med att min fråga gör så att user A kan matchas ihop med user B, samt att user C också kan matchas ihop med antingen user A eller user B, vilket gör att en och samma person kan vara med i flera olika par.

Någon annan får helt enkelt tänka istället för mig, så kanske det blir bättre

[JesperA]

Ursprungligen postat av rhdf

Ja, men du slipper 1000 anrop till databasen, vilket jag uppfattade var ditt största problem.

Jag ber om ursäkt, du hade helt rätt ända från början, det var mitt fel att jag inte gick vidare med din idé för det är sällan jag använder så stora arrayer & matchar arrayer med arrayer & modifierar & manipulerar dessa så jag hade svårt att visualisera konceptet men det är såklart bästa vägen att gå verkar det som (mer om det senare)

Ursprungligen postat av lubic

Om man tar bort syntax-felen i min fråga blir den som nedan:

Dock så tänkte jag inte riktigt rätt i och med att min fråga gör så att user A kan matchas ihop med user B, samt att user C också kan matchas ihop med antingen user A eller user B, vilket gör att en och samma person kan vara med i flera olika par.

Någon annan får helt enkelt tänka istället för mig, så kanske det blir bättre

Japp jag skall testa din query & se hur den presterar



Iaf, Alex slängde ihop en lösning som är i samma linje som rhdf:s förslag & prestandan är rejält förbättrad jämfört med min utgångspunkt:

1000 medlemmar tar 300ms att matcha istället för 3'000ms, 10ggr snabbare alltså :P

Första testerna jag körde så såg det ut att vara linjär ökning i exec tid motsvarande ökningen av event deltagare men det blir det ju såklart inte :P Ökar fortfarande exponentiellt och det tror jag inte man kan komma ifrån, tror aldrig att man kan få linjär skalning vid den här typen av matchning. Kanske lubic:s fungerar men har inte testat än.

Exponenten (fel terminologi tror jag men skit samma, ni förstår ändå), Alex version jämfört med min:

4000 medlemmar tar 5'200ms att matcha istället för 60'000ms, 10+ggr snabbare igen.

Så japp, det är mycket snabbare att leka med arrayen & köra logiken i PHP istället för att använda databasen för att sköta matchningen & begränsa så att samma användare inte blir dubletter i EventMatches.


Iaf, ursäkta att jag tjötar mer än postar kod men kommer inte hem förräns söndag & har begränsade möjligheter att testa under tiden, skall börja om igen på söndag & se om jag kan göra en egen version som kan matcha Alex:s version.

Tack för svaren allihopa sålänge iaf

[Alex]

Och för er som vill ha koden till min lösning: http://pastebin.com/H5yMiAEt

Väldigt hastigt, och inte alls jätteoptimalt, men jag var ganska säker på att det bara behövdes en fråga för att lösa det, så jag ville testa.

Jag testade även att göra samma logik genom att fråga databasen efter användarna, men hålla kontrollen om användaren redan var matchad eller inte i PHP, men det gjorde det inte särskilt mycket snabbare.

Gör man sökningen lite mer sorterad kan det gå snabbare. Man skulle tex, initialt kunna gruppera in användarna i en array som motsvarar deras kriteria, och sedan bara söka i den:

PHP-kod:

$users[$item['EventCity'] . '-' . $item['EventGender'] . '-' . $item['UserCity'] . '-' . $item['UserGender']][] = $item; 


och sedan söks det i den;

PHP-kod:

$users[$criteria['UserCity'] . '-' . $criteria['UserGender'] . '-' . $criteria['EventCity'] . '-' . $criteria['EventGender']] 


[Alex]

Nu har jag testat lite, och fått ner tiden ganska radikalt med ovanstående koncept. Det är fortfarande aningen exponentiellt, men det går mycket snabbare;

http://pastebin.com/S4UvCCs4

Koden ovan är verkligen inte optimal eller snygg. Man kan skippa en eller flera av looparna om man vill. Den är också ganska stökig, men även det går att städa upp. Som koncept duger det tycker jag...

5000 users kan jag matcha till 2398 par på 480-500 ms. 1000 går på 35 ms.

Förslag på förbättringar här hade varit att istället för att loopa grupperingsarrayn, bara ta första användaren

PHP-kod:

$item = array_values($searchUsers)[0] 


är han matchad (ta bort honom)

PHP-kod:

unset($searchUsers[$topKey][$item['UserID']]); 


eller är han nuvarande userid, gå på nästa.

Anledningen till att $this->matched ligger kvar är för att den första initiala loopen i metoden match() kör det första subsettet av users, man skulle kunna bryta den loopen och börja om när man har fått en match, men jag tror det blir mindre effektivt faktiskt.

[JesperA]

Esch, laddade ner MAMP så jag kan pilla lite till, orkar inte vänta i ett par dagar till.

Iaf, uppdaterade mitt exempel lite så det är lättare att verifiera sin matchningsfunktion (om nu någon fortfarande är intresserad :P ):



Filen: https://www.dropbox.com/s/h88dm41d8p...entMatches.zip (första gången jag använder dropbox så förhoppningsvis fungerar länken)

SQL filen har inte ändrats, kanske innehållet men inte strukturen så den kan ni strunta i om ni redan använt den :P

Senaste testet finns i index3.php (har ändrat endel för att peta in verifieringen av matchningen, allts är dokumenterat i början av filen)


Alex
Din senaste fungerar inte hos mig, får alldeles för många exakta matchningar, paren är inte 2 stegs matchade av någon anledning. Får över 400 matchade par per 1000 med dina senaste, medans brukar ligga runt 320-330.

Har dock inte kört din senaste i verifieringsversionen av min test"miljö", så vet inte riktigt vad som händer där. Verifieringsmiljön använder din senaste version som fungerade 100% korrekt, + lite annan skit.

[Alex]

Ah,

vänd på det så blir det rätt igen;

PHP-kod:

        $topKey = $criteria['UserCity'] . '-' . $criteria['UserGender'] . '-' . $criteria['EventCity'] . '-' . $criteria['EventGender'];

        $find = isset($searchUsers[$topKey]) ? $searchUsers[$topKey] : null; 


jag som tänkte lite galet...

[JesperA]

Ursprungligen postat av Alex

Ah,

vänd på det så blir det rätt igen;

PHP-kod:

        $topKey = $criteria['UserCity'] . '-' . $criteria['UserGender'] . '-' . $criteria['EventCity'] . '-' . $criteria['EventGender'];

        $find = isset($searchUsers[$topKey]) ? $searchUsers[$topKey] : null; 


jag som tänkte lite galet...

Japp, nu får alla mina versioner samma svar, även denna som är 10ggr snabbare (42ms) än din som redan var 10ggr snabbare än min utgångsversion :P Jösses, tvivlar starkt på att jag kan göra en egen version som ens kommer i närheten av din speed :P

Aja, dags för mig att kavla upp armarna och göra ett försök iaf.

[Alex]

Sista varianten som jag bidrar med: http://pastebin.com/MKvfp6cQ, ökar effektiviteten en aning genom att sätta keyn på grupparrayen till userid och att faktiskt ta bort redan matchade användare ur grupperingen.

Där har du också det andra förbättringsexemplet, som använder en rekursiv metod för att hitta matchningar istället för en loop. Loopen verkar dock vara aningen snabbare, så jag kommenterade ut den och optimerade loopen istället.

Det finns nog ett och annat trix du fortfarande kan göra för att snabba upp det. Men jag funderade lite på detta på vägen hem från kontoret. Hade det inte varit smartare att bara hitta en match så fort någon signar upp sig till eventet? Då får du typ ingen ansträngning alls, och du kan göra allt på sättet du är bekväm i.

[rhdf]

Ursprungligen postat av Alex

Hade det inte varit smartare att bara hitta en match så fort någon signar upp sig till eventet? Då får du typ ingen ansträngning alls, och du kan göra allt på sättet du är bekväm i.

Vettigt. Enda problemet är ju hur man gör med den första som reggar sig
Eller för den delen, om det inte finns några registrerade som matchar preferenserna man anger.

Så i slutänden kommer man ändå behöva köra någon form av matchnings-algortim som "städar upp" (dock kommer den antagligen inte behöva hantera lika stora mängder data.)