Problem: Noch nicht vergebene Planeten ermitteln

Hi,
Rahmenbedingungen:
- Ein Planet wird durch drei Koordinaten identifiziert (Galaxie, System und Planet)
- Jede Koordinate hat ihren eigenen Wertebereich von 1 - X
- In der Tabelle der Datenbank stehen lediglich die bereits vergebenen Planeten
Die Aufgabe an sich:
Ein noch nicht in der Tabelle existierender zufälliger Planet soll mit endlichen Versuchen ermittelt werden (daher Zufallszahlen ermitteln und schauen ob diese vergeben sind ist nicht praktisch).
Kennt da jemand schon eine Lösung oder Anhaltspunkt dafür?
Ich hatte bisher die try/catch Lösung, also einfach drei Zufallszahlen und schauen, ob diese noch nicht vergeben sind. Hat aber den Nachteil, dass immer mehr Versuche gebraucht werden, je voller das Spiel ist, was ich gerne vermeiden würde. Andererseits könnte man durch ein einfaches Select (order by random() limit 1) einfach einen Planeten selektieren, allerdings müssten dafür alle noch nicht vergebenen Planeten in der Datenbank stehen. Daher bin ich momentan etwas ratlos.
Falls die Lösungen spezifischer werden sollte, die Umgebung ist (auch klassisch) PHP/MySQL.

Es wird doch irgend ein Maximum an Planeten geben. Ermittel doch zum Anfang des Spiels die Positionen für alle potentielen Planeten, gibt ihnen eine Ordnung und schreibe sie in eine gesonderte Tabelle. Wenn Du jetzt im Spiel einen neuen Planete brauchst, nimmst Du den ersten aus dieser Tabelle und löschst ihn dort.

select from planeten left join belegte_dings on (gal=gal and sol=sol and pla=pla) where belegte_id is null order by rand() limit 1
oder irgendwie so

Gibt es ja, aber dann hätte ich zum Beispiel bei folgenden Wertebereichen:
Galaxy 1 - 10
System 1 - 200
Planet 1 - 15
30000 potenzielle Planeten. Hätte halt gedacht, wenn sich eine andere Lösung finden würde, könnt ich mir dies ersparen und auch ohne Probleme einfach den Wertebereich erhöhen wenn ich mehr Platz brauche und muss nicht immer schauen, dass die neuen freien Planeten dann in diese Tabellen übernommen werden.

Ich denke es ist ziemlich egal ob du nun 120kb mehr oder weniger in der DB liegen hast... und selbst wenn es ein paar mb waeren..
Glaub kaum, dass es da eine wirklich elegante Lösung gibt, der Sinn einer Datenbank ist es eigentlich Daten zu speichern und abrufen zu können, nicht deine Business Logik für dich zu übernehmen bzw. Daten zu erfinden, oder?
Du könntest auch einfach alle existierenden Planeten abrufen und in deinem Skript aus der Liste potentieller Kandidaten entfernen. Dann sparst du den Platz, aber hast halt längere Rechenzeit bei der Erzeugung neuer Planeten, nur immerhin nicht eine neue Anfrage für jedes Fehlgeschlagene rand. Denke das wäre performanter (aber nicht performant).
Ansonsten kommst du glaub ich um hsincs Ansatz nicht herum.
Der eleganteste Weg wäre wohl ein Hashing Algorithmus, der dir quasi auf Basis einer aufsteigenden ID automatisch eine unique Platzierung mit drei Koordinaten generiert (sollte mit Grundrechenarten und Modulo ganz gut möglich sein), so dass am Ende eine Pseudo-Zufällige Verteilung entsteht. Dann brauchst du weder Daten speichern, noch generieren, noch austesten.
Aber dafür ist es ja wahrscheinlich schon zu spät.

Original von Kallisti
Ich denke es ist ziemlich egal ob du nun 120kb mehr oder weniger in der DB liegen hast... und selbst wenn es ein paar mb waeren..

Mir geht es nicht um die Menge der Daten als mehr um den Grundsatz, dass ich vermeidbaren Daten in der Datenbank auch vermeiden will.

Original von Kallisti

Glaub kaum, dass es da eine wirklich elegante Lösung gibt, der Sinn einer Datenbank ist es eigentlich Daten zu speichern und abrufen zu können, nicht deine Business Logik für dich zu übernehmen bzw. Daten zu erfinden, oder?
Das wollte ich ja heraus finden, ob es eine bessere Lösung gäbe. Wenn es keine Bessere gibt, werden ich den alternativen Ansatz. Wobei ich keine Probleme hätte etwas "Logik" in die Datenbank zu verlegen. Als reiner Massenspeicher sehe ich die Datenbank nicht an. Wenn diese mir Rechenarbeit abnehmen kann und ich somit weniger Daten selektieren bzw. aktualisieren muss, dann soll sie das auch tun.
Da hab ich allerdings ein kleines Problem, Statement:

UPDATE planet SET 

memberid = 1
WHERE
id = (SELECT id FROM planet ORDER BY rand() LIMIT 1)
Wirft folgenden Fehler:

#1093 - You can't specify target table 'planet' for update in FROM clause

Der Fehler deutet für mich darauf hin, dass ich keine Subselects in Update Statements nehmen darf. Sehe ich das richtig? Dachte eigentlich das ginge in MySQL mittlerweile (Version ist 5.0.45).
Dann müsste ich da erst die ID selektieren, in PHP entgegennehmen und dann das Update Statement laufen.

Original von Kallisti

Du könntest auch einfach alle existierenden Planeten abrufen und in deinem Skript aus der Liste potentieller Kandidaten entfernen. Dann sparst du den Platz, aber hast halt längere Rechenzeit bei der Erzeugung neuer Planeten, nur immerhin nicht eine neue Anfrage für jedes Fehlgeschlagene rand. Denke das wäre performanter (aber nicht performant).
Na, dann muss ich ja alle existierenden Planeten selektieren. Das ist mehr Overhead als der alternative Ansatz.

alternativ alter table planeten add belegt enum (0,1) default 0
=> select from planeten where belegt='0' order by rand() limit 1 for update
update planeten set belegt = 1 weher id = ...
etc

stimmt, man sollte nur die Planeten als Potenzielle selektieren, die noch frei sind, also:

UPDATE planet SET 

memberid = 1
WHERE
id = (SELECT id FROM planet WHERE memberid = 0 ORDER BY rand() LIMIT 1)
Fehler bleibt aber weiterhin, genau wie die Frage, ob Subselects in Update Statements generell nicht funktionieren und man es über zwei Statements lösen muss?

Versuchs mal so:

UPDATE blub
SET blob = 3
WHERE id IN (SELECT ....)
LIMIT 1

Statement:

UPDATE planet SET 

memberid = 1
WHERE
id in (SELECT id FROM planet WHERE memberid = 0 ORDER BY rand() LIMIT 1)

Fehler:

#1235 - This version of MySQL doesn't yet support 'LIMIT & IN/ALL/ANY/SOME subquery'

Scheint als müsse ich dafür wohl doch zwei verschiedene Statements benutzen.

Hol dir die derzeitige Zahl an Planeten, seeede deinen Zufallsgenerator mit diesem Wert und probier dann so lange, bis du ne freie Stelle gefunden hast. Sollte (wenn du von Anfang an mit diesem System arbeitest) eig. immer in 1 Versuch durchlaufen

War mir klar, eher so:

UPDATE planet SET 

memberid = 1
WHERE
id in (SELECT id FROM planet WHERE memberid = 0 ORDER BY rand() ) LIMIT 1
(Habe die Klammer vor das limit gesetzt. So dass der Update nach dem ersten Satz aufhört).

Original von Kampfhoernchen
War mir klar, eher so:

UPDATE planet SET 

memberid = 1
WHERE
id in (SELECT id FROM planet WHERE memberid = 0 ORDER BY rand() ) LIMIT 1
(Habe die Klammer vor das limit gesetzt. So dass der Update nach dem ersten Satz aufhört).

naja .. das ist ja wohl echt eklig und unperformant. außerdem würde (zumindest so, wie ich mysql kenne) immer der erste datensatz abgeglichen.
wieso? deine subquery gibt ein set zurück .. die äußere query geht nun die planetenliste "von oben" (halt nach eintragungn/aktulisierungsreihenfolge - je nach db verschieden) durch und prüft, ob der planet noch frei ist.
angenommen wir hätten eine liste:

id | memberid

1 | 1
2 | 0
5 | 1
3 | 0
...
das subselect würd sich in sowas wie (3,2) auflösen und das update macht nun folgendes:
set memberid = 1 where 1 in (3,2) => false => weiter
set memberid = 1 where 2 in (3,2) => true => limit 1 getroffen => abbruch.
so ist zumindest meiner meinung nach die herangehensweise von mysql. sprich im endeffekt würden alle planeten der reihe nach belegt, was aber ganz klar nicht der intention entspricht.
deine qry geht auch kürzer und performanter:

UPDATE planet SET 

memberid = 1
WHERE
memberid=0 LIMIT 1
Tut dasselbe - ich denke hier wird es klar, wieso das keinen sinn macht.
kann man in einem update auch nen order by machen? dann könnte man da ein order by random() machen.
ansonsten würde ich auch zu einer "leere planeten" tabelle oder einem modulo-hashing-algorithmus raten.

UPDATE planet SET 
   memberid = 1
WHERE
   id in (SELECT id FROM planet WHERE memberid = 0 ORDER BY rand() ) LIMIT 1

Naja, da ist doch ein ORDER BY rand() bei.. müsste also gehen. Ich probier das mal aus

wie Drezil schon richtig bemerkete ist es an der stelle völliger schwachsinn eine subquery zu benutzen
ein simples update planeten set belegt=1 where belegt=0 order by rand() limit 1 macht har genau das selbe.
naja hauptsache es wird komplex und es werden subquerys benutzt, anstatt mal wirklich über das problem nachzudenken.
da es ja hier wohl primär um perf geht, nein performant ist es nicht wirklich. nach erklärung macht das ding Using where; Using temporary; Using filesort
mit nem key auf belegt würde sich die sache wohl reduzieren, aber nicht sehr. sollte aber von der struktur her schon klar sein

Original von HSINC
wie Drezil schon richtig bemerkete ist es an der stelle völliger schwachsinn eine subquery zu benutzen

Wenn ich mir die Lösung anschaue gebe ich dir vollkommen recht, mir war nur nicht bewusst, dass ein Update Statement ein Order By und ein Limit haben darf.

Original von HSINC

ein simples update planeten set belegt=1 where belegt=0 order by rand() limit 1 macht har genau das selbe.
Ich werde das mal probieren, danke.

Original von HSINC

da es ja hier wohl primär um perf geht, nein performant ist es nicht wirklich. nach erklärung macht das ding Using where; Using temporary; Using filesort
mit nem key auf belegt würde sich die sache wohl reduzieren, aber nicht sehr. sollte aber von der struktur her schon klar sein
Performance ist relativ egal, es geht ja hier um die Registrierung und die macht ein Spieler nur einmal. Ob das 100ms oder 2 sekunden dauert spielt keine Rolle. Mir war es nur wichtig, das Problem in einem Query zu erledigen um Race Conditions vorzubeugen.

> Race Conditions
Dafür gibt es Locking und andere Sperrmechanismen (Transaktionen oder andere Scherze).

UPDATE planet SET
memberid = 1
WHERE memberid = 0 ORDER BY RAND() LIMIT 1