1千万个浮点数存储问题，需要找出最大值

chenchaoting · 发表于 2022-5-8 11:22:15

1千万个浮点数据，要不要用数据库搞索引那些，还是直接内存里取出来，一个一个去找最大值，这样比较费时间。

Himem · 发表于 2022-5-8 11:23:58

本帖最后由 Himem 于 2022-5-8 11:26 编辑

这才40M数据呀…只是大小比较多线程跑能到ms级
什么场景？

chenchaoting · 发表于 2022-5-8 12:08:27

本帖最后由 chenchaoting 于 2022-5-8 12:09 编辑

Himem 发表于 2022-5-8 11:23
这才40M数据呀…只是大小比较多线程跑能到ms级
什么场景？
(引用自2楼)

数据量是不多，就是费时间，就是一段数据中，用光标去选择某一段时间，时间可能是1天，也可能是10分钟。然后得到最大最小值。

wye11083 · 发表于 2022-5-8 12:44:16

Himem 发表于 2022-5-8 11:23
这才40M数据呀…只是大小比较多线程跑能到ms级
什么场景？
(引用自2楼)

lz估计想的是用量子计算方法同时取出来千万个数据，然后一个周期内出来最终结果。。

1a2b3c · 发表于 2022-5-8 13:33:56

我很奇怪难道电脑上面数据库就不是一个个的去找最大值吗？

redroof · 发表于 2022-5-8 15:08:07

1a2b3c 发表于 2022-5-8 13:33
我很奇怪难道电脑上面数据库就不是一个个的去找最大值吗？
(引用自5楼)

你如果对值做个索引，就可以直接取到整个数据库的最大最小值了。当然正常情况下并不会这么做，因为这样没什么意义。
如果你允许用户随便指定一个起点和终点时间，问你最大最小值，那么没有任何优化的算法，只能顺着这个范围内的所有值一个一个扫描一遍。

brother_yan · 发表于 2022-5-8 15:13:29

竞赛里的RMQ问题，用线段树

chenchaoting · 发表于 2022-5-8 15:18:18

redroof 发表于 2022-5-8 15:08
你如果对值做个索引，就可以直接取到整个数据库的最大最小值了。当然正常情况下并不会这么做，因为这样没 ...
(引用自6楼)

对的，就是用户指定开始结束

redroof · 发表于 2022-5-8 15:21:58

wye11083 发表于 2022-5-8 12:44
lz估计想的是用量子计算方法同时取出来千万个数据，然后一个周期内出来最终结果。。 ...
(引用自4楼)

其实用自己的数据结构还真可以做到。数据库反而不好做。
做法如下:
每1万个连续数据叫作一组，预先算好每一组的起止时间和组内的最大最小值。
用户选择了时间以后，根据时间包括哪些组，在各个组的信息区里面扫描一遍，得到最大最小所在的组号，然后在组内再顺序扫描一遍取得最终结果即可。
让组数和每组的数据点数一样，那么复杂度就是根号级别。

redroof · 发表于 2022-5-8 15:27:40

chenchaoting 发表于 2022-5-8 15:18
对的，就是用户指定开始结束
(引用自8楼)

看我的这个做法就可以。
根号级别的复杂度已经比顺序查找的线性级别好多了。

wye11083 · 发表于 2022-5-8 15:36:50

redroof 发表于 2022-5-8 15:21
其实用自己的数据结构还真可以做到。数据库反而不好做。
做法如下:
每1万个连续数据叫作一组，预先算好每 ...
(引用自9楼)

你存不了。lz说的很清楚，用户可以任意指定时间段。。所以你只能按时间去存一个序列。

abigpad · 发表于 2022-5-8 15:36:56

固定时间算法，在存的时候比较好，存起来。

redroof · 发表于 2022-5-8 15:40:12

本帖最后由 redroof 于 2022-5-8 15:42 编辑

wye11083 发表于 2022-5-8 15:36
你存不了。lz说的很清楚，用户可以任意指定时间段。。所以你只能按时间去存一个序列。 ...
(引用自11楼)

就是在采样的时候预先按一组一组的存好最大最小值啊。比如一个小时做一组，或者一天做一组。这就是常规做法。
数据预处理肯定不可能低于线性复杂度，因为你获取数据本身就需要线性复杂度。
只要处理完数据以后，查询的时候能比线性更快就行。

wye11083 · 发表于 2022-5-8 15:43:57

redroof 发表于 2022-5-8 15:40
就是在采样的时候预先按一组一组的存好最大最小值啊。比如一个小时做一组，或者一天做一组。这就是常规做 ...
(引用自13楼)

你没法处理啊，lz说的是用户可以任意指定时间段。以秒为单位的话你无计可施，只能乖乖遍历数组。

redroof · 发表于 2022-5-8 15:50:45

本帖最后由 redroof 于 2022-5-8 16:10 编辑

wye11083 发表于 2022-5-8 15:43
你没法处理啊，lz说的是用户可以任意指定时间段。以秒为单位的话你无计可施，只能乖乖遍历数组。 ...
(引用自14楼)

就算一小时一组吧，
如果指定的时间段在一个小时内，就直接去这个组里扫描，反正一个组就这么多数据。
如果指定的时间跨多个组，就先到组的信息里面扫描，找到最大值在哪个组，然后到这个组内扫描一下，找到真正的时刻。
注意还有特殊情况，指定的时间段是从一组的一半开始的，最大值又恰好在这个组，那么要在组内扫一遍，看最大值在不在查询时间内，如果不在就从下个组开始重新找最大值，也包括这个组内的后一半。反正你要处理的数据量最多就是组数加上一组内的条数，理想情况下这俩都是总数据量的根号，所以总的复杂度还是根号，比原来的数据总数少的多

如果一秒钟一条数据，那么一年一共是3千万条数据。预处理的时候对每个小时预先存好最大最小值，实际查的时候先在每小时的信息里面查一下，最多8700小时，然后在这个小时内按秒查，一共就是3600加8700次操作。就算数据不常驻内存，按小时的索引表总得常驻内存的，所以这个操作仍然可以快速的完成。只是多了加载一个小时的数据到内存的时间而已

xstt · 发表于 2022-5-8 17:15:38

如果你的数据粒度很小的话这样让用户随意一个范围查是比较危险的，数据库数量到一定量时给个2年找个最大值你就麻烦了。
如果用户只是关注类似，某天最大值是多少或者日期到日期之间最大值是多少的话，可能做处理记录最大值（如每分钟最大最小值记录一下，1天也就60*24条数据，这样再给他日期时间找也不算数据多了）。不过还是看你实际场景了

redroof · 发表于 2022-5-8 17:41:20

xstt 发表于 2022-5-8 17:15
如果你的数据粒度很小的话这样让用户随意一个范围查是比较危险的，数据库数量到一定量时给个2年找个最大值 ...
(引用自16楼)

正常数据库直接找最大值就是很慢的。除非自己做数据结构，例如用我上面说的这种做法。

下一页 · 发表于 2022-5-8 18:26:39

如果cpu是单核的，不论多高级方法，都是遍历，这期间可以取巧，但是差别不大，如果是多核的，且有操作系统的情况下，可以分组，开多个线程去处理多组，然后再找每组最大值中的最大值，这样会快一些。

redroof · 发表于 2022-5-8 18:40:00

下一页发表于 2022-5-8 18:26
如果cpu是单核的，不论多高级方法，都是遍历，这期间可以取巧，但是差别不大，如果是多核的，且有操作系统 ...
(引用自18楼)

如果允许预处理数据，就不需要遍历所有，最简单的做法就是我上面那种。
既然数据是自己一点一点采集到的，那么做一些预处理来加速以后的查询就不是问题。

下一页 · 发表于 2022-5-8 20:08:58

redroof 发表于 2022-5-8 18:40
如果允许预处理数据，就不需要遍历所有，最简单的做法就是我上面那种。
既然数据是自己一点一点采集到的 ...
(引用自19楼)

如果是一边采集一边处理那肯定好

span42 · 发表于 2022-5-8 22:04:59

时序数据库搜 TDengine

lyz3432 · 发表于 2022-5-8 22:21:29

各种树用一用

dykwai1 · 发表于 2022-5-9 09:20:43

要想响应快，就是在采集的时候分段存并扫出最大最小值，用户随机选，
那么中间整段的结果已经扫过可以直接用，只需把两边的不完整的段重新扫一下就可以了

zyw19987 · 发表于 2022-5-10 10:49:18

存的时候按大小建个树，同时也按时间建个树呗

xmlbb · 发表于 2022-5-10 11:32:49

用gpu做并行归约。

1千万个浮点数存储问题，需要找出最大值

阿莫论坛20周年了！感谢大家的支持与爱护！！