3. Algorithmus optimieren - Binary Tree Search

Algorithmus optimieren - Binary Tree Search

  • V

    Werner Salomon schrieb:

    for( q.push( node_info( get_root(), 0 ) ); !q.empty(); q.pop() ) // for geht vor while

    Nö, nicht immer.
    Hier geht for nicht vor, würde ich sagen.
    for impliziert bei mir, daß die Anzahl irgendwie schon vorher feststeht.
    Das ist hier nicht gegeben, sondern es wird immer nachgelegt und selber produziert.

    0
  • W

    volkard schrieb:

    for impliziert bei mir, daß die Anzahl irgendwie schon vorher feststeht.

    😕 ... das hat 'for' bei mir noch nie impliziert - auch zu C-Zeiten nicht. Das würde ja bedeuten, dass Du auch eine Iteration über eine einfach verlinkte Liste nicht mit for lösen würdest - also eher:

    Node* p = start;
    while( p ) {
        // body
        p = p->next;
    }

    statt:

    for( Node* p = start; p; p = p->next ) {
        // body
    }

    Ich vertrete vielmehr die Ansicht, dass die Kontrolle der Schleife im wesentlichen innerhalb des for-Statements stehen soll - das ist in obigem Beispiel eher der Fall, als mit der while-Lösung.
    Aber das ist letztlich Geschmackssache - ich habe das oben mal abgeschwächt.

    Gruß
    Werner

    0
  • V

    Werner Salomon schrieb:

    volkard schrieb:

    for impliziert bei mir, daß die Anzahl irgendwie schon vorher feststeht.

    😕 ... das hat 'for' bei mir noch nie impliziert - auch zu C-Zeiten nicht. Das würde ja bedeuten, dass Du auch eine Iteration über eine einfach verlinkte Liste nicht mit for lösen würdest

    Doch, da steht die Anzahl irgendwie fest. Ich ändere beim Durchlaufen den Container nicht. Ich laufe ungern auf etwas, was ich verändere.
    for impliziert bei mir zum Beispiel auch, daß ich die Laufvariable außer im Weiterschaltungsausdruck nicht verändere. Möchte ich das tun, wird while draus.

    Werner Salomon schrieb:

    Ich vertrete vielmehr die Ansicht, dass die Kontrolle der Schleife im wesentlichen innerhalb des for-Statements stehen soll - das ist in obigem Beispiel eher der Fall, als mit der while-Lösung.

    Hmm. Ich kann mit stack eine Tiefensuche machen und mit queue eine Breitensuche.
    Das

    node_info nf=s.top();
               s.pop();

    ist eine Einheit und wäre in anderen Sprachen ein

    node_info nf=s.pop();

    Du hast Dich auf die queue festgelegt, indem Du das pop auseinandergerissen hast, um for benutzen zu können.

    Aber das ist letztlich Geschmackssache - ich habe das oben mal abgeschwächt.

    Jo, wollte es trotzdem mal erwähnt haben. Vielleicht hilft's ja mal.

    0
  • ?

    jetzt?

    typedef struct node_info {
		node_info(node *n1, int h): n(n1), height(h) {}
		node *n;
		int height;
	}node_info;

	void add_to_list(std::vector<std::list<node_info>> &l, node *n, int height) {
	  std::vector<std::list<node_info>>::iterator it;
	  std::list<node_info>::iterator it2;
	  bool found = false;

	  for(it = l.begin(); it != l.end(); it++) {
		it2 = (*it).begin();

		if(it2->height == height) {
		  node_info t(n, height);
		  it->push_back(t);
		  found = true;
		  break;
		}
	  }

	  if(!found) {
		node_info t(n, height);
		std::list<node_info> l2;
		l2.push_back(t);
		l.push_back(l2);
	  }  
	}

    bool get_nodes_in_height(int h1, std::list<node_info> &out) {
	  typedef struct n_info {
		n_info(node *nn, int h): n(nn), height(h) {}
		node *n;
		int height;	 
	  }n_info;

	  node *n = get_root();
	  std::vector<std::list<node_info>> l;
	  std::queue<n_info> s;
	  int height = 0;

	  s.push(n_info(n, height));

	  while(!s.empty()) {
		n_info nf = s.front();

		height = nf.height;
		node *t = nf.n;

		add_to_list(l, t, height);

		s.pop();

		if(t->right) {
		  s.push(n_info(t->right, height+1));
		}
		if(t->left) {
		  s.push(n_info(t->left, height+1));
		}
	  }

	  if(it2->height == h1) {
		  out = l[h1];
		  return true;
	  }
const node_info& top = q.front();
            if( top.height == h1 )
                out.push_back( top.n ); // <-

	  return false;
	}
    0
  • W

    geri1 schrieb:

    jetzt?

    Hallo geri1,

    was willst Du uns jetzt damit sagen?
    Das Listing ist fast identisch mit Deiner ersten Version - bis auf die Einfügung ab Zeile 67. ' q ' ist aber gar nicht definiert - sollte also nicht kompilieren, wenn ich mich nicht geirrt habe.

    Helfen Dir Volkards und meine Antwort oder hast Du noch Fragen?

    Gruß
    Werner

    PS.:

    volkard schrieb:

    Jo, wollte es trotzdem mal erwähnt haben. Vielleicht hilft's ja mal.

    😃 wobei?

    0
  • R

    So, ich hab mal ein wenig selbst programmiert:

    Zum Testen hab ich einen binären Baum mit 10.000.000 Einträgen erstellt. Beim Suchen aller Elemente der Höhe 20 benötigt mein Algorithmus 50 ms, während deiner 4500ms benötigt. Die Anzahl der gefundenen Knoten stimmt überein, von daher gehe ich davon aus, dass mein Algorihtmus korrekt ist.

    Weil 50ms eigentlich viel zu schnell ist, hab ich nochmal mit 50M Elementen und Höhe 30 getestet. Dein Algorithmus benötigte hier 102 Sekunden, meiner 22 Sekunden. Der größte Designfehler bei deinem Algorithmus ist, dass du den kompletten Baum durchgehst (daher der große Unterschied beim ersten Test).

    Hier nur der neue Code (inkl. geänderter Main):

    void get_list_nodes_of_height_fast(std::list<node_info> &out, int h1) {
    	 std::vector<node_info> stack; // Knoten, dessen rechte Seite noch analysiert werden muss
    	 node* n = get_root(); // aktueller Knoten
    	 int h_akt = 0; // aktuelle Höhe

    	 while (true) {
    		 if (n == NULL) {
    			 // aktueller Ast vollständig ausgewertet: Nächstes Element aus dem Stack nehmen
    			 if (stack.empty())
    				 break;
    			 n = stack.back().n;
    			 h_akt = stack.back().height;
				 stack.pop_back();
    		 }
			 if (h_akt == h1) {
				 // Knoten der gesuchten Höhe
				 out.push_back(node_info(n, h_akt));
				 n = NULL;
			 } else {
				 node* left = n->left;
				 node* right = n->right;
				 if (left && right)
					 // Linker und Rechter Ast existiert => Rechten zum Stack hinzufügen (und später analyieren
					 stack.push_back(node_info(right, h_akt+1));
				 if (left) {
					 // Linken Ast analysieren
					 n = left;
					 h_akt++;
				 } else if (right) {
					 // Rechten Ast analysieren, falls Linker nicht vorhanden war
					 n = right;
					 h_akt++;
				 } else {
					 // Ast ist komplett analysiert
					 n = NULL;
				 }
			 }
    	 }
     }
}; 

int main() {
	srand(time(0));
	tree tt;
	for (int i = 0; i < 50000000; i++) {
		if (i % 1000000 == 0) cout << i / 1000000 << "," << flush;
		tt.insert(rand() * RAND_MAX + rand());
	}
	cout << '\n';

	{
		std::list<tree::node_info> t;
		long long t0 = clock();
		tt.get_list_nodes_of_height(t, 30);
		cout << "TIME: " << (clock() - t0) << endl;
		cout << "size: " << t.size() << endl;

//		for(std::list<tree::node_info>::iterator it = t.begin(); it != t.end(); it++) {
//				cout << (*it).n->value << endl;
//		}
	}

	{
		std::list<tree::node_info> t;
		long long t0 = clock();
		tt.get_list_nodes_of_height_fast(t, 30);
		cout << "TIME: " << (clock() - t0) << endl;
		cout << "size: " << t.size() << endl;

//		for(std::list<tree::node_info>::iterator it = t.begin(); it != t.end(); it++) {
//				cout << (*it).n->value << endl;
//		}
	}
}
    0
  • ?

    geri scheint 0-Plan zu haben 🙂

    0
  • ?

    der letzte geri1 war ein doppelgänger und nicht der orginale! 🙂

    0
  • ?

    @Ramanujan: hast du die laufzeit von volkards version auch getestet?

    0
  • R

    jo, hab ich jetzt mal gemacht. Sie ist quasi genauso schnell wie meine. Manchmal war sie 2-3% schneller.

    0
Anmelden zum Antworten