SELFPHP: Version 5.8.2 Befehlsreferenz - Tutorial – Kochbuch – Forum für PHP Einsteiger und professionelle Entwickler

SELFPHP


Professional CronJob-Service

Suche



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



:: Buchempfehlung ::

Websites optimieren für Google & Co.

Websites optimieren für Google & Co. zur Buchempfehlung
 

:: Anbieterverzeichnis ::

Globale Branchen

Informieren Sie sich über ausgewählte Unternehmen im Anbieterverzeichnis von SELFPHP  

 

:: Newsletter ::

Abonnieren Sie hier den kostenlosen SELFPHP Newsletter!

Vorname: 
Name:
E-Mail:
 
 

Zurück   PHP Forum > SELFPHP > PHP Entwicklung und Softwaredesign

PHP Entwicklung und Softwaredesign Hier können strukturelle (Programmier-) Konzepte diskutiert und Projekte vorgestellt werden

Antwort
 
Themen-Optionen Ansicht
  #1  
Alt 18.08.2007, 16:34:14
feuervogel feuervogel ist offline
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...
Mit Zitat antworten
  #2  
Alt 18.08.2007, 17:24:26
Benutzerbild von z0iD
z0iD z0iD ist offline
Junior Member
 
Registriert seit: Mar 2006
Beiträge: 415
z0iD eine Nachricht über ICQ schicken
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.
Mit Zitat antworten
  #3  
Alt 18.08.2007, 21:13:15
feuervogel feuervogel ist offline
SELFPHP Guru
 
Registriert seit: Jan 2004
Ort: Leipzig
Beiträge: 4.549
AW: Datenstruktur die zufällige Reihenfolge beinhaltet

Zitat:
Zitat von z0iD Beitrag anzeigen
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*
Mit Zitat antworten
  #4  
Alt 18.08.2007, 21:34:48
rambi
Guest
 
Beiträge: n/a
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 21:43:44 Uhr)
Mit Zitat antworten
  #5  
Alt 19.08.2007, 00:52:44
Benutzerbild von z0iD
z0iD z0iD ist offline
Junior Member
 
Registriert seit: Mar 2006
Beiträge: 415
z0iD eine Nachricht über ICQ schicken
AW: Datenstruktur die zufällige Reihenfolge beinhaltet

Zitat:
Zitat von feuervogel Beitrag anzeigen
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.
Mit Zitat antworten
  #6  
Alt 19.08.2007, 10:37:29
feuervogel feuervogel ist offline
SELFPHP Guru
 
Registriert seit: Jan 2004
Ort: Leipzig
Beiträge: 4.549
AW: Datenstruktur die zufällige Reihenfolge beinhaltet

Zitat:
Zitat von z0iD Beitrag anzeigen
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.
Mit Zitat antworten
  #7  
Alt 19.08.2007, 13:04:39
rambi
Guest
 
Beiträge: n/a
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 13:07:34 Uhr)
Mit Zitat antworten
  #8  
Alt 19.08.2007, 13:59:14
Benutzerbild von meikel (†)
meikel (†) meikel (†) ist offline
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 Beitrag anzeigen
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.
Mit Zitat antworten
  #9  
Alt 19.08.2007, 18:21:14
Benutzerbild von z0iD
z0iD z0iD ist offline
Junior Member
 
Registriert seit: Mar 2006
Beiträge: 415
z0iD eine Nachricht über ICQ schicken
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 18:28:04 Uhr) Grund: war etwas undeutlich formuliert
Mit Zitat antworten
  #10  
Alt 19.08.2007, 18:25:02
Benutzerbild von z0iD
z0iD z0iD ist offline
Junior Member
 
Registriert seit: Mar 2006
Beiträge: 415
z0iD eine Nachricht über ICQ schicken
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.
Mit Zitat antworten
Antwort


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 
Themen-Optionen
Ansicht

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.

BB-Code ist an.
Smileys sind aus.
[IMG] Code ist aus.
HTML-Code ist aus.

Gehe zu

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
Reihenfolge VaN_tHe_MaN PHP Grundlagen 11 30.12.2006 15:37:57
3 zufällige Datensätze von ca. 1000, sortiert nach Spalte 2 ? bilbo_b MySQLi/PDO/(MySQL) 5 01.11.2006 00:49:15
Zufällige Anzeige von Bild + Text buero_b PHP Grundlagen 10 26.09.2006 11:28:01
reihenfolge von datensätzen ändern ingo PHP für Fortgeschrittene und Experten 5 17.08.2003 15:24:58


Alle Zeitangaben in WEZ +2. Es ist jetzt 18:18:02 Uhr.


Powered by vBulletin® Version 3.8.3 (Deutsch)
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.


© 2001-2024 E-Mail SELFPHP OHG, info@selfphp.deImpressumKontakt