Anspruchsvoll Aufgabe

hustbaer

Dazuschreiben in welcher Zeile du diesen Fehler bekommst wäre schon ne feine Sache gewesen...

Guck dir mal den Typ von ret und den Typ von hashtable an - ob dir da was auffällt.

ps: Das 'Raussuchen der N häufigsten Elemente funktioniert auch noch nicht, da fehlt noch was.

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?