N-sim v0.9.4

00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 
00036 #include "test.h"
00037 #include "avl.h"
00038 #include "comparable.h"
00039 
00040 
00041 class MyInteger : public Comparable<int> {
00042         const char *key_format_string() { return "%d"; };
00043 
00044  public:
00045         MyInteger() : Comparable<int>(0) {};
00046         MyInteger(int i) : Comparable<int>(i) {};
00047         MyInteger(Comparable<int> &c) : Comparable<int>(c.key_value()) {};
00048         ~MyInteger() {};
00049 };
00050 
00051 
00052 #define MULTIPLIER  1000
00053 #define TREE_SIZE   10
00054 #define ITERATIONS  1
00055 #define FINDS       2
00056 
00057 
00058 int main(int argc, char *argv[])
00059 {
00060         int i, j, error = 0;
00061         int tree_size, iterations, finds, multiplier = MULTIPLIER;
00062         unsigned int avg_ins, avg_list, avg_list_error, avg_ht;
00063         AVL_node<int> *list = 0;
00064 
00065         if (argc > 1)
00066                 multiplier = atoi(argv[1]);
00067         tree_size = TREE_SIZE * multiplier;
00068         iterations = ITERATIONS * multiplier;
00069         finds = FINDS * multiplier;
00070 
00071         struct timeval seed;
00072         struct timeval begin_ins[iterations], end_ins[iterations];
00073         struct timeval begin_list[iterations], end_list[iterations];
00074         struct timeval begin_find[iterations], end_find[iterations];
00075         struct timeval avg_ins_time, avg_list_time, avg_find_time;
00076 
00077         avg_ins = avg_list = avg_list_error = avg_ht = 0;
00078         gettimeofday(&seed, NULL);
00079         srand((int) (seed.tv_sec - seed.tv_usec));
00080 
00081         printf("\n");
00082         for (i = 0; i < iterations; i++) {
00083                 AVL_tree<int> tree;
00084                 MyInteger val;
00085 
00086                 list = 0;
00087                 error = 0;
00088                 gettimeofday(&begin_ins[i], NULL);
00089                 for (j = 0; j < tree_size; j++) {
00090                         MyInteger *comp = new MyInteger(
00091                                 (int) (((double)tree_size) * 
00092                                        ((double)rand() / RAND_MAX)));
00093                         int err = tree.insert_elt(comp);
00094                         if (err != 0) {
00095                                 delete comp;
00096                                 error++;
00097                         }
00098                 }
00099                 gettimeofday(&end_ins[i], NULL);
00100                 avg_ins += j - error;
00101                 avg_ht += tree.get_height();
00102 
00103 #if 0    /* enable for detailed debugging */
00104                 printf("  %d items created, %d in tree.\n", tree_size, 
00105                        tree_size - error);
00106                 tree.print();
00107                 tree.print_list();
00108 #endif
00109 
00110                 error = 0;
00111                 gettimeofday(&begin_list[i], NULL);
00112                 for (j = 0, list = tree.find_min(); 
00113                      list != NULL; list = list->get_next(), j++) {
00114                         Comparable<int> c = *list->elt();
00115                         if (val > c)
00116                                 error++;
00117                         val = c;
00118                 }
00119                 gettimeofday(&end_list[i], NULL);
00120                 avg_list += j;
00121                 avg_list_error += error;
00122 
00123                 error = 0;
00124                 gettimeofday(&begin_find[i], NULL);
00125                 for (j = 0; j < finds; j++) {
00126                         MyInteger num((int) (((double)tree_size) * 
00127                                            ((double)rand() / RAND_MAX)));
00128                         if (tree.find(num) == 0)
00129                                 error++;
00130                 }
00131                 gettimeofday(&end_find[i], NULL);
00132 
00133                 tree.burn();
00134         }
00135         avg_ins = avg_ins / iterations;
00136         avg_list = avg_list / iterations;
00137         avg_list_error = avg_list_error / iterations;
00138         avg_ht = avg_ht / iterations;
00139 
00140         avg_ins_time = average_time(begin_ins, end_ins, iterations);
00141         avg_list_time = average_time(begin_list, end_list, iterations);
00142         avg_find_time = average_time(begin_find, end_find, iterations);
00143 
00144         printf("  %d trees averaging a height of %d, with %d items "
00145                "in %ld secs, %ld usecs.\n",
00146                iterations, avg_ht, avg_ins, avg_ins_time.tv_sec, 
00147                avg_ins_time.tv_usec);
00148         printf("  Iteration over an average of %d items with %d errors "
00149                "in %ld secs, %ld usecs.\n", 
00150                avg_list, avg_list_error, avg_list_time.tv_sec, 
00151                avg_list_time.tv_usec);
00152         printf("  %d random finds in %ld secs, %ld usecs (%d misses).\n",
00153                finds, avg_find_time.tv_sec, avg_find_time.tv_usec, error);
00154 
00155         return 0;
00156 }
/home/brennan/n-sim/OrbisQuartus/shared/avl_test.cpp
