3. Effizientes Suchen

Effizientes Suchen

  • F

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

    0
  • ?

    ist das nicht, was life vorgeschlagen hat?

    0
  • ?

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

    0
  • F

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

    0
  • L

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

    0
  • M

    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.

    0
  • F

    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"?

    0
  • L

    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.

    0
  • L

    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] << " "; 
		}
	}
    0
  • F

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

    0
Anmelden zum Antworten