From bc2fc50f5953d8d086c505febd837fc77f3cd61d Mon Sep 17 00:00:00 2001 From: Christian Bauer Date: Wed, 20 Aug 2003 22:01:35 +0000 Subject: [PATCH] added exams and timings for exhashmap<> --- check/Makefile.am | 20 +-- check/exam_hashmap.cpp | 293 +++++++++++++++++++++++++++++++++++++++++ check/exams.cpp | 1 + check/exams.h | 1 + check/exams.ref | 2 + check/time_hashmap.cpp | 110 ++++++++++++++++ check/times.cpp | 1 + check/times.h | 1 + check/times.ref | 2 + 9 files changed, 421 insertions(+), 10 deletions(-) create mode 100644 check/exam_hashmap.cpp create mode 100644 check/time_hashmap.cpp diff --git a/check/Makefile.am b/check/Makefile.am index 5e3d2d5a..48e7a999 100644 --- a/check/Makefile.am +++ b/check/Makefile.am @@ -9,19 +9,19 @@ checks_LDADD = ../ginac/libginac.la exams_SOURCES = exam_paranoia.cpp exam_numeric.cpp exam_powerlaws.cpp \ exam_inifcns.cpp exam_inifcns_nstdsums.cpp exam_inifcns_nstdsums.h \ - exam_differentiation.cpp \ - exam_polygcd.cpp exam_normalization.cpp exam_pseries.cpp exam_matrices.cpp \ - exam_lsolve.cpp exam_indexed.cpp exam_color.cpp exam_clifford.cpp \ - exam_archive.cpp exam_structure.cpp exam_misc.cpp exams.cpp exams.h + exam_differentiation.cpp exam_polygcd.cpp exam_normalization.cpp \ + exam_pseries.cpp exam_matrices.cpp exam_lsolve.cpp exam_indexed.cpp \ + exam_color.cpp exam_clifford.cpp exam_archive.cpp exam_structure.cpp \ + exam_hashmap.cpp exam_misc.cpp exams.cpp exams.h exams_LDADD = ../ginac/libginac.la times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp \ - time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp \ - time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp \ - time_lw_H.cpp time_lw_IJKL.cpp time_lw_M1.cpp time_lw_M2.cpp time_lw_N.cpp \ - time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp time_lw_Q.cpp \ - time_lw_Qprime.cpp time_antipode.cpp time_fateman_expand.cpp \ - timer.cpp timer.h times.cpp times.h + time_vandermonde.cpp time_toeplitz.cpp time_hashmap.cpp time_lw_A.cpp \ + time_lw_B.cpp time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp \ + time_lw_G.cpp time_lw_H.cpp time_lw_IJKL.cpp time_lw_M1.cpp time_lw_M2.cpp \ + time_lw_N.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp time_lw_Q.cpp \ + time_lw_Qprime.cpp time_antipode.cpp time_fateman_expand.cpp timer.cpp \ + timer.h times.cpp times.h times_LDADD = ../ginac/libginac.la INCLUDES = -I$(srcdir)/../ginac -I../ginac diff --git a/check/exam_hashmap.cpp b/check/exam_hashmap.cpp new file mode 100644 index 00000000..b360476b --- /dev/null +++ b/check/exam_hashmap.cpp @@ -0,0 +1,293 @@ +/** @file exam_hashmap.cpp + * + * Regression tests for the exhashmap<> container. */ + +/* + * GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "exams.h" + +unsigned exam_hashmap() +{ + unsigned result = 0; + unsigned N = 100; + + cout << "examining hash maps" << flush; + clog << "----------hash maps:" << endl; + + // Create empty container + exhashmap M1; + if (M1.size() != 0) { + clog << "Newly constructed container has size() != 0" << endl; + ++result; + } + if (!M1.empty()) { + clog << "Newly constructed container is not empty" << endl; + ++result; + } + + cout << '.' << flush; + + // Insert elements + for (unsigned i = 0; i < N; ++i) + M1.insert(make_pair(i, i)); + + if (M1.size() != N) { + clog << "After " << N << " insertions, size() returns " << M1.size() << " instead of " << N << endl; + ++result; + } + + for (unsigned i = 0; i < N; ++i) { + if (M1[i] != i) { + clog << "Lookup of key " << i << " in M1 didn't return correct value" << endl; + ++result; + break; + } + } + + if (M1.size() != N) { + clog << "After " << N << " lookups, size() returns " << M1.size() << " instead of " << N << endl; + ++result; + } + + cout << '.' << flush; + + // Test constructor from two iterators and operator== + exhashmap M2(M1.begin(), M1.end()); + if (M2.size() != M1.size()) { + clog << "Constructor from two iterators: size of destination container (" << M2.size() << ") not equal to size of source (" << M1.size() << ")" << endl; + ++result; + } + + for (unsigned i = 0; i < N; ++i) { + if (M2[i] != i) { + clog << "Lookup of key " << i << " in M2 didn't return correct value" << endl; + ++result; + break; + } + } + + if (M2 != M1) { + clog << "Copied container not equal to source" << endl; + ++result; + } + + cout << '.' << flush; + + // Test assignment operator + exhashmap M3; + M3 = M1; + if (M3.size() != N) { + clog << "Assignment operator: size of assigned container not equal to size of original" << endl; + ++result; + } + + for (unsigned i = 0; i < N; ++i) { + if (M3[i] != i) { + clog << "Lookup of key " << i << " in M3 didn't return correct value" << endl; + ++result; + break; + } + } + + cout << '.' << flush; + + // Test insert(it, it) + exhashmap M4; + M4.insert(M1.begin(), M1.end()); + + if (M4.size() != M1.size()) { + clog << "insert(it, it): size of destination container not equal to size of source" << endl; + ++result; + } + + for (unsigned i = 0; i < N; ++i) { + if (M4[i] != i) { + clog << "Lookup of key " << i << " in M4 didn't return correct value" << endl; + ++result; + break; + } + } + + cout << '.' << flush; + + // Test insert()/find() + symbol x("x"), y("y"); + exhashmap M5; + M5.insert(make_pair(x-2, 1)); + M5.insert(make_pair(sin(x+y), 2)); + M5.insert(make_pair(Pi, 3)); + M5.insert(make_pair(0, 4)); + M5.insert(make_pair(4*pow(x, y), 5)); + if (M5.size() != 5) { + clog << "After 5 insertions, size() returns " << M5.size() << " instead of 5" << endl; + ++result; + } + + exhashmap::const_iterator cit = M5.find(sin(x+y)); + if (cit == M5.end()) { + clog << "Lookup of sin(x+y) didn't find anything" << endl; + ++result; + } + if (!cit->first.is_equal(sin(x+y))) { + clog << "Lookup of sin(x+y) returned an incorrect iterator" << endl; + ++result; + } + if (cit->second != 2) { + clog << "Lookup of sin(x+y) returned wrong value" << endl; + ++result; + } + + cout << '.' << flush; + + // Test re-inserting insert() + pair::iterator, bool> pit = M5.insert(make_pair(sin(x+y), 42)); + if (pit.second) { + clog << "Reinsertion of sin(x+y) inserted a new value" << endl; + ++result; + } + if (!pit.first->first.is_equal(sin(x+y))) { + clog << "Reinsertion of sin(x+y) returned an incorrect iterator" << endl; + ++result; + } + if (pit.first->second != 2) { + clog << "Reinsertion of sin(x+y) changed the value" << endl; + ++result; + } + + cout << '.' << flush; + + // Test operator[] + unsigned v = M5[sin(x+y)]; + if (M5.size() != 5) { + clog << "operator[] with an existing key changed the container size" << endl; + ++result; + } + if (v != 2) { + clog << "operator[] with an existing key returned the wrong value" << endl; + ++result; + } + + v = M5[y+1]; + if (M5.size() != 6) { + clog << "operator[] with a new key didn't insert a new value" << endl; + ++result; + } + if (v != 0) { + clog << "operator[] with a new key returned the wrong value" << endl; + ++result; + } + + cout << '.' << flush; + + // Test erase() + exhashmap::iterator it = M5.find(y+1); + if (it == M5.end()) { + clog << "Key y+1 wasn't found" << endl; + ++result; + } + if (!it->first.is_equal(y+1)) { + clog << "find() returned an incorrect iterator" << endl; + ++result; + } + if (it->second != 0) { + clog << "find() returned an incorrect value" << endl; + +result; + } + + M5.erase(it); + if (M5.size() != 5) { + clog << "erase(it) didn't reduce the size of the container" << endl; + ++result; + } + + it = M5.find(y+1); + if (it != M5.end()) { + clog << "Key was still found after erase()" << endl; + ++result; + } + + exhashmap::size_type n = M5.erase(Pi); + if (n != 1) { + clog << "erase(Pi) returned " << n << " instead of 1" << endl; + ++result; + } + if (M5.size() != 4) { + clog << "erase(Pi) didn't reduce the size of the container" << endl; + ++result; + } + + n = M5.erase(42); + if (n != 0) { + clog << "erase(42) returned " << n << " instead of 0" << endl; + ++result; + } + if (M5.size() != 4) { + clog << "erase(42) reduced the size of the container" << endl; + ++result; + } + + cout << '.' << flush; + + // Test swap() + exhashmap M6; + M6.swap(M1); + if (M6.size() != N) { + clog << "After swap, size() returns " << M6.size() << " instead of " << N << endl; + ++result; + } + if (M1.size() != 0) { + clog << "After swap with empty container, size() returns " << M1.size() << " instead of 0" << endl; + ++result; + } + + cout << '.' << flush; + + // Test clear() + M2.clear(); + if (M2.size() != 0) { + clog << "Size of cleared container is " << M5.size() << " instead of 0" << endl; + ++result; + } + + cout << '.' << flush; + + // Test count() + n = M5.count(Pi); + if (n != 0) { + clog << "count(Pi) returns " << n << " instead of 0" << endl; + ++result; + } + + n = M5.count(4*pow(x, y)); + if (n != 1) { + clog << "count(4*x^y) returns " << n << " instead of 1" << endl; + ++result; + } + + cout << '.' << flush; + + if (!result) { + cout << " passed " << endl; + clog << "(no output)" << endl; + } else { + cout << " failed " << endl; + } + + return result; +} diff --git a/check/exams.cpp b/check/exams.cpp index ed8f814b..11c73200 100644 --- a/check/exams.cpp +++ b/check/exams.cpp @@ -52,6 +52,7 @@ try { \ EXAM(clifford) EXAM(archive) EXAM(structure) + EXAM(hashmap) EXAM(misc) if (result) { diff --git a/check/exams.h b/check/exams.h index 635ff0de..9de12385 100644 --- a/check/exams.h +++ b/check/exams.h @@ -45,6 +45,7 @@ unsigned exam_color(); unsigned exam_clifford(); unsigned exam_archive(); unsigned exam_structure(); +unsigned exam_hashmap(); unsigned exam_misc(); #endif // ndef EXAMS_H diff --git a/check/exams.ref b/check/exams.ref index e83d4091..016a9c2c 100644 --- a/check/exams.ref +++ b/check/exams.ref @@ -30,5 +30,7 @@ (no output) ----------structure template: (no output) +----------hash maps: +(no output) ----------miscellaneous other things: (no output) diff --git a/check/time_hashmap.cpp b/check/time_hashmap.cpp new file mode 100644 index 00000000..a72e4680 --- /dev/null +++ b/check/time_hashmap.cpp @@ -0,0 +1,110 @@ +/** @file time_hashmap.cpp + * + * Timings for exhashmap<> operations. */ + +/* + * GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "times.h" + +template +static void run_timing(unsigned size, double &time_insert, double &time_find, double &time_erase) +{ + vector S; + T M; + timer t; + + S.reserve(size); + for (unsigned i=0; i sizes(s, s+sizeof(s)/sizeof(*s)); + + vector times_insert, times_find, times_erase; + + for (vector::const_iterator i = sizes.begin(); i != sizes.end(); ++i) { + double time_insert, time_find, time_erase; + + run_timing< exhashmap >(*i, time_insert, time_find, time_erase); + +// If you like, you can compare it with this: +// run_timing< std::map >(*i, time_insert, time_find, time_erase); + + times_insert.push_back(time_insert); + times_find.push_back(time_find); + times_erase.push_back(time_erase); + cout << '.' << flush; + } + + if (!result) { + cout << " passed "; + clog << "(no output)" << endl; + } else { + cout << " failed "; + } + + // print the report: + cout << endl << " size:\t"; + copy(sizes.begin(), sizes.end(), ostream_iterator(cout, "\t")); + cout << endl << " insert/s:\t"; + copy(times_insert.begin(), times_insert.end(), ostream_iterator(cout, "\t")); + cout << endl << " find/s:\t"; + copy(times_find.begin(), times_find.end(), ostream_iterator(cout, "\t")); + cout << endl << " erase/s:\t"; + copy(times_erase.begin(), times_erase.end(), ostream_iterator(cout, "\t")); + cout << endl; + + return result; +} diff --git a/check/times.cpp b/check/times.cpp index e405403e..9ada2bf6 100644 --- a/check/times.cpp +++ b/check/times.cpp @@ -39,6 +39,7 @@ try { \ TIME(gammaseries) TIME(vandermonde) TIME(toeplitz) + TIME(hashmap) TIME(lw_A) TIME(lw_B) TIME(lw_C) diff --git a/check/times.h b/check/times.h index 85052de0..cd0645b5 100644 --- a/check/times.h +++ b/check/times.h @@ -39,6 +39,7 @@ unsigned time_dennyfliegner(); unsigned time_gammaseries(); unsigned time_vandermonde(); unsigned time_toeplitz(); +unsigned time_hashmap(); unsigned time_lw_A(); unsigned time_lw_B(); unsigned time_lw_C(); diff --git a/check/times.ref b/check/times.ref index d34c8fd3..e0530792 100644 --- a/check/times.ref +++ b/check/times.ref @@ -6,6 +6,8 @@ (no output) -------determinant of polyvariate symbolic Toeplitz matrices: (no output) +-------hash map operations: +(no output) -------Lewis-Wester test A (divide factorials): (no output) -------Lewis-Wester test B (sum of rational numbers): -- 2.49.0