编程珠玑续

参考资料

• 编程珠玑续

性能监视工具

• 监视你哪里耗时最多

关联数组

• 就是字典

程序员的忏悔

• 强调其所谓脚手架 (测试框架)

自描述数据

• 古老的技巧早已转化为现代的默认工具...

劈开戈尔迪之结

• 和第一性原理是一个概念, 我称之为假智鸡汤
• 贝尔实验室的人真爽啊

计算机科学箴言集

• 略

粗略估算

• 同上一本

人员备忘录

• 略

小语言

• 略

文档设计

• 略

图形化输出

• 略

对调查的研究

• 略

绝妙的取样

// 辅助函数: 生成 [min, max] 范围内的随机整数
int get_rand(int min, int max);

// 算法 F2: 随机抽样
void floyd_f2(int M, int N, int *result_array) {
    int size = 0; // 当前集合 S 的大小

    // 核心循环: 从 N-M+1 到 N
    for (int J = N - M + 1; J <= N; J++) {
        int T = get_rand(1, J);

        // 检查 T 是否已经在集合 S 中 (线性查找)
        // 注意：如果 M 很大, 这里应该用哈希表优化
        bool t_in_s = false;
        for (int i = 0; i < size; i++) {
            if (result_array[i] == T) {
                t_in_s = true;
                break;
            }
        }

        if (!t_in_s) {
            // T 不在 S 中, 插入 T
            result_array[size++] = T;
        } else {
            // T 已在 S 中, 插入 J
            result_array[size++] = J;
        }
    }
}

//算法 P: 随机排列
void floyd_p(int M, int N, int *result_array) {
    int size = 0; // 当前序列 S 的大小

    for (int J = N - M + 1; J <= N; J++) {
        int T = get_rand(1, J);

        // 检查 T 是否在序列 S 中, 并记录位置
        int t_index = -1;
        for (int i = 0; i < size; i++) {
            if (result_array[i] == T) {
                t_index = i;
                break;
            }
        }

        if (t_index == -1) {
            // 情况1: T 不在 S 中 -> 将 T 插入到序列最前面
            // 将现有元素全部后移一位
            if (size > 0) {
                memmove(&result_array[1], &result_array[0], size * sizeof(int));
            }
            result_array[0] = T;
        } else {
            // 情况2: T 在 S 中 -> 将 J 插入到 T 的后面
            // 将 T 后面的元素全部后移一位
            int items_to_move = size - (t_index + 1);
            if (items_to_move > 0) {
                memmove(&result_array[t_index + 2], &result_array[t_index + 1], items_to_move * sizeof(int));
            }
            result_array[t_index + 1] = J;
        }
        size++;
    }
}

编写数值计算程序

• 牛顿迭代法加速求欧式距离的平方根操作 (详见数值分析)

选择

• 减治法求第 K 小元素