数据结构与算法 / 系统课时

封装可复用算法组件

封装可复用算法组件

算法进入公共代码库后,正确结果只是最低要求,还要明确参数、排序规则、输入是否会被修改以及结果能否被外部篡改。本课将把 Top K 选择封装成可复用的泛型组件。

学习目标

  • 设计与具体业务类型解耦的算法接口
  • 明确参数校验、比较器方向和边界行为
  • 使用大小为 k 的堆返回不可变 Top K 结果

从算法实现到组件契约

公共组件应把调用方必须决定的策略放进接口,而不是写死在实现中。Top K 选择需要输入列表、数量 k 和比较器;比较器定义“更大”代表更优,返回结果按从优到弱排列。

组件还要说明是否允许 null、k=0 如何处理、是否修改原列表,以及返回集合能否被修改。契约越明确,调用方越不需要阅读内部代码猜测行为。

Top K 组件结构图

堆如何保留 Top K

遍历元素时,用小顶堆保存当前最优的 k 个值。堆顶是其中最弱的元素;新值更优时,删除堆顶并加入新值。遍历完成后再按比较器逆序排序,因为优先队列的迭代顺序不等于完整有序结果。

该方案遍历 n 个元素,每次堆调整最多需要 O(log⁡k)O(\log k),总时间复杂度为 O(nlog⁡k)O(n\log k),额外空间为 O(k)O(k)。当 k 远小于 n 时,通常比复制全部数据后排序更合适。

主示例

下面的 Java 17 示例用泛型和比较器封装 Top K。实现不修改输入列表,拒绝 null 元素和越界的 k,并通过 List.copyOf 返回不可修改的结果结构。

java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class ReusableAlgorithmComponentDemo {
    private record Product(String name, int score) {
    }

    private static final class TopKSelector<T> {
        List<T> select(List<T> values, int k, Comparator<? super T> comparator) {
            // 公共组件尽早校验契约,避免在比较器或堆操作中延迟失败。
            if (values == null) {
                throw new IllegalArgumentException("输入列表不能为空");
            }
            if (comparator == null) {
                throw new IllegalArgumentException("比较器不能为空");
            }
            if (k < 0 || k > values.size()) {
                throw new IllegalArgumentException("k 超出范围");
            }

            // 小顶堆的堆顶始终是当前 Top K 中最弱的元素。
            PriorityQueue<T> heap = new PriorityQueue<>(Math.max(1, k), comparator);
            for (T value : values) {
                if (value == null) {
                    throw new IllegalArgumentException("元素不能为 null");
                }
                if (heap.size() < k) {
                    heap.offer(value);
                } else if (k > 0 && comparator.compare(value, heap.peek()) > 0) {
                    heap.poll();
                    heap.offer(value);
                }
            }

            // 堆的迭代顺序不保证全局有序,返回前必须显式排序。
            List<T> result = new ArrayList<>(heap);
            result.sort(comparator.reversed());
            return List.copyOf(result);
        }
    }

    public static void main(String[] args) {
        List<Product> products = List.of(
                new Product("A", 90),
                new Product("B", 75),
                new Product("C", 95),
                new Product("D", 88)
        );

        Comparator<Product> byScoreThenName =
                Comparator.comparingInt(Product::score).thenComparing(Product::name);

        List<Product> result =
                new TopKSelector<Product>().select(products, 3, byScoreThenName);

        System.out.println("Top 3:");
        for (Product product : result) {
            System.out.println(product.name() + ": " + product.score());
        }

        // 通过一次失败的修改验证结果结构不可变。
        boolean immutable;
        try {
            result.add(new Product("E", 100));
            immutable = false;
        } catch (UnsupportedOperationException exception) {
            immutable = true;
        }
        System.out.println("结果不可修改: " + immutable);
        System.out.println("输入顺序未改变: " + products.get(0).name().equals("A"));
    }
}

将代码保存为 ReusableAlgorithmComponentDemo.java,再编译运行:

bash
javac ReusableAlgorithmComponentDemo.java
java ReusableAlgorithmComponentDemo

预期输出:

text
Top 3:
C: 95
A: 90
D: 88
结果不可修改: true
输入顺序未改变: true

边界与交付检查

k=0 应返回空列表,k=values.size() 应返回全部元素的有序副本。同分规则由比较器决定,必须写入文档并通过测试固定下来。返回列表不可修改,不代表其中的元素自动不可变;若元素是可变对象,调用方仍可能改变其内部状态。

发布公共组件前,应测试正常结果、空列表、边界 k、非法参数、同分顺序、输入未修改和结果不可修改。还应注明线程安全性:本实现每次调用只使用局部状态,组件本身无共享可变字段。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

封装可复用算法组件

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通