Anspruchsvoll Aufgabe

[Nathan]

matze16 schrieb:

Hui,

char k = ' ';

ist also Leerzeichen . Wusst ich gar nicht. Dankkeee

Wie gesagt: lern die Grundlagen.

[hustbaer]

wieesgeht schrieb:

Wenn man die Hashtable durch einen Trie mit Counter ersetzt, geht es in O(n). Und man muss keine Hash brechnen und braucht kein riesen Array.

Nö, dann hast du O(n*log m), wobei m=max(len(word)).

EDIT: Quatsch, wenn man N passend wählt verschwindet dieses Problem, und der Trie geht mit O(N) (worst case)! /EDIT

[m.e.]

hustbaer schrieb:

wieesgeht schrieb:

Wenn man die Hashtable durch einen Trie mit Counter ersetzt, geht es in O(n). Und man muss keine Hash brechnen und braucht kein riesen Array.

Nö, dann hast du O(n*log m), wobei m=max(len(word)).

Das ist jetzt aber ein bisschen unfair, weil wir auch so getan haben, als ob wir Hashes in O(1) berechnen könnten. Die vorgeschlagene Lösung läuft linear in der Eingabelänge. Ich muss gestehen, dass ich mal wieder nicht an Tries gedacht habe.

[hustbaer]

@m.e.
OK, ich verstehe und akzeptiere diesen Einwand

Wenn wir einfach N=strlen(input) nehmen, wobei input der String mit allen Wörtern vor dem Split in einzelne Wörter ist, dann sollte das reichen um für den Trie wieder auf O(N) (worst-case) zu kommen.
Und um für den Hashtable auf O(N) (average) zu kommen.

Hab' ich wieder nicht weit genug gedacht.

[Finnegan]

m.e. schrieb:

hustbaer schrieb:

wieesgeht schrieb:

Wenn man die Hashtable durch einen Trie mit Counter ersetzt, geht es in O(n). Und man muss keine Hash brechnen und braucht kein riesen Array.

Nö, dann hast du O(n*log m), wobei m=max(len(word)).

Das ist jetzt aber ein bisschen unfair, weil wir auch so getan haben, als ob wir Hashes in O(1) berechnen könnten. Die vorgeschlagene Lösung läuft linear in der Eingabelänge. Ich muss gestehen, dass ich mal wieder nicht an Tries gedacht habe.

Was ich auch ein wenig unfair finde, ist dass $n$ sich mittlerweile zur Eingabelänge eines Textes mit Wörtern gewandelt hat, während am Anfang noch die Rede von einer "Liste mit Wörtern" war, und ich davon ausging, dass $n$ die Anzahl der Wörter ist.
In diesem Fall kann man die Hash-Berechnung nämlich durchaus als O(1) betrachten, wenn man davon ausgeht, dass die maximale Wortlänge eine genügend groß gewählte Konstante ist.
Interessant ist auch, dass wenn $n$ die Anzahl der Wörter ist, ein Trie einen Faktor ins Spiel bringt, der sich ähnlich wie ein binärer Suchbaum verhält (abgesehen davon dass er einen höheren Verzweigungsgrad hat).

Bei $n$ als Textlänge lässt sich argumentieren, dass wir für jedes Textzeichen einen Schritt hinab in den Trie machen müssen, wodurch der Trie-Aufwand pro Zeichen konstant ist.

Aber wie schon erwähnt wurde, das ist alles Definitionssache und in der ursprünglichen Frage wird darauf nicht genau eingegangen (gibt schon einen Grund weshalb man solche Betrachtungen am besten immer mit "Sei/Let ..." beginnt :D).
Mittlerweile sieht es aber so aus als sei $n$ die Anzahl der Zeichen im Text. In diesem Fall ist ein Trie also eine gar nicht mal so schlechte Lösung.

Finnegan

P.S.: Im übrigen finde ich dass die Textlänge auch ein besseres $n$ ist, da es die zu verarbeitende Datenmenge besser widerspiegelt und ohne solche Krücken wie maximale Wortlänge auskommt

[Matze16]

Ich dachte ja erst ihr verarscht mich aber es gibt ja wirklich einen Trie
Ich kannte bislang nur diesen Tree .

[Matze16]

Das hier ist übrigends mein working code. Welche Laufzeit hat der nun jetzt. ERfülle ich das Kriterium O(n) ?

#include <iostream>
#include <string>
#include <list>
#include<map>
#include <algorithm>
#include <unordered_map>

using namespace std;

std::list<string> findFrequentWords(string x,int nrOfReturnItems )
{
	std::list<string> lstWords;
	std::unordered_map<string,int> hashtable;
	std::pair<std::unordered_map<string,int>::iterator,bool> ret;

	string tmp = "";
    int i = 0;
	while(i < x.length())
	{
		while( i < x.length() && x[i] != 0x20 )
		{
			tmp+=x[i];
			i++;
		}

		 ret = hashtable.insert ( std::pair<string,int>(tmp,1) );
		 if(ret.second==false) 
		 {
			 hashtable[tmp]++;
		 }
		 tmp="";
		 i++;

	}

	int count = 0 ;

	for(int i = 0 ; i < nrOfReturnItems ; i++)
	{
		for (unordered_map<string,int>::iterator it=hashtable.begin(); it!=hashtable.end(); ++it)
		{

			if(it->second > count)
			{
				tmp = it->first;
				count = it->second;
			}

		}

		lstWords.push_back(tmp);
		hashtable.erase(tmp);
		count = 0;
	}

	return lstWords;
}

int main()
{
	string exampleString = "my is my a to a to my by there my I my go go go" ;
	std::list<string> lstWords;
	int numberOfWords = 3;

	lstWords = findFrequentWords(exampleString,numberOfWords);
	std::list<string>::iterator it;
	for(it = lstWords.begin();it != lstWords.end();it++)
	{
		cout<<*it<<endl;
	}
}

[Skym0sh0]

Also ich bin nicht von einem String ausgegangen, der eine Reihe Wörter enthält, die durch ein Leerzeicheng etrennt sind, sodnern von einer Liste (vector, list, doer oder oder) mit (std::)Strings...

[volkard]

wieesgeht schrieb:

Trie mit Counter

Gratulation. Genial einfach.

Ich bin recht sicher, man muss im worst case jedes Zeichen anschauen, also biste im worst case optimal mit O(zeichen). Wenn die Daten als Stream reinkommen, ist das zugleich der best case. Fertig.

Was ist, wenn die Daten schon als vector<string> im Speicher liegen?
Mal folgende Datei:
10 mal "A"
und dann 9 zufällige Strings zu je einer Fantastillion Zeichen, die aber nicht mit "A" anfangen.
Man kann offensichtlich schnell die Anfangsbuchstaben der dummen Strings anschauen und dann abbrechen, weils selbst wenn die 9 langen Strings gleich wären, sie könnten nicht zu zehnt sein.
Also es kann sein, daß man Sonderfälle hat, wo man unter O(zeichen) kommt und bei O(strings) landet. Womit ich auch gleich ein Verfahren habe, das im best case O(strings) hat.

Kann man den average case drücken, wäre dann nur die Frage. Jo, klar, Hashtable. Aber dabei geht der extrem leckere worst case O(zeichen) leider total kaputt.

Kann man unter Beibehaltung des worst case O(zeichen) den average case noch drücken?

[hustbaer]

@volkard
Man muss beim Trie ja nicht pro Zeichen eine Ebene machen. Ist zwar die übliche Variante, aber nicht muss.

Man könnte dann z.B. pro Zeichen eine Ebenen anlegen, aber nur bis zu dem Punkt wo es eindeutig ist. Und dort dann einfach ein Blatt lassen. Die weiteren Zeichen müsste man sich dann nichtmal angucken - man müsste nur irgendwie den restlichen, noch nicht betrachteten Teilstring mit O(1) in diesem Blatt vermerken können.
Und dann erst weiter splitten wenn man es braucht.
Wenn man dann haufenweise unterschiedliche Strings reinbekommt, die immer nur 1x auftreten, und sich "ausreichend weit vorne" unterscheiden, dann sollte man damit auf unter O(sum(strlen(word))) kommen.

Allerdings auch nur wenn man "no-copy-strings" hat*, denn sonst kommt man mit teilweisem Angucken + Kopieren der nicht angeguckten Teilstrings zusammen auch wieder auf O(sum(strlen(word))) .

Wobei die Überlegung ziemlich müssig ist, denn irgendwo her müssen die Strings ja kommen, und dort hat man dann immer mindestens O(sum(strlen(word))) . Ausser die Strings liegen z.B. bereits fertig in einem ROM vor. Nur dann könnte man das Ergebnis gleich mit ins ROM packen, und hätte dann gleich O(1) .

*: Wenn der String über z.B. shared_ptr<char[]> implementiert ist (also ein COW-String), dann ginge es natürlich auch, da das Kopieren eines solchen Strings dann auch wieder O(1) und nicht O(strlen) wäre. Aber wie gesagt: die Strings müssen irgendwo entstehen, und damit ...

ps

volkard schrieb:

Kann man den average case drücken, wäre dann nur die Frage. Jo, klar, Hashtable.

Wie würdest du den average case mit nem Hashtable drücken wollen? Um einen sinnvollen Hash zu erstellen musst du ja auch den ganzen String durchgehen. Oder meinst du man sollte einfach nach N Buchstaben abbrechen und beten?

[volkard]

hustbaer schrieb:

ps

volkard schrieb:

Kann man den average case drücken, wäre dann nur die Frage. Jo, klar, Hashtable.

Wie würdest du den average case mit nem Hashtable drücken wollen? Um einen sinnvollen Hash zu erstellen musst du ja auch den ganzen String durchgehen. Oder meinst du man sollte einfach nach N Buchstaben abbrechen und beten?

Ups, nee. Werd jedes Zeichen hashen müssen.

[BLBALa]

Die Aufgabe ist doch total total easy !!

Alle Wörter durch gehen, diese einfach zählen, am Ende vergleichen und dann schauen, welche Wörter am Meisten vorkamen. Eine Aufgabe von unter 10 Minuten.

[hustbaer]

Na dann zeig mal her.

[hallooo]

BLBALa schrieb:

Die Aufgabe ist doch total total easy !!

Alle Wörter durch gehen, diese einfach zählen, am Ende vergleichen und dann schauen, welche Wörter am Meisten vorkamen. Eine Aufgabe von unter 10 Minuten.

Es handelt sich um 100000000 Wörter, so schnell kannst du garnicht zählen.

[hmmmm...]

volkard schrieb:

wieesgeht schrieb:

Trie mit Counter

Gratulation. Genial einfach.

Ich bin recht sicher, man muss im worst case jedes Zeichen anschauen, also biste im worst case optimal mit O(zeichen). Wenn die Daten als Stream reinkommen, ist das zugleich der best case. Fertig.

Was ist, wenn die Daten schon als vector<string> im Speicher liegen?
Mal folgende Datei:
10 mal "A"
und dann 9 zufällige Strings zu je einer Fantastillion Zeichen, die aber nicht mit "A" anfangen.
Man kann offensichtlich schnell die Anfangsbuchstaben der dummen Strings anschauen und dann abbrechen, weils selbst wenn die 9 langen Strings gleich wären, sie könnten nicht zu zehnt sein.
Also es kann sein, daß man Sonderfälle hat, wo man unter O(zeichen) kommt und bei O(strings) landet. Womit ich auch gleich ein Verfahren habe, das im best case O(strings) hat.

Ich würde sagen, dass das nicht die Sonderfälle sind, wo man unter O(zeichen) kommt. Man kann ja immer die Strings wegwerfen, die nicht mehr auf dem "erfolgreichen Pfad" mit den meisten gleichen Anfangsbuchstaben sind.
Eigentlich muss man sich nur alle Zeichen anschauen, wenn alle Strings gleich sind bzw. alle Strings Gruppen von X gleichen Strings sind.

[BLBALABASD]

hallooo schrieb:

BLBALa schrieb:

Die Aufgabe ist doch total total easy !!

Alle Wörter durch gehen, diese einfach zählen, am Ende vergleichen und dann schauen, welche Wörter am Meisten vorkamen. Eine Aufgabe von unter 10 Minuten.

Es handelt sich um 100000000 Wörter, so schnell kannst du garnicht zählen.

Natürlich meine ich das in einem Programm !!!!!!!