Anspruchsvoll Aufgabe

[Nathan]

m.e. schrieb:

und dann schrieb:

Das bringt dir auch nichts, um die 3 häufigsten zu finden. Du brauchst schon noch den 2ten Vector für die 3 häufigsten.

Ich glaube, da hast du mich falsch verstanden. Ich wollte nicht sagen, dass man mit begin das häufigste Element findet, sondern: Schau mal auf dieser Seite, da findest du Code, mit dem man durch die Elemente einer Hashtabelle iterieren kann.

Nathan schrieb:

Matze16 schrieb:

Aber erstens ist die unsortiert.

Ja...?

Ja, sonst hätten wir beim einfügen nicht mal theoretisch O(1).

Ich denke, er meinte eher sowas wie: Ja und? Was soll das für schlimme Konsequenzen haben?

das.

[Matze16]

Also ich würds mal so machen. Ich bekomme jetzt nur noch diesen Fehler hier.

Fehler 1 error C2664: 'std::_Tree_iterator<_Mytree>::_Tree_iterator(const std::_Tree_iterator<_Mytree> &)': Konvertierung des Parameters 1 von 'std::_List_iterator<_Mylist>' in 'const std::_Tree_iterator<_Mytree> &' nicht möglich

#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::map<string,int>::iterator,bool> ret;

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

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

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

		}

		lstWords.push_back(tmp);
		hashtable.erase(tmp);
	}

	return lstWords;
}

int main()
{
	string exampleString = "Terror in Kopenhagen Während einer Diskussionsrunde zum Thema Meinungsfreiheit und Blasphemie fallen Dutzende Schüsse Ein unbekannter Täter schoss von außen auf das Cafe  in dem die Veranstaltung stattfand ein Zivilist wurde bei der Attacke getötet mindestens drei Polizisten wurden angeschossen Sie sind außer Lebensgefahr Die dänische Regierung geht von einem Terrorakt aus.Alles deutet darauf hin  dass die Schüsse eine politisch motivierte Attacke darstellen und deswegen ein Akt des Terrorismus sind  sagte Ministerpräsidentin Helle Thorning-Schmidt  Das Attentat galt offenbar dem schwedischen Karikaturisten Lars Vilks, der bei der Diskussionsrunde anwesend war Vilks brachte sich in einer Kühlkammer in Sicherheit  er blieb unverletzt" ;
	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;
	}

}

[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.

[m.e.]

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.

[matze16]

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++;
}

[Matze16]

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.

[matze16]

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.

[matze16]

Hui,

char k = ' ';

ist also Leerzeichen . Wusst ich gar nicht. Dankkeee

[wieesgeht]

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.

[DirkB]

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

[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;
	}
}