Effizientes Suchen

ja, map ist schon sehr schnell. wenn's aber bei großen dateien hinkommt, dass du schnell viel zu viele verschiedene wörter hast? kommt auf die wörter an. menschliche wörter oder zufällige buchstabenkombinationen?
wenn sich das aber in grenzen hält (große grenzen), gibt es noch einen hinweis bei der verwendung von map:

wenn du zuerst schaust, ob ein schlüssel in der map schon vorhanden ist und dann - falls nicht - einen neuen einfügst, kannst du insert mit einem "hint" verwenden: du weißt ja nach einmal suchen schon, wo sich das element befinden *sollte*.
das funktioniert dann c.a. so: (steht in "effective stl" oder so ausführlicher drin)

map<string, int> words;

map<string, int>::iterator pos = words.lower_bound(key); //nach key wird gesucht

if (pos == words.end() || key != pos->first)
//lower_bound liefert entweder end zurück oder den ersten schlüssel, der größer gleich dem gesuchten ist. deshalb die beiden überprüfungen
{
   //element nicht gefunden, neues einfügen.
   words.insert(pos, make_pair(key, counter++));
}
else
 //element ist in der map.

ansonsten liefern mir tests gerade, dass ein stringstream wohl besser wäre als das zwischenspeichern in einem vector. (80 MB, 80000 verschiedene wörter)

life

Oder so: Pseudocode:

charSetSize = 'z' - 'A' + 1;
vector<array<int, charSetSize >> stateMachine;
vector<int> stateToInt;
int wordCounter = 0;
vector<int> result;

stateMachine.push_back(array<int, charSetSize>(-1)); //inits array with -1
stateToInt.push_back(0);

for each word in input {
    currentState = 0;
    for each c in word {
        currentCharCount = c - 'A';
        if(stateMachine[currentState][currentCharCount] == -1) {
            stateMachine.push_back(array<int, charSetSize>(-1));
            stateToInt.push_back(0);
            stateMachine[currentState][currentCharCount] = stateMachine.size()-1;
        }
        currentState = stateMachine[currentState][currentCharCount];
    }
    if(stateToInt[currentState] == 0) {
        stateToInt[currentState] = ++wordCounter;
    }
    result.push_back(stateToInt[currentState]);
}

Laufzeit: O(n) statt O(n * log(n))

fabske

Mir ist da gerade was eingefallen: Bisher nehme ich das erste Wort und gebe ihm die Zahl 1, dem zweiten die Zahl 2 usw. Es ist aber nicht nötig dass alle Zahlen vorkommen!
Wäre es nicht besser, die Zahl aus dem Wort zu berechnen? Also z.B. zu Hashen anstatt immer im Container zu suchen, ob das Wort schon eine Zahl hat und wenn nicht eine zuzuordnen? Wenn ich die Zahl direkt aus dem Wort berechnen kann, kann ich gleich in einem Vektor an der besagten Position nachschauen ob es dort schon eine Zahl gibt. Bzw. Eigentlich bräuchte ich gar keine "Look-up-Table" mehr sondern benutze nur einen Algorithmus um die Zahl für das Wort zu berechnen. ?

ist das nicht, was life vorgeschlagen hat?

Das schreit doch geradezu nach einem Trie oder Patricia-Trie.

fabske

dummfrager schrieb:

ist das nicht, was life vorgeschlagen hat?

Ich dachte das auch so verstanden zu haben, auch wenn ich nicht genau verstanden hab was er da macht.

ABER: Kommando zurück! Es müssen aufeinanderfolgende Zahlen beginnend bei 1 sein (so sieht es DIMACS vor..). Das heißt ich werde wohl doch einen Container brauchen..

life

Im Prinzip baue ich einen Trie, wie seldon es auch vorgeschlagen hat. Bei meiner Lösung sind die Zahlen dementsprechend aufeinanderfolgendend.

Michael E.

Dumme Frage: Nutzt du map<int, string> oder map<string, int>? Das Suchen beim einen ist natürlich viel langsamer als das Suchen beim anderen.

An dieser Stelle würde ich den Zweck von std::string hinterfragen und die Lookup-Tabelle mit rohen Strings bauen, wenns zu lahm läuft.

fabske

Ich verstehe nicht ganz, wie du diesen Trie baust! Wie berechnest du denn die Zahlen für die Worte? Kannst du bitte ein bisschen erklären?

Daneben hab ich noch eine zweite Bremse in meinem Programm gefunden:

boost::algorithm::split(), damit splitte ich jede Zeile in einzelne Worte auf. Es braucht aber 50% meiner Programmlaufzeit..

Hier ist der Quellkode meines Programms: http://nopaste.info/703fbb53cc.html Der hier behandelte Teile ist für die Option -dimacs.

Ich verwende std::map<std::string, int> literals;
Was ist eine look-up-tabelle mit "rohen Strings"?

life

fabske schrieb:

Ich verstehe nicht ganz, wie du diesen Trie baust! Wie berechnest du denn die Zahlen für die Worte? Kannst du bitte ein bisschen erklären?

Der stateMachine Vector beschreibt die Knoten+Kanten des Tries. Die Knotenmenge ist 0,...,stateMachine.size()-1 . Die Kanten werden im Array gespeichert. So werden also die ausgehende Kanten von z.B. dem Knoten 0 in stateMachine[0] gespeichert.

Da es im Trie nur für jeden möglichen Buchstaben im Alphabet eine Kante geben kann, benutze ich ein Array, um die Kanten zu speichern. Dabei bedeutet der Wert -1, dass zur Zeit keine Kante für den entsprechenden Buchstaben vorhanden ist (also falls z.B. stateMachine[0]['a'-'A'] == -1 ist, gibt es keine mit 'a' beschriftete Kante im Trie für den Knoten 0).

Um den Wörtern Zahlen zuzuordnen, ordne ich einfach mittels stateToInt Knoten im Trie Zahlen zu.

life

Also deinen Quellcode aufgreifend, müsste es ungefähr wie folgt aussehen:

const unsigned charset_size = 'z'- 'A' + 1;
	std::vector<boost::array<int, charset_size>> state_machine;
	std::vector<int> state_to_int;

	int num_literals = 0; 
	std::stringstream outputline;

	state_machine.push_back(boost::array<int, charset_size>()); 
	std::fill(&state_machine.back()[0], &state_machine.back()[charset_size-1], -1);
	state_to_int.push_back(0); 

	unsigned current_state = 0;	

	while(std::getline(infile, inputline))
	{
		// look for comments (//) and ignore them.
		if(inputline.find("//")!=std::string::npos) 
			inputline.resize(inputline.find("//"));
		if(inputline.empty()) 
			continue;

		for(std::string::const_iterator it = inputline.begin(); it != inputline.end(); ++it) {
			char current_char = *it;
			if(!(current_char >= 'A' && current_char <= 'z')) {
				if(current_state != 0) {
					if(state_to_int[current_state] == 0) {
						state_to_int[current_state] = ++num_literals;
					 }
					outputline << state_to_int[current_state] << " "; 
				}
				current_state = 0; 
			}
			else {
				int current_char_number = current_char - 'A';
				if(state_machine[current_state][current_char_number] == -1) {
					state_machine.push_back(boost::array<int, charset_size>()); 
					std::fill(&state_machine.back()[0], &state_machine.back()[charset_size-1], -1);
					state_to_int.push_back(0); 

					state_machine[current_state][current_char_number] = state_machine.size()-1;
				}
				current_state = state_machine[current_state][current_char_number];
			}
		}	
		if(current_state != 0) {
			if(state_to_int[current_state] == 0) {
				state_to_int[current_state] = ++num_literals;
			}
			outputline << state_to_int[current_state] << " "; 
		}
	}

fabske

Sehr interessant! Nur dass meine "Wörter" eigentlich Strings sind die auch _,'. und Zahlen enthalten können. Vielen Dank erstmal!