Effizienz in C++

Question

Ich versuche, einen Baum zu erstellen (eventuell für den Einsatz in einem "neuronalen Netzwerk" und versuchen, nur das Setup so effizient wie möglich zu machen. Leider dauert sogar die Einrichtung des Baumes ca. 3 Minuten und Ich kann nicht herausfinden, was es macht es so ineffizient. Ich versuchte, Zeiger wo immer möglich zu verwenden, um die Last zu minimieren, aber es dauert immer noch. Was mache ich falsch?

PS. Dies ist schließlich für eine Tic Tac Toe AI (ja, ich weiß, dass es nur durch das blöde Spiel gelöst werden kann, aber ich wollte es als einfache KI machen, um mir selbst beizubringen.

Jeder Ast des Baumes würde 9 Knoten haben, mit jedem Knoten verzweigt, um einen anderen zu machen 9. Das gibt der letzten Reihe von Zweigen ungefähr 400 Millionen Knoten. Gibt es eine Möglichkeit, diesen Code effizienter zu machen?

#include <iostream> 
#include <vector> 


using namespace std; 

class Node; 
class Set; 


class Node { 
    public: 
     Node(double, Set*); 
     Node(); 
     double value; 
     Set * nextSet; 
}; 
class Set { 
    public: 
     Set(vector<Node *>); 
     Set(); 
     vector<Node *> nodes; 
}; 
class NeuralNet { 
    public: 
     Set * firstSet; 
}; 
Node::Node(double val, Set * newSet){ 
    value = val; 
    nextSet = newSet; 
} 
Set::Set(vector<Node *> input){ 
    nodes = input; 
} 
Node::Node(){ 
    Set temp; 
    nextSet = &temp; 
} 
Set::Set(){ 
    vector<Node *> temp; 
    nodes = temp; 
} 
void setUpNeuralNetRecursive(Set * curSet, int curDepth){ 
    if(curDepth<9){ 
     for(int i=0;i<9;i++){ 
      Set newSet; 
      Node newNode(1,&newSet); 
      (*curSet).nodes.push_back(&newNode); 
      setUpNeuralNetRecursive(&newSet, curDepth+1); 
     } 
    } 
} 
void setUpNeuralNet(NeuralNet net){ 
    Set newSet; 
    net.firstSet=&newSet; 
    setUpNeuralNetRecursive(&newSet, 0); 
} 
int main() 
{ 
    cout << "Setting up neural network. This may take up to 3 minutes." << endl; 
    NeuralNet net; 
    setUpNeuralNet(net); 
    cout << "Setup ended." << endl; 

    return 0; 
} 

Answer 1

Sie haben einen vollständig ausgeglichenen, 9-gliedrigen Baum? Do not einen Knoten für jedes Element zuweisen! Stattdessen zuteilen ein Array für Sie Knoten und navigieren Sie den Baum Berechnungen mit:

• , um von Knoten zu navigieren i zu seinem übergeordneten Sie (i - 1)/9
• berechnen würde, um die am weitesten links stehende Kind finden Sie berechnen würde i * 9 + 1

(oder so ähnlich; es ist mitten in der Nacht, und ich bin nicht ganz in der Lage, diese Mathematik zu tun). In jedem Fall können Sie mit einer solchen Formel durch einen vollständig ausgeglichenen n-stufigen Baum navigieren. Dieser Ansatz wird z. B. für d-heaps verwendet. Der Vorteil dieses Ansatzes besteht darin, dass Sie nur eine große Zuweisung haben und das Navigieren durch den Baum zu Rechen- und nicht zu Speicher-Look-Ups wird.

Das heißt, ich bezweifle, dass Sie wirklich einen Baum wie folgt wollen: Die Anzahl der Entscheidungen wird kleiner mit jeder Bewegung und Sie wollen wahrscheinlich bestimmte Zweige vollständig töten. Die Technik für Bäume kann jedoch immer noch nützlich sein.