江苏龙网

  1. 主页 > 生活百科 > >

详解 DeepMind 排序算法( 三 )

排序算法


此时，可能你最想知道的是，我可以使用这个排序算法吗？这些排序网络内核真的能提高排序速度吗？我认为答案需要视情况而定 。如果你只想对 long 进行升序排序，上面的代码将比 C 库提供的标准 qsort 函数快 2 倍 。而且你还不需要内核来处理 。到目前为止，我确定的是，在我的个人计算机（搭载了英特尔酷睿 i9-12900KS）上，上述函数对 long 进行排序的速度为每秒 255 兆字节 。但是，如果我注释掉排序内核：
voidlongsort( long*A, longn ) { longt, p, i, j; switch(n) { case0: return; case1: return; /* case 2: */ /* return Sort2(A, A + 1); */ /* case 3: */ /* return Sort3(A, A + 1, A + 2); */ /* case 4: */ /* return Sort4(A, A + 1, A + 2, A + 3); */ /* case 5: */ /* return Sort5(A, A + 1, A + 2, A + 3, A + 4); */ default: if(n <= 32) { InsertionSort(A, n); } else{ for(p = A[n >> 1], i = 0, j = n - 1;; i++, j--) { while(A[i] < p) i++; while(A[j] > p) j--; if(i >= j) break; t = A[i]; A[i] = A[j]; A[j] = t; } LongSort(A, i); LongSort(A + i, n - i); } break; } }longsort 函数的排序速度可以达到每秒 275 兆字节 。我在简化算法后，又实现了 7% 的性能提升 。这个函数就是 libc 在加载可执行文件时对 elf 符号表进行排序时使用的函数 。long 的好处是，它的长度足以存储一个 int 键值对 。能够快速排序映射项是非常有用的技巧 。结合朴素快速排序与朴素插入排序是我迄今为止找到的最佳解决方案，因为我必须平衡规模和性能 。上面的函数编译后只有 181 字节的 x86-64 机器码 。由于 DeepMind 的 sort3 只有 42 字节，我希望我可以牺牲一些大小来获得性能优势 。因为到目前为止我发现的第二佳算法是基数排序，性能可达每秒 400 MB，除了依赖于 malloc 之外，还需要高达 763 字节的二进制 。所以很高兴看到这些内核的表现更好 。
我并不是说 DeepMind 的想法没有价值 。我认为值得注意的是，去年 DeepMind 非常慷慨地公开了矢量化快速排序库（当时还是 google Brain），并以此实现了永远无法挑战的排序霸权 。在我的电脑上，使用 Vqsort 对 long 进行排序的速度为每秒 1155 MB，甚至略胜于 djbsort，后者是开源社区中最受欢迎的库之一，尽管除了 int 之外并没有推广至更多的数据类型 。两种实现方式都是通过向量化排序网络来实现的 。我认为这就是排序网络技术大放异彩的地方 。我想，如果不是 AlphaDev 的智能实体还处于起步阶段，它也会采用这种做法 。如果从第一原则开始，仅支持基础指令集就非常困难 。我认为再等一等，我们可以期待 AlphaDev 未来会取得伟大的成就，因为它会努力应对更艰巨的挑战 。
此外，DeepMind 压缩了算法的规模，这一点我也很喜欢，因为这并不常见 。极限规模编程是我的爱好之一 。我曾在一篇博客文章中发布过一个用于 lambda 演算的虚拟机只有 383 字节，还有一个拥有垃圾收集功能的 lisp 机器，只有 436 字节 。我也曾在博客中介绍优化 cosmpolitan c 库大小的技巧 。我也喜欢 DeepMind 的母公司谷歌，几周前谷歌授予了我一份开源伙伴的奖金，很高兴看到他们也对压缩代码规模充满了热情 。很高兴看到他们用我的库来改进向量化快速排序 。我只是希望全世界最佳 long 排序不要因为多加了 24 KB 的二进制编码而变成 C++ 庞然大物 。仅升序排序就有 23,000 行汇编代码 。我迫切希望有一天看到 AlphaDev 能够对这些代码下手 。
最后，我喜欢一家人工智能公司建造用机器语言编写代码的机器的想法 。为什么他们不喜欢这个想法呢？成为机器是机器的本性 。作为一名开发人员，我发现 OpenAI 正在创造的未来缺乏这样的想法，他们建立了一个伟大的大型家长式机器，在零和经济中与地球上的每一位开发者竞争，然后吸引世界各地的租客通过政府监管来控制那台机器 。OpenAI 承诺要自动化所有的任务，包括我最喜欢的编程，但他们正在努力创造的未来并不是在朝着这个方向前进 。
我想要的是能够控制一台能够完成我自己无法完成的事情的机器，比如发现排序内核 。这才是真正的进步，我认为我们可以去除的每一行汇编代码都是朝着这个梦想积极迈出的一步 。

【详解 DeepMind 排序算法】


推荐阅读


上一篇：小红书上如何开店铺

下一篇：在线刷空间人气