+/EE312

software design

git clone https://git.julia.blue/+/EE312

Joseph RyanProject 57bf8175

master
15.1 KiB542 linesraw
1#include <stdio.h>
2#include <stdint.h>
3#include <stdlib.h>
4#include <assert.h>
5#include <chrono>
6#include <time.h>
7#include "Set.h"
8
9unsigned time();
10int const number_of_tests = 1000;
11int const maximum_set_size = 100;
12
13void randomSet(Set* s);
14void visualTests(void);
15void equalityTests(void);
16void specialCaseTests(void);
17void relationalTests(void);
18void algebraicTests(void);
19void testTime(void);
20
21int main (void) {
22    visualTests();
23    equalityTests();
24    specialCaseTests();
25    relationalTests();
26    algebraicTests();
27    testTime();
28    printf("The tests are over\n");
29    return 0;
30}
31
32void randomSet(Set* s) {
33    Set t;
34    int n = rand() % maximum_set_size + 1;
35    int i;
36
37    createEmptySet(&t);
38    for (i = 0; i < n; i += 1) {
39        insertSet(&t, rand() % maximum_set_size);
40    }
41    assignSet(s, &t);
42    destroySet(&t);
43}
44
45void showOutput(const char* str, Set* set) {
46    printf("%s", str);
47    displaySet(set);
48    printf("\n");
49}
50
51void visualTests() {
52    Set s;
53    Set t;
54    int i;
55    createEmptySet(&s);
56    showOutput("The set constructed with the default constructor: ", &s);
57
58    for (i = 0; i < 10; i += 1) {
59        insertSet(&s, i);
60    }
61    showOutput("The set should be {0, ..., 9}:  ", &s);
62
63    // test Insert() and Contains() with '<<'
64    for (i = 0; i < 10; i += 1) {
65        insertSet(&s, i);
66    }
67    showOutput("The set should be {0, ..., 9}:  ", &s);
68
69    createCopySet(&t, &s);
70    showOutput("The copy of s constructed with the copy constructor = ", &t);
71
72    randomSet(&t);
73    showOutput("The random set generated equals = ", &t);
74
75    printf("The visual tests are over\n");
76    destroySet(&s);
77    destroySet(&t);
78}
79
80void equalityTests(void) {
81    int i;
82    for (i = 0; i < number_of_tests; i += 1) {
83        Set s;
84        Set t;
85
86        createEmptySet(&s);
87        randomSet(&s);
88        createCopySet(&t, &s);
89        assert(isEqualToSet(&t, &s));
90        assert(isEqualToSet(&s, &t));
91        insertSet(&t, maximum_set_size);
92        assert(! isEqualToSet(&s, &t));
93        assert(! isEqualToSet(&t, &s));
94        randomSet(&t);
95        assert(! isEqualToSet(&t, &s));
96        destroySet(&s);
97        destroySet(&t);
98    }       // This test could fail with small probability
99    printf("The equality tests have been passed\n");
100}
101
102typedef void (*setFun)(Set*, const Set*);
103void checkCase(setFun fun, Set* s1, Set* s2, Set* expect) {
104    Set res;
105    createCopySet(&res, s1);
106    (*fun)(&res, s2);
107    assert(isEqualToSet(&res, expect));
108    destroySet(&res);
109}
110
111void specialCaseTests(void) {
112    Set empty;
113    Set universal;
114    int i;
115    Set s;
116    Set r;
117
118    createEmptySet(&empty);
119    createEmptySet(&universal);
120    createEmptySet(&r);
121    for (i = 0; i < maximum_set_size; i += 1) {
122        insertSet(&universal, i);
123    }
124    checkCase(&subtractFromSet, &universal, &universal, &empty);
125    checkCase(&unionInSet, &universal, &universal, &universal);
126    checkCase(&intersectFromSet, &universal, &universal, &universal);
127    checkCase(&intersectFromSet, &universal, &empty, &empty);
128    checkCase(&intersectFromSet, &empty, &universal, &empty);
129    checkCase(&unionInSet, &universal, &empty, &universal);
130    checkCase(&unionInSet, &empty, &universal, &universal);
131    checkCase(&unionInSet, &empty, &empty, &empty);
132    checkCase(&subtractFromSet, &empty, &empty, &empty);
133    checkCase(&intersectFromSet, &empty, &empty, &empty);
134
135    createEmptySet(&s);
136    assert(isEmptySet(&s));
137    for (i = 0; i < 10; i += 1) {
138        insertSet(&s, i);
139    }
140    assert(s.len == 10);
141    for (i = 0; i < 10; i += 1) {
142        assert(isMemberSet(&s, i));
143    }
144    for (i = 0; i < 10; i += 1) {
145        removeSet(&s, i);
146        removeSet(&s, i);
147        assert(s.len == 9 - i);
148    }
149    assert(isEmptySet(&s));
150    for (i = 0; i < number_of_tests; i += 1) {
151        randomSet(&s);
152        assert(isSubsetOf(&empty, &s));
153        assert(!isSubsetOf(&s, &empty));
154        assert(isSubsetOf(&s, &universal));
155        assert(!isSubsetOf(&universal, &s));
156
157        checkCase(&intersectFromSet, &empty, &s, &empty);
158        checkCase(&intersectFromSet, &s, &empty, &empty);
159        checkCase(&intersectFromSet, &universal, &s, &s);
160        checkCase(&intersectFromSet, &s, &universal, &s);
161
162        checkCase(&unionInSet, &universal, &s, &universal);
163
164        checkCase(&unionInSet, &s, &universal, &universal);
165
166        checkCase(&subtractFromSet, &s, &empty, &s);
167
168        assignSet(&r, &universal);
169        subtractFromSet(&r, &s); // r = u - s;
170        checkCase(&subtractFromSet, &universal, &r, &s); // (u - (u - s) == s)
171        checkCase(&unionInSet, &s, &r, &universal); // s + (u - s) == u
172        checkCase(&unionInSet, &r, &s, &universal); // (u - s) + s == u
173    }
174    printf("The special case tests have been passed\n");
175    destroySet(&empty);
176    destroySet(&universal);
177    destroySet(&s);
178    destroySet(&r);
179}
180
181void relationalTests() {
182    Set s;
183    Set t;
184    int i;
185
186    createEmptySet(&s);
187    createEmptySet(&t);
188    for (i = 0; i < number_of_tests; i += 1) {
189        randomSet(&s);
190        assignSet(&t, &s);
191        assert(isSubsetOf(&s, &t));
192        assert(isSubsetOf(&t, &s));
193        assert(isEqualToSet(&s, &t));
194        assert(isEqualToSet(&t, &s));
195        insertSet(&s, rand() % maximum_set_size + maximum_set_size);
196        assert(isSubsetOf(&t, &s));
197        assert(! isSubsetOf(&s, &t));
198    }
199    printf("The relational tests have been passed\n");
200    destroySet(&s);
201    destroySet(&t);
202}
203
204void algebraicTests(void) {
205    Set empty;
206    Set universal;
207    int i;
208    Set s;
209    Set t;
210    Set u;
211    Set v;
212    Set w;
213
214    createEmptySet(&empty);
215    createEmptySet(&universal);
216    for (i = 0; i < maximum_set_size; i += 1) {
217        insertSet(&universal, i);
218    }
219
220    createEmptySet(&s);
221    createEmptySet(&t);
222    createEmptySet(&u);
223    createEmptySet(&v);
224    createEmptySet(&w);
225
226    for (i = 0; i < number_of_tests; i += 1) {
227        randomSet(&u);
228        randomSet(&v);
229        randomSet(&w);
230
231        /* u + v == v + u */
232        assignSet(&s, &u);
233        unionInSet(&s, &v);
234        assignSet(&t, &v);
235        unionInSet(&t, &u);
236        assert(isEqualToSet(&s, &t));
237
238        /* u + (v + w) == (u + v) + w */
239        assignSet(&t, &v);
240        unionInSet(&t, &w);
241        assignSet(&s, &u);
242        unionInSet(&s, &t);
243        assignSet(&t, &u);
244        unionInSet(&t, &v);
245        unionInSet(&t, &w);
246        assert(isEqualToSet(&s, &t));
247
248        /* u * v == v * u */
249        assignSet(&s, &u);
250        intersectFromSet(&s, &v);
251        assignSet(&t, &v);
252        intersectFromSet(&t, &u);
253        assert(isEqualToSet(&s, &t));
254
255        /* u * (v * w) == (u * v) * w */
256        assignSet(&t, &v);
257        intersectFromSet(&t, &w);
258        assignSet(&s, &u);
259        intersectFromSet(&s, &t);
260        assignSet(&t, &u);
261        intersectFromSet(&t, &v);
262        intersectFromSet(&t, &w);
263        assert(isEqualToSet(&s, &t));
264
265        /* u - v == u - (u * v) */
266        assignSet(&s, &u);
267        intersectFromSet(&s, &v);
268        assignSet(&t, &u);
269        subtractFromSet(&t, &s);
270        assignSet(&s, &u);
271        subtractFromSet(&s, &v);
272        assert(isEqualToSet(&s, &t));
273
274        /* additional tests, not implemented
275           assert(w * (u - v) == w * u - w * v);
276           assert(u * (v + w) == (u * v) + (u * w));
277           assert(universal - (u * v) == (universal - u) + (universal - v));
278           assert(universal - (u + v) == (universal - u) * (universal - v));
279           */
280    }
281    printf("The algebraic tests have been passed\n");
282    destroySet(&empty);
283    destroySet(&universal);
284    destroySet(&s);
285    destroySet(&t);
286    destroySet(&u);
287    destroySet(&v);
288    destroySet(&w);
289}
290
291/*
292 * create two sets with n random elements
293 * the sets should have 50% of the elements in common
294 */
295void createRandomSetN(int n, Set* a, Set* b) {
296    int x;
297    int last_size = 0;
298    createEmptySet(a);
299    while (a->len < n) {
300//        printf("doing stuff %d\n", last_size);
301        if (a->len != last_size) {
302            last_size = a->len;
303            if (last_size % 1000 == 0) {
304                printf("%d..", last_size);
305                fflush(stdout);
306            }
307        }
308        x = 2 * (5 * n - (rand() % (10 * n)));
309        if (isMemberSet(a, x)) {
310            continue;    // try another number
311        }
312        /* a will have only even elements */
313        insertSet(a, x);
314        if ((rand() % 2) == 0) {
315            insertSet(b, x);
316        } else {
317            insertSet(b, x + 1); // an odd value, can't be in a
318        }
319    }
320    assert(a->len == b->len);
321}
322
323typedef void (*Function)(void);
324
325double timeFunction(Function f) {
326    int reps = 128;
327    uint64_t time = 0;
328    volatile int k;
329    while (time < 6000) {
330        if (reps > 1000000000) {
331            return 0.0;    // overflow?
332        }
333        auto start = std::chrono::high_resolution_clock::now();
334        for (k = 0; k < reps; k += 1) {
335            f();
336        }
337        auto end = std::chrono::high_resolution_clock::now();
338        time = std::chrono::duration_cast<std::chrono::milliseconds>
339               (end - start).count();
340        reps *= 2;
341    }
342
343    return ((double) time) / reps;
344}
345
346volatile int
347bogus_value; // used to ensure compiler does not optimize away our func calls
348
349Set* setA;
350Set* setB;
351Set* setAPrime; // almost exactly the same as A
352
353int is_mem_x;
354void isMemberTimeFun(void) {
355    if (isMemberSet(setA, is_mem_x)) {
356        is_mem_x ^= 1;
357        is_mem_x <<= 1;
358    } else {
359        is_mem_x >>= 1;
360        is_mem_x ^= 2;
361    }
362}
363
364void isEqualTimeFun(void) {
365    bogus_value = isEqualToSet(setA, setAPrime);
366}
367
368void isSubsetTimeFun(void) {
369    bogus_value = isSubsetOf(setA, setAPrime);
370}
371
372void unionTimeFun(void) {
373    Set t;
374    createCopySet(&t, setA);
375    unionInSet(&t, setB);
376    destroySet(&t);
377}
378
379void intersectTimeFun(void) {
380    Set t;
381    createCopySet(&t, setA);
382    intersectFromSet(&t, setB);
383    destroySet(&t);
384}
385
386void subtractTimeFun(void) {
387    Set t;
388    createCopySet(&t, setA);
389    subtractFromSet(&t, setB);
390    destroySet(&t);
391}
392
393bool checkLinear(double times[], int sizes[], int first, int last) {
394    double time_ratio = times[last] / times[first];
395    double size_ratio = sizes[last] / sizes[first];
396
397    if (time_ratio < size_ratio * 1.25) {
398        return true;
399    } else {
400        return false;
401    }
402}
403
404bool checkSubLinear(double times[], int sizes[], int first, int last) {
405    double time_ratio = times[last] / times[first];
406    double size_ratio = sizes[last] / sizes[first];
407
408    if (time_ratio < size_ratio * 0.5) {
409        return true;
410    } else {
411        return false;
412    }
413}
414
415enum Tests {
416    IS_MEMBER = 0,
417    INSERT = 1,
418    REMOVE = 2,
419    IS_EQUAL_TO = 3,
420    IS_SUBSET_OF = 4,
421    UNION_IN = 5,
422    INTERSECT_FROM = 6,
423    SUBTRACT_FROM = 7,
424
425    NUM_TESTS /* MUST BE LAST */
426};
427
428typedef enum Scales {
429    SUB_LINEAR,
430    LINEAR,
431    SUPER_LINEAR
432} Scales;
433/* NOTE: the order of these strings MUST MATCH EXACTLY the order of the Scales enum */
434const char* scaling_strings[] = {
435    "sub linear (YAHOO!)",
436    "linear",
437    "super linear, yuck."
438};
439
440int sizes[] = { 100, 400, 1600, 6400, 25600 };
441//const unsigned num_times = sizeof(sizes) / sizeof(int);
442#define num_times (sizeof(sizes) / sizeof(int))
443Set setsA[num_times];
444Set setsAPrime[num_times];
445Set setsB[num_times];
446double times[num_times];
447
448Scales determineScaling(Function fun) {
449    bool linear;
450    bool sublinear;
451
452    unsigned trial = 0;
453    for (; trial < num_times; trial += 1) {
454        if (trial > 0 && ((times[trial - 1] * sizes[trial])	> 10)) {
455            break;
456        }
457        setA = &setsA[trial];
458        setB = &setsB[trial];
459        setAPrime = &setsAPrime[trial];
460        times[trial] = timeFunction(fun);
461        printf("time taken for size %d was %g\n",
462               sizes[trial], times[trial]);
463    }
464
465    if (trial < 3) {
466        printf("I'm sorry, your program is way too inefficient.\n");
467        printf("you'll need to find a way-faster computer to test it on\n");
468        return SUPER_LINEAR;
469    }
470    linear = checkLinear(times, sizes, 0, trial - 1)
471             || checkLinear(times, sizes, 1, trial - 1);
472    sublinear = checkSubLinear(times, sizes, 0, trial - 1)
473                || checkSubLinear(times, sizes, 1, trial - 1);
474
475    if (sublinear) {
476        return SUB_LINEAR;
477    } else if (linear) {
478        return LINEAR;
479    } else {
480        return SUPER_LINEAR;
481    }
482}
483
484void testTime(void) {
485    Scales behavior[NUM_TESTS];
486
487    for (uint32_t k = 0; k < num_times; k += 1) {
488        printf("creating a random set with %d elements...", sizes[k]);
489        fflush(stdout);
490        createRandomSetN(sizes[k], &setsA[k], &setsB[k]);
491        printf("done creating\n");
492        int x = 10 * sizes[k];
493        createCopySet(&setsAPrime[k], &setsA[k]);
494        insertSet(&setsA[k], x);
495        insertSet(&setsAPrime[k], x + 1);
496        insertSet(&setsB[k], x);
497        printf("done\n");
498    }
499
500    printf("checking scaling of isMember\n");
501    behavior[IS_MEMBER] = determineScaling(&isMemberTimeFun);
502    printf("isMember's scaling appears to be: %s\n",
503           scaling_strings[behavior[IS_MEMBER]]);
504
505    printf("checking scaling of isEqualTo\n");
506    behavior[IS_EQUAL_TO] = determineScaling(&isEqualTimeFun);
507    printf("isEqualTo's scaling appears to be: %s\n",
508           scaling_strings[behavior[IS_EQUAL_TO]]);
509
510    printf("checking scaling of isSubsetOf\n");
511    behavior[IS_SUBSET_OF] = determineScaling(&isSubsetTimeFun);
512    printf("isSubsetOf's scaling appears to be: %s\n",
513           scaling_strings[behavior[IS_SUBSET_OF]]);
514
515    printf("checking scaling of unionIn\n");
516    behavior[UNION_IN] = determineScaling(&unionTimeFun);
517    printf("unionIn's scaling appears to be: %s\n",
518           scaling_strings[behavior[UNION_IN]]);
519
520    printf("checking scaling of intersectFrom\n");
521    behavior[INTERSECT_FROM] = determineScaling(&intersectTimeFun);
522    printf("intersectFrom's scaling appears to be: %s\n",
523           scaling_strings[behavior[INTERSECT_FROM]]);
524
525    printf("checking scaling of subtractFrom\n");
526    behavior[SUBTRACT_FROM] = determineScaling(&subtractTimeFun);
527    printf("subtractFrom's scaling appears to be: %s\n",
528           scaling_strings[behavior[SUBTRACT_FROM]]);
529
530    printf("Performance Summary:\n");
531    printf("isMemberSet\t\t%s\n", scaling_strings[behavior[IS_MEMBER]]);
532    printf("isEqualToSet\t\t%s\n", scaling_strings[behavior[IS_EQUAL_TO]]);
533    printf("isSubsetOf\t\t%s\n", scaling_strings[behavior[IS_SUBSET_OF]]);
534    printf("unionInSet\t\t%s\n", scaling_strings[behavior[UNION_IN]]);
535    printf("intersectFromSet\t%s\n", scaling_strings[behavior[INTERSECT_FROM]]);
536    printf("subtractFromSet\t\t%s\n", scaling_strings[behavior[SUBTRACT_FROM]]);
537    for (int i = 0; i < num_times; i++) {
538        destroySet(&setsA[i]);
539        destroySet(&setsAPrime[i]);
540        destroySet(&setsB[i]);
541    }
542}