[avida-cvs] avida CVS commits: /current/source/main genebank.cc genebank.hh
mercere99
avida-cvs at alife.org
Mon Oct 6 22:16:07 PDT 2003
mercere99 Mon Oct 6 14:16:07 2003 EDT
Modified files:
/avida/current/source/main genebank.cc genebank.hh
Log:
Fixed genebank hash tables to speed them up and generally improve
their functionality. This should help a lot with slowdowns do to
large numbers of genotypes.
-------------- next part --------------
Index: avida/current/source/main/genebank.cc
diff -u avida/current/source/main/genebank.cc:1.33 avida/current/source/main/genebank.cc:1.34
--- avida/current/source/main/genebank.cc:1.33 Thu Aug 7 20:24:19 2003
+++ avida/current/source/main/genebank.cc Mon Oct 6 14:16:06 2003
@@ -14,101 +14,13 @@
#include "config.hh"
#include "stats.hh"
+#include "../tools/tArray.hh"
#include "../cpu/test_util.hh"
using namespace std;
-/////////////////////
-// cGenotypeQueue
-/////////////////////
-
-cGenotypeQueue::cGenotypeQueue()
-{
- size = 0;
- root.SetNext(&root);
- root.SetPrev(&root);
-}
-
-
-cGenotypeQueue::~cGenotypeQueue()
-{
- while (root.GetNext() != &root) {
- Remove(root.GetNext());
- }
-}
-
-bool cGenotypeQueue::OK()
-{
- bool result = true;
- int count = 0;
-
- for (cGenotypeElement * temp_element = root.GetNext();
- temp_element != &root;
- temp_element = temp_element->GetNext()) {
- assert (temp_element->GetNext()->GetPrev() == temp_element);
- assert (temp_element->GetGenotype()->GetID() >= 0);
-
- count++;
- assert (count <= size);
- }
-
- assert (count == size);
-
- return result;
-}
-
-void cGenotypeQueue::Insert(cGenotype & in_genotype)
-{
- cGenotypeElement * new_element = new cGenotypeElement(&in_genotype);
- new_element->SetNext(root.GetNext());
- new_element->SetPrev(&root);
- root.GetNext()->SetPrev(new_element);
- root.SetNext(new_element);
- size++;
-}
-
-void cGenotypeQueue::Remove(cGenotype & in_genotype)
-{
- cGenotypeElement * cur_element;
-
- for (cur_element = root.GetNext();
- cur_element != &root;
- cur_element = cur_element->GetNext()) {
- if (cur_element->GetGenotype() == &in_genotype) break;
- }
-
- assert (cur_element != &root);
-
- Remove(cur_element);
-}
-
-void cGenotypeQueue::Remove(cGenotypeElement * in_element)
-{
- in_element->GetPrev()->SetNext(in_element->GetNext());
- in_element->GetNext()->SetPrev(in_element->GetPrev());
- in_element->SetNext(NULL);
- in_element->SetPrev(NULL);
- delete(in_element);
-
- size--;
-}
-
-cGenotype * cGenotypeQueue::Find(const cGenome & in_genome) const
-{
- for (cGenotypeElement * cur_element = root.GetNext();
- cur_element != &root;
- cur_element = cur_element->GetNext()) {
- if (cur_element->GetGenotype()->GetGenome() == in_genome) {
- return cur_element->GetGenotype();
- }
- }
-
- return NULL;
-}
-
-
///////////////////////
// cGenotypeControl
///////////////////////
@@ -720,6 +632,22 @@
filename, best_genotype, stats.GetUpdate());
}
}
+
+// tArray<int> hist_array(15);
+// hist_array.SetAll(0);
+// int total_gens = 0;
+
+// for (int i = 0; i < GENOTYPE_HASH_SIZE; i++) {
+// int cur_val = active_genotypes[i].GetSize();
+// total_gens += cur_val;
+// if (cur_val < 15) hist_array[cur_val]++;
+// else cout << cur_val << " ";
+// }
+// cout << endl;
+// for (int i = 0; i < 15; i++) {
+// cout << i << " : " << hist_array[i] << endl;
+// }
+// cout << "Total genotypes: " << total_gens << endl;
}
cString cGenebank::GetLabel(int in_size, int in_num)
@@ -740,14 +668,13 @@
}
-void cGenebank::AddGenotype(cGenotype * in_genotype, int in_list_num)
+void cGenebank::AddGenotype(cGenotype * in_genotype, int list_num)
{
assert( in_genotype != 0 );
- if ( in_list_num < 0 )
- in_list_num = FindCRC(in_genotype->GetGenome()) % GENOTYPE_HASH_SIZE;
+ if (list_num < 0) list_num = FindCRC(in_genotype->GetGenome());
- active_genotypes[in_list_num].Insert(*in_genotype);
+ active_genotypes[list_num].Push(in_genotype);
genotype_control->Insert(*in_genotype);
stats.AddGenotype(in_genotype->GetID());
@@ -767,42 +694,42 @@
cGenotype * cGenebank::AddGenotype(const cGenome & in_genome,
cGenotype * parent_genotype)
{
- int list_num = FindCRC(in_genome) % GENOTYPE_HASH_SIZE;
- cGenotype * found_genotype;
-
- found_genotype = active_genotypes[list_num].Find(in_genome);
+ int list_num = FindCRC(in_genome);
+ cGenotype * found_genotype = FindGenotype(in_genome, list_num);
if (!found_genotype) {
found_genotype = new cGenotype(stats.GetUpdate());
found_genotype->SetGenome(in_genome);
found_genotype->SetParent(parent_genotype);
- AddGenotype( found_genotype, list_num );
- /*
- active_genotypes[list_num].Insert(*found_genotype);
- genotype_control->Insert(*found_genotype);
- stats.AddGenotype(found_genotype->GetID());
-
- // Speciation... If we are creating a new genotype here, we must
- // initilize it to the species of its parent genotype.
-
- cSpecies * parent_species = NULL;
- if (parent_genotype != NULL) {
- parent_species = parent_genotype->GetSpecies();
- }
-
- found_genotype->SetSpecies(parent_species);
- if (parent_species != NULL) parent_species->AddGenotype();
- */
+ AddGenotype(found_genotype, list_num);
}
return found_genotype;
}
-cGenotype * cGenebank::FindGenotype(const cGenome & in_genome) const
+const cGenotype * cGenebank::FindGenotype(const cGenome & in_genome,
+ int list_num) const
+{
+ if (list_num < 0) list_num = FindCRC(in_genome);
+
+ tConstListIterator<cGenotype> list_it(active_genotypes[list_num]);
+ while (list_it.Next() != NULL) {
+ if (list_it.GetConst()->GetGenome() == in_genome) break;
+ }
+ return list_it.GetConst();
+}
+
+cGenotype * cGenebank::FindGenotype(const cGenome & in_genome,
+ int list_num)
{
- int list_num = FindCRC(in_genome) % GENOTYPE_HASH_SIZE;
- return active_genotypes[list_num].Find(in_genome);
+ if (list_num < 0) list_num = FindCRC(in_genome);
+
+ tListIterator<cGenotype> list_it(active_genotypes[list_num]);
+ while (list_it.Next() != NULL) {
+ if (list_it.Get()->GetGenome() == in_genome) break;
+ }
+ return list_it.Get();
}
void cGenebank::RemoveGenotype(cGenotype & in_genotype)
@@ -812,8 +739,8 @@
// assigned to it.
if (in_genotype.GetActive() == true) {
- int list_num = FindCRC(in_genotype.GetGenome()) % GENOTYPE_HASH_SIZE;
- active_genotypes[list_num].Remove(in_genotype);
+ int list_num = FindCRC(in_genotype.GetGenome());
+ active_genotypes[list_num].Remove(&in_genotype);
genotype_control->Remove(in_genotype);
in_genotype.Deactivate(stats.GetUpdate());
if (cConfig::GetTrackMainLineage()) {
@@ -1178,12 +1105,6 @@
#endif
- // Loop through all of the reference lists for matching genotypes...
-
- for (i = 0; i < GENOTYPE_HASH_SIZE; i++) {
- assert (active_genotypes[i].OK());
- }
-
assert (ret_value == true);
return ret_value;
@@ -1206,15 +1127,13 @@
unsigned int cGenebank::FindCRC(const cGenome & in_genome) const
{
- unsigned int total = 13;
- int i;
+ unsigned int total = 0;
- for (i = 0; i < in_genome.GetSize(); i++) {
- total *= in_genome[i].GetOp() + 10 + i << 6;
- total += 3;
+ for (int i = 0; i < in_genome.GetSize(); i++) {
+ total += (in_genome[i].GetOp() + 3) * i;
}
- return total;
+ return total % GENOTYPE_HASH_SIZE;
}
void cGenebank::SpeciesTest(char * message, cGenotype & genotype)
Index: avida/current/source/main/genebank.hh
diff -u avida/current/source/main/genebank.hh:1.21 avida/current/source/main/genebank.hh:1.22
--- avida/current/source/main/genebank.hh:1.21 Thu Jul 31 16:03:35 2003
+++ avida/current/source/main/genebank.hh Mon Oct 6 14:16:06 2003
@@ -9,6 +9,7 @@
#define GENEBANK_HH
#include "../tools/string.hh"
+#include "../tools/tList.hh"
#include "../defs.hh"
// porting to gcc 3.1 -- k
@@ -21,7 +22,7 @@
class cSpecies;
class cStats;
-#define GENOTYPE_HASH_SIZE 307 // @CAO Is this an optimal number?
+#define GENOTYPE_HASH_SIZE 3203 // @CAO Is this an optimal number?
#define SPECIES_HASH_SIZE 101
#define GENOTYPE_THREADS 2
@@ -29,42 +30,6 @@
#define SPECIES_RECORD_FULL 1
#define SPECIES_RECORD_LIMITED 2
-class cGenotypeElement {
-private:
- cGenotype * genotype;
- cGenotypeElement * next;
- cGenotypeElement * prev;
-public:
- inline cGenotypeElement(cGenotype * in_gen=NULL) : genotype(in_gen) {
- next = NULL; prev = NULL;
- }
- inline ~cGenotypeElement() { ; }
-
- inline cGenotype * GetGenotype() const { return genotype; }
- inline cGenotypeElement * GetNext() const { return next; }
- inline cGenotypeElement * GetPrev() const { return prev; }
-
- inline void SetNext(cGenotypeElement * in_next) { next = in_next; }
- inline void SetPrev(cGenotypeElement * in_prev) { prev = in_prev; }
-};
-
-class cGenotypeQueue {
-private:
- int size;
- cGenotypeElement root;
-
- void Remove(cGenotypeElement * in_element);
-public:
- cGenotypeQueue();
- ~cGenotypeQueue();
-
- bool OK();
-
- void Insert(cGenotype & in_genotype);
- void Remove(cGenotype & in_genotype);
- cGenotype * Find(const cGenome & in_genome) const;
-};
-
class cGenotypeControl {
private:
int size;
@@ -162,7 +127,7 @@
class cGenebank {
private:
unsigned int genotype_count[MAX_CREATURE_SIZE];
- cGenotypeQueue active_genotypes[GENOTYPE_HASH_SIZE];
+ tList<cGenotype> active_genotypes[GENOTYPE_HASH_SIZE];
cGenotypeControl * genotype_control;
cSpeciesControl * species_control;
cStats & stats;
@@ -183,10 +148,11 @@
* function AddGenotype(const cGenome & in_genome,
* cGenotype * parent_genotype = NULL), which then calls this one.
**/
- void AddGenotype(cGenotype *in_genotype, int in_list_num = -1 );
+ void AddGenotype(cGenotype *in_genotype, int list_num=-1);
cGenotype * AddGenotype(const cGenome & in_genome,
cGenotype * parent_genotype = NULL);
- cGenotype * FindGenotype(const cGenome & in_genome) const;
+ const cGenotype * FindGenotype(const cGenome & in_genome, int list_num=-1) const;
+ cGenotype * FindGenotype(const cGenome & in_genome, int list_num=-1);
void RemoveGenotype(cGenotype & in_genotype);
void ThresholdGenotype(cGenotype & in_genotype);
bool AdjustGenotype(cGenotype & in_genotype);
More information about the Avida-cvs
mailing list