亿级数据K-Means全栈性能优化，十四小时到两分钟的演进之路

2301_81164012

432人浏览 · 2026-08-03 02:14:32

2301_81164012 · 2026-08-03 02:14:32 发布

前言

近期，我们接到了一个性能优化课设任务：针对 6 亿二维点（k=500） 的朴素K-Means实现，将原本约 14.8 小时的运行时间至少压缩至 30 分钟以内。经过团队的多轮分析与优化，最终将程序运行时间缩短至 2分5秒；

起初，我们认为这只是一次算法优化任务。然而，当数据规模达到 6 亿时，朴素 K-Means 的瓶颈早已不再局限于算法本身，而是演变成了一个典型的系统性能优化问题。

面对如此庞大的数据量，我们首先需要回答三个问题：

数据如何高效读取？ —— 如何减少磁盘 IO 和内存拷贝带来的开销？
数据如何合理存储？ —— 如何设计内存布局，降低 Cache Miss 和线程竞争？
数据如何高效计算？ —— 如何充分利用多核 CPU，并减少无效计算？

围绕这三个问题，我们分别从磁盘 IO、内存访问、CPU Cache、多线程并行以及数据结构与算法等多个层面展开优化。

本文将完整复盘整个优化过程，不仅介绍最终采用的优化方案，也会分享团队踩过的坑、推翻过的错误思路以及背后的原因。文章涉及 操作系统、计算机体系结构、并发、数据结构与算法 等多个领域，希望能够为读者提供一些大规模数据处理与性能优化的实践经验。

一、数据如何高效读取？

对于 6 亿个二维数据点，原始数据以二进制文件的形式存储，总大小约 9GB，IO的业务场景为冷启动 + 全量加载。

K-Means 的每一轮迭代都需要遍历所有数据点，因此无论后续采用何种算法优化，这 9GB 数据至少都需要完整读取一次。如果数据读取本身效率不高，那就会拖慢整体速度。

因此，在正式优化计算逻辑之前，我们首先关注数据读取过程是否可优化？

1.1 原方案是什么？

1.2.1数据从固态硬盘到JVM 堆内存需要三次搬运（两次拷贝加一次解析）通过JMH基准测试，该方式完整读取一次数据需耗时约15s，见下图

1.2 能不能再快一点?

1.2.1 尝试1：使用 mmap 实现"零拷贝"

经过上一节分析，我们发现真正存在优化空间的是 Page Cache → 用户态 这一阶段。

InputStream 方案中，数据已经进入操作系统的 Page Cache，却仍需经历：

Page Cache → byte[]（CPU 拷贝）
byte[] → double[]（CPU 解析）

理论上，如果能够直接访问 Page Cache 中的数据，就可以省去一次内存拷贝，因此我们首先想到的是 Memory Mapped File零拷贝技术。

mmap是一种将文件映射到进程虚拟地址空间的机制。通过映射， CPU可直接根据虚拟地址访问页缓存数据。下图给出了 mmap 从建立映射到访问数据的完整流程。

想法是美好的，但现实是苍白的。通过JMH基准实测mmap并未带来显著的优化，数据如下

1.2.2 说好的"零拷贝"，为什么反而更慢？

起初，我们认为 mmap 能够减少一次数据拷贝，因此理应获得明显的性能提升。

重新分析整个流程后，我们发现：

mmap 省掉的，其实只是 Page Cache → byte[] 这一段 CPU 内存拷贝。

而我们的测试平台内存带宽约为 51.2 GB/s，传输整个 9GB 数据理论耗时仅约：

9 ÷ 51.2 ≈ 0.17 s

相比之下，mmap 首次访问每个页面时，都需要建立虚拟地址到物理页面的映射，并伴随着大量缺页异常处理、页表建立以及 TLB 填充（见下图）。

9GB 数据约包含：

9GB ÷ 4KB ≈ 236 万个页面

即使单次(中断处理+页表与TLB修改）仅产生约 500 ns 的额外开销，总体仍接近 1.2 s。

粗略算下来，在冷启动且只加载一次的业务场景下，引入mmap甚至是负优化。

踩完这个坑，我们团队也意识到了高级的技术并非政治正确的技术道路，而是解决问题的工具。在选择技术之前，我们应该深入分析问题，找到瓶颈所在。

1.2.3 尝试2：定位问题所在——“SSD带宽”

经过上述分析，既然 Page Cache → 用户态 已经几乎没有优化空间，我们决定继续向前追踪整个 IO 链路。也就是说，把目光从：

Page Cache → 用户态

转移到：

SSD → Page Cache

我们的测试环境中，SSD 顺序读取极限带宽约为 3.6 GB/s。理论上，读取完整个 9GB 文件大概仅需：

9 ÷ 3.6 = 2.5 s 。然而实际测试却需要 15 s 左右。

这意味着，真正拖慢程序的，很可能不是数据拷贝，而是磁盘读取阶段本身没有充分发挥硬件性能。

带着这个疑问，我们开始监测程序运行过程中的磁盘性能。

结果如下图所示：

文件读取过程中，SSD 带宽远未达到理论峰值，磁盘利用率仅约 40%。

初步推测，磁盘带宽未打满的原因可能是单线程串行读取导致 I/O 请求并发度不足，无法持续向 SSD 提交足够数量的读请求，从而限制了磁盘带宽的发挥。

为验证这一猜测，我们将文件读取改造为 8 线程并行读取，每个线程负责文件的一个连续区间，以提高 I/O 请求并发度。

实验结果表明，磁盘利用率由约 40% 提升至 100%，文件读取时间由约 15 s 降低至 2.5 s。由此可以说明，原程序的主要瓶颈在于I/O 请求并发度不足，并行读取能够充分发挥 SSD 的带宽性能。

1.3 IO层总结

最初，我们尝试用 mmap 减少一次内存拷贝，但实际测试发现，在冷启动、全量加载的业务场景下，节省的内存拷贝收益并不明显。进一步沿着 IO 链路分析后，我们将优化目标从内存拷贝转向 SSD 带宽利用率，并通过监测磁盘性能发现，真正限制读取速度的是 I/O 请求并发度不足。最终，通过并行读取充分发挥了 SSD 的顺序读带宽，将文件加载时间从约 15 s 降低至 2.5 s。

二、数据如何合理存储？

上一章解决了数据读取问题后，6 亿个二维点已经全部加载到内存中。在 K-Means 的每一轮迭代中，程序都需要遍历6亿个数据点，并不断计算其与聚类中心的距离，因此这些数据会被高频访问。

整个计算过程反复进行内存访问和浮点计算，可以认为这是一个内存受限与CPU密集并存的计算场景。在这种场景下，数据的存储位置将直接影响 CPU 的访问效率。

存储层级	访问耗时 (ns)
寄存器	< 0.5
L1 缓存	~1
L2 缓存	~4
L3 缓存	~20
主存 (RAM)	~100

CPU 访问主存的延迟约为 L1 Cache 的百倍。如果程序频繁发生 Cache Miss，无论你的CPU性能再高，都必须要先等待主存返回数据，这就是冯诺依曼瓶颈的典型表现。因此，在数据全部驻留内存后，优化的重点便转向设计合理的内存布局以减少 Cache Miss。

2.1 工作一：设计缓存友好布局

对于 6 亿个二维点，原程序采用如下存储方式：

优化后，我们将其改为：

2.1.1 这么改的依据在哪？能带来多少收益？

下面分别分析两种存储方式CPU 的缓存访问情况。
假设现在只有 8 个二维点，即需要存储 16 个 double。

原方案：二维数组

Java 中的二维数组本质上是数组的数组。

第一维数组连续存放的是各个第二维数组的引用，而每个第二维数组都是独立对象，在堆内存中通常离散分布。

CPU 每次从主存读取数据时，并不是按元素读取，而是以 Cache Line 为单位进行加载。现代 CPU 的 Cache Line 通常为 64 Byte，而一个引用占 8 Byte，因此一个 Cache Line 可以容纳 8 个引用（是否开启指针压缩不影响下述分析）。

也就是说，当 CPU 首次访问 points[0] 时，会将 points[1] ~ points[7] 的引用一并加载到缓存，因此访问整个第一维数组仅发生 1 次 Cache Miss (假设points[0]地址64字节对齐)。

每个第二维数组仅包含两个 double：X, Y

由于 X 和 Y 位于同一个数组对象内，因此访问 X 时，Y 通常也会被同时加载到缓存。

但不同二维数组对象之间彼此独立，在堆中的地址通常并不连续，因此加载 points[0] 对应的数据，并不会将 points[1] 对应的数据同时加载到缓存。

因此，遍历这 8 个二维点时，每个第二维数组通常都会发生一次 Cache Miss，总计约 8 次 Cache Miss。

合计二维数组方案Cache Miss次数为8 + 1 = 9次。

改进方案：平铺数组

改造后，所有 X 坐标统一存放在 pointX[] 中，所有 Y 坐标统一存放在 pointY[] 中。

由于 Java 一维数组采用连续内存布局，一个 Cache Line（64 Byte）恰好能够容纳：

64 ÷ 8 = 8 个 double

因此，当 CPU 首次访问pointX[0]时，pointX[1] ~ pointX[7] 会被同时加载到缓存 (假设pointX[0]地址64字节对齐）。后续访问这些元素均可直接命中缓存。pointY 同理。

因此，访问完整的 8 个二维点，仅需分别为 pointX 和 pointY 各发生一次 Cache Miss，即总计约 2 次 Cache Miss。

这样改进收益明显吗？

相比于原方案，Cache Miss 次数减少 7 / 9。这意味着，在每轮迭代遍历 6 亿个数据点时，理论上可减少约： $6 \times 10^8 \times \frac{7}{9} \approx 4.67 \times 10^8$ 次 Cache Miss。根据前文给出的存储层级访问延迟，CPU 从主存获取数据相比命中Cache 大约会额外产生 80 ns 左右的访问开销。若仅从理论模型进行估算，则每轮迭代最多可减少约： $4.67 \times 10^8 \times 80\ \text{ns} \approx 37\ \text{s}$ 的访存等待时间。

我们的程序在未进行算法优化时（后续KMeans++优化见下文），总共需要进行约 175 轮迭代，因此从数量级上看，该优化具有带来数千秒收益的潜力。虽然实际运行过程中，由于硬件预取、CPU 流水线、缓存空间不足导致缓存剔除等因素的存在，真实收益不会完全等于上述理论值，但这一估算足以说明：优化数据布局能够显著减少 Cache Miss，从而有效提升程序整体性能。

测试结果

由于 9GB 数据集单次运行耗时较长，为提高实验效率，本节采用 900MB 测试集进行对照实验。

为了验证数据布局优化是否有效，我们分别对两个方案进行对照测试，并使用 perf 统计程序运行前 10 轮迭代期间的缓存访问情况。其中：

rfe04：缓存访问次数
r0404：Cache Miss 次数

图一为二维数组方案，图二为平铺数组方案。

（图一）

（图二）

可以看到，两种方案的缓存访问次数基本保持一致，而 Cache Miss 次数由 3,448,153 次下降至 223,544 次，下降约 93.5%。这说明将二维数组平铺为两个连续的一维数组后，大幅减少了 CPU 在遍历数据时发生 Cache Miss 的概率，与前文的理论分析基本一致。

缓存命中率的提升最终是否能够转化为程序性能提升？下面通过完整运行时间进行验证。

图一为二维数组方案，图二为平铺数组方案。

（图一）

（图二）

实验结果表明，两种方案均进行了 107 轮迭代，算法执行流程完全一致，仅数据存储方式不同。

其中：

二维数组方案总耗时 3479944 ms
平铺数组方案总耗时 3308684 ms

由实验结果可知，仅通过调整数据存储布局，无需修改任何算法逻辑，就能获得 约 171 秒（4.9%总体时间） 的性能提升。这已经可以说明，对于需要遍历数亿数据点的内存密集型程序而言，合理的数据布局能够显著提升程序性能。

2.2 工作二：线程安全解决方案与伪共享解决方案选型

在完成数据存储布局的优化后，我们成功将 Cache Miss 降到了极低水平，数据访存问题解决后，性能优化的重头戏自然转向了如何彻底释放多核 CPU 的算力潜力。

在 K-Means 算法的每轮迭代中，有两个核心阶段：

1. 样本点归类阶段
对于任意一个二维数据点，程序需遍历计算其到所有K个质心的欧氏距离，并判定其归属的最近质心索引 best。这一阶段完全是纯只读操作，任意两点之间的计算完全无数据依赖与状态耦合。
2.簇信息累加阶段
在确定归属后，需要将该点的坐标实时汇聚到全局状态中：

sumX[best] += px;
sumY[best] += py;
cnt[best]++;

样本归类阶段在逻辑上具备极高的数据级并行度，非常适合拆分任务给多线程并发处理；然而，并行化改造却给簇信息累加阶段带来了天然的全局状态共享——如果多个线程同时尝试更新同一个质心 best 的统计量，必会带来严重的竞态问题。

并行环境下如何高效地保证簇信息累加阶段的线程安全，是我们接下来要解决的问题。

所谓的线程安全解决方案，无非可以归类为以下3种：

2.2.1 加锁与内存屏障

常见的 synchronized、ReentrantLock 以及底层的 CAS 原子指令均属于此类。通过加锁或原子指令保障原子性，通过插入内存屏障保障可见性与有序性。

然而，这类方案对追求极致吞吐的 CPU 极不友好：

竞争开销：无论是软件锁导致的线程上下文切换，还是 CAS 的总线锁开销，都会阻碍 CPU 满载运行。
硬件优化受限：内存屏障会直接抑制 CPU 的Pipeline优化，并打破 MESI 协议下的异步化缓存同步。

因此，在 6 亿次高频累加的场景下，这类方案的性能表现极其低下。

注：如果读者想更深层次地学习线程安全的原子、可见、有序性，加深对线程安全的理解。
推荐阅读博主的另外两篇文章《从CPU到内存屏障，再到JMM。深挖并发可见性的底层原理》
《你真的懂原子性吗？》

2.2.2 改造为线程私有

锁优化的圣经是 Lock-Free，而比 Lock-Free 更彻底的，是直接消除共享状态的无共享模式。
严格来说，“改造为线程私有”并不是一种固定的 API，而是一种设计思路。其核心逻辑非常纯粹：将数据按线程数进行分片，私有化分配给各个线程。每个线程在无锁环境下独立修改各自的私有副本，待计算完成后再进行一次轻量级的全局汇总。

这种方案以极小的空间开销换取时间，从根本上清除了锁竞争与内存屏障的开销，极具性能优势。

2.2.3 设计成不可变对象

该方案的核心逻辑为取消"写"操作，多线程只读，自然无竞争。常见实现方式为不修改原对象，每次"变更"都创建新副本并切换引用（如String）。该方案有两个致命缺陷：

解决不了竞态问题（引用切换本身非原子）
高频变更场景下，对象频繁创建GC不友好，性能可能比加锁还差。

2.2.4 方案选型

根据上述分析，“设计为不可变对象”方案在该场景下无法保障线程安全，所以直接摒弃。
下图为方案1与方案2具体实现在同等测试集下的运行结果：

测试结果验证了上述理论分析：相比基于 CAS 和内存屏障实现的原子累加方案，线程私有化方案减少了约 31 秒的运行时间。显著的性能差距证明：在簇信息累加阶段，线程私有方案是最佳选择。

我们的线程私有方案具体实现为：

直接在堆上开辟 3 个物理连续的一维数组，按线程数 $T$ 划分为 $T$ 个逻辑私有片段

double[] localSumX = new double[THREADS * K];
double[] localSumY = new double[THREADS * K];
long[]   localCnt  = new long[THREADS * K];

在 6 亿次点的归属累加过程中，线程 $t$ 算得点落入第 $t$ 簇时，仅更新各自专属的偏移位置

· $localSumX[t * K + i] += x;$
$localSumY[t * K + i] += y;$
$localCnt[t * K + i]++;$

在迭代完成后，所有线程的局部累加结果已经散落在 $T$ 个私有片段中。此时只需要全局归并，将 $T$ 个线程的局部统计量按簇下标合并为最终的全局数值。

聪明的你可以注意到，这 3 个连续数组在物理内存中是顺序铺开的。这意味着 Thread $t$ 片段的尾部元素与 Thread $t + 1$ 片段的头部元素，在内存地址上是连续的。多个线程并发地修改一块连续的地址空间，极易引发 “伪共享” 问题。

2.2.5 伪共享问题的由来

伪共享是MESI协议下的产物，本质就是多个核心各自修改互不相干的数据，却因这些数据共享同一个 64 字节缓存行，导致 MESI 协议频繁广播 RFO 强制作废彼此的缓存，产生业务无效的缓存一致性开销。

2.2.6 怎么规避伪共享问题呢？

既然伪共享问题的起因是被频繁修改的数据同处一个缓存行， 那解决的思路就很直观——不要让他们在同一个缓存行就行了。

要达到这个目的，常见的有两种方式

1、字节填充

这种做法最为直观粗暴。既然 CPU 缓存行以 64 字节为单位划分，那么只需要在频繁修改的变量前后手动填充64字节的Padding，通过物理隔离的方式确保这些数据一定不会被读入到同一个缓存行。

2、内存对齐

相比于 Padding 的暴力填充，利用内存对齐从根源上划分边界要更为优雅。
CPU 载入缓存行时，并非从变量的实际起始地址开始随意截取 64 字节，而是先计算出小于等于当前地址且能被 64 整除的最大基地址，再以此基地址为起点一次性拉取 64 字节。硬件底层通过极简的位运算即可完成寻址：

aligned_address = address & ~63L; // 清零低 6 位

基于这一寻址机制，举个例子，要彻底隔离相邻变量 $p$ 与 $q$ ，我们只需将后置变量 $q$ 的起始地址强制设置为 64 字节对齐：

读取 $q$ 时：由于 $q$ 的起始地址本身已对齐，CPU 将直接以 $q$ 的地址为起始点往后读取 64 字节，绝不会向前夹带前面的变量 $p$ 。
读取 $p$ 时：无论 $p$ 是否对齐，CPU 算出的基地址往后读取 64 字节最远只能触及 $q$ 的起始地址，绝对无法载入 $q$ 。

通过对齐物理边界，两个变量即可实现自然的分行隔离，互不干涉。

因此，为消除多线程间相邻数据块（即上一个线程片段尾部与下一个线程片段头部）的伪共享问题，可采用以下两种方案：

字节填充方案：无需关心基地址，只需在 8 个线程各自修改区域的边界处各填充 64 字节
7 处边界共448字节，即可实现物理隔离。
内存对齐方案：只需让每个线程修改区域的边界按 64 字节对齐。由于 JVM 保证对象的起始地址按 8 字节对齐（可表示为 $8p$ ），且数组的对象头占 16 字节，每个线程处理 500 个 double 元素（即 4000 字节）。因此，第 $k$ 个修改区域边界的实际物理地址可表示为： $Address(k) = 8p + 16 + 4000k\;\;\; (k\in [1, 7], p \in \mathbb{N})$
由于上述式子中的各项均为 8 的倍数，根据整数的封闭性，Address 的结果必然落在
{0，8，16，24，32，40，48，56} 集合中。若要实现 64 字节对齐，则对应需要补齐的字节数分别为 {0，56，48，40，32，24，16，8}。
我们无需为所有边界硬性预留56 字节的保守上限；只需在首个边界（k = 1）处根据运行时基地址动态补齐（最多 56 字节），同时在每个线程区域末尾固定填充 32 字节，使得每个线程的处理块大小占用 4032 字节（4032 % 64 = 0），即可确保后续所有边界天然对齐。此方案仅需约 248 字节即可解决问题。

2.2.7 方案选型

内存对齐方案虽然更为优雅且需要冗余的字节也更少，但公式中的基地址因子 $p$ 是个未知量，所以代价是必须在运行时动态获取地址并计算填充量。更关键的是，JVM 的 GC 垃圾回收过程可能会随时移动对象并改变其物理地址，破坏已对齐的边界。

相比之下，字节填充方案能够在编译期通过静态分配直接规避地址不确定带来的麻烦，实现更加简单高效。而代价仅仅是要多开200字节的冗余空间， 这个数据量是完全可以接受的。

综合考量下，我们团队最终选择字节填充方案来解决伪共享问题。

2.2.8 规避伪共享是否能带来价值？

鉴于默认配置下 $k = 500$ 的数据离散度较高，伪共享的触发具有高度的随机性与偶发性，难以进行精确的定量对比。为此，我们在测试集里将 $k$ 值精简至 5，通过这样来人为放大伪共享的触发概率，其余控制变量保持完全一致，以此精准评估该优化方案对计算性能的真实提升。

图 1：未进行伪共享优化的单轮迭代运行结果。
图 2：采用字节填充规避伪共享的单轮迭代运行结果。

（图一）

（图二）

总结这组数据，投入产出比极其夸张：在极端情况下，我们仅付出了不到 1 MB 的冗余空间作为填充代价，就从硬件层面消除了约19.6 亿次 L1 Cache Miss 和约14.7 亿次 L3 Cache Miss。

这不仅说明我们的方案是能带来实际价值的，同时也警示了我们：在并发设计中必须要高度重视伪共享问题。

三、数据如何高效计算

如果说磁盘 I/O 优化解决的是“数据如何快速进入内存”，内存布局优化解决的是“CPU 如何高效访问数据”，那么进入计算阶段后，我们还需要进一步思考三个问题：

如何减少不必要的计算？
如何充分利用计算资源？
如何提升计算资源的计算速度？

针对第一个问题，我们可以通过数据结构与算法优化，降低 K-Means 中大量重复距离计算带来的开销。

而针对第二个问题，则可以利用并行计算充分发挥 CPU 多核能力，提高程序整体吞吐量。

对于第三个问题而言，除了升级更好的硬件设施后别无他法，本文将不展开对该问题的讨论。

因此，本章主要从两个方向展开：

3.1 数据结构与算法

在 K-Means 算法中，计算量最大的部分是 样本点与质心之间的距离计算。
对于每一个数据点，都需要遍历所有质心，找到距离最近的类别中心。K-Means 每轮迭代的计算复杂度为： $O(N * K)$

本次实验数据规模：N ≈ 6亿，K = 500。这意味着每一轮迭代需要进行3000亿次距离计算。

如果继续使用最原始的暴力搜索：

for 每个数据点:
    
    for 每个质心:
        
        计算距离
        
    找最近质心

大量重复且没有意义的距离计算会产生不少开销，因此，需要从算法层面减少计算量。

3.1.1 KMeans++优化初始化过程

传统 K-Means 通常随机选择初始质心，但随机初始化容易导致质心分布不均，使算法需要更多轮迭代才能收敛。

因此采用 KMeans++ 算法进行质心初始化。

KMeans++ 不再完全随机选择质心，而是根据数据点与已有质心之间的距离进行概率选择，使初始质心尽可能分散，覆盖更广的数据空间。

相比随机初始化，KMeans++ 能够提供更好的初始聚类中心，减少后续迭代次数。其初始化复杂度为： O(NK), 在并行化改造后，整个KMeans++过程约占用415秒。

下图分别展示了随机初始化与 KMeans++ 初始化下的迭代收敛情况
（左图：随机初始化；右图：KMeans++ 初始化）：

可以看到，引入 KMeans++ 后，算法收敛迭代次数减少约 165 轮。按照当前单轮迭代耗时 223 秒 计算（串行且无算法优化），仅 KMeans++ 这一项优化即可带来约 10.3小时 的计算收益，该收益远高于初始化阶段引入的额外计算成本，大幅提升了整体算法执行效率。

注：每轮迭代耗时并非均匀，前后差异较大，计算结果较为粗略。

3.1.2 Elkan 三角不等式剪枝：避免重复计算

传统 K-Means 的一个问题是：

在每轮迭代中，即使质心只发生了很小的移动，也会重新计算所有点到所有质心的距离。

但实际运行过程中：

相邻两轮迭代之间，绝大部分数据点所属类别并不会发生变化。

Elkan 算法利用三角不等式：如果一个点当前属于质心 C，

那么其他质心 C' 到该点的距离一定满足： $d(x,C') \geq d(x,C) - d(C,C')$

当能够确定其他质心不可能比当前质心更近，那么无需重新计算距离，可以直接保留当前分类结果。

3.1.3 KD-Tree：优化剩余点的最近质心搜索

虽然 Elkan 可以过滤大量计算，但是仍然存在部分点无法满足剪枝条件。对于这些点，仍然需要寻找最近质心。传统方式：

for(int c = 0;c < k;c++){
    calculateDistance(point, centroid[c]);
}

时间复杂度O(K)，当K = 500, N = 6亿时依然需要进行大量搜索。因此引入 KD-Tree。

KD-Tree 的核心思想是：

利用数据空间分布特征，提前排除不可能成为最近质心的区域，避免遍历所有质心。

相比暴力搜索： $O(K)$
KD-Tree 在平均情况下可以将最近邻搜索降低到： $O(logK)$
原本每个数据点检查500个质心变成每个数据点通过空间索引快速定位候选区域，只检查少量可能的质心。

3.1.4 算法优化后的整体计算流程

最终，K-Means 的距离计算流程由最初的暴力搜索：

优化为：

通过两层优化：

第一层：

Elkan 三角不等式，减少大量重复距离计算。

第二层：

KD-Tree 空间索引

降低无法剪枝数据点的搜索成本。

最终时间复杂度从 O(N * K) 转变为 O(N(α+(1−α)logK))，其中 α 为 Elkan 剪枝比例。

3.1.5 Elkan + KD-Tree 剪枝优化效果验证

为了验证优化效果，将优化版本与原始暴力计算版本进行对比测试，实验结果如下：

从实验结果可以看到，该组合带来了 7674s（约2.13h）的收益。该实验说明，对于大规模数据场景，减少无效计算比单纯优化计算速度更加重要。

3.2 并行计算

前文已经从多个角度介绍了并行化改造过程：从 IO 层面的并行读取，到 KMeans++ 初始化过程的并行加速，再到计算阶段的任务拆分。

这些优化的核心目标都是提高硬件资源利用率：

让 SSD 能够持续提交多个 IO 请求，避免磁盘带宽浪费；
让多个 CPU 核心同时参与计算，避免CPU资源浪费；

相信读者通过前文已经可以了解我们并行改造具体做了什么，因此本节将不再赘述具体的并行实现方式，而是通过实验数据，统一评估所有并行化改造带来的整体性能收益。

下图展示了 IO 阶段串行读取与并行读取的耗时对比。

由实验结果可知，IO的并行化改造带来了约 13 秒的收益。

下图展示了 KMeans++ 初始化过程串行执行与并行执行的耗时差异。

由实验结果可知，对KMeans++的并行化改造带来了约263秒的收益。

下图展示了 KMeans 单轮迭代过程在 KD-Tree + Elkan 优化基础上，串行执行与并行执行的性能差异。

由实验结果可知，该并行化改造给单轮迭代带来了约644秒的收益。在结合KMeans++优化后，由于算法收敛轮次由175轮降低至10轮，因此在最终优化方案中，该并行化改造实际减少约： $644s * 10 = 6440s \approx 1.8h$ 的计算时间。

综上，在最终版本中，并行化改造累计带来约 1.86 小时的性能收益。

总结

初始版本在完整数据集上的运行时间约为 14.8 小时。通过逐层分析程序执行链路，并针对不同阶段的性能瓶颈进行优化：

优化方向	性能收益
缓存友好设计	在 700MB 测试集下减少约 171 秒运行时间
并行化改造	减少约 1.86 小时计算耗时
数据结构与算法优化	减少约 12.43 小时计算耗时

（注：上述收益基于不同优化阶段的独立对比测试结果，用于衡量各优化方向的性能贡献，实际收益不可简单线性叠加。）

下图展示了优化前后的运行耗时对比：左侧为初始版本执行时间，右侧为最终优化版本执行时间。程序从 14.8 小时降低至约 2 分钟，实现了数量级的性能提升。

这次优化实践让我更加深刻地认识到：

性能优化的本质，不是寻找某个“万能技术”，而是建立从业务场景到硬件执行层的完整分析链路，找到真正的性能瓶颈，并选择最合适的解决方案。

只有真正理解程序如何运行，才能让代码突破语言和框架的限制，充分发挥底层硬件的计算能力。

实验环境

CPU：8C16T，3.1 GHz
内存：32 GB DDR4（理论带宽约 51.2 GB/s）
SSD：顺序读取上限约 3.6 GB/s
操作系统：Windows + Ubuntu
JDK：Java 21

写下这篇博客时，时间已经来到了 8 月 3 日凌晨一点半。

这是我大三下阶段的最后一篇技术总结，也是我大学学习过程中的一次阶段性记录。

回顾过去的三年，有独自啃技术书籍时的迷茫与煎熬，也有和舍友一起参加算法竞赛时的激情与热血，还有一起为了一个 Bug 反复调试到深夜的无奈，也有项目最终跑通时那份难以言喻的喜悦。

技术学习的道路并不总是一帆风顺，但正是在一次次阅读、实践、踩坑和复盘中，我逐渐找到了自己感兴趣的方向，也更加坚定了继续深入探索计算机技术的想法。

一个月后，秋招即将开始；一年后，我也将正式踏入社会。

我不知道未来会面临什么样的选择，但希望自己无论身处什么阶段，都能够保持现在这份对技术的热爱与探索欲，始终做一个有激情的的人。

这篇洋洋洒洒一万两千字的博客，到这里就结束了。

最后，由衷感谢每一位读到这里的读者，感谢您的阅读，也感谢我们因技术产生的这一次相遇。

愿我们都能在自己的道路上不断成长。

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

告别几KB/s！2026 PanDownload复活版与百度网盘加速解析终极指南

应用软件配置与临时数据积压原因：应用软件在长期运行过程中会产生大量的日志文件和临时数据，如果这些历史数据积压过多，容易影响软件内部的逻辑运转。操作系统资源占用过高原因：当电脑或手机同时开启了多个大型软件，或者系统正在后台进行自动更新、磁盘碎片整理等任务时，硬件处理能力会被大量分摊，限制了数据写入本地存储盘的实际速度。数据文件分散与碎片化处理原因：如果一次性提取成百上千个零散的小文件，系统需要

openEuler 社区

PanDownload还能用吗？2026百度网盘加速与直链解析全平台方法汇总

建议：如果条件允许，可以尝试切换不同的网络连接方式，例如从宽带网络切换到移动热点，或者更换其他运营商的网络环境进行尝试，从而绕开拥堵的跨网节点。操作系统并发连接限制与设置问题原因：部分操作系统默认对单应用的网络并发连接数做出了限制，或者系统内部的网络协议栈配置不佳，导致软件无法充分利用当前的物理带宽进行多通道数据接收。路由器长时间运行导致缓存堆积原因：家中的无线路由器在连续工作数周甚至数月后，