Anspruchsvoll Aufgabe

Matze16 schrieb:

Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.

Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.

Du scheinst Probleme damit zu haben, Informationen aus ner Hashtabelle wieder auszulesen. Wenn du std::unordered_map benutzt, dann schau dir mal z.B. http://www.cplusplus.com/reference/unordered_map/unordered_map/begin/ an.

Die Aufgabe kommt von Evernote.

Zitat: Implement this function as you would for a production/commercial system

Finnegan

Matze16 schrieb:

Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.

Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.

Schau dir mal meine erste Antwort an. Du aktualisierst die Liste (oder die einzelnen Variablen) mit deinen 3 häufigsten Strings direkt nach jedem erhöhen der Anzahl in der Hash-Map: niedrigere Häufigkeiten fallen raus und werden durch höhere ersetzt.

Alternativ kannst du die Hash-Map auch im Anschluss 3 mal durchlaufen und dabei jeweils das größte Element suchen, das kleiner ist als das gefundene des letzten Durchlaufs (O(4 * n) ist schließlich immer noch O(n)).

Zumindest die std::unordered_map lässt sich in O(n) iterieren. Soweit ich weiss haben die Elemente intern einen Zeiger auf das nachfolgende Element, so dass man nicht immer alle Buckets durchlaufen muss.

Finnegan

P.S.:

m.e. schrieb:

Um mal wieder etwas Konstruktives beizutragen: Es geht nicht schneller als Theta(n log n) (im selben Modell wie "Sortieren geht nicht schneller als Theta(n log n)), weil unser Problem schwerer ist als das Element Distinctness Problem. Also ist Sortieren, was SeppJ zu Recht aus praktischer Sicht nicht mag, theoretisch optimal für den Worst Case.

Das ist ein schönes Argument, falls der Vorwurf kommt, dass die Hash-Map-Variante im Worst Case nicht mehr O(n) ist ... es mag zwar für den Worst Case besser gehen, aber immer noch nicht in O(n).

Wie kann ich überhaupt prüfen ob der Key schon existiert ? Jedenfalls hab ich keine exisit Funktion gesehen?
Würde der value dann einfach überschrieben ?

Nathan

Matze16 schrieb:

Wie kann ich überhaupt prüfen ob der Key schon existiert ? Jedenfalls hab ich keine exisit Funktion gesehen?

Es gibt eine count() Funktion.

Würde der value dann einfach überschrieben ?

Ja. Siehe die Dokumentation zu operator[].

Finnegan schrieb:

Alternativ kannst du die Hash-Map auch im Anschluss 3 mal durchlaufen und dabei jeweils das größte Element suchen, das kleiner ist als das gefundene des letzten Durchlaufs (O(4 * n) ist schließlich immer noch O(n)).

Das funktioniert nicht, falls es mehrere Elemente gibt, die am häufigsten vorkommen. Es ist trotzdem kein Problem, die drei häufigsten Elemente in einem Durchlauf zu finden, so wie Insertion Sort, nur dass man nur die größten drei Elemente speichert.

Finnegan

Matze16 schrieb:

Wie kann ich überhaupt prüfen ob der Key schon existiert ? Jedenfalls hab ich keine exisit Funktion gesehen?
Würde der value dann einfach überschrieben ?

if (unorderedMap.find(key) != unorderedMap.end())
{
   // Key existiert in map
}

Alternativ gibt die insert() -Methode auch ein std::pair<iterator, bool> zurück, wobei der bool -Wert angibt, ob das Element eingefügt werden konnte (true), oder nicht, weil schon eines mit selbem Key existiert.

Finnegan

P.S.: Aber für das Wörter-Zählen brauchst du das nicht. Siehe operator[] ... der kann alles was du dafür brauchst.

m.e. schrieb:

Matze16 schrieb:

Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.

Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.

Du scheinst Probleme damit zu haben, Informationen aus ner Hashtabelle wieder auszulesen. Wenn du std::unordered_map benutzt, dann schau dir mal z.B. http://www.cplusplus.com/reference/unordered_map/unordered_map/begin/ an.

Notice that an unordered_map object makes no guarantees on which specific element is considered its first element.

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.

Nathan schrieb:

Matze16 schrieb:

Aber erstens ist die unsortiert.

Ja...?

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

Finnegan

m.e. schrieb:

Finnegan schrieb:

Alternativ kannst du die Hash-Map auch im Anschluss 3 mal durchlaufen und dabei jeweils das größte Element suchen, das kleiner ist als das gefundene des letzten Durchlaufs (O(4 * n) ist schließlich immer noch O(n)).

Das funktioniert nicht, falls es mehrere Elemente gibt, die am häufigsten vorkommen. Es ist trotzdem kein Problem, die drei häufigsten Elemente in einem Durchlauf zu finden, so wie Insertion Sort, nur dass man nur die größten drei Elemente speichert.

Oh ja... stimmt. Nicht weit genug gedacht. I stand corrected.
War allerdings nur Alternativvorschlag dazu die 3 größten gleich beim ersten durchlauf "mitzuführen".

Finnegan

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?

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.

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.

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.