Anspruchsvoll Aufgabe

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?

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.

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.

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.

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.

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 !!!!!!!