Non-Linear-Data-Structures-Project/main.cpp at main · Aditya08p/Non-Linear-Data-Structures-Project · GitHub

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
// ===================== main.cpp =====================
#include <iostream>
#include <chrono>
#include <cstdlib>
#include "Dijkstra.h"
#include "KMPTrie.h"
#include "DisjointSet.h"
using namespace std;
int main() {
    while (true) {
        cout << "\nChoose an algorithm to run:\n";
        cout << "1. Dijkstra's Algorithm (Naive vs Optimized)\n";
        cout << "2. Pattern Search (Naive Trie vs KMP + Trie)\n";
        cout << "3. Union-Find (Naive vs Optimized)\n";
        cout << "4. Run All Comparisons\n";
        cout << "0. Exit\n";
        cout << "Enter choice: ";

        int choice;
        cin >> choice;
        if (choice == 0) break;

        if (choice == 1 || choice == 4) {
            cout << "\n[Running Dijkstra Comparison]\n";
            const int N = 1000;
            NaiveGraph ng(N);
            Graph og(N);
            for (int i = 0; i < N - 1; ++i) {
                int w = 1 + rand() % 10;
                ng.addEdge(i, i + 1, w);
                og.addEdge(i, i + 1, w);
            }
            for (int i = 0; i < 10000; ++i) {
                int u = rand() % N, v = rand() % N;
                if (u != v) {
                    int w = 1 + rand() % 10;
                    ng.addEdge(u, v, w);
                    og.addEdge(u, v, w);
                }
            }
            ng.dijkstra(0);
            og.dijkstra(0);
            auto start = chrono::high_resolution_clock::now();
            for (int i = 0; i < 10; ++i) ng.dijkstra(0);
            auto end = chrono::high_resolution_clock::now();
            auto t1 = chrono::duration_cast<chrono::milliseconds>(end - start).count();
            start = chrono::high_resolution_clock::now();
            for (int i = 0; i < 10; ++i) og.dijkstra(0);
            end = chrono::high_resolution_clock::now();
            auto t2 = chrono::duration_cast<chrono::milliseconds>(end - start).count();
            cout << "Naive:      (avg over 10 runs): " << t1 / 10.0 << " ms\n";
            cout << "Optimized:  (avg over 10 runs): " << t2 / 10.0 << " ms\n";
        }

        if (choice == 2 || choice == 4) {
            cout << "\n[Running Pattern Search Comparison]\n";
            string text(10000, 'a');
            for (int i = 1000; i < 1100; ++i) text[i] = "catbatrat"[rand() % 9];
            vector<string> words = {"cat", "bat", "rat", "aaa", "aab"};
            NaiveTrie nt;
            KMPTrie kt;
            for (const auto& w : words) {
                nt.insert(w);
                kt.insert(w);
            }
            nt.searchInText(text);
            kt.searchInText(text);
            auto start = chrono::high_resolution_clock::now();
            for (int i = 0; i < 100; ++i) nt.searchInText(text);
            auto end = chrono::high_resolution_clock::now();
            auto t1 = chrono::duration_cast<chrono::milliseconds>(end - start).count();
            start = chrono::high_resolution_clock::now();
            for (int i = 0; i < 100; ++i) kt.searchInText(text);
            end = chrono::high_resolution_clock::now();
            auto t2 = chrono::duration_cast<chrono::milliseconds>(end - start).count();
            cout << "Naive:      (avg over 100 runs): " << t1 / 100.0 << " ms\n";
            cout << "Optimized:  (avg over 100 runs): " << t2 / 100.0 << " ms\n";
        }

        if (choice == 3 || choice == 4) {
            cout << "\n[Running Union-Find Comparison]\n";
            const int N = 1000;
            NaiveDisjointSet nds(N);
            DisjointSet ds(N);
            vector<pair<int, int>> ops;
            for (int i = 0; i < 10000; ++i) {
                int u = rand() % N, v = rand() % N;
                if (u != v) ops.emplace_back(u, v);
            }
            auto start = chrono::high_resolution_clock::now();
            for (const auto& p : ops) nds.unite(p.first, p.second);
            for (int i = 0; i < N; ++i) nds.find(i);
            auto end = chrono::high_resolution_clock::now();
            auto t1 = chrono::duration_cast<chrono::microseconds>(end - start).count();
            start = chrono::high_resolution_clock::now();
            for (const auto& p : ops) ds.unite(p.first, p.second);
            for (int i = 0; i < N; ++i) ds.find(i);
            end = chrono::high_resolution_clock::now();
            auto t2 = chrono::duration_cast<chrono::microseconds>(end - start).count();
            cout << "Naive:      (total): " << t1 / 1000.0 << " ms\n";
            cout << "Optimized:  (total): " << t2 / 1000.0 << " ms\n";
        }
    }
    return 0;
}