Anspruchsvoll Aufgabe

Sehe ich das richtig, dass wir dir bei Programmierproblemen helfen sollen und du unsere Korrekturen dann bei deiner Bewerbung als Programmierer benutzt? Da würde ich doch alle bitten, sich mit Kommentaren zu Fehlern und vor allem Stil zurückzuhalten.

hustbaer

Ja, hast Recht.
Hab mich wieder mal ködern lassen
Jetzt noch weglöschen fände ich aber auch kindisch, also lass ich es halt stehen.

lol,

also ich hab jetzt schon mal rausgefunden dass std::string nicht nullterminiert ist sondern man die length funktion braucht Wahrscheinlich löst das schon einiges

das hier geht also nicht

std::string mystring = "Hallo Forum";

while(mystring[i])
{
   i++;
}

Und das Leerzeichen ist natuerlich ASCII Code 32 und nicht 20 was es ja hexadezimal wäre Leider kann man beim Leerzeichen kein '' machen sondern muss sich wirklich den Code merken

Nathan

Matze16 schrieb:

Leider kann man beim Leerzeichen kein '' machen sondern muss sich wirklich den Code merken

Lern die Grundlagen. Du solltest wirklich die Grundlagen lernen.

Was heisst grundlagen. Ich hab halt den Code verwechselt. Hex und Dez verwechselt. Anders gehts doch nicht oder ?

Und was sagt ihr eigentlich zu sowas

Die Reihenfolge der Parameter der logischen Verknüpfung bestimmt ob das Programm abstürzt oder nicht. Ist das nicht gefährlich. Ich mein der Standard legt es fest.

// so gehts 
while(i < string.length() && string[i] != 32)
{
}
//hier stürzt es ab
while(string[i] != 32 && i < string.length())
{
}

tkausl

'' ist auch kein Leerzeichen sondern ' '. '' ist einfach nur... garnichts.

Hui,

char k = ' ';

ist also Leerzeichen . Wusst ich gar nicht. Dankkeee

volkard schrieb:

Finnegan schrieb:

Laufzeit des Algorithmus ist O(n): Jedes der n Wörter wird einmal durchlaufen und im Schleifenkörper werden nur Operationen mit konstantem Aufwand durchgeführt (Hash-Map-Zugriffe und 3 Listen-Elemente prüfen).
Oder auch: n * (O(1) + O(3)) = n * O(1) = O(n)

... oder hab ich hier was übersehen?

Ich lese Deinen Code, finde die Hashfunktion, und bastele eine Wörterliste, wo alle Wörter den gleichen Hashwert haben und schau mal, ob der Hashtable-Zugriff noch O(1) hat.

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.

matze16 schrieb:

Und was sagt ihr eigentlich zu sowas

Die Reihenfolge der Parameter der logischen Verknüpfung bestimmt ob das Programm abstürzt oder nicht. Ist das nicht gefährlich. Ich mein der Standard legt es fest.
// so gehts 
while(i < string.length() && string[i] != 32)
{
}
//hier stürzt es ab
while(string[i] != 32 && i < string.length())
{
}

Weißt du auch, was der Standard dazu sagt?

1. Wenn es dem Compiler überlassen wird, wie er das Auswertet, dann wüßtest du nie, wie es funktioniert.
2. Ohne die besondere Regel (Short Circuit Evaluation ) dabei, würde es auch im ersten Fall nicht gehen.

Es ist immer dann gefährlich, wenn man nicht weiß was man tut.

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

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

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

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?