개요

HashMap 형태의 자료구조를 특정 인덱스를 통해 정렬 후, 원하는 키 값으로 찾는 로직이 필요하다. BTreeMap을 활용해서 구현해볼 예정이다.

내용

#[derive(Debug, Clone)]
struct Group {
    group_uid: u32,
    name: String,
    level: u32,
    member_count: u32,
}

impl std::fmt::Display for Group {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // write! 매크로를 사용하여 포맷터 f에 데이터를 작성합니다.
        // 모든 필드를 "이름: 값" 형태로 한 줄에 출력합니다.
        write!(
            f,
            "Guild(UID: {}, 이름: {}, 레벨: {}, 멤버 수: {})",
            self.group_uid,
            self.name,
            self.level,
            self.member_count
        )
        // 이 포맷은 `{}` 포맷팅(예: println!("{}", guild))에 사용됩니다.
    }
}

impl Group {
    fn new(guild_uid: u32, name: String, level: u32, member_count: u32) -> Self {
        Self {
            group_uid: guild_uid,
            name,
            level,
            member_count,
        }
    }
}

Group이라는 구조체를 하나 만들어 주었고, 보기 좋게 출력하고자 Display를 구현해 주었다.

fn main() {
    let mut map = HashMap::<u32, Group>::new();

    let vec: Vec<Group> = vec![
        Group::new(0, "새벽의 그림자 수호대".to_string(), 1, 9),
        Group::new(1, "엘리트 와플 특공대".to_string(), 1, 2),
        Group::new(2, "마법 양들의 침묵".to_string(), 1, 12),
        Group::new(3, "황금 붕어빵 연구소".to_string(), 1, 12),
        Group::new(4, "김광란의 펭귄 부대재성".to_string(), 9, 14),
        Group::new(5, "꼬꼬마 유치원 졸업반".to_string(), 6, 3),
        Group::new(6, "미스테리한 도넛 구출대".to_string(), 3, 22),
        Group::new(7, "고독한 달팽이들의 행진".to_string(), 8, 5),
        Group::new(8, "별똥별 연금술 협회".to_string(), 1, 15),
        Group::new(9, "영원의 시간 관리팀".to_string(), 15, 30),
        Group::new(10, "무지개빛 해파리 사냥꾼".to_string(), 4, 18),
        Group::new(11, "그림자 속의 곰돌이".to_string(), 9, 7),
        Group::new(12, "침묵의 우주 정복자".to_string(), 20, 45),
        Group::new(13, "재채기하는 용들의 동맹".to_string(), 2, 10),
        Group::new(14, "투명한 모래시계 수집가".to_string(), 12, 25),
        Group::new(15, "전설의 고양이 발바닥".to_string(), 5, 11),
        Group::new(16, "천상의 팝콘 배달부".to_string(), 18, 33),
        Group::new(17, "심해의 아이스케이크".to_string(), 7, 2),
        Group::new(18, "시간을 달리는 양말".to_string(), 10, 28),
        Group::new(19, "은하계 오징어 조종사".to_string(), 1, 6),
        Group::new(20, "아르헨티나의 마늘 빵".to_string(), 16, 40),
        Group::new(21, "마지막 남은 연필심".to_string(), 6, 19),
        Group::new(22, "오로라를 굽는 제빵사".to_string(), 19, 48),
        Group::new(23, "바람의 비누방울 전문가".to_string(), 3, 13),
        Group::new(24, "지하철 노선의 비밀".to_string(), 14, 38),
        Group::new(25, "잊혀진 꿀벌 기사단".to_string(), 11, 21),
        Group::new(26, "화산 속의 아이팟".to_string(), 2, 4),
        Group::new(27, "중력 거부자 클럽".to_string(), 17, 31),
        Group::new(28, "자정의 오이 피클".to_string(), 8, 16),
        Group::new(29, "우유곽 탐험대".to_string(), 13, 27),
        Group::new(30, "하늘을 나는 고슴도치".to_string(), 4, 9),
        Group::new(31, "신비한 큐브 해결사".to_string(), 15, 36),
        Group::new(32, "미래를 보는 커피콩".to_string(), 6, 23),
        Group::new(33, "소용돌이 치는 감자".to_string(), 10, 17),
        Group::new(34, "영원한 숙제 제출자".to_string(), 12, 42),
        Group::new(35, "비 오는 날의 양동이".to_string(), 7, 20),
    ];

    // HashMap<u32, Guild> 생성
    vec.into_iter().for_each(|g| {
        map.insert(g.group_uid, g);
    });

    let result = sort_by_level(&map, (7, 2, "심해의 아이스케이크"));
    for g in result {
        println!("{}", g);
    }
}

fn sort_by_level(map: &HashMap<u32, Group>, target: (u32, u32, &str)) -> Vec<Group> {
    let mut b_tree = BTreeMap::<(u32, u32, &str), &Group>::new();
    map.iter().for_each(|(_, g)| {
        b_tree.insert((g.level, g.member_count, &g.name), g);
    });

    b_tree.iter().for_each(|(_, g)| {
        println!("(level: {}, member_count: {}, name: {}) {}", g.level, g.member_count, g.name, g);
    });

    let res = b_tree.get(&target);
    
    let mut vec = Vec::new();
    let cnt = 10;

    for (_, value) in b_tree.range(target..) {
        if vec.len() >= cnt {
            break;
        }

        vec.push((*value).clone());
    }

    vec
}

gemini에게 데이터값을 뽑아달라 하여 약 30개 정도의 데이터를 Vector 형태로 만들어 주었다. Vec를 HashMap으로 변환해 주었고, 생성한 HashMap을 sort_by_level 함수에 참조 매개변수로 넘겨주었고, 특정 타겟을 넘겨주었다.
level이 동일하다면, 멤버 수로 정렬하도록 하였고, 역시 동일하다면 이름으로 정렬하도록 하였다. 이름은 고유하기 때문에 key 값은 고유하다고 볼 수 있다.

(level: 1, member_count: 2, name: 엘리트 와플 특공대) Guild(UID: 1, 이름: 엘리트 와플 특공대, 레벨: 1, 멤버 수: 2)
(level: 1, member_count: 6, name: 은하계 오징어 조종사) Guild(UID: 19, 이름: 은하계 오징어 조종사, 레벨: 1, 멤버 수: 6)
(level: 1, member_count: 9, name: 새벽의 그림자 수호대) Guild(UID: 0, 이름: 새벽의 그림자 수호대, 레벨: 1, 멤버 수: 9)
(level: 1, member_count: 12, name: 마법 양들의 침묵) Guild(UID: 2, 이름: 마법 양들의 침묵, 레벨: 1, 멤버 수: 12)
(level: 1, member_count: 12, name: 황금 붕어빵 연구소) Guild(UID: 3, 이름: 황금 붕어빵 연구소, 레벨: 1, 멤버 수: 12)
(level: 1, member_count: 15, name: 별똥별 연금술 협회) Guild(UID: 8, 이름: 별똥별 연금술 협회, 레벨: 1, 멤버 수: 15)
(level: 2, member_count: 4, name: 화산 속의 아이팟) Guild(UID: 26, 이름: 화산 속의 아이팟, 레벨: 2, 멤버 수: 4)
(level: 2, member_count: 10, name: 재채기하는 용들의 동맹) Guild(UID: 13, 이름: 재채기하는 용들의 동맹, 레벨: 2, 멤버 수: 10)
(level: 3, member_count: 13, name: 바람의 비누방울 전문가) Guild(UID: 23, 이름: 바람의 비누방울 전문가, 레벨: 3, 멤버 수: 13)
(level: 3, member_count: 22, name: 미스테리한 도넛 구출대) Guild(UID: 6, 이름: 미스테리한 도넛 구출대, 레벨: 3, 멤버 수: 22)
(level: 4, member_count: 9, name: 하늘을 나는 고슴도치) Guild(UID: 30, 이름: 하늘을 나는 고슴도치, 레벨: 4, 멤버 수: 9)
(level: 4, member_count: 18, name: 무지개빛 해파리 사냥꾼) Guild(UID: 10, 이름: 무지개빛 해파리 사냥꾼, 레벨: 4, 멤버 수: 18)
(level: 5, member_count: 11, name: 전설의 고양이 발바닥) Guild(UID: 15, 이름: 전설의 고양이 발바닥, 레벨: 5, 멤버 수: 11)
(level: 6, member_count: 3, name: 꼬꼬마 유치원 졸업반) Guild(UID: 5, 이름: 꼬꼬마 유치원 졸업반, 레벨: 6, 멤버 수: 3)
(level: 6, member_count: 19, name: 마지막 남은 연필심) Guild(UID: 21, 이름: 마지막 남은 연필심, 레벨: 6, 멤버 수: 19)
(level: 6, member_count: 23, name: 미래를 보는 커피콩) Guild(UID: 32, 이름: 미래를 보는 커피콩, 레벨: 6, 멤버 수: 23)
(level: 7, member_count: 2, name: 심해의 아이스케이크) Guild(UID: 17, 이름: 심해의 아이스케이크, 레벨: 7, 멤버 수: 2)
(level: 7, member_count: 20, name: 비 오는 날의 양동이) Guild(UID: 35, 이름: 비 오는 날의 양동이, 레벨: 7, 멤버 수: 20)
(level: 8, member_count: 5, name: 고독한 달팽이들의 행진) Guild(UID: 7, 이름: 고독한 달팽이들의 행진, 레벨: 8, 멤버 수: 5)
(level: 8, member_count: 16, name: 자정의 오이 피클) Guild(UID: 28, 이름: 자정의 오이 피클, 레벨: 8, 멤버 수: 16)
(level: 9, member_count: 7, name: 그림자 속의 곰돌이) Guild(UID: 11, 이름: 그림자 속의 곰돌이, 레벨: 9, 멤버 수: 7)
(level: 9, member_count: 14, name: 김광란의 펭귄 부대재성) Guild(UID: 4, 이름: 김광란의 펭귄 부대재성, 레벨: 9, 멤버 수: 14)
(level: 10, member_count: 17, name: 소용돌이 치는 감자) Guild(UID: 33, 이름: 소용돌이 치는 감자, 레벨: 10, 멤버 수: 17)
(level: 10, member_count: 28, name: 시간을 달리는 양말) Guild(UID: 18, 이름: 시간을 달리는 양말, 레벨: 10, 멤버 수: 28)
(level: 11, member_count: 21, name: 잊혀진 꿀벌 기사단) Guild(UID: 25, 이름: 잊혀진 꿀벌 기사단, 레벨: 11, 멤버 수: 21)
(level: 12, member_count: 25, name: 투명한 모래시계 수집가) Guild(UID: 14, 이름: 투명한 모래시계 수집가, 레벨: 12, 멤버 수: 25)
(level: 12, member_count: 42, name: 영원한 숙제 제출자) Guild(UID: 34, 이름: 영원한 숙제 제출자, 레벨: 12, 멤버 수: 42)
(level: 13, member_count: 27, name: 우유곽 탐험대) Guild(UID: 29, 이름: 우유곽 탐험대, 레벨: 13, 멤버 수: 27)
(level: 14, member_count: 38, name: 지하철 노선의 비밀) Guild(UID: 24, 이름: 지하철 노선의 비밀, 레벨: 14, 멤버 수: 38)
(level: 15, member_count: 30, name: 영원의 시간 관리팀) Guild(UID: 9, 이름: 영원의 시간 관리팀, 레벨: 15, 멤버 수: 30)
(level: 15, member_count: 36, name: 신비한 큐브 해결사) Guild(UID: 31, 이름: 신비한 큐브 해결사, 레벨: 15, 멤버 수: 36)
(level: 16, member_count: 40, name: 아르헨티나의 마늘 빵) Guild(UID: 20, 이름: 아르헨티나의 마늘 빵, 레벨: 16, 멤버 수: 40)
(level: 17, member_count: 31, name: 중력 거부자 클럽) Guild(UID: 27, 이름: 중력 거부자 클럽, 레벨: 17, 멤버 수: 31)
(level: 18, member_count: 33, name: 천상의 팝콘 배달부) Guild(UID: 16, 이름: 천상의 팝콘 배달부, 레벨: 18, 멤버 수: 33)
(level: 19, member_count: 48, name: 오로라를 굽는 제빵사) Guild(UID: 22, 이름: 오로라를 굽는 제빵사, 레벨: 19, 멤버 수: 48)
(level: 20, member_count: 45, name: 침묵의 우주 정복자) Guild(UID: 12, 이름: 침묵의 우주 정복자, 레벨: 20, 멤버 수: 45)

level로 우선 정렬이 된 후, member_count 그다음 name으로 정렬되는 것을 볼 수 있다.

 for (_, value) in b_tree.range(target..) {
        if vec.len() >= cnt {
            break;
        }

        vec.push((*value).clone());
    }

위 로직을 실행 후, 출력 내용을 보면 아래와 같다.

Guild(UID: 17, 이름: 심해의 아이스케이크, 레벨: 7, 멤버 수: 2)
Guild(UID: 35, 이름: 비 오는 날의 양동이, 레벨: 7, 멤버 수: 20)
Guild(UID: 7, 이름: 고독한 달팽이들의 행진, 레벨: 8, 멤버 수: 5)
Guild(UID: 28, 이름: 자정의 오이 피클, 레벨: 8, 멤버 수: 16)
Guild(UID: 11, 이름: 그림자 속의 곰돌이, 레벨: 9, 멤버 수: 7)
Guild(UID: 4, 이름: 김광란의 펭귄 부대재성, 레벨: 9, 멤버 수: 14)
Guild(UID: 33, 이름: 소용돌이 치는 감자, 레벨: 10, 멤버 수: 17)
Guild(UID: 18, 이름: 시간을 달리는 양말, 레벨: 10, 멤버 수: 28)
Guild(UID: 25, 이름: 잊혀진 꿀벌 기사단, 레벨: 11, 멤버 수: 21)
Guild(UID: 14, 이름: 투명한 모래시계 수집가, 레벨: 12, 멤버 수: 25)

총 10개 가 타겟한 인덱스부터 잘 얻어져오는 것을 볼 수 있다.
추가로 해야하는 작업은 타겟 인덱스를 포함하는 것이 아닌 다음 값 부터 얻어오는 것이다.

    for (_, value) in b_tree.range(target..) {
        if vec.len() >= cnt {
            break;
        }

        vec.push((*value).clone());
    }

    println!("vec len: {}", vec.len());

    vec.remove(0);

    vec

편법으로 11개를 얻어온 뒤, 맨 앞을 지운다. 시간 복잡도의 경우 O(n)이라는데, VecDeque를 사용하면 O(1)의 시간 복잡도로 지울 수 있다. 그러나 넘겨야 하는 타입이 Vec이므로 다시 변환하는 속도까지 계산했을 때 일단은 Vec으로 처리하는 게 좋을 것 같다. n의 수가 그렇게 크지는 않을 것이기 때문이다.

data 1만개 테스트

    let mut rng = rand::rng();

    let mut random_vec = Vec::new();
    let nums: Vec<u32> = (1..100).collect();
    for i in 0..100_00 {
        let level = nums.choose(&mut rng).unwrap();
        let member_count = nums.choose(&mut rng).unwrap();

        random_vec.push(Group::new(i, format!("RANDOM_NAME_{}", i), *level, *member_count));
    }

    random_vec.push(Group::new(17, "심해의 아이스케이크".to_string(), 7, 2),);

    println!("random_vec len: {}", random_vec.len());

rand 크레이트를 사용해 랜덤으로 level과 member_count를 생성해 주었다.

동일한 로직으로 실행했는데 출력이 아래와 같다.

random_vec len: 10001
vec len: 11
elpased time: 3ms
Guild(UID: 259, 이름: RANDOM_NAME_259, 레벨: 7, 멤버 수: 4)
Guild(UID: 3383, 이름: RANDOM_NAME_3383, 레벨: 7, 멤버 수: 4)
Guild(UID: 4308, 이름: RANDOM_NAME_4308, 레벨: 7, 멤버 수: 4)
Guild(UID: 9861, 이름: RANDOM_NAME_9861, 레벨: 7, 멤버 수: 5)
Guild(UID: 4961, 이름: RANDOM_NAME_4961, 레벨: 7, 멤버 수: 6)
Guild(UID: 1980, 이름: RANDOM_NAME_1980, 레벨: 7, 멤버 수: 9)
Guild(UID: 8405, 이름: RANDOM_NAME_8405, 레벨: 7, 멤버 수: 11)
Guild(UID: 4066, 이름: RANDOM_NAME_4066, 레벨: 7, 멤버 수: 12)
Guild(UID: 5595, 이름: RANDOM_NAME_5595, 레벨: 7, 멤버 수: 12)
Guild(UID: 9196, 이름: RANDOM_NAME_9196, 레벨: 7, 멤버 수: 12)

약 3ms의 실행 시간이 나왔다.

그렇다면 데이터를 더 100,000개로 늘려보면?
약 52ms가 나온다. 인 메모리로 처리해도 상관없을 듯?

결론

in memory로 데이터를 캐싱 하여 가지고 있는 상태에서 인덱스를 만들어서 정렬하고, 특정 인덱스를 빠른 속도로 찾는 방법을 찾고 있다. 참조 형태로 BTreeMap을 만들면 쓰기 속도도 보장이 되므로 나쁘지 않은 방법인 것 같다. 100,000 개의 데이터로도 나쁘지 않은 속도가 나왔다. 그러나 더 복잡한 서버에서 여러 로직들이 병렬로 처리되는 경우에도 속도가 보장되는지는 테스트 해봐야 할듯하다.