import time
import random
import numpy as np

# 데이터 크기 설정
data_size = 10_000_000

# NumPy 배열 생성
data_array = np.arange(data_size, dtype=np.int32)

# 순차 접근 함수
def sequential_access(data):
    total = 0
    for value in data:
        total += value
    return total

# 랜덤 인덱스 생성
random_indices = np.arange(data_size)
np.random.shuffle(random_indices)

# 랜덤 접근 함수
def random_access(data, indices):
    total = 0
    for idx in indices:
        total += data[idx]
    return total

# 순차 접근 시간 측정
start_time = time.time()
sequential_access(data_array)
seq_time = time.time() - start_time
print(f"순차 접근 시간: {seq_time:.6f}초")

# 순차 접근(per element) 시간 측정
per_element_time = seq_time / data_size
print(f"순차 접근(per element) 시간: {per_element_time*1_000_000_000:.6f}ns")

# 랜덤 접근 시간 측정
start_time = time.time()
random_access(data_array, random_indices)
rand_time = time.time() - start_time
print(f"랜덤 접근 시간: {rand_time:.6f}초")

# 랜덤 접근(per element) 시간 측정
per_element_time = rand_time / data_size
print(f"랜덤 접근(per element) 시간: {per_element_time*1_000_000_000:.6f}ns")

# 성능 비교
print(f"\n랜덤 접근은 순차 접근보다 {rand_time / seq_time:.2f}배 느립니다.")

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 순차 검색 함수
int sequential_search(int *data, int size, int target) {
    for (int idx = 0; idx < size; idx++) {
        if (data[idx] == target) {
            return idx;
        }
    }
    return -1;
}

// 이진 검색 함수
int binary_search(int *data, int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (data[mid] == target) {
            return mid;
        } else if (data[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 비교 함수 (qsort에 사용)
int compare_ints(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

int main() {
    int data_size = 1000000; // 백만 개의 요소
    int num_trials = 100;     // 반복 횟수 설정

    double total_seq_time = 0.0;
    double total_sort_time = 0.0;
    double total_bin_time = 0.0;

    // 난수 시드 설정
    srand((unsigned int)time(NULL));

    for (int trial = 0; trial < num_trials; trial++) {
        int *data = (int *)malloc(data_size * sizeof(int));
        if (data == NULL) {
            fprintf(stderr, "메모리 할당 실패\n");
            return 1;
        }

        // 데이터셋 생성 (랜덤 정수)
        for (int i = 0; i < data_size; i++) {
            data[i] = rand() % (data_size * 10);
        }

        // 검색할 값 설정 (데이터셋에 존재하는 값)
        int target_index = rand() % data_size;
        int target = data[target_index];

        // 순차 검색 시간 측정
        clock_t start_seq = clock();
        int index_seq = sequential_search(data, data_size, target);
        clock_t end_seq = clock();
        double time_seq = (double)(end_seq - start_seq) / CLOCKS_PER_SEC * 1000.0; // 밀리초 단위

        // 데이터 정렬 시간 측정
        clock_t start_sort = clock();
        qsort(data, data_size, sizeof(int), compare_ints);
        clock_t end_sort = clock();
        double time_sort = (double)(end_sort - start_sort) / CLOCKS_PER_SEC * 1000.0; // 밀리초 단위

        // 이진 검색 시간 측정
        clock_t start_bin = clock();
        int index_bin = binary_search(data, data_size, target);
        clock_t end_bin = clock();
        double time_bin = (double)(end_bin - start_bin) / CLOCKS_PER_SEC * 1000.0; // 밀리초 단위

        // 총 시간 누적
        total_seq_time += time_seq;
        total_sort_time += time_sort;
        total_bin_time += time_bin;

        // 메모리 해제
        free(data);
    }

    // 평균 시간 계산
    double avg_seq_time = total_seq_time / num_trials;
    double avg_sort_time = total_sort_time / num_trials;
    double avg_bin_time = total_bin_time / num_trials;
    double avg_total_bin_time = avg_sort_time + avg_bin_time;

    // 결과 출력
    printf("실행 횟수: %d회\n", num_trials);
    printf("순차 검색 평균 시간: %.6fms\n", avg_seq_time);
    printf("데이터 정렬 평균 시간: %.6fms\n", avg_sort_time);
    printf("이진 검색 평균 시간: %.6fms\n", avg_bin_time);
    printf("\n순차 검색 평균 총 시간: %.6fms\n", avg_seq_time);
    printf("정렬 + 이진 검색 평균 총 시간: %.6fms\n", avg_total_bin_time);

    if (avg_seq_time < avg_total_bin_time) {
        printf("\n순차 검색이 전체적으로 더 빠릅니다.\n");
    } else {
        printf("\n정렬 후 이진 검색이 전체적으로 더 빠릅니다.\n");
    }

    return 0;
}

CC = gcc
CFLAGS = -O2 -Wall
TARGET = test

all: $(TARGET)

$(TARGET): test.c
    $(CC) $(CFLAGS) -o $(TARGET) test.c

clean:
    rm -f $(TARGET)