search

airuikun / technology-blog

个人博客，前端技术收集，一起共同学习与成长
3.18k stars 292 forks source link

第 18 题：（开放题）100亿排序问题：内存不足，一次只允许你装载和操作1亿条数据，如何对100亿条数据进行排序 #18

Open airuikun opened 5 years ago

airuikun commented 5 years ago

这题是考察算法和实际问题结合的一个问题

很多场景的数据量都是百亿甚至千亿级别。

那么如何对这些数据进行高效的操作呢，可以通过这题考察出来。

以前老听说很多人问，前端学算法没有用，考算法都是垃圾，面不出候选人的能力

其实。。。老哥实话告诉你，当你在做前端需要用到crc32、并查集、字典树、哈夫曼编码、LZ77之类东西的时候

已经是涉及到框架实现和极致优化层面了

那时你就已经到了另外一个前端高阶境界了

所以不要抵触算法，可能只是我们目前的眼界和能力，还没触及到那个层级

我前面已经公布了两道开放题的答案了，相信大家已经有所参悟。我觉得在思考开放题的过程中，会有很多意想不到的成长，所以我建议这道题大家可以尝试自己思考一下。 本题答案会在周五公布

qile222 commented 5 years ago

将100亿数据分割到100个桶当中，一次遍历一亿条数据，按照排序规则将数据动态的插入到对应的桶里面？

rhythm1995 commented 5 years ago

将100亿数据分割到100个桶当中，一次遍历一亿条数据，按照排序规则将数据动态的插入到对应的桶里面？

感觉没打全，得外部桶排序+内部排序。 桶排序很吃数据情况的，一般适用于数据固定值（身高分数这种）的情况是可行的，桶排序有基数和计数。基数是可以固定桶数量但有可能一个桶中数据太多1G不够，这种情况下又得考虑多个基数桶怎么办的问题，换句话说基数排序得内存够。计数排序的话，假如说100亿数据全都不相同或者相同的很少，就就得有100亿个桶了，内存不够用；如果桶是区间桶是能解决桶不够用的情况，但桶内得内部排序，这也就可以，不过这也就降低了性能。 但在数据特殊的情况下计数排序是可以的并且可能是最快的。 通常认为的排序数据为均匀数据情况下，多路归并应该性能好点）。

qile222 commented 5 years ago

将100亿数据分割到100个桶当中，一次遍历一亿条数据，按照排序规则将数据动态的插入到对应的桶里面？

感觉没打全，得外部桶排序+内部排序。 桶排序很吃数据情况的，一般适用于数据固定值（身高分数这种）的情况是可行的，桶排序有基数和计数。基数是可以固定桶数量但有可能一个桶中数据太多1G不够，这种情况下又得考虑多个基数桶怎么办的问题，换句话说基数排序得内存够。计数排序的话，假如说100亿数据全都不相同或者相同的很少，就就得有100亿个桶了，内存不够用；如果桶是区间桶是能解决桶不够用的情况，但桶内得内部排序，这也就可以，不过这也就降低了性能。 但在数据特殊的情况下计数排序是可以的并且可能是最快的。 通常认为的排序数据为均匀数据情况下，多路归并应该性能好点）。

此题中瓶颈是内存，但是外部存储是够用的，将数据存到外部存储的区间桶里面不会有内存问题。 桶用哈希表的思路，将哈希算法替换为排序算法，将数据划分到区间，区间内的碰撞通过插入排序解决，同时通过不断的 rehash 将数据调整到均匀的分布，这样能否达到一个较优的解？

totatolin commented 5 years ago

将100亿数据分割到100个桶当中，一次遍历一亿条数据，按照排序规则将数据动态的插入到对应的桶里面？

感觉没打全，得外部桶排序+内部排序。 桶排序很吃数据情况的，一般适用于数据固定值（身高分数这种）的情况是可行的，桶排序有基数和计数。基数是可以固定桶数量但有可能一个桶中数据太多1G不够，这种情况下又得考虑多个基数桶怎么办的问题，换句话说基数排序得内存够。计数排序的话，假如说100亿数据全都不相同或者相同的很少，就就得有100亿个桶了，内存不够用；如果桶是区间桶是能解决桶不够用的情况，但桶内得内部排序，这也就可以，不过这也就降低了性能。 但在数据特殊的情况下计数排序是可以的并且可能是最快的。 通常认为的排序数据为均匀数据情况下，多路归并应该性能好点）。

这题不能用桶排序、计数排序、基数排序这些非比较的算法吧，这三个算法没记错的话空间复杂度都是O(n + k)，而且题目也没说是纯数字，况且可能有些很极端的情况所以空间复杂度也是不可控的（比如计数排序里处理[0, 1, 9999999999]这样的数组，k值就会很大，桶排序里也可能造成链表很长）。我觉得可以考虑下希尔排序，虽然时间复杂度差一些，但是目前的性能瓶颈主要是内存上，希尔排序同样可以实现分布式的排序，不会产生额外的内存损耗，以100为间隔进行插入排序，然后再不断缩小这个间隔。

totatolin commented 5 years ago

将100亿数据分割到100个桶当中，一次遍历一亿条数据，按照排序规则将数据动态的插入到对应的桶里面？

感觉没打全，得外部桶排序+内部排序。 桶排序很吃数据情况的，一般适用于数据固定值（身高分数这种）的情况是可行的，桶排序有基数和计数。基数是可以固定桶数量但有可能一个桶中数据太多1G不够，这种情况下又得考虑多个基数桶怎么办的问题，换句话说基数排序得内存够。计数排序的话，假如说100亿数据全都不相同或者相同的很少，就就得有100亿个桶了，内存不够用；如果桶是区间桶是能解决桶不够用的情况，但桶内得内部排序，这也就可以，不过这也就降低了性能。 但在数据特殊的情况下计数排序是可以的并且可能是最快的。 通常认为的排序数据为均匀数据情况下，多路归并应该性能好点）。

此题中瓶颈是内存，但是外部存储是够用的，将数据存到外部存储的区间桶里面不会有内存问题。 桶用哈希表的思路，将哈希算法替换为排序算法，将数据划分到区间，区间内的碰撞通过插入排序解决，同时通过不断的 rehash 将数据调整到均匀的分布，这样能否达到一个较优的解？

这样可能确实更好一些，充分结合时间和空间两方面综合考虑。利用1亿的数据装载用散列表申请1亿的数据链表节点，用桶排序将每个桶里的数据排序好。此时对于100个桶里的数据，有序程度更高，更有利于插入排序，再用插入排序来处理桶和桶之间的数据排序。

shuson commented 5 years ago

抛个砖:

  1. 把这100亿的int型数据以文件形式存储到100个小文件中
  2. 对这100个小文件分别读取后排序再存入
  3. 遍历排序后对100个小文件，每个小文件里面取第一个数字, 组成一个100大数的堆 2.1. new个空的大文件存最后的结果
  4. 之后出100个数的那个堆,找到对应的小文件取数字,写入大文件, 记得flash, gc之类的
  5. 循环3, 等所有的小文件都取完, 大文件就是存的最后结果
zsxsoft commented 5 years ago
  1. 在前端对100亿个数字排序大多数情况下是没有意义的事情，真的遇到这种需求，应该先判断是不是对需求的理解出现问题了。例如，只是想取其中最大的1000个数字，那就不应该对100亿个数字排序，而应该使用Top K问题的解决方案，如分治、局部淘汰、Hash等。
  2. 不应该使用JavaScript解决这个问题，ECMA-262规定ECMAScript的数字实现为浮点数（as specified in the IEEE Standard for Binary Floating-Point Arithmetic），应该使用WASM、Native Module乃至RPC通讯。
  3. 之后就是正统的外排序算法上场了，要是内存足够的话直接快排也行。
thoamsy commented 5 years ago

不应该使用JavaScript解决这个问题，ECMA-262规定ECMAScript的数字实现为浮点数（as specified in the IEEE Standard for Binary Floating-Point Arithmetic），应该使用WASM、Native Module乃至RPC通讯。

引擎内部会做优化，64 位系统小于 2^31 -1 次方的整数就对应 c++ 里的整数

zsxsoft commented 5 years ago

@thoamsy

https://v8.dev/blog/elements-kinds

  1. 如果使用普通Array的话，当数字是“Small Integer”的情况下这个Array的类型是PACKED_SMI_ELEMENTS https://medium.com/fhinkel/v8-internals-how-small-is-a-small-integer-e0badc18b6da 而按照SMI的定义，64位下kSmiMaxValue = -(-2^31+1) = 2^31-1，你说的确实正确。
  2. 然而，即使是SMI运行效率仍然不行。我执行代码，看了下内存 var a = [0x0deadbee, 0x0deadbef, 0x0deadbf0, 0x0deadbf1, 0xdeadbeef] image image 内存布局不够紧凑，使用TypedArray而非PACKED_SMI_ELEMENTS会是更合适的选择。那篇文章也指出了建议使用TypedArray。

不是反驳，仅作为补充信息。

thoamsy commented 5 years ago

@zsxsoft 感谢补充。

WkBord commented 5 years ago

一脸懵逼的来了，一脸懵逼的走了

twotwoba commented 5 years ago

一脸懵逼的来了，一脸懵逼的走了

我也是😂水平不够

slbyml commented 5 years ago

bit-map了解下

cisen commented 5 years ago

bit-map了解下

bit-map自动去重怎么搞？

thoamsy commented 5 years ago

bit-map自动去重怎么搞？

bit map 自动去重的, 只不过 十亿的数据, 用 bit map 也没啥用.

SituC commented 5 years ago

一脸懵逼的来了，一脸懵逼的走了

+1

Constantine112 commented 5 years ago

满怀好奇的进来，一脸蒙蔽的走了，都是什么神仙打架

mannymu commented 5 years ago

神仙

libin1991 commented 4 years ago

外排序

ruofengOvO commented 4 years ago

多路归并不可以吗？

zhutengfei123 commented 3 years ago

webworker多线程+ArryBuffer试试呢？ 1.获取计算机的CPU核心数量，一般线程数是CPU核心数量的两倍，默认是4个； 2.获取线程数多少个就开辟多少子进程来处理，每个进程处理的数据量是：100亿/n进程； 3.ArryBuffer按位存储，解决耗内存问题； 4.未完待续。。。。

aaa1999 commented 2 years ago

这个题我感觉第一思路也是多路归并排序。

by 大四学生。

多多指教

tangeping commented 6 months ago

抛个砖: 0. 把这100亿的int型数据以文件形式存储到100个小文件中

  1. 对这100个小文件分别读取后排序再存入
  2. 遍历排序后对100个小文件，每个小文件里面取第一个数字, 组成一个100大数的堆 2.1. new个空的大文件存最后的结果
  3. 之后出100个数的那个堆,找到对应的小文件取数字,写入大文件, 记得flash, gc之类的
  4. 循环3, 等所有的小文件都取完, 大文件就是存的最后结果

这种方法没有考虑到每个小文件里面的数组有没有重叠？如果有数据重叠，你连起来就不是有序的

jkai1217 commented 6 months ago

这是来自QQ邮箱的假期自动回复邮件。您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

wugy0103 commented 6 months ago

这是来自QQ邮箱的自动回复邮件。