CronJob-Service
bei SELFPHP mit ...
|
+ minütlichen Aufrufen
+ eigenem Crontab Eintrag
+ unbegrenzten CronJobs
+ Statistiken
+ Beispielaufrufen
+ Control-Bereich
Führen Sie mit den CronJobs von
SELFPHP zeitgesteuert Programme
auf Ihrem Server
aus. Weitere Infos
|
:: Anbieterverzeichnis ::
Globale Branchen
Informieren Sie sich über ausgewählte Unternehmen im Anbieterverzeichnis von SELFPHP
:: Newsletter ::
Abonnieren Sie hier den kostenlosen
SELFPHP Newsletter!
|
PHP Entwicklung und Softwaredesign Hier können strukturelle (Programmier-) Konzepte diskutiert und Projekte vorgestellt werden |
18.08.2007, 15:34:14
|
SELFPHP Guru
|
|
Registriert seit: Jan 2004
Ort: Leipzig
Beiträge: 4.549
|
|
Datenstruktur die zufällige Reihenfolge beinhaltet
Hallo,
ich grüble schon recht lange über ein Problem nach. Im Prinzip habe ich nur eine Menge Wörter, die ich in einer bestimmten Reihenfolge speichere, ich aber in einer anderen (zufälligen) Reihenfolge auslesen möchte, immer häppchenweise.
Eine MySQL-Datenbank mit einem ORDER BY RAND() LIMIT 0,10000 bietet sich deswegen nicht an, weil ich mindestens 1 Milliarde Einträge habe.
Ein Auslesen mit SELECT ... LIMIT 0,10000 oder LIMIT 234234,10000 geht recht flott, allerdings bekomme ich sie dann so zurück, wie ich sie eingefügt habe, und genau das will ich ja nicht.
Das ganze von vorneherein zufällig in Datei zu schreiben ist auch doof, weil ich wenn ich in Zeile x schreibe muss ich alle höheren Zeilen um eins verschieben.
Nach dem Auslesen zu sortieren ist auch nicht so gut möglich, da das nicht in meinen RAM passt, leider.
Kann ich das ganze also irgendwie zufällig in eine Datenbank schreiben, so dass ich danach nicht mehr sortieren muss? Wenn das Einfügen ein wenig dauert, ist es nicht so schlimm, Hauptsache, ich kann schnell auslesen...
|
18.08.2007, 16:24:26
|
|
Junior Member
|
|
Registriert seit: Mar 2006
Beiträge: 415
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Hallo feuervogel,
wie wärs denn, wenn Du Deiner Tabelle eine weitere Spalte hinzufügst in der eine Priorität gespeichert wird? Du kannst dann beim Einfügen einer Zeile einen zufälligen Wert aus einem hinreichend großen Universum an diese Stelle schreiben. Jetzt kannst Du beim Auslesen bequem mit Deinem ORDER BY kommen und mit der LIMIT Angabe Deine Häppchen einteilen.
Die Reihenfolge in der ausgelesen wird ist dabei natürlich immer dieselbe. Wenn die immer anders sein soll wirds denke ich schwerer, weil Du das ganze ja "Häppchenweise" lesen willst. Dann müsste die Sortierung für einen kompletten Lesevorgang sozusagen festgehalten werden.
Dazu könnte man eine Streufunktion (Hash) definieren die einen konstanten Parameter erhält, und die Prioritäten abhängig von diesem Parameter permutiert. Dann könnte man mithilfe dieses Parameters immer eine andere Sortierung generieren. Die Streufunktion zu finden dürfte dabei wohl das größte Problem sein, da sie schon universell sein sollte (sonst gibts überall Kollisionen).
So, ich hoffe das hat Dir weitergeholfen.
__________________
Bitte sprich entweder deutsch oder englisch mit mir, aber nicht beides gleichzeitig.
----------
Bitte vor dem Fragen lesen: Wie man Fragen richtig stellt.
|
18.08.2007, 20:13:15
|
SELFPHP Guru
|
|
Registriert seit: Jan 2004
Ort: Leipzig
Beiträge: 4.549
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Zitat:
Zitat von z0iD
Hallo feuervogel,
wie wärs denn, wenn Du Deiner Tabelle eine weitere Spalte hinzufügst in der eine Priorität gespeichert wird? Du kannst dann beim Einfügen einer Zeile einen zufälligen Wert aus einem hinreichend großen Universum an diese Stelle schreiben. Jetzt kannst Du beim Auslesen bequem mit Deinem ORDER BY kommen und mit der LIMIT Angabe Deine Häppchen einteilen.
|
Gut gedacht, allerdings ist das genau das, was MySQL macht, wenn man ORDER BY RAND() sagt. und 1 Milliarde zeilen zu sortieren macht keinen Spaß.
Zitat:
Die Reihenfolge in der ausgelesen wird ist dabei natürlich immer dieselbe. Wenn die immer anders sein soll wirds denke ich schwerer, weil Du das ganze ja "Häppchenweise" lesen willst. Dann müsste die Sortierung für einen kompletten Lesevorgang sozusagen festgehalten werden.
Dazu könnte man eine Streufunktion (Hash) definieren die einen konstanten Parameter erhält, und die Prioritäten abhängig von diesem Parameter permutiert. Dann könnte man mithilfe dieses Parameters immer eine andere Sortierung generieren. Die Streufunktion zu finden dürfte dabei wohl das größte Problem sein, da sie schon universell sein sollte (sonst gibts überall Kollisionen).
So, ich hoffe das hat Dir weitergeholfen.
|
Hmmmm *grübel*
|
18.08.2007, 20:34:48
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Zitat:
Kann ich das ganze also irgendwie zufällig in eine Datenbank schreiben, so dass ich danach nicht mehr sortieren muss? Wenn das Einfügen ein wenig dauert, ist es nicht so schlimm, Hauptsache, ich kann schnell auslesen...
|
Vorschlag:
einmal im Monat
Code:
ALTER TABLE worte ORDER BY RAND()
Und deine Tabelle ist gründlich durchwirbelt :D
Geändert von rambi (18.08.2007 um 20:43:44 Uhr)
|
18.08.2007, 23:52:44
|
|
Junior Member
|
|
Registriert seit: Mar 2006
Beiträge: 415
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Zitat:
Zitat von feuervogel
Gut gedacht, allerdings ist das genau das, was MySQL macht, wenn man ORDER BY RAND() sagt. und 1 Milliarde zeilen zu sortieren macht keinen Spaß.
Hmmmm *grübel*
|
Hm müsste das nicht in der gewünschten Reihenfolge (ohne ORDER BY) zurückgegeben werden, wenn man die Prioritätsspalte als Primärschlüssel oder Index (welches von beiden weiß ich nicht, aber eines müsste es tun) definiert?
P.S.: Was meinst Du mit "Hmmmm *grübel*"? Habe ich mich unverständlich ausgedrückt?
__________________
Bitte sprich entweder deutsch oder englisch mit mir, aber nicht beides gleichzeitig.
----------
Bitte vor dem Fragen lesen: Wie man Fragen richtig stellt.
|
19.08.2007, 09:37:29
|
SELFPHP Guru
|
|
Registriert seit: Jan 2004
Ort: Leipzig
Beiträge: 4.549
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Zitat:
Zitat von z0iD
Hm müsste das nicht in der gewünschten Reihenfolge (ohne ORDER BY) zurückgegeben werden, wenn man die Prioritätsspalte als Primärschlüssel oder Index (welches von beiden weiß ich nicht, aber eines müsste es tun) definiert?
|
das hab ich auch schon ausprobiert und es funktioniert leider nicht :-(
Zitat:
P.S.: Was meinst Du mit "Hmmmm *grübel*"? Habe ich mich unverständlich ausgedrückt?
|
ich muss es mir wahrscheinlich nur ein paar mal in ruhe durchlesen, dann hab ichs auch verstanden.
|
19.08.2007, 12:04:39
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Da du auf mein Posting nicht eingehst, vermute ich mal, dass dir der Weg nicht so richtig zusagt....
Alternative:
Wende es nur einmal an..(oder auch gar nicht :D)
Dann bleibt dir noch das Problem beim Einfügen:
(du hast doch hoffendlich eine autoincrement ID)
1. Mit "COUNT(*) AS anzahl" bestimmen, wieviele Datensätze es gibt
2. mit PHP einen mt_rand(1,$anzahl-1) Wert bestimmen (LIMIT $rand,1)
3. Diesen Datensatz lesen
4. und ans Ende schreiben (INSERT)
5. den neuen an den "frei gewordenen" Platz schreiben (UPDATE)
Ansonsten fällt mit auch nach langer Überlegung nix dazu ein......
Geändert von rambi (19.08.2007 um 12:07:34 Uhr)
|
19.08.2007, 12:59:14
|
|
SELFPHP Guru
|
|
Registriert seit: Dec 2003
Ort: Erfurt
Alter: 75
Beiträge: 4.001
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Zitat:
Zitat von feuervogel
und 1 Milliarde zeilen zu sortieren macht keinen Spaß.
|
Wozu sortieren? Erbsen sortiert man doch nicht in der Tüte.
Selbst wenn Du 1 Mrd. Einträge in der Tabelle hast, wirst Du hoffentlich/wahrscheinlich nicht alle Einträge auf einen Schlag verwursten wollen.
Wieviel Einträge willst Du nach welchen Kriterien selektieren?
Bedenke dabei, daß ein DBMS keine Excel Tabelle ist.
|
19.08.2007, 17:21:14
|
|
Junior Member
|
|
Registriert seit: Mar 2006
Beiträge: 415
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Ich kenne mich leider mit MySQL nicht sehr gut aus, aber ich meine dass man dort auch selbst definierte Funktionen ausführen kann. Dann könnte man doch mit einem Quickselect die k-te Prioriät (in der von mir vorgeschlagenen Struktur) finden und jeweils alle kleineren mithilfe der WHERE Klausel rauspulen. Der Quickselect ist eine Modifizierung des Quicksorts zum finden des k kleinsten/größten Elements in einem Array und läuft im Erwartungswert in linearer Zeit.
Also sagen wir, Du möchtest ab der m ten Stelle k Elemente lesen, dann Suchst Du mit Quickselect die Priorität von Stelle m (wenn Du sie nicht schon aus vorherigen Operationen kennst) und suchst anschließend die Priorität von Stelle m+k. Dann kannst Du Dir alle Elemente dazwischen bequem ausgeben lassen. Und das in linearer Zeit.
Es ist nur fragwürdig ob man so eine komplizierte Funktion wie den (rekursiven) Quickselect in MySql bekommt. Allerdings ist der Quickselect ja endrekursiv sodass es einfach sein dürfte ihn iterativ zu machen. Nur wiegesagt, ich weiß nicht ob man sowas in eine MySql Abfrage reinquetschen kann.
__________________
Bitte sprich entweder deutsch oder englisch mit mir, aber nicht beides gleichzeitig.
----------
Bitte vor dem Fragen lesen: Wie man Fragen richtig stellt.
Geändert von z0iD (19.08.2007 um 17:28:04 Uhr)
Grund: war etwas undeutlich formuliert
|
19.08.2007, 17:25:02
|
|
Junior Member
|
|
Registriert seit: Mar 2006
Beiträge: 415
|
|
AW: Datenstruktur die zufällige Reihenfolge beinhaltet
Nachtrag: Mit einer (simpel zu implementierenden) Erweiterung von Blum, Floyd, Pratt, Rivest und Tarjan läuft der Quickselect wohl nicht nur im Erwartungswert sondern auch im schlimmsten Fall in linearer Zeit.
__________________
Bitte sprich entweder deutsch oder englisch mit mir, aber nicht beides gleichzeitig.
----------
Bitte vor dem Fragen lesen: Wie man Fragen richtig stellt.
|
Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
|
|
Forumregeln
|
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.
HTML-Code ist aus.
|
|
|
Alle Zeitangaben in WEZ +2. Es ist jetzt 18:04:50 Uhr.
|