9
« on: December 12, 2009, 06:00:51 AM »
I haven't looked at the code in DB2 but by the looks of it (memory consumption, speed of speciation algorithm) mutations are stored as an array per bot. This results in n(bots)* m(mutations) as the big O
If mutations are stored in a tree of life structure this number goes down, and sifting through mutation info takes less space and goes faster. Worst case (no common ancestor of the bots) the number is up to (n+1)*m ((n+1) because for every series of mutations I want to store the number of individuals with those mutations.) The storage becomes increasingly efficient as more bots share al larger common ancestry. In addition to increased performance all sorts of nice graphs and stats can be made.
Definitions
branch: a series of mutations separated in time shared by a number of bots (n>=0, 0 meaning that the branch is now extinct)
node: endpoint of a branch. Branches may link at nodes, referring to an older branch
Every mutation either expands a branch or creates a new branch on a node.
The mutations a bot has inherited or accumulated can now be defined as a reference to the branch structure.
If a bot is born, the population count of the branches in the branch structure in increased. Similarly it is decreased if a bot dies.
Branches may be merged if the older and newer branch have the same population count. Branches where the population count has decreased to 0 may be pruned (deleted or stored off line)
With all that has been said about the first version not being optimised, I just would like to put it up here as an idea, to keep in mind, and hopefully not to put too much effort in work that would be erdone if this would be implemented.