lab01/task3_frequent_element.cpp - master - Konst_And/Labs_cpp

lab01/task3_frequent_element.cpp
206 строк6 KB
And Konst
update cpp files
05 мар 2026, 17:36
05 мар 2026, 17:36f68416c
#include <iostream>
#include <chrono>
#include <random>

using namespace std;
using namespace chrono;

// обычный линейный поиск
int lin(int* arr, int n, int key) {
    for (int i = 0; i < n; i++)
        if (arr[i] == key) return i;
    return -1;
}

// стратегия А
int stratA(int* arr, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            if (i > 0) {
                int t = arr[i];
                arr[i] = arr[0];
                arr[0] = t;
                return 0;
            }
            return i;
        }
    }
    return -1;
}

// стратегия В
int stratB(int* arr, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            if (i > 0) {
                int t = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = t;
                return i-1;
            }
            return i;
        }
    }
    return -1;
}

// стратегия С
int stratC(int* arr, int* cnt, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            cnt[i]++;
            if (i > 0 and cnt[i] > cnt[i-1]) {
                int t1 = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = t1;
                
                int t2 = cnt[i];
                cnt[i] = cnt[i-1];
                cnt[i-1] = t2;
                return i-1;
            }
            return i;
        }
    }
    return -1;
}

void zapoln(int* arr, int n) {
    int pop[] = {42, 777, 1234, 5678, 9999, 111, 222, 333, 444, 555};
    int m = 10;

    // заполняем 20% массива 10 элементами (pop = popular)
    for (int i = 0; i < n/5; i++) {
        arr[i] = pop[i % m];
    }
    
    // остальные 80% массива - рандомные числа
    for (int i = n/5; i < n; i++) {
        arr[i] = 10000 + i;
    }
    
    // перемешиваем элементы, чтобы частые были распределены по массиву
    for (int i = n-1; i > 0; i--) {
        int j = rand() % (i+1);
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

// замер времени
long long test(int* base, int n, int (*f)(int*, int, int), int it, bool ravnom) {
    int* a = new int[n];
    for (int i = 0; i < n; i++) a[i] = base[i];
    
    long long t = 0;
    int res = 0;
    
    for (int k = 0; k < it; k++) {
        int key;
        if (ravnom) {
            if (rand() % 10 < 9) key = a[rand() % n];
            else key = -k-100;
        } else {
            int r = rand() % 10;
            if (r < 8) {
                int pop[] = {42, 777, 1234, 5678, 9999, 111, 222, 333, 444, 555};
                key = pop[rand() % 10];
            } else if (r < 9) {
                key = 10000 + rand() % 100000;
            } else {
                key = -k-100;
            }
        }
        
        auto b = steady_clock::now();
        res += f(a, n, key);
        auto e = steady_clock::now();
        
        t += duration_cast<nanoseconds>(e - b).count();
    }
    
    if (res == -1) cout << ""; // чтобы не оптимизировал
    
    delete[] a;
    return t;
}

long long testC(int* base, int n, int it, bool ravnom) {
    int* a = new int[n];
    int* cnt = new int[n];
    for (int i = 0; i < n; i++) a[i] = base[i];
    
    long long t = 0;
    int res = 0;
    
    for (int k = 0; k < it; k++) {
        int key;
        if (ravnom) {
            if (rand() % 10 < 9) key = a[rand() % n];
            else key = -k-100;
        } else {
            int r = rand() % 10;
            if (r < 8) {
                int pop[] = {42, 777, 1234, 5678, 9999, 111, 222, 333, 444, 555};
                key = pop[rand() % 10];
            } else if (r < 9) {
                key = 10000 + rand() % 100000;
            } else {
                key = -k-100;
            }
        }
        
        auto b = steady_clock::now();
        res += stratC(a, cnt, n, key);
        auto e = steady_clock::now();
        
        t += duration_cast<nanoseconds>(e - b).count();
    }
    
    if (res == -1) cout << "";
    
    delete[] a;
    delete[] cnt;
    return t;
}

int main() {
    srand(12345);
    int sz[] = {100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000};
    int it = 10000;
    
    cout << "Равномерное распределение: лин. поиск, стратегия А, стратегия B, стратегия C\n";
    for (int i = 0; i < 9; i++) {
        int n = sz[i];
        int* arr = new int[n];
        zapoln(arr, n);
        
        long long t1 = test(arr, n, lin, it, 1);
        long long t2 = test(arr, n, stratA, it, 1);
        long long t3 = test(arr, n, stratB, it, 1);
        long long t4 = testC(arr, n, it, 1);
        
        cout << n << ": " << t1/1000 << " " << t2/1000 << " " << t3/1000 << " " << t4/1000 << "\n";
        
        delete[] arr;
    }
    
    cout << "Неравномерное распределение: лин. поиск, стратегия А, стратегия B, стратегия C\n";
    for (int i = 0; i < 9; i++) {
        int n = sz[i];
        int* arr = new int[n];
        zapoln(arr, n);
        
        long long t1 = test(arr, n, lin, it, 0);
        long long t2 = test(arr, n, stratA, it, 0);
        long long t3 = test(arr, n, stratB, it, 0);
        long long t4 = testC(arr, n, it, 0);
        
        cout << n << ": " << t1/1000 << " " << t2/1000 << " " << t3/1000 << " " << t4/1000 << "\n";
        
        delete[] arr;
    }
    
    return 0;
}