인생의 쾌를 찾는 고찰족/충만족: Week02 - Rust 예제 코드 분석 (Prime)

이번에 분석할 코드는 특정 범위에서 조건에 맞는 prime(소수)를 검출하는 코드이다.

일단 우리가 학교에서 프로그래밍을 하면서 맞이하게 되는 각종 lab, assignment 등에 심심찮게 등장하는 것이 바로 prime의 개념과 응용인데, 문득 이런 생각이 들었다. 과연 이게 어디에 쓰이는 물건이기에 이렇게 자주 등장하는 것인가? 그냥 무작정 시키는대로 하기 보다는 이 개념을 왜 알아야 하고, 또 프로그래밍에서 왜 구현을 해야하는지에 대해서 근본적인 원인과 이유를 파악하는 것이 동기부여 측면에서도 좋겠다는 생각이 들었다. 그래서 아래와 같이 조사를 해봤다.

실제로 소수(prime)는 컴퓨터 과학과 프로그래밍에서 꽤 중요한 역할을 한다. 특히 암호화, 해시 함수, 데이터 구조 등 다양한 분야에서 소수가 쓰인다.

암호화: RSA 알고리즘 같은 공개키 암호화에서는 큰 소수 두 개를 사용해서 공개키와 개인키를 생성한다. 이는 온라인 결제, 정보 전송 등에서 광범위하게 쓰인다.
해시 함수: 좋은 해시 함수를 만들 때, 소수는 중요한 역할을 한다. 해시 함수는 데이터를 빠르게 접근하거나 저장할 수 있도록 도와주는데, 소수를 사용하면 충돌 확률이 줄어들어 더 효율적인 해시 함수를 만들 수 있다.
알고리즘과 데이터 구조: 몇몇 알고리즘은 소수의 특성을 이용해서 동작한다. 예를 들어, 소수를 사용한 배열 크기는 해시 충돌을 줄일 수 있다.
그래픽: 몇몇 그래픽 처리 알고리즘에서도 소수가 활용된다. 예를 들어, 안티-에일리어싱이나 텍스처 매핑에서도 그렇다.
분산 시스템: 소수는 로드 분산이나 데이터 샤딩에서도 유용하게 쓰인다. 소수 개수의 노드를 사용하면 데이터 분산이 더 균일하게 이루어진다.

위와 같은 이유로 소수는 프로그래밍에서 자주 나오는 개념이며, 그로 인해 lab이나 assignment에서도 종종 등장한다. 이런 다양한 용도를 이해하면 소수와 관련된 문제에 대한 동기부여가 될 수 있을 것이다.

"에라토스테네스의 체(Sieve of Eratosthenes)"는 소수를 찾는 알고리즘이다. 이 알고리즘은 고대 그리스 수학자 에라토스테네스에 의해 처음 소개되었다. 이 방법은 특정 범위 내의 모든 소수를 효율적으로 찾을 수 있다. 아래에 알고리즘의 주요 단계를 설명하겠다.

초기 설정: 범위 2, 3, 4, ..., n까지의 숫자를 쓴다. 여기서 n은 찾고자 하는 소수의 최대 값이다.
첫 번째 숫자 선택: 리스트에서 가장 작은 수 p를 선택한다. 초기에는 2가 된다. 이 수는 소수이다.
제거 작업: 선택한 수 p의 배수를 모두 리스트에서 제거한다. 단, p 자신은 제거하지 않는다.
반복: 리스트에 남아있는 다음 가장 작은 수 p를 선택하고 3단계로 돌아가서 배수를 제거한다. 이 과정을 p의 제곱이 n보다 큰 수가 될 때까지 반복한다.
완료: 리스트에 남은 모든 수는 소수이다.

최적화 팁

실제 구현에서는 주로 불리언 배열을 사용하여, i 번째 요소가 true면 i는 소수, false면 합성수인 것으로 처리한다.
배열의 값이 true인 i에 대해서만 i * i부터 n까지 i의 배수를 제거한다.
i가 n의 제곱근까지만 반복해도 된다는 것이 중요한 최적화 포인트다.

이러한 방식으로 에라토스테네스의 체는 특정 범위 내의 모든 소수를 효과적으로 찾을 수 있다. 이 알고리즘의 시간 복잡도는 대략 O(n log log n)이다, 상당히 효율적이다.

이제 코드를 분석해보자.

use std::collections::HashMap;

// Function to find primes between m and n
fn primes(m: usize, n: usize) -> Vec<usize> {
    let mut sieve = vec![true; n];
    sieve[0] = false;
    sieve[1] = false;
    
    for p in 2..=((n as f64).sqrt() as usize) {
        if sieve[p] {
            for multiple in (p * p..n).step_by(p) {
                sieve[multiple] = false;
            }
        }
    }

    let mut primes = Vec::new();
    for (i, &is_prime) in sieve.iter().enumerate().skip(m).take(n - m) {
        if is_prime {
            primes.push(i);
        }
    }

    primes
}

fn main() {
    let prime_list = primes(100_000, 1_000_000); // 6-digit primes
    let mut groups: HashMap<String, Vec<usize>> = HashMap::new();

    // Grouping primes by their sorted digits as the key
    for &prime in &prime_list {
        let mut digits: Vec<char> = prime.to_string().chars().collect();
        digits.sort();
        let key: String = digits.into_iter().collect();
        groups.entry(key).or_insert(Vec::new()).push(prime);
    }

    let mut max_size = 0;
    let mut largest_group = Vec::new();
    
    // Finding the largest group of primes that are permutations of one another
    for group in groups.values() {
        if group.len() > max_size {
            max_size = group.len();
            largest_group = group.clone();
        }
    }

    println!("The size of the largest set of 6-digit primes that are permutations of one another is: {}", max_size);
    println!("The primes in this largest set are: {:?}", largest_group);
}

이 코드는 100,000부터 999,999까지의 범위에서 6자리 소수를 찾고, 그 중에서 숫자의 순열로 이루어진 가장 큰 소수 그룹을 찾는 작업을 한다. 즉, 같은 숫자들을 조합해서 만들 수 있는 다양한 소수가 얼마나 많은지를 알아보고, 그 중 가장 큰 그룹을 찾는 것이다.

primes(m: usize, n: usize) -> Vec<usize> 함수:

m부터 n까지의 범위에서 소수를 찾아 벡터로 반환한다.
에라토스테네스의 체 알고리즘을 사용한다.

main 함수:

primes 함수를 호출해서 6자리의 소수 리스트(prime_list)를 얻는다.
HashMap을 사용해서 소수들을 그룹화한다. 그룹의 키는 각 소수의 숫자를 정렬한 문자열이다.
가장 큰 그룹(largest_group)을 찾아 그 크기(max_size)와 그룹에 속한 소수들을 출력한다.

결과적으로, 이 코드는 6자리 소수 중에서 숫자의 순열로 이루어진 가장 큰 소수 그룹과 그 그룹의 크기를 찾아 출력한다.

이제 상세 분석에 들어가본다.

usize

usize는 Rust에서 부호 없는 정수를 나타내는 데이터 타입이다. 이 데이터 타입은 특별히 시스템 아키텍처에 의존적이다. 즉, 32비트 시스템에서는 32비트 크기를 가지고, 64비트 시스템에서는 64비트 크기를 가진다. usize 타입은 주로 컬렉션의 길이나 인덱스 등을 다룰 때 사용되며, 이러한 경우에 부호가 없는 정수가 적합하기 때문에 자주 사용된다.

fn primes(m: usize, n: usize) -> Vec<usize>에서 usize는 m과 n이 부호 없는 정수라는 것을 의미하고, 반환되는 벡터(Vec)도 부호 없는 정수(usize)로 이루어져 있다는 것을 나타낸다.

sieve vector

sieve 벡터는 "에라토스테네스의 체" 알고리즘을 구현하는 데 사용된다. 이 알고리즘은 특정 범위 내의 모든 소수를 찾는 방법이다. 여기서 sieve 벡터의 각 인덱스는 해당 인덱스의 수가 소수인지 아닌지를 나타낸다.

초기에는 모든 수를 소수라고 가정하기 위해 sieve의 모든 요소를 true로 설정한다.
0과 1은 소수가 아니므로 false로 설정한다.
이후에 알고리즘이 진행되면서 실제로 소수가 아닌 수들을 false로 바꾼다.

이렇게 하면 sieve 벡터의 인덱스를 통해 소수인지 아닌지 쉽게 판별할 수 있다. 예를 들어, sieve[17]이 true면 17은 소수라는 뜻이다. 반면에 sieve[4]가 false면 4는 소수가 아니다. 이런 방식으로 소수를 효율적으로 찾을 수 있다.

for p in 2..=((n as f64).sqrt() as usize)

물론이다. for p in 2..=((n as f64).sqrt() as usize) 코드를 여러 부분으로 나눠서 설명하겠다.

for p in ...: 이 부분은 p라는 변수를 다음 범위 안의 각 값에 대해 반복문을 돌린다는 것을 의미한다.
2..: 시작점이 2인 범위를 생성한다. 여기서는 2부터 시작하는데, 이유는 2가 첫 번째 소수이기 때문이다.
((n as f64).sqrt() as usize): 이 부분은 여러 작업을 한 번에 수행한다.
- n as f64: n을 부동소수점 숫자로 형변환한다.
- .sqrt(): 제곱근을 구한다. 소수점이 있을 수 있으므로 f64 타입이다.
- as usize: 다시 usize 형으로 변환한다. 이는 배열의 인덱스나 벡터의 크기 등에 사용되는 부호 없는 정수 타입이다.
2..=((n as f64).sqrt() as usize): 이 전체 표현은 2부터 n의 제곱근까지의 범위를 의미한다. 소수점은 버린다.

그래서 이 for 문은 2부터 n의 제곱근까지 p를 변화시키면서 반복한다. 이 범위를 사용하는 이유는 에라토스테네스의 체 알고리즘을 최적화하기 위해서다. n의 제곱근까지만 확인해도 충분하기 때문이다. 이 최적화로 인해 알고리즘의 실행 시간이 줄어든다.

for p 문 내부 로직

    for p in 2..=((n as f64).sqrt() as usize) {
        if sieve[p] {
            for multiple in (p * p..n).step_by(p) {
                sieve[multiple] = false;
            }
        }
    }

이 로직은 에라토스테네스의 체 알고리즘을 구현한 부분이다. sieve라는 이름의 불리언 벡터를 사용해서 소수인지 아닌지를 판단한다. 먼저 sieve[p]를 체크해서 true인지 확인한다. true라는 것은 p가 소수라는 뜻이다.

p..n은 Rust에서 범위(Range)를 표현하는 문법이다. 이는 p부터 n-1까지의 수를 포함하는 범위를 생성한다. 즉, p는 범위에 포함되고, n은 포함되지 않는다. 예를 들어 2..5라는 범위는 2, 3, 4라는 값을 포함하고 5는 포함하지 않는다.

이 범위는 주로 반복문에서 사용되며, 다음과 같이 쓸 수 있다:

for i in 2..5 {
    println!("{}", i);  // 2, 3, 4가 출력된다.
}

따라서, for multiple in (p * p..n).step_by(p)에서 p * p..n은 p * p부터 n - 1까지의 수를 가리킨다. step_by(p) 메서드를 사용하면 이 범위 내에서 p의 배수만 순회하게 된다.

if sieve[p]: 만약 현재 p가 소수라면 (sieve[p]가 true면), 다음 단계로 넘어간다.
for multiple in (p * p..n).step_by(p): p의 배수를 p * p부터 n까지 탐색한다. 왜 p * p부터 시작하는지 궁금할 수 있는데, 그 이유는 p 미만의 모든 수의 배수들은 이미 이전 단계에서 제거되었기 때문이다. 예를 들어, p가 5라면, 2와 3의 배수는 이미 이전에 제거되었을 것이므로, 5의 배수를 제거할 차례다.
sieve[multiple] = false;: p의 배수인 multiple은 소수가 아니므로, 해당 인덱스의 값을 false로 설정한다.

이런 식으로 p가 n의 제곱근까지만 반복해도, sieve 벡터의 true로 남아있는 값들이 해당 범위 내의 모든 소수가 된다. 이 과정이 끝나면 sieve 배열에서 true로 표시된 인덱스가 소수인 것이다.

let 문 이하

    let mut primes = Vec::new();
    for (i, &is_prime) in sieve.iter().enumerate().skip(m).take(n - m) {
        if is_prime {
            primes.push(i);
        }
    }

이 코드의 목적은 sieve 벡터를 사용하여 m과 n 사이의 모든 소수를 찾고, 이를 새로운 벡터 primes에 저장하는 것이다.

let mut primes = Vec::new();: 새로운 빈 벡터 primes를 생성한다. 이 벡터에는 나중에 소수들이 저장될 것이다.
for (i, &is_prime) in sieve.iter().enumerate().skip(m).take(n - m): 이 부분이 중요하다.
- sieve.iter(): sieve 벡터의 각 요소에 대한 반복자(Iterator)를 생성한다.
- enumerate(): 반복자를 수정하여 현재 요소의 인덱스도 함께 반환한다.
- skip(m): 첫 번째 요소부터 m - 1번째 요소까지 무시한다.
- take(n - m): m부터 시작해서 n - m 개의 요소만 사용한다.

결국, 이 반복문은 m과 n 사이의 인덱스에 있는 sieve 벡터의 요소를 순회한다.

if is_prime: 만약 현재 요소(즉, is_prime)이 true라면 (소수라면),
- primes.push(i);: 그 인덱스 i를 primes 벡터에 추가한다.

이렇게 for 루프가 끝나면, primes 벡터에는 m과 n 사이의 모든 소수가 저장되어 있을 것이다.

for &prime in &prime_list

    for &prime in &prime_list {
        let mut digits: Vec<char> = prime.to_string().chars().collect();
        digits.sort();
        let key: String = digits.into_iter().collect();
        groups.entry(key).or_insert(Vec::new()).push(prime);
    }

이 코드는 prime_list에 있는 모든 6자리 소수를 그룹화한다. 그룹화의 기준은 소수의 각 자릿수의 숫자들이다. 예를 들어, 소수 123, 213, 312는 같은 그룹에 속하게 된다. 이를 위해 HashMap이라는 자료구조를 사용한다.

for &prime in &prime_list: prime_list 벡터에 있는 모든 소수에 대해 반복한다.
let mut digits: Vec<char> = prime.to_string().chars().collect();: 현재 소수(prime)를 문자열로 변환한 다음, 각 자릿수를 Vec<char> 타입의 digits 벡터로 만든다.
digits.sort();: digits 벡터를 정렬한다. 이렇게 하면, 예를 들어 소수 213과 312의 digits 벡터는 동일하게 [1, 2, 3]이 되고, 같은 그룹으로 분류할 수 있다.
let key: String = digits.into_iter().collect();: 정렬된 digits 벡터를 다시 문자열로 변환한다. 이 문자열이 HashMap에서 사용할 키가 된다.
groups.entry(key).or_insert(Vec::new()).push(prime);: HashMap의 entry 메소드를 사용하여 특정 키에 대한 값에 접근한다. 만약 키가 존재하지 않으면, 빈 벡터(Vec::new())를 삽입한다. 그리고 해당 벡터에 현재의 소수 prime을 추가한다.

이렇게 반복문이 끝나면, groups HashMap에는 각각의 키(정렬된 자릿수)에 해당하는 소수들의 그룹이 저장되어 있다.

& 용도의 구분

Rust에서 & 기호는 주로 참조(Reference)를 나타낸다. 주소 자체를 다루는 것은 C나 C++과는 다르다. Rust에서 &는 borrow라고 생각하면 되고, 이것을 통해 소유권을 넘기지 않고 데이터에 접근할 수 있다.

함수의 매개변수에서 &를 본다면, 그것은 해당 함수가 데이터를 borrow하는 것이다. 예를 들어, for &prime in &prime_list에서 &prime_list는 prime_list의 불변 참조이다.
변수를 선언할 때 &가 있는 경우, 그것 역시 참조다. 예: let x = &y;
&mut은 가변 참조(mutable reference)를 나타낸다. 즉, 데이터를 수정할 수 있는 참조다.

주소로 사용되는 경우는 상대적으로 드물다. 대부분의 상황에서 &는 참조, 즉 borrow용도로 사용된다.

구분하는 몇 가지 팁:

만약 &가 포인터 연산이나 메모리 관련 작업에 사용되면 주소로 사용될 가능성이 높다. 하지만 Rust에서는 일반적으로 그런 상황이 드물다.
함수 시그니처나 변수 선언에서 &를 볼 경우, 대부분 참조(borrow)로 사용된다.

주로 컨텍스트를 통해 &의 용도를 판단한다. Rust의 경우, 대부분은 borrow 목적으로 &를 사용한다고 볼 수 있다.

for &prime in &prime_list와 for prime in prime_list의 차이는 소유권과 변수의 타입에 있다.

for &prime in &prime_list: prime_list의 각 원소를 불변 참조(&usize)로 순회하면서, 참조를 해제(dereference)하여 복사본을 prime에 할당한다. 즉, prime은 usize 타입이 된다.
for prime in prime_list: 이 경우, prime_list의 소유권이 for 루프로 이동하게 된다. prime은 usize 타입이지만, 이 경우에는 prime_list를 루프 이후에 다시 사용할 수 없게 된다. 즉, 소유권이 이동(move)했다.

일반적으로는 for &prime in &prime_list 형태를 더 많이 사용한다. 왜냐하면 이 방식은 원본 리스트(prime_list)에 대한 불변 참조만을 사용하기 때문에, 루프 이후에도 prime_list를 다른 용도로 계속 사용할 수 있기 때문이다.

만약 for prime in prime_list를 사용한다면, prime_list를 루프가 끝난 후에 다시 사용하려면 다음과 같은 방법을 사용해야 한다:

.clone()을 이용해 복제본을 만들고 그 복제본으로 순회한다.
prime_list.iter()를 사용해 불변 참조로 순회한다.

for prime in prime_list를 사용하면, 그 다음 코드에서 prime_list를 사용하려고 할 때 컴파일 에러가 발생할 것이다.

    for group in groups.values() {
        if group.len() > max_size {
            max_size = group.len();
            largest_group = group.clone();
        }
    }

이 코드는 HashMap에 저장된 소수 그룹들 중에서 가장 큰 그룹을 찾는 로직이다. 각 라인별로 설명하면 다음과 같다.

for group in groups.values() {: HashMap의 values() 메서드를 호출하여 모든 값(이 경우에는 소수 그룹을 나타내는 Vec<usize>)에 대해 순회한다.
if group.len() > max_size {: 현재 순회 중인 그룹(group)의 길이가 지금까지 찾은 가장 큰 그룹의 길이(max_size)보다 큰지 확인한다.
max_size = group.len();: 만약 현재 그룹이 더 크다면, max_size를 현재 그룹의 길이로 업데이트한다.
largest_group = group.clone();: 현재 그룹이 더 크다면, largest_group 변수를 현재 그룹의 복사본으로 업데이트한다. .clone()은 Vec<usize>의 복사본을 만들기 위해 사용한다.

루프가 끝날 때까지 이 과정을 반복하여, 가장 큰 그룹과 그 크기(max_size)를 찾는다. 이 정보를 이용해서 최종 결과를 출력한다.

이상으로 prime 관련된 코드도 분석해봤다.

인생의 쾌를 찾는 고찰족/충만족

Page

관련 포스팅

2023년 9월 22일 금요일

Week02 - Rust 예제 코드 분석 (Prime)