Efficiency in C++ [closed]

Question

I'm trying to set up a tree (eventually for use in a "neural network" and attempting to make just the setup as efficient as possible. Unfortunately, even setting up the tree is taking approximately 3 minutes and I can't figure out what about it is making it so inefficient. I attempted to use pointers wherever possible to minimize the load, but it still is taking forever. What am I doing wrong?

PS. This is eventually for a Tic Tac Toe AI (yes I know it can be solved just by looking at the stupid game, but I wanted to do it as a simple AI to teach myself how.

Each branch of the tree would have 9 nodes, with each node branching out to make another 9. That gives the last set of branches approximately 400 million nodes. Is there ANY way to do this code more efficiently?

#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

You have a fully balanced, 9-ary tree? Don't allocate a node for each element! Instead, allocate an array for you nodes and navigate the tree using computations:

• To navigate from node i to its parent you'd compute (i - 1) / 9
• To find the left-most child you'd compute i * 9 + 1

(or something like this; it is in the middle of the night and I'm not quite up to do this math). In any case, you can navigate a fully balanced n-ary tree using a formula like this. This approach is, e.g., is used for d-heaps. The advantage of this approach is that you only have one big allocation and navigating the tree becomes computing rather than memory look-ups.

That said, I doubt that you really want a tree like this: the number of choices become smaller with each move and you probably want to kill certain branches entirely. The technique for trees may still be useful, though.