Zufaellige zeile auslesen.

[volkard]

Coda@linux.PrayLoad schrieb:

so weit so gut aber wie kann ich result vom typ line haben???

sorry, string war gemeint.

habs mal mit ohne ungetestet gemacht.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

int main(){
	srand(static_cast<int>(time(0)));rand();//nur einmal am anfang der main() 

	ifstream in("C:/LogiSetup.log"); 
	string result;
	string line;
	int count=1; 
	while(getline(in,line)){ 
	   if(rand()%count==0){ 
		  result=line; 
		  ++count; 
	   } 
	} 
	cout<<result<<'\n'; 
}

[volkard]

da hab ich bestimmt nen programmierfehler gemacht.
ich wollte mal sehen, ob die beiden ergebnisse einigermaßen gleichwahrscheinlich sind.

#include <iostream>
using namespace std;

int main(){
    unsigned int const n=2;
    int count[n]={0};
    for(int i=0;i<1000000;++i){
        int index = rand() * ( n - 1 ) / RAND_MAX;
//        int index = rand() % n;
        ++count[index];
    }
    for(int i=0;i<n;++i){
        cout<<i<<' '<<count[i]<<'\n';
    }
}

ausgabe:

0 999963
1 37

was stimmt da nicht?

[camper]

wenn überhaupt, dann wohl

rand()*n/(RAND_MAX+1)

Das spart u.U. eine Division, was allerdings im Verhältnis zum Aufwand von rand eher unbedeutend sein dürfte. So lange n klein gegen RAND_MAX ist, wird es praktisch keine Rolle spielen, welche Formel man verwendet.

Interessanter dürfte die Frage sein, wie viele Zeilen die Quelle haben darf, bevor volkards Methode starke Abweichungen von der Gleichverteilung zeigt, weil entsprechend kleine Wahrscheinlichkeiten nicht mehr hinreichend exakt dargestellt werden können (was man wiederum durch Verkettung von rand beheben könnte).

[proggingmania]

volkard schrieb:

ich wollte mal sehen, ob die beiden ergebnisse einigermaßen gleichwahrscheinlich sind.

Interessante Idee, der Sache werd ich nachgehen, aber heute wird das wohl nix mehr.
Gruß,
p.

[volkard]

camper schrieb:

wenn überhaupt, dann wohl

rand()*n/(RAND_MAX+1)

Das spart u.U. eine Division, was allerdings im Verhältnis zum Aufwand von rand eher unbedeutend sein dürfte. So lange n klein gegen RAND_MAX ist, wird es praktisch keine Rolle spielen, welche Formel man verwendet.

ich krieg das mit dieser formel auch nicht hin, wenn RAND_MAX==INT_MAX. hab mir sagen lassen, das sei jetzt auf modwernen compilern so.

Interessanter dürfte die Frage sein, wie viele Zeilen die Quelle haben darf, bevor volkards Methode starke Abweichungen von der Gleichverteilung zeigt, weil entsprechend kleine Wahrscheinlichkeiten nicht mehr hinreichend exakt dargestellt werden können (was man wiederum durch Verkettung von rand beheben könnte).

nur bis RAND_MAX zeilen.

vorschlag zur behebung, solange MS kleines RAND_MAX hat.

unsigned r2=0;
    while(getline(in,line)){ 
       r2=r2*3+rand();
       if((r2%count==0){

[proggingmania]

camper schrieb:

Das spart u.U. eine Division

Welche Divion willst du sparen ? Es gibt nur eine.

[camper]

volkard schrieb:

camper schrieb:

wenn überhaupt, dann wohl

rand()*n/(RAND_MAX+1)

Das spart u.U. eine Division, was allerdings im Verhältnis zum Aufwand von rand eher unbedeutend sein dürfte. So lange n klein gegen RAND_MAX ist, wird es praktisch keine Rolle spielen, welche Formel man verwendet.

ich krieg das mit dieser formel auch nicht hin, wenn RAND_MAX==INT_MAX. hab mir sagen lassen, das sei jetzt auf modwernen compilern so.

Um dieses triviale Problem geht es mir nicht. Dass man dafür sorgen muss, dass rand()*n keine Überläufe produziert, ist sowieso klar (wobei wir hier möglicherweise sogar mit Überläufen leben können, da RAND_MAX ja meist irgendein 2^n-1 ist). Ein hinreichend großer Datentyp muss es schon sein. Gleiches gilt entsprechend für RAND_MAX+1.

rand()*(n-1)/RAND_MAX

ist dagegen offensichtlich schlechter als rand()%n
Denn die wahrscheinlichkeit, dass hierbei n-1 (für n>1) herauskommt, ist immmer nur 1/RAND_MAX

volkard schrieb:

Interessanter dürfte die Frage sein, wie viele Zeilen die Quelle haben darf, bevor volkards Methode starke Abweichungen von der Gleichverteilung zeigt, weil entsprechend kleine Wahrscheinlichkeiten nicht mehr hinreichend exakt dargestellt werden können (was man wiederum durch Verkettung von rand beheben könnte).

nur bis RAND_MAX zeilen.

Das ist klar; mir geht es um den Fehler, der sich schon vorher mit jedem Durchgang fortpflanzt.

volkard schrieb:

vorschlag zur behebung, solange MS kleines RAND_MAX hat.

unsigned r2=0;
    while(getline(in,line)){ 
       r2=r2*3+rand();
       if((r2%count==0){

Das ergibt immer noch nicht mehr Möglichkeiten in jedem Durchgang. Wie wäre es mit

if((rand()+rand()*(RAND_MAX+1)%n==0){

[camper]

proggingmania schrieb:

camper schrieb:

Das spart u.U. eine Division

Welche Divion willst du sparen ? Es gibt nur eine.

Eine Division durch eine Potenz von 2 die üblicherweise durch schnelles Bitverschieben implementiert wird. Wie schon gesagt, das ist ein unbedeutender Fakt.

[proggingmania]

Neee neee

rand()*(n-1)/ RAND_MAX // eine Division
rand()*n/(RAND_MAX+1) // auch eine Division

Gesparte Anzahl Divisionen == 0

Dieser Service bietet "echte" Zufallszahlen die durch weißes atmospärischen Rauschen entstehen:
http://www.random.org/
Nehmen wir diese Zahlen, können wir uns eine Diskussion sparen
*g*

LG,
p.

[volkard]

camper schrieb:

Das ist klar; mir geht es um den Fehler, der sich schon vorher mit jedem Durchgang fortpflanzt.

welchen fehler genau?

ich sehe keinen bei

string result; 
    string line; 
    int count=1; 
    while(getline(in,line)){ 
       if(rand()%count==0){ 
          result=line; 
          ++count; 
       } 
    } 
    cout<<result<<'\n';

außer, daß RAND_MAX kleiner sein könnte als die zeilenzahl.

was pflanzt sich da durch?

[proggingmania]

camper schrieb:

Denn die wahrscheinlichkeit, dass hierbei n-1 (für n>1) herauskommt, ist immmer nur 1/RAND_MAX

Na, mal gut das das so ist, wenn man eine Gleichverteilung möchte.

[proggingmania]

welchen fehler genau?
ich sehe keinen bei

string result; 
    string line; 
    int count=1; 
    while(getline(in,line)){ 
       if(rand()%count==0){ 
          result=line; 
          ++count; 
       } 
    } 
    cout<<result<<'\n';

außer, daß RAND_MAX kleiner sein könnte als die zeilenzahl.

was pflanzt sich da durch?

Da pflanzt sich nichts durch, das Resultat bleibt immer das Gleiche:
Es wird immer nach dem höchst möglichen Index gesucht, die unteren Indizes kommen dabei zu kurz.

[volkard]

proggingmania schrieb:

Da pflanzt sich nichts durch, das Resultat bleibt immer das Gleiche:
Es wird immer nach dem höchst möglichen Index gesucht, die unteren Indizes kommen dabei zu kurz.

ok, kleinen programmierfehler übersehen. sorry.

string result; 
    string line; 
    int count=1; 
    while(getline(in,line)){ 
       if(rand()%count==0){ 
          result=line; 
<del>     ++count; </del>
       } 
<ins>  ++count; </ins>
    } 
    cout<<result<<'\n';

aber damit sollte es endlich funktionieren.

induktionsanfang:
ich lese die erste zeile.
mit wahtscheinlichkeit 1 wird sie zum ergebnis.
effekt: alle bisher gelesenen zeilen sind gleich wahtscheinlich das ergebnis.

ich lese die zweite zeile.
mit wahtscheinlichkeit 1/2 wird sie zunm ergebnis.
effekt: alle bisher gelesenen zeilen sind gleich wahtscheinlich das ergebnis.

ich lese die dritte zeile.
mit wahtscheinlichkeit 1/3 wird sie zum ergebnis.
effekt: alle bisher gelesenen zeilen sind gleich wahtscheinlich das ergebnis.

überraschend, gell?

induktionsschritt:
ich lese die n-te zeile.
mit wahtscheinlichkeit 1/n wird sie zum ergebnis.
effekt: alle bisher gelesenen zeilen sind gleich wahtscheinlich das ergebnis.

qed.

[proggingmania]

Das ist ja noch schlimmer als die erste Version, so wird das nichts mit der Gleichverteilung sorry.
Die erste Version suchte nach dem höchsten Index, die zweite Version macht das nun etwas intensiver.

Außerdem, so nebenbei, wenn du sowieso zeilenweise bis zum Ende der Datei einliest, warum rufst du dann jedesmal rand() immer wieder neu auf ?

Performance-technisch nicht gerade optimal, nicht wahr ?

Kurz ausgedrückt:

Für jede neu eingelesene Zeile wird rand() aufgerufen. EIN Aufruf von rand() reicht völlig.

Dann noch:

Wenn man sowieso nicht vorhat, alle Zeilen in ein Array einzulesen,
wozu überhaupt jede Zeile in line reinschreiben ?
Eine Suche nach '\n' in der Datei reicht völlig aus.

Und vielleicht noch:

Wenn man doch alle Zeilen in ein Array schreiben will, ok, macht man das eben.
Der Aufruf von rand() braucht in jedem Fall nur EINMAL zu erfolgen,
denn bekanntlich muss die Anzahl n VOR der Berechnung der Zufallszahl bekannt sein, logisch ne ?

Ostern ist bald vorbei, juhuuu, Freiheit für die Eier!

LG,
p.

[volkard]

proggingmania schrieb:

Das ist ja noch schlimmer als die erste Version, so wird das nichts mit der Gleichverteilung sorry.
Die erste Version suchte nach dem höchsten Index, die zweite Version macht das nun etwas intensiver.

das glaube ich nicht. meinen "beweis" willste nich anerkennen.

dann erkläre mir mal, warum

#include <cstdlib>
#include <iostream>
using namespace std;

int const lines=100;

int selectLine(){
    int line;
    int result;
    int count=1;
    for(line=0;line<lines;++line){//statt while(getline(in,line)
       if(rand()%count==0){
          result=line;
       }
        ++count;
    }
    return result;
}

int main(){
    int count[lines]={};
    for(int i=0;i<1000000;++i)
        ++count[selectLine()];
    for(int i=0;i<lines;++i)
        cout<<count[i]<<'\n';
}

gleichverteilt ausgibt.

Außerdem, so nebenbei, wenn du sowieso zeilenweise bis zum Ende der Datei einliest, warum rufst du dann jedesmal rand() immer wieder neu auf ?

um nicht zweimal die datei lesen zu müssen. wir erinnern uns, daß eine kopfbewegung der schreib-lese-kamms mal lockere 6ms kosten kann. und der prozessor macht 1000000000 takte pro sekunde. einmal kamm-bewegen-einsparen und du hast 166666 takte gewonnen. dafür kann man oft rand() aufrufen. gehen wir davon aus, daß das betriebssystem die zugriffe im cache hat. im zweiten durchlauf bezahlst du dann keine kopfbewegung mehr (puh! glück gehabt.) aber endlos viele aufrufe von read() mit syscalls also context-switches. mit netter implementierung von istream aber nur selten. dafür ist die verwaltung im istream aber wieder da. also nochmal-lesen kommt vielleicht frage. aber ich hab da ein sehr ungutes gefühl. das hast du sicherlich auch. probieren wir es mit zwischenspeichern der zeilen in einem array. ich nehme an, du rufst dann pro zeile einmal new (oder malloc) auf. kostet mehr als eine division.

Performance-technisch nicht gerade optimal, nicht wahr ?

nicht optimal. netter wäre es vermutlich, das file per file mapping zu lesen und sich die zeilenanfänge in einer std::queue zu sammeln und danach mit einem rand()-aufruf die gesuchte zeile zu fassen und dann byteweise bis zum zeilenumbruch zu lesen. könnte aber sein, daß diese version erst so ab einer 10MB großen datei mehr als 1% gegenüber meiner lösung schneller ist.

CStoll hat dieses vorgehen direkt als erste antwort gebracht. statt file mapping, was noch ein klitzekleines bißchen rausholen könnte, ne standardfunktion. *notitzmach: wenn ich zu faul zum nachdenken bin, hat CStoll im technischen programmieren erstmal recht.*

Kurz ausgedrückt:
Für jede neu eingelesene Zeile wird rand() aufgerufen. EIN Aufruf von rand() reicht völlig.

ja, ist mir klar. aber zwischenspeichern kostet speicherallokationen, die teurer sind; nochmal-lesen kostet syscalls, die abermals teurer sind.

Dann noch:
Wenn man sowieso nicht vorhat, alle Zeilen in ein Array einzulesen,
wozu überhaupt jede Zeile in line reinschreiben ?
Eine Suche nach '\n' in der Datei reicht völlig aus.

ja, ich kopieren im durchschnitt 1+1/2+1/3+1/4+1/5+1/6... zeilen.
siehe auch http://de.wikipedia.org/wiki/Harmonische_Reihe
bei 10000 zeilen durchschnittlich gerade mal 10 mal der string::op=. damit kann ich leben und der code ist einfach.

Und vielleicht noch:
Wenn man doch alle Zeilen in ein Array schreiben will, ok, macht man das eben.
Der Aufruf von rand() braucht in jedem Fall nur EINMAL zu erfolgen,
denn bekanntlich muss die Anzahl n VOR der Berechnung der Zufallszahl bekannt sein, logisch ne ?

nö. mein algo braucht die anzahl der zeilen in der datei *nicht* VORHER. immer, wenn eine neue zeile von der platte eintröpfelt, wird gewürfelt, ob die neue zeile die vorläufige ergebniszeile sein soll. dabei wird der würfel so geschickt gewählt, daß am ende alle zeilen die gleiche chance hatten, das endergebnis zu werden.

könntest du, wenn du weiter zweifelst, daß mein verfahren funktioniert, ein programm bauen, das nachweist, daß mein verfahren keine gleichverteilung liefert?

[camper]

volkard schrieb:

außer, daß RAND_MAX kleiner sein könnte als die zeilenzahl.

was pflanzt sich da durch?

Bei Gleichverteilung ist die Wahrscheinlichkeit, dass eine bestimmte Zeile aus n Zeilen ausgewählt wird, 1/n. Mangels besserer Alternativen nehmen wir an, dass rand() uns eine gleichverteilte Zufallsfolge im Bereich 0..RAND_MAX liefert. Diesen Bereich bilden wir, ob nun durch rand()%n oder rand()*n/(RAND_MAX+1), auf den Bereich 0..n-1 ab. Immer dann aber, wenn n kein Teiler von RAND_MAX+1 ist, ist die Verteilung nicht mehr gleichmäßig. Die Wahrscheinlichkeit für rand()%n==0 ist eben nicht 1/n, sondern ((RAND_MAX+n)div n)/(RAND_MAX+1) (div hier für Ganzzahldivision); also etwas größer als 1/n wenn n kein Teiler von RAND_MAX+1 ist. Die Wahrscheinlichkeit, dass die neu eingelesene Zeile ausgewählt wird, ist damit fast immer etwas zu groß und nie kleiner als 1/n. Das führt dann dazu, dass der Erwartungswert (deines Algoritmus) größer als n/2 wird und die Wahrscheinlichkeit für eine bestimmte Zeile monoton mit der Zeilennummer wächst. Die Frage, die ich stellte, bezog sich darauf, wie groß dieser Effekt im Verhältnis ist. Meine Tabellenkalkulation ist da etwas überfordert und ich hab keine rechte Lust, ein Programm dafür zu schreiben.
Der Fehler ist immer kleiner als 1/(RAND_MAX+1) - aber sobald die Zeilenzahl nicht mehr klein gegen RAND_MAX ist, dürfte sich auch dieser Fehler zu einer nicht zu vernachlässigenden Größe akkumuliert haben.

[proggingmania]

Moin moin Proggies und Mathematiker !

Ich habe tierisch dicke Rübe ( Kopfschmerzen ) ! Gesoffen ? Nein ! Wegen Gleichverteilug ?
Lol, nein !
Keineee Ahnuung, aber was schönes hab ich trotzdem:

#define HASTA_LA_VISTA_BABY(s) cout << s << endl

#include <time.h>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std ;

void main()
{
	vector <string> zeilen;
	string zeile, dateiname("Sprueche.txt");
	ifstream datei;
	unsigned int zufallsindex = 0;

    datei.open( dateiname.c_str() );

	if ( ! datei ) 
	{
		cout << dateiname << " nicht gefunden." << endl;
		return;
	}

	while(getline( datei, zeile )) // Datei einlesen
	{
		zeilen.push_back(zeile); // Zeilen in Vector speichern
	}
	datei.close(); // So gut wie selbstredend

	srand((unsigned)time(NULL));

	// 100 mal "würfeln" und zugehörigen Spruch ausgeben.
	for( int i = 0; i< zeilen.size(); i++ )
	{
		zufallsindex =  rand() * zeilen.size()  / ( RAND_MAX + 1 ) ;
		cout << zeilen.at(zufallsindex) << endl;
	}

	HASTA_LA_VISTA_BABY("I'll be Back");
}

[proggingmania]

proggingmania schrieb:

// 100 mal "würfeln" und zugehörigen Spruch ausgeben.
	for( int i = 0; i< zeilen.size(); i++ )
	{
		zufallsindex =  rand() * zeilen.size()  / ( RAND_MAX + 1 ) ;
		cout << zeilen.at(zufallsindex) << endl;
	}

	
}

Und wenn meine Datei zufällig keine 100 Zeilen hat ?
Dann wird natürlich nur zeilen.size() mal "gewürfelt" ( aua ! )