-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtests.h
105 lines (85 loc) · 6.84 KB
/
tests.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//
// tests.h
// SubmatrixQueries
//
// Created by Raphael Bost on 08/02/13.
// Copyright (c) 2013 Raphael Bost. All rights reserved.
//
#ifndef __SubmatrixQueries__tests__
#define __SubmatrixQueries__tests__
#include <iostream>
#include "matrix.h"
#include "range.h"
#include "envelope_tree.h"
using namespace matrix;
#ifdef __MACH__
typedef clock_t bench_time_t;
#else
typedef timespec bench_time_t;
#endif
double benchTimeAsMiliSeconds(bench_time_t t);
/*
* class SubmatrixQueriesTest
*
* This is a simple class to test the data structures we built on big matrices.
* Naive maximum search functions are provided and their results are compared
* to the ones returned by our data structures.
*
* We also provide a function to generate inverse Monge matrices.
*/
class SubmatrixQueriesTest {
const Matrix<double> *_testMatrix;
SubmatrixQueriesDataStructure<double> *_queryDS;
public:
SubmatrixQueriesTest(Matrix<double> *m);
SubmatrixQueriesTest(size_t rows, size_t cols);
~SubmatrixQueriesTest();
static bool benchmarkNaiveQueries;
static bool showProgressBar;
static bool verboseBenchmarks;
static bool verboseMatrixGeneration;
bool testColumnQuery(Range rowRange, size_t col, bench_time_t *naiveTime, bench_time_t *queryTime);
bool testColumnQuery(bench_time_t *naiveTime, bench_time_t *queryTime);
bool testCascadingColQuery(Range rowRange, size_t col, bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
bool testCascadingColQuery(bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
bool testRowQuery(Range colRange, size_t row, bench_time_t *naiveTime, bench_time_t *queryTime);
bool testRowQuery(bench_time_t *naiveTime, bench_time_t *queryTime);
bool testCascadingRowQuery(Range colRange, size_t row, bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
bool testCascadingRowQuery(bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
bool testSubmatrixQuery(Range rowRange, Range colRange, bench_time_t *naiveTime, bench_time_t *explicitNodesTime, bench_time_t *implicitNodesTime);
bool testSubmatrixQuery(bench_time_t *naiveTime, bench_time_t *explicitNodesTime, bench_time_t *implicitNodesTime);
static void multiBenchmarksPositionQueries(size_t maxNRows, size_t maxNCols, size_t nSamples, bench_time_t *naiveTime, bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
static bench_time_t** multiSizeBenchmarksPositionQueries(size_t maxNRows, size_t maxNCols, size_t nSampleSize, size_t nSamplePerSize);
static void multiBenchmarksSubmatrixQueries(size_t nRows, size_t nCols, size_t nSamples, bench_time_t *naiveTime, bench_time_t *explicitNodesTime, bench_time_t *implicitNodesTime);
static bench_time_t** multiSizeBenchmarksSubmatrixQueries(size_t maxNRows, size_t maxNCols, size_t minNRows, size_t minNCols, size_t stepSize, size_t nSamplePerSize, size_t *sampleSize);
static void multiSizeBenchmarksSubmatrixQueries(size_t maxNRows, size_t maxNCols, size_t stepSize, size_t nSamplePerSize, ostream &outputStream);
static void multiSizeBenchmarksSubmatrixQueries(size_t maxNRows, size_t maxNCols, size_t minNRows, size_t minNCols, size_t stepSize, size_t nSamplePerSize, ostream &outputStream);
void multipleBenchmarksAllQueries(size_t nPosition,bench_time_t *positionNaiveTime, bench_time_t *positionExplicitNodesTime, bench_time_t *positionImplicitNodesTime, bench_time_t *positionSimpleCascadingTime,size_t nSubmatrix,bench_time_t *submatrixNaiveTime, bench_time_t *submatrixExplicitNodesTime, bench_time_t *submatrixImplicitNodesTime);
static void multiBenchmarksAllQueries(size_t nRows, size_t nCols, size_t nSamples,bench_time_t *positionNaiveTime, bench_time_t *positionExplicitNodesTime, bench_time_t *positionImplicitNodesTime, bench_time_t *positionSimpleCascadingTime,bench_time_t *submatrixNaiveTime, bench_time_t *submatrixExplicitNodesTime, bench_time_t *submatrixImplicitNodesTime);
static void multiSizeBenchmarksAllQueries(size_t maxNRows, size_t maxNCols, size_t stepSize, size_t nSamplePerSize, ostream &outputStream);
static void multiSizeBenchmarksAllQueries(size_t maxNRows, size_t maxNCols, size_t minNRows, size_t minNCols, size_t stepSize, size_t nSamplePerSize, ostream &outputStream);
void multipleBestPositionAndSubmatrixQueries(size_t nSMQueries, size_t nPosQueries,bench_time_t *positionQueryTime, bench_time_t *submatrixQueryTime);
static void multipleBenchmarkBestPositionAndSubmatrixQueries(size_t nRows, size_t nCols, size_t nSamples, size_t nSMQueries, size_t nPosQueries,bench_time_t *positionQueryTime, bench_time_t *submatrixQueryTime);
static void multiSizeBenchmarkBestPositionAndSubmatrixQueries(size_t maxNRows, size_t maxNCols, size_t minNRows, size_t minNCols, size_t stepSize, size_t nSamplePerSize, size_t nSMQueries, size_t nPosQueries, ostream &outputStream);
static void envelopeSizesForMongeMatrices(size_t nRows, size_t nCols, size_t nSamples, float *rowEnvelopes, float *colEnvelopes, size_t *maxRowSize,size_t *maxColSize);
static void envelopeSizesStats(size_t maxN, size_t minN, size_t stepSize, bool logSteps, size_t nSamplePerSize, ostream &outputStream);
bool multipleColumnQueryTest(size_t n);
bool multipleRowQueryTest(size_t n);
bool multipleSubmatrixQueryTest(size_t n);
bool multipleRowQueryTestVsCascading(size_t n);
bool multipleColQueryTestVsCascading(size_t n);
void multipleBenchmarksRowQueries(size_t n);
void multipleBenchmarksRowQueries(size_t n, bench_time_t *naiveTime, bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
void multipleBenchmarksColQueries(size_t n);
void multipleBenchmarksColQueries(size_t n, bench_time_t *naiveTime, bench_time_t *queryTime, bench_time_t *cascadingTime, bench_time_t *simpleCascadingTime);
void multipleBenchmarksSubmatrixQueries(size_t n);
void multipleBenchmarksSubmatrixQueries(size_t n,bench_time_t *naiveTime, bench_time_t *explicitNodesTime, bench_time_t *implicitNodesTime);
static double naiveMaximumInColumn(const Matrix<double> *m, Range rowRange, size_t col);
static double naiveMaximumInRow(const Matrix<double> *m, Range colRange, size_t row);
static double naiveMaximumInSubmatrix(const Matrix<double> *m, Range rowRange, Range colRange);
static Matrix<double>* generateInverseMongeMatrixStrip1(size_t rows, size_t cols);
static Matrix<double>* generateInverseMongeMatrixStrip2(size_t rows, size_t cols);
static Matrix<double>* generateInverseMongeMatrixSlope(size_t rows, size_t cols);
static Matrix<double>* generateInverseMongeMatrixSlopeMultithread(size_t rows, size_t cols,size_t threadCount);
};
#endif /* defined(__SubmatrixQueries__tests__) */