MySQL: Para ihop medlemmar 2 & 2?
 

Tja!

Har ett litet problem som blev krångligare än vad jag tänkt, antingen det eller så har jag tillfällig hjärnblödning för jag kommer inte ihop något smart & effektivt sätt att lösa detta på för enda sättet jag kommer på resulterar i en otroligt mängd queries, jag måste ha missat något.

Har kollat runt lite men nja:
http://stackoverflow.com/questions/1...pair-two-users
http://stackoverflow.com/questions/1...pairs-in-mysql


Iaf, jag vill para ihop medlemmar 2 & 2 bland medlemmar som har anmält sig till ett evenemang.

Har en användardatabas, förenklar grovt nu & tar bara med dom relevanta kolumnerna:

Tabellen Users
UserID BIGINT auto_increment
UserGender TINYINT (1 = man, 2 = kvinna)
UserCity SMALLINT (använder kommunkoder så City är lite missvisande men spelar ingen roll)



Tabellen EventUsers
EventID BIGINT auto_increment
EventUserID (sparar UserID för varje person som anmält sig till eventet)
EventGender (gender i detta fallet är inte anmälarens UserGender utan vilket gender som anmälaren önskas paras ihop med, kan lämnas tom)
EventCity (samma här, det är inte anmälarens UserCity utan det är vilken stad som anmälaren önskas paras ihop med)


Tabellen EventMatches (för att spara paren så dom 2 inte kan paras ihop igen eller med andra)
MatchID BIGINT auto_increment
MatchUser1ID BIGINT (ja detta är bara pseudonamn änsålänge)
MatchUser2ID BIGINT (ja detta är bara pseudonamn änsålänge)

Både tabell EventUsers & EventMatches rensas efter varje event

Det som ställer till det är att jag måste kunna matcha ihop 2 användare inom samma matchnings kriterier, hade inte kriterierna funnits, EventGender & EventCity så hade jag ju kunnat göra det lätt för mig och bara slumpa ihop 2 & 2 från EventUsers tabellen, men det kan jag ju inte nu.

Jag kan ju lösa det genom att loopa igenom alla EventID & köra 1 query på Users databasen för varje EventUsers deltagare för att para ihop 2 st med kriterier som passar varandra & sen lägg in resultatet i en annan tabell (EventMatches), en rad för varje par matchning. detta fungerar, & det är så jag gör tillfälligt nu, MEN om jag skulle få 1000 deltagare i eventet så blir det ju 1000 queries mot Users+join mot EventMatches tabellen. Vilket är långt, långt ifrån optimalt.


Så ja, ett smartare sätt att lösa detta på? Ni behöver inte slänga upp massa kod osv utan det räcker att ni pekar mig mot rätt riktning :D

Kanske en query för varje kön, sätt ett "par ID" för varje rad. Sen UNION på "par ID"?

Ett alternativ skulle väl vara att plocka ut alla deltagare till en array som du sen loopar igenom och jämför med "sig själv" för att göra matchningen. I den loopen bygger du ihop en stor query som du sen kör . (insert into matches(.. ..) Values (.. ..), (.. ..) osv )

När du hittar matchningar så plockar du helt enkelt bort de 2 deltagarna ur arrayen. Kvar har du sen de som inte valt några preferenser.

Hur ofta behöver du köra detta, och hur lång tid tar frågan som den ser ut nu?

1000 tupler i en SQL-fråga verkar vara "peanuts", har du prestandaproblem?

Tack så mycket för svaren allihopa.

Säg till om jag skall slänga ihop en databas + PHP kod om någon tycker det är roligt att leka runt lite :P

Kanske missuppfattande men ser tyvärr inte hur detta hjälper mitt problem för jag måste ändå kors matcha paren så användare #1 kön & stad passar in på användares #2 önskemål när det gäller kön & stad, MEN det räcker ju inte att #1 kan paras ihop med #2, #2 kön & stad måste också passa in på #1 önskemål. Det är just korsmatchningen som gör att det tar ett par queries för att matcha ihop dom.

Ja så skulle jag också kunna göra, men det är ändå bara en annan version av det jag redan har, är det 1000 deltagare så måste jag loopia igenom arrayen minst 500ggr & max 1000ggr beroende på om den hittar par matchningar eller inte. Kan ju använda Redis istället för just arrayen och bortplockningen av deltagarna från arrayen så blir det något mindre prestandaproblem men jao hmm.


Evenemangen är 1ggr i veckan & 1 omgång per event. Detta kan komma att ändras till 1 ggr i veckan & upp till 20 omgångar beroende på popularitet. Frågan tar mellan 5-10s per 1´000 deltagare (loopar igenom 1000 deltagare, korsmatchar med 1 query per deltagare + insert av matchningen) så minst 1000st queries för 1000 deltagare :P Kan maskera dom 5-10s med en eventloader iofs: "Eventet börjar om 20s" + nedräkning & köra querien under tiden, men är viss aktivitet på andra delar av sidan också som blir påverkare/köade under tiden vilket inte är så optimalt.

1000 rader år såklart en fis i rymden, problemet är dom 1000-1500 ytterligare SQL-frågor det resulterar i.

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

Släng ihop en databas med PHP så kan vi kolla lite :)

Detta kan kanske fungera, eller inte :)
Dock helt otestat (då jag inte har tabeller och eller data) samt att det inte finns stöd för att EventGender kan vara tomt, så det måste läggas på lite mer logik för att få till det, om resten nu mot förmodan fungerar.

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()
) group by userID1

Men som sagt, det är otestat och jag är långt i från säker på vilket (om något) resultat som kommer ut.
Men testa och se om det kanske är en väg framåt?

Om TS kan bidra med lite DDL kod (CREATE) för tabeller och nycklar samt lite INSERTS med testdata så kanske fler orkar göra mer tester. Det blir för mycket jobb om alla ska bygga allt från scratch.... i alla fall för mig....

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.

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 :)

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)


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

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:

och sedan söks det i den;

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 är han matchad (ta bort honom)
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.

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 ):

http://f.cl.ly/items/2W2R1A1f3s3t2B2u0m0s/veri2.png

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.

Ah,

vänd på det så blir det rätt igen;
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.

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.

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.)

Tack så mycket för ditt deltagande, har varit mycket lärorikt ;)

Mjao jo, i teorin, men det blir lite konstigt ändå av diverse anledningar

Just nu i början när vi bara kör 1 gruppering per event så skulle det fungera bra, men tanken är att om evenemanget blir hyfsat populär så kommer vi utöka antalet grupper, grupp A (dom 500 grupperna som 1000 deltagare skulle ge), sen grupp B, grupp C, grupp D...........semifinal, final. (är inget spel men kommer ändå struktureras som en liggande spelpyramid), 2 minuter per grupp, vilka som går vidare baseras på den tidigare gruppens score, så vi måste ändå köra matchningen efter varje runda.

Eller om man kör alla deltagare i grupp efter grupp, kanske 10 grupp ronder så vill jag ha random matchningar varje gång, detta går ju att förkalkylera men ja, denna algoritmen kan ju användas till flera olika saker som inte kan förkalkyleras.

Och som rhdf nämnde, personer som inte kunde matchas, dom måste vi ju ändå para ihop random när eventet väl kör igång :P

Så vi kan bara förkalkylera första gruppen, men sen behöver vi ändå denna matchningsalgoritmen resterande grupper :P