在游戏开发和数据分析中，处理和分析分数数据是一项常见任务。在 Exercism 的 “high-scores” 练习中，我们需要实现一个分数管理器，能够存储分数并提供各种查询功能。这不仅能帮助我们掌握数据结构设计，还能深入学习Rust中的所有权、生命周期和数据处理技巧。

什么是High Scores问题？

High Scores问题要求我们实现一个分数管理器，支持以下功能：

  1. 存储分数列表
  2. 查询所有分数
  3. 查询最新分数（最后一个）
  4. 查询个人最佳分数（最高分）
  5. 查询个人前三名分数（按分数排序的前三个）

这个问题模拟了游戏中的分数管理需求，是数据处理和分析的典型场景。

让我们先看看练习提供的结构和函数签名：

#[derive(Debug)]
pub struct HighScores;

impl HighScores {
    pub fn new(scores: &[u32]) -> Self {
        unimplemented!(
            "Construct a HighScores struct, given the scores: {:?}",
            scores
        )
    }

    pub fn scores(&self) -> &[u32] {
        unimplemented!("Return all the scores as a slice")
    }

    pub fn latest(&self) -> Option<u32> {
        unimplemented!("Return the latest (last) score")
    }

    pub fn personal_best(&self) -> Option<u32> {
        unimplemented!("Return the highest score")
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        unimplemented!("Return 3 highest scores")
    }
}

我们需要实现一个完整的分数管理器，支持存储和查询各种分数信息。

设计分析

1. 核心组件

  1. HighScores结构体：存储分数数据
  2. new函数：创建HighScores实例
  3. scores方法：返回所有分数的引用
  4. latest方法：返回最新分数
  5. personal_best方法：返回最高分数
  6. personal_top_three方法：返回前三名分数

2. 技术要点

  1. 所有权和生命周期：正确处理数据的所有权和引用生命周期
  2. Option类型：处理空数据的情况
  3. Vec操作：排序和切片操作
  4. 数据复制：在需要时进行数据复制

完整实现

1. 基础实现

#[derive(Debug)]
pub struct HighScores<'a> {
    scores: &'a [u32],
}

impl<'a> HighScores<'a> {
    pub fn new(scores: &'a [u32]) -> Self {
        HighScores { scores }
    }

    pub fn scores(&self) -> &[u32] {
        self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        let mut sorted_scores = self.scores.to_vec();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a)); // 降序排序
        sorted_scores.truncate(3);
        sorted_scores
    }
}

2. 使用Owned数据的实现

#[derive(Debug)]
pub struct HighScores {
    scores: Vec<u32>,
}

impl HighScores {
    pub fn new(scores: &[u32]) -> Self {
        HighScores {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a)); // 降序排序
        sorted_scores.truncate(3);
        sorted_scores
    }
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn test_list_of_scores() {
    let expected = [30, 50, 20, 70];
    let high_scores = HighScores::new(&expected);
    assert_eq!(high_scores.scores(), &expected);
}

应该能够正确存储和返回所有分数。

#[test]
fn test_latest_score() {
    let high_scores = HighScores::new(&[100, 0, 90, 30]);
    assert_eq!(high_scores.latest(), Some(30));
}

最新分数应该是数组中的最后一个元素。

#[test]
fn test_latest_score_empty() {
    let high_scores = HighScores::new(&[]);
    assert_eq!(high_scores.latest(), None);
}

空数组应该返回None。

#[test]
fn test_personal_best() {
    let high_scores = HighScores::new(&[40, 100, 70]);
    assert_eq!(high_scores.personal_best(), Some(100));
}

个人最佳分数应该是数组中的最大值。

#[test]
fn test_personal_top_three() {
    let high_scores = HighScores::new(&[10, 30, 90, 30, 100, 20, 10, 0, 30, 40, 40, 70, 70]);
    assert_eq!(high_scores.personal_top_three(), vec![100, 90, 70]);
}

前三名应该是按分数排序的前三个分数。

#[test]
fn test_personal_top_three_with_less_than_three_scores() {
    let high_scores = HighScores::new(&[30, 70]);
    assert_eq!(high_scores.personal_top_three(), vec![70, 30]);
}

当分数少于三个时，应返回所有分数。

性能优化版本

考虑性能的优化实现：

#[derive(Debug)]
pub struct HighScores {
    scores: Vec<u32>,
}

impl HighScores {
    pub fn new(scores: &[u32]) -> Self {
        HighScores {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        // 对于小数组，直接排序是高效的
        if self.scores.len() <= 3 {
            let mut sorted_scores = self.scores.clone();
            sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
            return sorted_scores;
        }
        
        // 对于大数组，使用部分排序更高效
        let mut scores_copy = self.scores.clone();
        scores_copy.select_nth_unstable_by(2, |a, b| b.cmp(a));
        scores_copy.truncate(3);
        scores_copy.sort_unstable_by(|a, b| b.cmp(a));
        scores_copy
    }
}

// 使用缓存优化的版本
#[derive(Debug)]
pub struct HighScoresCached {
    scores: Vec<u32>,
    cached_top_three: Option<Vec<u32>>,
}

impl HighScoresCached {
    pub fn new(scores: &[u32]) -> Self {
        HighScoresCached {
            scores: scores.to_vec(),
            cached_top_three: None,
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&mut self) -> Vec<u32> {
        if let Some(ref cached) = self.cached_top_three {
            cached.clone()
        } else {
            let mut sorted_scores = self.scores.clone();
            sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
            sorted_scores.truncate(3);
            self.cached_top_three = Some(sorted_scores.clone());
            sorted_scores
        }
    }
    
    // 当分数更新时清除缓存
    pub fn add_score(&mut self, score: u32) {
        self.scores.push(score);
        self.cached_top_three = None;
    }
}

错误处理和边界情况

考虑更多边界情况的实现：

#[derive(Debug, PartialEq)]
pub enum HighScoresError {
    EmptyScores,
    InvalidIndex,
}

#[derive(Debug)]
pub struct HighScores {
    scores: Vec<u32>,
}

impl HighScores {
    pub fn new(scores: &[u32]) -> Self {
        HighScores {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        if self.scores.is_empty() {
            return None;
        }
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
        sorted_scores.truncate(3);
        sorted_scores
    }
    
    // 扩展功能：获取前N名
    pub fn personal_top(&self, n: usize) -> Vec<u32> {
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
        sorted_scores.truncate(n);
        sorted_scores
    }
    
    // 扩展功能：获取指定排名的分数
    pub fn score_at_rank(&self, rank: usize) -> Option<u32> {
        if rank == 0 || rank > self.scores.len() {
            return None;
        }
        
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
        sorted_scores.get(rank - 1).copied()
    }
    
    // 扩展功能：计算平均分
    pub fn average_score(&self) -> Option<f64> {
        if self.scores.is_empty() {
            return None;
        }
        
        let sum: u32 = self.scores.iter().sum();
        Some(sum as f64 / self.scores.len() as f64)
    }
}

扩展功能

基于基础实现，我们可以添加更多功能：

#[derive(Debug)]
pub struct HighScores {
    scores: Vec<u32>,
}

impl HighScores {
    pub fn new(scores: &[u32]) -> Self {
        HighScores {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable_by(|a, b| b.cmp(a));
        sorted_scores.truncate(3);
        sorted_scores
    }
    
    // 添加新分数
    pub fn add_score(&mut self, score: u32) {
        self.scores.push(score);
    }
    
    // 批量添加分数
    pub fn add_scores(&mut self, scores: &[u32]) {
        self.scores.extend_from_slice(scores);
    }
    
    // 获取分数统计信息
    pub fn statistics(&self) -> ScoreStatistics {
        if self.scores.is_empty() {
            return ScoreStatistics {
                count: 0,
                sum: 0,
                average: 0.0,
                median: 0.0,
                best: 0,
                worst: 0,
            };
        }
        
        let count = self.scores.len();
        let sum: u32 = self.scores.iter().sum();
        let average = sum as f64 / count as f64;
        
        let mut sorted_scores = self.scores.clone();
        sorted_scores.sort_unstable();
        
        let median = if count % 2 == 0 {
            let mid = count / 2;
            (sorted_scores[mid - 1] as f64 + sorted_scores[mid] as f64) / 2.0
        } else {
            sorted_scores[count / 2] as f64
        };
        
        let best = *sorted_scores.last().unwrap();
        let worst = *sorted_scores.first().unwrap();
        
        ScoreStatistics {
            count,
            sum,
            average,
            median,
            best,
            worst,
        }
    }
    
    // 获取分数分布
    pub fn score_distribution(&self) -> Vec<(u32, usize)> {
        use std::collections::HashMap;
        
        let mut counts = HashMap::new();
        for &score in &self.scores {
            *counts.entry(score).or_insert(0) += 1;
        }
        
        let mut distribution: Vec<(u32, usize)> = counts.into_iter().collect();
        distribution.sort_unstable_by(|a, b| b.0.cmp(&a.0));
        distribution
    }
    
    // 检查是否有新纪录
    pub fn is_personal_best(&self, score: u32) -> bool {
        match self.personal_best() {
            Some(best) => score > best,
            None => true,
        }
    }
    
    // 获取分数趋势（最近5个分数的变化）
    pub fn recent_trend(&self) -> Option<ScoreTrend> {
        if self.scores.len() < 2 {
            return None;
        }
        
        let recent_scores: Vec<u32> = if self.scores.len() >= 5 {
            self.scores[self.scores.len()-5..].to_vec()
        } else {
            self.scores.clone()
        };
        
        let first = recent_scores[0];
        let last = *recent_scores.last().unwrap();
        
        Some(ScoreTrend {
            scores: recent_scores,
            improvement: last as i32 - first as i32,
        })
    }
}

pub struct ScoreStatistics {
    pub count: usize,
    pub sum: u32,
    pub average: f64,
    pub median: f64,
    pub best: u32,
    pub worst: u32,
}

pub struct ScoreTrend {
    pub scores: Vec<u32>,
    pub improvement: i32, // 正数表示进步，负数表示退步
}

// 支持排行榜功能的版本
pub struct Leaderboard {
    entries: Vec<ScoreEntry>,
}

#[derive(Debug, Clone)]
pub struct ScoreEntry {
    pub player_name: String,
    pub score: u32,
    pub timestamp: std::time::SystemTime,
}

impl Leaderboard {
    pub fn new() -> Self {
        Leaderboard {
            entries: Vec::new(),
        }
    }
    
    pub fn add_score(&mut self, player_name: String, score: u32) {
        self.entries.push(ScoreEntry {
            player_name,
            score,
            timestamp: std::time::SystemTime::now(),
        });
    }
    
    pub fn top_scores(&self, count: usize) -> Vec<&ScoreEntry> {
        let mut sorted_entries = self.entries.iter().collect::<Vec<_>>();
        sorted_entries.sort_by(|a, b| b.score.cmp(&a.score));
        sorted_entries.truncate(count);
        sorted_entries
    }
    
    pub fn player_best(&self, player_name: &str) -> Option<u32> {
        self.entries
            .iter()
            .filter(|entry| entry.player_name == player_name)
            .map(|entry| entry.score)
            .max()
    }
}

实际应用场景

High Scores在实际开发中有以下应用：

  1. 游戏开发：管理游戏分数和排行榜
  2. 数据分析：处理和分析性能数据
  3. 教育系统：管理学生成绩和排名
  4. 电商平台：处理商品评分和排名
  5. 健身应用：跟踪运动成绩和个人记录
  6. 金融系统：处理股票价格和交易数据
  7. 监控系统：分析系统性能指标
  8. 社交网络：处理用户活跃度和排名

算法复杂度分析

  1. 时间复杂度：

    • scores(): O(1) - 直接返回引用
    • latest(): O(1) - 获取最后一个元素
    • personal_best(): O(n) - 遍历查找最大值
    • personal_top_three(): O(n log n) - 排序操作

  2. 空间复杂度：

    • 基础操作: O(1) - 不需要额外空间
    • personal_top_three(): O(n) - 需要复制数组进行排序

与其他实现方式的比较

// 使用BinaryHeap实现的高效版本
use std::collections::BinaryHeap;

pub struct HighScoresHeap {
    scores: Vec<u32>,
    top_three: Option<BinaryHeap<u32>>,
}

impl HighScoresHeap {
    pub fn new(scores: &[u32]) -> Self {
        HighScoresHeap {
            scores: scores.to_vec(),
            top_three: None,
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&mut self) -> Vec<u32> {
        if let Some(ref heap) = self.top_three {
            let mut vec: Vec<u32> = heap.iter().copied().collect();
            vec.sort_unstable_by(|a, b| b.cmp(a));
            vec.truncate(3);
            vec
        } else {
            let mut heap = BinaryHeap::new();
            for &score in &self.scores {
                if heap.len() < 3 {
                    heap.push(score);
                } else if let Some(&min) = heap.peek() {
                    if score > min {
                        heap.pop();
                        heap.push(score);
                    }
                }
            }
            self.top_three = Some(heap.clone());
            let mut vec: Vec<u32> = heap.into_iter().collect();
            vec.sort_unstable_by(|a, b| b.cmp(a));
            vec
        }
    }
}

// 使用第三方库的实现
// [dependencies]
// itertools = "0.10"

use itertools::Itertools;

pub struct HighScoresItertools {
    scores: Vec<u32>,
}

impl HighScoresItertools {
    pub fn new(scores: &[u32]) -> Self {
        HighScoresItertools {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        self.scores
            .iter()
            .sorted_by(|a, b| b.cmp(a))
            .take(3)
            .copied()
            .collect()
    }
}

// 函数式风格实现
pub struct HighScoresFunctional {
    scores: Vec<u32>,
}

impl HighScoresFunctional {
    pub fn new(scores: &[u32]) -> Self {
        HighScoresFunctional {
            scores: scores.to_vec(),
        }
    }

    pub fn scores(&self) -> &[u32] {
        &self.scores
    }

    pub fn latest(&self) -> Option<u32> {
        self.scores.last().copied()
    }

    pub fn personal_best(&self) -> Option<u32> {
        self.scores.iter().max().copied()
    }

    pub fn personal_top_three(&self) -> Vec<u32> {
        self.scores
            .iter()
            .fold(Vec::new(), |mut acc, &score| {
                acc.push(score);
                acc.sort_unstable_by(|a, b| b.cmp(a));
                acc.truncate(3);
                acc
            })
    }
}

总结

通过 high-scores 练习，我们学到了：

  1. 数据结构设计：掌握了如何设计合适的数据结构来存储和管理数据
  2. 所有权和生命周期：深入理解了Rust的所有权系统和生命周期概念
  3. 数据处理：学会了排序、过滤和切片等数据处理技巧
  4. 错误处理：熟练使用Option类型处理可能为空的情况
  5. 性能优化：了解了不同实现方式的性能特点和优化策略
  6. API设计：学会了设计简洁易用的公共接口

这些技能在实际开发中非常有用，特别是在构建数据管理系统、排行榜系统、数据分析工具等场景中。High Scores虽然是一个简单的练习，但它涉及到了数据结构设计、所有权管理、数据处理和API设计等许多核心概念，是学习Rust实用编程的良好起点。

通过这个练习，我们也看到了Rust在数据处理方面的强大能力，以及如何用安全且高效的方式实现数据管理系统。这种结合了安全性和性能的语言特性正是Rust的魅力所在。

# rust # 算法 # 网络
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

孟加拉语OCR数据集-19610个文件覆盖40地区-手写单词与文本检测识别-完整原始图像与标注-适用于模型训练与自然语言处理应用

avatar AtomGit开源社区
cover

【新手必看】5分钟搞定Claude配置：官方+weelinking双方案

avatar AtomGit开源社区
cover

拒绝盲目海投！我开发了一款真正懂你的AI简历助手

avatar AtomGit开源社区