4단원에서 배운 것을 섞어 쓰는 네 문제다. 트레이트와 트레이트 객체로 서로 다른 타입을 한 목록에 담고(p1), next 하나로 반복자를 만들고(p2), 클로저와 어댑터 사슬로 데이터를 세고(p3), 표준 트레이트 다섯 개의 약속을 한 기준으로 맞춘다(p4). 각 문제의 코드를 cargo new로 만든 패키지의 src/main.rs에 옮겨 cargo run으로 돌려 본다.

검증: 네 문제의 답, 경계 사례 테스트, 변형 문제의 컴파일 오류와 실행 결과를 코드로 확인했다 — p1 · p2 · p3 · p4

p1 · 섞인 도형을 넓이 순으로

원(반지름 1), 직사각형(2×3), 삼각형(밑변 4, 높이 2)을 한 목록에 담고 넓이가 큰 것부터 설명을 만든다.

  • (가) area와 name을 요구하고, describe는 기본 몸통으로 "이름 넓이"(넓이는 소수 둘째 자리까지)를 돌려주는 트레이트 Shape를 써라.
  • (나) fn ranked(shapes: &mut [Box<dyn Shape>]) -> Vec<String>을 써라. 결과는 ["직사각형 6.00", "삼각형 4.00", "원 3.14"]여야 한다.
  • (다) 넓이의 합을 반복자로 구하는 fn total_area(shapes: &[Box<dyn Shape>]) -> f64를 써라. 위 목록에서 \(\pi + 10 \approx 13.14159\)이고, 빈 목록이면 0이다.

사용 개념: 트레이트의 기본 메서드, 트레이트 객체, 반복자의 map과 sum.

풀이 전략: 타입이 서로 다른 값을 한 Vec에 담아야 하므로 Box<dyn Shape>로 감싼다. 넓이가 f64라서 Ord가 없다. 그래서 키를 뽑는 sort_by_key 대신 비교 함수를 직접 주는 sort_by를 쓰고, f64 두 개를 늘 비교할 수 있는 total_cmp로 비교한다.

풀이
  1. 트레이트에 기본 몸통 두기: describe는 필수 메서드 name과 area만으로 만들 수 있으니 트레이트 안에 몸통을 둔다. 도형마다 area와 name 두 개만 구현하면 된다.
trait Shape {
    fn area(&self) -> f64;
    fn name(&self) -> String;
    fn describe(&self) -> String {
        format!("{} {:.2}", self.name(), self.area())
    }
}

impl Shape for Circle {
    fn area(&self) -> f64 { PI * self.r * self.r }
    fn name(&self) -> String { "원".into() }
}
// Rect: w * h, Triangle: base * height / 2.0 도 같은 모양이다
  1. 큰 것부터 정렬: 비교 함수에 b를 앞에 두면 내림차순이 된다.
  2. 설명으로 바꿔 모으기: iter().map(...).collect().
fn ranked(shapes: &mut [Box<dyn Shape>]) -> Vec<String> {
    shapes.sort_by(|a, b| b.area().total_cmp(&a.area()));
    shapes.iter().map(|s| s.describe()).collect()
}

fn total_area(shapes: &[Box<dyn Shape>]) -> f64 {
    shapes.iter().map(|s| s.area()).sum()
}
  1. 확인: 넓이는 원 \(\pi \approx 3.14\), 직사각형 6, 삼각형 4다. 출력은 ["직사각형 6.00", "삼각형 4.00", "원 3.14"], 합은 13.14159다. 빈 목록의 sum()은 0.0이다.

s.describe()는 상자 안의 실제 타입을 실행 중에 찾아가 부른다(동적 디스패치)1. 기본 몸통 안의 self.name()과 self.area()도 마찬가지다.

변형. (가) ranked의 정렬을 shapes.sort_by_key(|s| s.area())로 바꾸면 컴파일되는가? (나) total_cmp는 넓이가 NaN인 도형이 섞여도 정렬할 수 있는가?

답

(가) 안 된다. error[E0277]: the trait bound `f64: Ord` is not satisfied다. sort_by_key는 키가 Ord여야 하는데, f64는 NaN 때문에 Ord가 아니다(꼭 구현할 표준 트레이트).
(나) 된다. total_cmp는 IEEE 754의 totalOrder 규칙으로 모든 f64에 순서를 매긴다. 음수 NaN이 가장 작고 양수 NaN이 가장 크다2. f64::NAN의 부호는 정해져 있지 않다고 std 문서가 적는다2. 이 기계에서는 [2.0, NaN, -1.0]을 total_cmp로 정렬하니 NaN이 맨 끝으로 갔다.

p2 · 피보나치 반복자

1, 1, 2, 3, 5, 8, …을 내주는 반복자 Fib를 만든다. 다음 항이 u64를 넘을 때 panic하지 말고 거기서 끝나야(None) 한다.

  • (가) 앞 10개를 모으면 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]여야 한다.
  • (나) 4,000,000 이하인 항 가운데 짝수의 합을 어댑터 사슬로 구하라.
  • (다) u64에 들어가는 항은 몇 개이고, 마지막 항은 무엇인가?

사용 개념: 반복자의 Iterator 트레이트와 take_while, Option과 Result의 ?, 값·변수·타입의 checked_add.

풀이 전략: 반복자는 “지금 항”과 “다음 항”만 기억하면 된다. 넘칠 수 있는 덧셈을 checked_add로 바꾸면 넘칠 때 None이 나온다. 이 None을 “다음 항이 없다”로 저장해 두면 끝내기가 저절로 된다.

풀이
  1. 상태 정하기: 두 칸 모두 Option<u64>로 둔다. None은 “그 항은 u64에 들어가지 않는다”는 뜻이다.
  2. 끝내기: self.cur?는 지금 항이 None이면 그 자리에서 None을 돌려준다.
  3. 넘침을 None으로: 다음다음 항을 checked_add로 구한다. 넘치면 None이 저장된다.
struct Fib { cur: Option<u64>, next: Option<u64> }

fn fib() -> Fib { Fib { cur: Some(1), next: Some(1) } }

impl Iterator for Fib {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let out = self.cur?;
        let after = match (self.cur, self.next) {
            (Some(a), Some(b)) => a.checked_add(b),
            _ => None,
        };
        self.cur = self.next;
        self.next = after;
        Some(out)
    }
}
  1. 사슬로 답 구하기: 4,000,000을 처음 넘는 순간 끝내야 하므로 take_while, 짝수만 남기는 filter, 더하는 sum.
fn even_sum_below(limit: u64) -> u64 {
    fib().take_while(|&x| x <= limit).filter(|x| x % 2 == 0).sum()
}
  1. 확인: (나)는 4613732다. 작은 한도로 손 계산과 맞춰 본다: even_sum_below(1) = 0, even_sum_below(2) = 2, even_sum_below(10) = 2 + 8 = 10. (다)는 fib().count()가 93, fib().last()가 12200160415121876738이다. fib().nth(92)는 그 값이고 fib().nth(93)은 None이다. 94번째 항을 구하는 덧셈이 넘쳐서 반복자가 거기서 끝났다.

변형. (나)의 take_while(|&x| x <= limit)을 filter(|&x| x <= limit)로 바꾸면 답이 달라지는가? 사슬 맨 앞에 inspect를 넣어 반복자가 내준 항의 수를 세면 두 판은 각각 몇인가?

답

답은 똑같이 4613732다. 하지만 본 항의 수가 다르다. take_while 판은 34개, filter 판은 93개다. take_while은 처음으로 한도를 넘는 34번째 항(5,702,887)을 보고 끝난다. filter는 조건이 거짓이어도 계속 다음 항을 달라고 해서 반복자가 끝날 때까지 93개를 다 본다. Fib가 넘침에서 스스로 끝나니 이번엔 결과가 같았다. 끝이 없는 반복자였다면 filter 판은 끝나지 않는다(반복자).

p3 · 가장 많이 나온 단어 k개

글에서 가장 많이 나온 단어 k개를 (단어, 횟수)로 돌려주는 fn top_words(text: &str, k: usize) -> Vec<(String, usize)>를 써라.

  • 글자나 숫자가 아닌 문자에서 끊고, 대소문자는 가리지 않는다(소문자로 바꾼다).
  • 횟수가 많은 것부터, 횟수가 같으면 사전 순으로 앞선 단어부터.
  • top_words("The cat and the dog. And THE bird!", 3)은 [("the", 3), ("and", 2), ("bird", 1)]이다.
  • 단어가 없는 " ... !!"는 빈 목록, 단어 종류보다 큰 k는 있는 만큼만 돌려준다.

사용 개념: 반복자, 컬렉션의 entry, 클로저.

풀이 전략: 일을 네 단계로 나눈다. 자르기, 세기, 줄 세우기, 앞에서 자르기. 줄 세우기의 두 기준(횟수는 큰 것부터, 단어는 작은 것부터)은 튜플 키 (Reverse(횟수), 단어) 하나로 쓸 수 있다. Reverse는 비교를 뒤집는 감싸개다.

풀이
  1. 자르기: split에 클로저를 주면 그 조건이 참인 문자에서 끊는다. ". "처럼 끊는 문자가 이어지면 그 사이에 빈 문자열이 생기므로 filter로 버린다.
  2. 세기: entry(w).or_insert(0)에 1을 더한다.
  3. 줄 세우기: HashMap을 Vec으로 모은 뒤 튜플 키로 정렬한다. 튜플은 앞 원소부터 비교한다.
  4. 앞에서 자르기: take(k). k가 더 커도 있는 만큼만 나온다.
fn top_words(text: &str, k: usize) -> Vec<(String, usize)> {
    let mut freq: HashMap<String, usize> = HashMap::new();
    for w in text
        .split(|c: char| !c.is_alphanumeric())
        .filter(|w| !w.is_empty())
        .map(str::to_lowercase)
    {
        *freq.entry(w).or_insert(0) += 1;
    }
    let mut pairs: Vec<(String, usize)> = freq.into_iter().collect();
    pairs.sort_by_key(|(w, n)| (Reverse(*n), w.clone()));
    pairs.into_iter().take(k).collect()
}

횟수는 the 3, and 2, cat·dog·bird 각 1이다. 동점인 셋 중 사전 순으로 bird가 앞이라 셋째가 된다.

키 함수 안의 w.clone()은 비교할 때마다 String을 새로 만든다. sort_by_key는 키 함수 비용이 \(O(m)\)일 때 최악 \(O(m \cdot n \log n)\)이다. sort_by_cached_key는 원소마다 키를 한 번만 계산해 두므로, 키가 비싸면 이쪽이 낫다3.

변형. 정렬 키에서 단어를 빼고 pairs.sort_by_key(|(_, n)| Reverse(*n))만 쓰면 결과의 셋째 자리는 늘 같은가?

답

같지 않다. 같은 글로 200번 돌린 실행에서 셋째 자리에 bird, cat, dog가 모두 나왔다. sort_by_key는 안정 정렬이라 횟수가 같은 원소끼리는 정렬 전 순서를 그대로 둔다3. 그런데 정렬 전 순서는 HashMap이 내준 순서이고, 그 순서는 맵마다 달라진다(컬렉션). 결과가 매번 같아야 하는 출력과 테스트에는 동점을 가르는 둘째 기준이 꼭 필요하다.

p4 · 대소문자를 가리지 않는 사용자 이름

가입할 때 "Kim"과 "kim"은 같은 이름으로 봐야 한다. 이름을 감싼 struct Username(String)을 만들어 HashSet과 BTreeSet에서 모두 그렇게 동작하게 하라.

  • PartialEq, Eq, Hash, PartialOrd, Ord를 손으로 구현한다.
  • fn unique_sorted(names: &[&str]) -> Vec<String>은 처음 나온 표기를 남기고 중복을 없앤 뒤, 대소문자를 무시한 사전 순으로 돌려준다.
  • 입력 ["Kim", "kim", "LEE", "Park", "lee", "KIM"]이면 ["Kim", "LEE", "Park"]이고, 같은 입력으로 만든 HashSet<Username>과 BTreeSet<Username>은 둘 다 원소가 3개다.

사용 개념: 꼭 구현할 표준 트레이트의 Eq·Hash 약속과 Ord·PartialOrd 약속, 반복자.

풀이 전략: 다섯 트레이트가 같은 기준을 쓰게 하는 것이 전부다. 그 기준(소문자로 바꾼 바이트 열)을 메서드 하나로 만들어 두고, 다섯 구현이 모두 그 메서드만 쓰게 한다. 기준이 한 곳에 있으면 어긋날 수가 없다.

풀이
  1. 기준 하나 만들기: 소문자로 바꾼 바이트를 내주는 반복자를 돌려준다. 문자열을 새로 만들지 않는다.
  2. 같음: eq_ignore_ascii_case로 비교한다. 같은 기준이다.
  3. 해시: 기준 바이트를 하나씩 넣고 끝에 0xff를 넣는다. 끝 표시는 ("ab", "c")와 ("a", "bc") 같은 묶음이 서로 다른 해시를 내게 한다. 해시에 넣는 값들이 서로의 앞부분이 되면 안 된다는 std 문서의 권고를 따른 것이다4.
  4. 순서: 두 기준 반복자를 Iterator::cmp로 비교한다. 원소를 앞에서부터 사전식으로 비교하는 메서드다5. partial_cmp는 Some(self.cmp(other))로 둔다6.
#[derive(Debug, Clone)]
struct Username(String);

impl Username {
    fn key(&self) -> impl Iterator<Item = u8> + '_ {
        self.0.bytes().map(|b| b.to_ascii_lowercase())
    }
}

impl PartialEq for Username {
    fn eq(&self, other: &Self) -> bool { self.0.eq_ignore_ascii_case(&other.0) }
}
impl Eq for Username {}

impl Hash for Username {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for b in self.key() { state.write_u8(b); }
        state.write_u8(0xff);
    }
}

impl Ord for Username {
    fn cmp(&self, other: &Self) -> Ordering { self.key().cmp(other.key()) }
}
impl PartialOrd for Username {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}
  1. 처음 표기 남기기: HashSet::insert는 처음 넣으면 true, 이미 있으면 false를 돌려준다. 그래서 filter(|u| seen.insert(u.clone()))는 처음 나온 것만 통과시킨다.
fn unique_sorted(names: &[&str]) -> Vec<String> {
    let mut seen = HashSet::new();
    let mut kept: Vec<Username> = names
        .iter()
        .map(|n| Username(n.to_string()))
        .filter(|u| seen.insert(u.clone()))
        .collect();
    kept.sort();
    kept.into_iter().map(|u| u.0).collect()
}
  1. 확인: 결과는 ["Kim", "LEE", "Park"], HashSet 3개, BTreeSet 3개다. 테스트에서 ("Kim", "KIM"), ("a", "A"), ("Rust", "rUST") 세 쌍이 모두 ==, 같은 해시, cmp가 Equal인지 확인했다.

변형. 다른 것은 그대로 두고 Ord만 self.0.cmp(&other.0)(대소문자를 구별하는 원래 문자열 비교)로 바꾼다. 같은 입력으로 만든 HashSet과 BTreeSet에는 각각 몇 개가 들어가는가? BTreeSet을 collect()로 만들 때와 빈 집합에 insert를 여섯 번 할 때가 같은가?

답

HashSet은 그대로 3개다. Eq와 Hash는 바꾸지 않았기 때문이다. BTreeSet은 만드는 방법에 따라 다르게 나왔다(rustc 1.99.0에서 본 결과).

만드는 법 개수 들어간 것
insert 여섯 번 6 KIM, Kim, LEE, Park, kim, lee
collect() 5 Kim, LEE, Park, kim, lee

insert는 Ord로만 자리를 찾는다7. 대소문자를 구별하는 Ord에게 여섯 이름은 모두 다르다. collect()는 원소를 먼저 모두 정렬한 뒤 한꺼번에 트리를 만든다8. 그 과정에서 바로 이웃한 두 키가 !=가 아니면, 즉 ==이면 앞의 것을 버리고 뒤의 것만 남긴다9. 정렬 결과 KIM 바로 뒤에 Kim이 오고, 둘은 ==로 같으므로 KIM이 빠졌다. kim과 Kim은 서로 떨어져 있어서 둘 다 남았다.

핵심은 개수가 아니다. Ord와 Eq가 어긋나면 PartialOrd의 약속(a == b일 때, 그리고 그때만 partial_cmp가 Equal)이 깨진다10. 이것은 논리 오류이고, 그 결과는 정해져 있지 않다6. 같은 데이터에서 만드는 법만 바꿨는데 답이 달라진 것이 바로 “정해져 있지 않다”의 뜻이다. 다음 버전의 표준 라이브러리에서는 또 다른 답이 나올 수 있다.

  1. The Rust Programming Language, 18.2 Using Trait Objects to Abstract over Shared Behavior (Trait Objects Perform Dynamic Dispatch) — https://doc.rust-lang.org/book/ch18-02-trait-objects.html ↩

  2. std 문서, Primitive Type f64, total_cmp — https://doc.rust-lang.org/std/primitive.f64.html ↩ ↩2

  3. std 문서, Primitive Type slice, sort_by_key(stable, \(O(m \cdot n \log n)\)), sort_by_cached_key(key function called at most once per element) — https://doc.rust-lang.org/std/primitive.slice.html ↩ ↩2

  4. std 문서, Trait std::hash::Hash (Hash and Eq, Prefix collisions) — https://doc.rust-lang.org/std/hash/trait.Hash.html ↩

  5. std 문서, Trait std::iter::Iterator, cmp (“Lexicographically compares the elements of this Iterator with those of another”) — https://doc.rust-lang.org/std/iter/trait.Iterator.html ↩

  6. std 문서, Trait std::cmp::Ord (consistency with PartialOrd, logic errors) — https://doc.rust-lang.org/std/cmp/trait.Ord.html ↩ ↩2

  7. std 문서, Struct std::collections::BTreeSet (원소의 순서는 Ord가 정한다, insert의 T: Ord) — https://doc.rust-lang.org/std/collections/struct.BTreeSet.html ↩

  8. 표준 라이브러리 소스, alloc/collections/btree/set.rs, impl FromIterator for BTreeSet (inputs.sort() 뒤 from_sorted_iter) — https://doc.rust-lang.org/src/alloc/collections/btree/set.rs.html ↩

  9. 표준 라이브러리 소스, alloc/collections/btree/dedup_sorted_iter.rs (“only the last key-value pair is yielded”, if next.0 != peeked.0) — https://doc.rust-lang.org/src/alloc/collections/btree/dedup_sorted_iter.rs.html ↩

  10. std 문서, Trait std::cmp::PartialOrd (“a == b if and only if partial_cmp(a, b) == Some(Equal)”) — https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html ↩