Data Structure

그래프 연산이나 저장 구조를 최적화할 때 빠지지 않고 등장하는 자료구조가 CSR(Compressed Sparse Row)입니다. 1977년 예일 대학교가 발표한 Yale Sparse Matrix Package 보고서에서 처음 소개되어 Yale Format이라고도 불리는데, 희소 행렬(sparse matrix)을 효율적으로 저장하고 처리하기 위해 고안되었습니다. 희소 행렬이란 희소 행렬은 대부분의 원소가 0인 행렬을 말합니다. 과학 계산, 그래프 이론, 머신러닝 등 현대 컴퓨팅의 거의 전 영역에서 마주치게 되는데, 현실의 데이터를 행렬로 옮기면 십중팔구 이런 모양이 됩니다. SNS를 예로 들면, 사용자가 100만 명이라 해도 한 사람의 친구 수는 보통 500명 안팎입니다. 그런데 이것을 그대로 행렬로 표현하려면 1조(10^12) 크기, 그러니까 7.3PB에 달하는 행렬이 필요해집니다. 실제 정보량에 비해 저장 공간이 터무니없이 커지는 셈입니다. ...

이 글은 Rust hash iteration+reinsertion 글과 관련 Rust 이슈/PR을 제가 이해한 대로 정리한 글입니다. 원문이 정확한 소스이니, 정확한 내용은 원문을 확인해주세요. Rust의 HashMap에서 발생했던 흥미로운 버그를 하나 소개하려고 합니다. 겉보기에는 지극히 평범한 코드인데, 특정 조건이 갖춰지면 O(n)이어야 할 연산이 O(n²)으로 폭발합니다. 버그 재현 다음 코드를 보겠습니다. 첫 번째 해시맵(one)에 1부터 5,000,000까지의 값을 삽입한 뒤(T1), 그 해시맵을 순회하면서 두 번째 해시맵(two)에 값을 그대로 재삽입(T2)하는 것이 전부입니다. use std::collections::hash_set::HashSet; fn main() { println!("inserting..."); let mut one = HashSet::new(); for i in 1..5000000 { one.insert(i); } println!("reinserting..."); let mut two = HashSet::new(); for v in one { two.insert(v); } } T1과 T2 모두 원소를 하나씩 삽입하는 동작이니, 둘 다 O(n)이어야 할 것 같습니다. 그런데 실제로 실행해보면 T1은 예상대로 O(n)에 끝나지만, T2는 O(n²)에 가까운 시간이 걸립니다. 같은 일을 하는 코드인데 왜 이런 차이가 발생할까요? ...