Query SQL per ottenere combinazioni casuali inutilizzate - sql, database

Sfondo:

Voglio creare un database che possa eseguire un filetorneo di matchup 1 contro 1. Ha bisogno di tenere traccia di chi ha vinto e perso ogni incontro e di eventuali commenti su quell'incontro, oltre a decidere casualmente il prossimo incontro unico.

Regole:

Ci sono x numero di giocatori. Ogni giocatore alla fine giocherà ogni altro giocatore una volta, coprendo in effetti tutte le possibili combinazioni uniche di giocatori.

Tabelle database (con dati di esempio):

DECLARE @Players TABLE (
ID INT PRIMARY KEY IDENTITY,
Name VARCHAR(50)
)

ID Name
-- -----
1  Alex
2  Bob
3  Chris
4  Dave

DECLARE @Matches TABLE (
ID INT PRIMARY KEY IDENTITY,
WinnerId INT,
LoserId INT
)

ID WinnerId LoserId
-- -------- -------
1  1        2
2  4        2
3  3        1

DECLARE @Comments TABLE (
ID INT PRIMARY KEY IDENTITY,
MatchId INT,
Comment VARCHAR(MAX)
)

ID MatchId Comment
-- ------- ------------------------------
1  2       That was a close one.
2  3       I did not expect that outcome.

Problema:

• Come posso eseguire query in modo efficiente per ottenere una singola corrispondenza casuale che non si è ancora verificata?

Il problema principale è che il numero di giocatori può e crescerà nel tempo. In questo momento nei miei dati di esempio ho solo 4 giocatori che lasciano 6 possibili corrispondenze.

Alex,Bob
Alex,Chris
Alex,Dave
Bob,Chris
Bob,Dave
Chris,Dave

Sarebbe abbastanza piccolo da poter essere semplicemente mantenutoprendere 2 numeri casuali che corrispondono all'id del giocatore e poi controllare la tabella dei matchup se quel match è già avvenuto. Se lo è: prendine altri 2 e ripetere il processo. Se non lo ha, usalo come matchup successivo. Tuttavia, se avessi 10.000 giocatori, sarebbero 49995000 possibili matchup e sarebbe semplicemente troppo lento.

Qualcuno può indicarmi la giusta direzione per una query più efficiente? Sono aperto a modifiche nella progettazione del database se ciò contribuisse a rendere le cose più efficienti.

risposte:

1 per risposta № 1

Se fai un'unione esterna tra ogni possibileaccoppiamento e quelli che sono stati giocati, quindi filtra quelli che sono stati giocati, ti rimangono gli accoppiamenti che non sono ancora stati giocati. Selezionarne uno casuale è quindi un banale caso di ordinamento:

SELECT p1.Name, p2.Name FROM
Players p1
JOIN Players p2 ON (
p1.ID < p2.ID
)
LEFT JOIN Matches ON (
(WinnerId = p1.ID AND LoserId = p2.ID)
OR (WinnerId = p2.ID AND LoserId = p1.ID)
)
WHERE Matches.ID IS NULL
ORDER BY RAND()
LIMIT 1;

---

MODIFICARE

Come notato da ypercube sotto, sopra LIMIT la sintassi è specifica di MySQL.Potrebbe essere necessario utilizzare invece la sintassi appropriata per l'implementazione SQL: facci sapere di cosa si tratta e qualcuno può consigliarlo, se necessario. So che in Microsoft SQL Server si usa TOP e in Oracle ROWNUM, ma per il resto il tuo Google è probabilmente buono come il mio. :)

---

0 per risposta № 2

Mi chiedo perché devi scegliere 2 giocatoricasuale. Che ne dici di generare l'intero elenco di possibili corrispondenze in anticipo, ma poi aggiungere una colonna WinnerId? Per la prossima partita, seleziona la prima riga che non ha WinnerId impostato.

---

0 per risposta № 3

Sebbene il set di dati sia ampio, l'utilizzo di limit key interromperà l'elaborazione aggiuntiva non appena viene restituita una singola chiave. Una possibilità potrebbe essere quella di utilizzare una query come di seguito per restituire la corrispondenza successiva.

SELECT * FROM Players p1, Players p2 WHERE p1.ID <> p2.ID AND (p1.ID, p2.ID) NOT IN (Select WinnerID, LoserID FROM Matches) AND (p2.ID, p1.ID) NOT IN (Select WinnerID, LoserID FROM Matches) LIMIT 1

---

0 per risposta № 4

Per il tuo problema, vuoi che A) consideri tutti i sottoinsiemi di 2 elementi dei giocatori B) in un ordine casuale.

Per A, altre risposte suggeriscono di utilizzare SQLsi unisce a varie condizioni. Una soluzione meno intensiva del database se hai davvero bisogno di gestire 10.000 giocatori potrebbe essere quella di utilizzare un algoritmo di generazione di combinazioni efficiente. Ho trovato una risposta precedente che elencava alcuni di TAOCP vol. 4 Qui. Per il caso del sottoinsieme di 2 elementi, un semplice doppio ciclo annidato sugli ID del giocatore in sequenza lessicografica andrebbe bene:

for player_a in 1..num_players:
for player_b in player_a+1..num_players:
handle a vs. b

Per la parte B, potresti usare una seconda tabella mappatura giocatori 1..n a un mescolamento degli interi 1..n. Conserva questa mappatura mescolata finché non hai completato il processo del torneo. Puoi usare il Knuth-Fisher-Yates mescola.

Per tenere traccia di dove ti trovi in ​​un'istanza diquesto problema, probabilmente vorrai salvare regolarmente lo stato del generatore di combinazioni nel database. Questo sarebbe probabilmente più veloce che capire dove ti trovi nella sequenza dalle sole tabelle originali.

Come hai detto, gestendo 10.000 giocatori inmatchup in questo modo si traducono in quasi cinquanta milioni di matchup da gestire. Potresti prendere in considerazione una struttura di torneo che non richieda a tutti i giocatori di competere tra loro. Ad esempio, se A batte B e B batte C, potresti non dover considerare se A batte C. Se applicabile nel tuo scenario, quel tipo di scorciatoia potrebbe far risparmiare molto tempo.

---