how to reduce the memory needed of a tree?

[werto87]

I use st_tree to create a tree and then "solve" it using the minimax algorithm. The result tree get stored in a vector. There are 1,000,000 trees and one tree needs around 5000 bytes. The mean_depth is 16 and the mean_size is 26. The tree type is

st_tree::tree<std::tuple<Result, bool>, st_tree::keyed<Action> > > >

Where "Result" and "Action" have a size of 1 byte. After creating the tree and "solving" it the tree is only needed for lookup. I think the problem is that the tree has a lot of vectors which have a small size so most of the memory is occupied by the 24 byte of a vector.

I think I can transform the tree into something else which needs less memory. Do you have an idea how to save memory per tree?

[erikerlandson]

I think if you are using the trees as lookup tables, then an alternative representation is going to be superior, maybe map<input,output>. It's hard to avoid that kind of overhead for trees having many smallish objects where the ratio of "overhead" to data is high.

[werto87]

Thank you for the fast reply, in the end I use the trees as lookup tables. The trees contain all the possible moves from a state in the game and are saved together with the state. So its possible to see all the possible moves and the result given the game state.

I do not know if I understand your suggestion: Do you suggest to save all the paths of the tree to the leaves in a map?

[erikerlandson]

Sometimes people will use a tree as a way to map a key to a value (at the leaves), in which case something like map<> is likely to be more memory efficient. It sounds like you need the trees to model the space of game states, and so in that case your tree representation is probably best.

[werto87]

There are 1,000,000 trees and one tree needs around 5000 bytes. The mean_depth is 16 and the mean_size is 26.

I made a mistake here. One tree is around 2500bytes and the mean depth is 3.52049 and mean size is 9.15034. I created an minimal example:

#include "st_tree.h"
#include <iostream>
#include <string>

int
main ()
{
  auto tree = st_tree::tree<std::tuple<uint8_t, uint8_t>, st_tree::keyed<uint8_t> >{};
  tree.insert ({ 1, 1 });
  tree.root ().insert (1, { 1, 1 });
  tree.root ().insert (2, { 2, 2 });
  tree.root ()[0].insert (1, { 42, 42 });
  tree.root ()[0].insert (2, { 42, 42 });
  tree.root ()[1].insert (1, { 42, 42 });
  tree.root ()[1].insert (2, { 42, 42 });
  tree.root ()[1].insert (3, { 42, 42 });
  tree.root ()[0][0].insert (1, { 42, 42 });

  auto results = std::vector<st_tree::tree<std::tuple<uint8_t, uint8_t>, st_tree::keyed<uint8_t> > >{};
  for (auto i = size_t{ 0 }; i < 1000000; i++)
    {
      results.push_back (tree);
    }
  std::cout << "depth: " << tree.root ().depth () << std::endl;
  std::cout << "subtree_size: " << tree.root ().subtree_size () << std::endl;
  return 0;
}

This creates 1 million trees and it costs around 2.5 gig of ram. So one tree is 2500 bytes. It prints:

depth: 4
subtree_size: 11

Why one tree needs 2500 bytes in this example? May you explain how to calculate the size of a tree? Why subtree size is 11 after 9 inserts?