wxf666

34 楼纠正下数据，实测轻薄本 i5-8250U ，1.5 秒归并排序 320W 个 336 长度的随机字符串，约 6500W 次比较。

- 多线程快排/归并：总计 6017 亿次比较，我的轻薄本 8 线程需 0.5 小时。
- 单线程小根堆：总计 1910 亿次比较，单线程需 1.2 小时。

差不太远。。

想到个方法，预计耗时：10 小时，准确率：100% 剔除重复行。


## 简单流程

1. 分块排序。
2. 同时循环每块，删掉非首次出现的重复行。
3. 分别循环每块，按行号顺序，输出未被删掉的行。


## 详细流程

1. 分块 240GB 文件，每块排序后，写入固态。同时保存每行长度+原始偏移量（约 (240 << 30) / 335 * 8 / 1024 ^ 3 = 5.7 GB ）。
2. 利用小根堆，流式排序（按 <string, offset> 排）所有分块每一行。非首次出现行，保存该行偏移量，到相应块的删除名单里。
3. 循环每块，排序原始偏移量、删除名单，按序输出（未被删除的）相应行，至最终文件。


## 耗时计算

1. 顺序读写：9 小时（ 3 次顺序读，2 次顺序写，假设都为 1GB/s ）。
2. 内存字符串排序：< 1 小时（实测轻薄本 i5-8250U ，每秒归并排序 200W 次 335 长度的随机字符串，约 6900W 次比较）。
- 多线程快排/归并：`(每块行数 = (240 << 30) / 335) * log2(每块行数) * 块数 = 6017 亿` 次比较，我的轻薄本 8 线程需 0.3 小时。
- 单线程小根堆：`202e8 * log2(块数 = 6.2 * 1024 / 240 = 26.5) * 2 = 1910 亿` 次比较，需 0.7 小时。

@wanghr64 #5 老板：帮我统计该员工认真工作时长？

@testonly #5 听起来有点像网络世界的房产税？

每年贡献点钱保号？不想交，就会被赶出去？价值越高的号，概率越高？

狠一点，就像毛伊岛一样，强抢了事？

@Archeb #2 以前想让 OpenAI 出海龟汤题给我，它一直不理解是啥。。

我就举个例子（好像涉及杀人啥的），然后就被封号了。。

@ys1992 #10

我又改了改，速度提升到，仅 0.2 秒了。。

原来大部分时间，都在遍历这张一亿数据的表，查有哪些独立的 point_id 了。。

如果有 point 表，直接从里面抽出所有 point_id 即可。我是手动用 generate_series(1, 100) 模拟的。




@Zaden #22：

可能你和我原因一样，想分组 point_id ，查最后时间，数据库居然扫全索引去了。。

其他快的原因，我觉得就是，不断跳来跳去，直接查最接近 24 小时前的时间，而不是每两条时间一一对比。

这需要高度依赖 4K 随机读取。比如，浏览器里运行数据库时，会将数据留存在内存里，自然快一些。

- 本地上测试，同样缓存在内存里时，只需 0.1 秒
- 7 年前垃圾固态上（顺序读 420 MB/s ，4K 随机读 25 MB/s ），且清除系统对文件缓存后，需 10 秒
- 10 年前硬盘上（顺序读 150 MB/s ，4K 随机读 0.65 MB/s ），也清除系统对文件缓存后，需 80 秒。。

我也不知道，为啥硬盘 4K 随机读，比固态差近 40 倍，但耗时才慢 8 倍。。

可能夹杂着一些顺序读取（比如有时跳到相邻页上了？），使得差距没这么大吧。。

总之，我浏览器里都能缓存一亿数据（约 1.3 GB ），对你来说应该也不是啥难事的。


## 0.2 秒截图

@ys1992 #10 不一定要扫全表吧。。

不断根据索引，查最接近 24 小时前的推送时间，应该只需要检查很少数据量，就能算出来了？


@Zaden 我用最垃圾的 SQLite ，在七年前的 i5-8250U 轻薄本上，效率一般的浏览器 wasm 环境里，试了下，

100 设备、一亿数据（每分钟推送、持续两年），每设备断线十次，每次 1~2 天，

只需 7 秒，就能全找出来了？


## 截图



## SQL 测试代码

```sql
-- V 站吞空格，缩进改成全角空格了

-- 建表，当 (point_id, push_time) 索引用
DROP TABLE IF EXISTS data;
CREATE TABLE data (
　　 point_id INT,
　　 push_time INT,
　　 PRIMARY KEY (point_id, push_time)
) WITHOUT ROWID;

-- 添加一亿条数据（ 100 设备、每分钟推送、持续两年）
INSERT INTO data
SELECT point.value, time.value
FROM generate_series(1, 100) point
JOIN generate_series(
　　 unixepoch('2024-05-24', '-2 year'),
　　 unixepoch('2024-05-24'), 60) time;

-- 删掉断线数据（ 100 设备，每台断线 10 次，第 N 次是 id*N 天前，持续 1, 1.1, ..., 1.9 天）
DELETE FROM data
WHERE (point_id, push_time) IN (
　　 SELECT point_id, push_time
　　 FROM generate_series(1, 100) point
　　 JOIN generate_series(1, 10) nth
　　 CROSS JOIN data
　　 WHERE point_id = point.value
　　 AND push_time >= unixepoch('2024-05-24', format('-%f day', nth.value * (point.value + 0.1) - 0.1))
　　 AND push_time < unixepoch('2024-05-24', format('-%f day', nth.value * point.value - 1))
);

-- 循环每个设备，从今天开始，不断往前找，最接近 24 小时前的推送时间
-- 若俩时间 >= 24 小时，则属于断线过久
WITH RECURSIVE
　　 t(id, a, b) AS (
　　　　 SELECT point_id, unixepoch('2024-05-24'), NULL
　　　　 FROM data
　　　　 GROUP BY point_id
　　　　 UNION ALL
　　　　 SELECT id, ifnull((
　　　　　　　　 SELECT min(push_time)
　　　　　　　　 FROM data
　　　　　　　　 WHERE point_id = t.id
　　　　　　　　 AND push_time > t.a - 86400
　　　　　　　　 AND push_time < t.a
　　　　　　), (
　　　　　　　　 SELECT max(push_time)
　　　　　　　　 FROM data
　　　　　　　　 WHERE point_id = t.id
　　　　　　　　 AND push_time < t.a - 86400
　　　　　　)), a
　　　　 FROM t
　　　　 WHERE a
　　)
SELECT
　　 id "设备 ID",
　　 datetime(a, 'auto') "最后在线",
　　 format('%d 天 %d 小时 %d 分钟', (b-a)/86400, (b-a)%86400/3600, (b-a)%3600/60) "断线时长"
FROM t
WHERE b - a >= 86400
ORDER BY id IN (1, 2, 73) DESC, id, a DESC;
```