我可以用什么语言快速执行这个数据库摘要任务？
我写了一个Python程序来处理一些数据。
下面是我想要的计算的简单说明，用一种虚构的语言描述：
parse "%s %lf %s" aa bb cc | group_by aa | quickselect --key=bb 0:5 | \
flatten | format "%s %lf %s" aa bb cc
也就是说，对于每一行，提取出一个单词、一个浮点数和另一个单词。可以把它们想象成玩家ID、得分和日期。我想要每个玩家的前五个得分和日期。数据量不算小，但也不算大，大约630兆字节。
我想知道我应该用什么实际可执行的语言来写这个程序，以便让它的代码长度和下面的Python差不多，但速度更快。
#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys
top_5 = {}
for line in sys.stdin:
aa, bb, cc = line.split()
# We want the top 5 for each distinct value of aa. There are
# hundreds of thousands of values of aa.
bb = float(bb)
if aa not in top_5: top_5[aa] = []
current = top_5[aa]
current.append((bb, cc))
# Every once in a while, we drop the values that are not in
# the top 5, to keep our memory footprint down, because some
# values of aa have thousands of (bb, cc) pairs.
if len(current) > 10:
current.sort()
current[:-5] = []
for aa in top_5:
current = top_5[aa]
current.sort()
for bb, cc in current[-5:]:
print aa, bb, cc
这里有一些示例输入数据：
3 1.5 a
3 1.6 b
3 0.8 c
3 0.9 d
4 1.2 q
3 1.5 e
3 1.8 f
3 1.9 g
这是我从程序中得到的输出：
3 1.5 a
3 1.5 e
3 1.6 b
3 1.8 f
3 1.9 g
4 1.2 q
对于3，有七个值，所以我们去掉c和d的值，因为它们的bb值让它们不在前五名之内。由于4只有一个值，它的“前五名”就只有这个值。
这个程序运行得比在MySQL中执行相同查询要快（至少是我们找到的查询方式），但我很确定它大部分时间都在Python的字节码解释器中。我觉得如果用其他语言，我可能能让它每秒处理成千上万的行，而不是每分钟处理。
所以我想用一种实现更快的语言来写这个程序。
但我不确定该选择哪种语言。
我还没能弄明白如何用SQL写出一个单一的查询，实际上我对MySQL的能力也不太满意，甚至连简单的select * from foo into outfile 'bar';都做不好。
C语言是个明显的选择，但像line.split()、对2元组列表排序和制作哈希表这些功能，都需要写一些不在标准库里的代码，所以最后可能会写出100行代码以上，而不是14行。
C++似乎是个更好的选择（它的标准库里有字符串、映射、对和向量），但用STL的话，代码可能会变得很乱。
OCaml也可以，但它有类似line.split()的功能吗？它的映射性能会让我失望吗？
Common Lisp可能也行？
有没有类似Matlab的数据库计算工具，可以让我把循环放到快速代码里？有人试过Pig吗？
（编辑：回应了davethegr8的评论，提供了一些示例输入和输出数据，并修复了Python程序中的一个bug！）
（附加编辑：哇，这个评论线程到目前为止真不错。谢谢大家！）
编辑：
在2007年，有一个非常相似的问题被问过（谢谢，Rainer！），还有Will Hartung的一个awk脚本，用于生成一些测试数据（虽然它没有真实数据的Zipfian分布）：
BEGIN {
for (i = 0; i < 27000000; i++) {
v = rand();
k = int(rand() * 100);
print k " " v " " i;
}
exit;
}
18 个回答
这是一个用Common Lisp写的草图。
注意，对于很长的文件，使用READ-LINE会有一些问题，因为它会为每一行创建一个新的字符串。如果你遇到这种情况，可以使用一些改进版的READ-LINE，这些版本使用了行缓冲区。还有，你可能需要考虑一下哈希表是否要区分大小写。
第二版
现在不再需要拆分字符串，因为我们在这里已经做了。这段代码比较底层，希望能提高一些速度。它会检查一个或多个空格作为字段分隔符，还有制表符。
(defun read-a-line (stream)
(let ((line (read-line stream nil nil)))
(flet ((delimiter-p (c)
(or (char= c #\space) (char= c #\tab))))
(when line
(let* ((s0 (position-if #'delimiter-p line))
(s1 (position-if-not #'delimiter-p line :start s0))
(s2 (position-if #'delimiter-p line :start (1+ s1)))
(s3 (position-if #'delimiter-p line :from-end t)))
(values (subseq line 0 s0)
(list (read-from-string line nil nil :start s1 :end s2)
(subseq line (1+ s3)))))))))
上面的函数返回两个值：一个是键，另一个是剩下的列表。
(defun dbscan (top-5-table stream)
"get triples from each line and put them in the hash table"
(loop with aa = nil and bbcc = nil do
(multiple-value-setq (aa bbcc) (read-a-line stream))
while aa do
(setf (gethash aa top-5-table)
(let ((l (merge 'list (gethash aa top-5-table) (list bbcc)
#'> :key #'first)))
(or (and (nth 5 l) (subseq l 0 5)) l)))))
(defun dbprint (table output)
"print the hashtable contents"
(maphash (lambda (aa value)
(loop for (bb cc) in value
do (format output "~a ~a ~a~%" aa bb cc)))
table))
(defun dbsum (input &optional (output *standard-output*))
"scan and sum from a stream"
(let ((top-5-table (make-hash-table :test #'equal)))
(dbscan top-5-table input)
(dbprint top-5-table output)))
(defun fsum (infile outfile)
"scan and sum a file"
(with-open-file (input infile :direction :input)
(with-open-file (output outfile
:direction :output :if-exists :supersede)
(dbsum input output))))
一些测试数据
(defun create-test-data (&key (file "/tmp/test.data") (n-lines 100000))
(with-open-file (stream file :direction :output :if-exists :supersede)
(loop repeat n-lines
do (format stream "~a ~a ~a~%"
(random 1000) (random 100.0) (random 10000)))))
; (create-test-data)
(defun test ()
(time (fsum "/tmp/test.data" "/tmp/result.data")))
第三版，LispWorks
使用了一些SPLIT-STRING和PARSE-FLOAT函数，其他部分是通用的Common Lisp。
(defun fsum (infile outfile)
(let ((top-5-table (make-hash-table :size 50000000 :test #'equal)))
(with-open-file (input infile :direction :input)
(loop for line = (read-line input nil nil)
while line do
(destructuring-bind (aa bb cc) (split-string '(#\space #\tab) line)
(setf bb (parse-float bb))
(let ((v (gethash aa top-5-table)))
(unless v
(setf (gethash aa top-5-table)
(setf v (make-array 6 :fill-pointer 0))))
(vector-push (cons bb cc) v)
(when (> (length v) 5)
(setf (fill-pointer (sort v #'> :key #'car)) 5))))))
(with-open-file (output outfile :direction :output :if-exists :supersede)
(maphash (lambda (aa value)
(loop for (bb . cc) across value do
(format output "~a ~f ~a~%" aa bb cc)))
top-5-table))))
你可以使用更聪明的数据结构，同时还可以继续用Python编程。我在我的电脑上运行了你提供的参考实现和我自己的Python实现，并且对比了输出结果，以确保结果是正确的。
这是你的代码：
$ time python ./ref.py < data-large.txt > ref-large.txt
real 1m57.689s
user 1m56.104s
sys 0m0.573s
这是我的代码：
$ time python ./my.py < data-large.txt > my-large.txt
real 1m35.132s
user 1m34.649s
sys 0m0.261s
$ diff my-large.txt ref-large.txt
$ echo $?
0
这是源代码：
#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys
import heapq
top_5 = {}
for line in sys.stdin:
aa, bb, cc = line.split()
# We want the top 5 for each distinct value of aa. There are
# hundreds of thousands of values of aa.
bb = float(bb)
if aa not in top_5: top_5[aa] = []
current = top_5[aa]
if len(current) < 5:
heapq.heappush(current, (bb, cc))
else:
if current[0] < (bb, cc):
heapq.heapreplace(current, (bb, cc))
for aa in top_5:
current = top_5[aa]
while len(current) > 0:
bb, cc = heapq.heappop(current)
print aa, bb, cc
更新：了解自己的极限。我还测试了一段不做任何操作的代码，以了解在使用与原始代码相似的情况下，Python能达到的最快速度：
$ time python noop.py < data-large.txt > noop-large.txt
real 1m20.143s
user 1m19.846s
sys 0m0.267s
这是noop.py的代码：
#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys
import heapq
top_5 = {}
for line in sys.stdin:
aa, bb, cc = line.split()
bb = float(bb)
if aa not in top_5: top_5[aa] = []
current = top_5[aa]
if len(current) < 5:
current.append((bb, cc))
for aa in top_5:
current = top_5[aa]
current.sort()
for bb, cc in current[-5:]:
print aa, bb, cc
我很难相信，任何没有事先了解数据的脚本（不像MySql那样有预加载的信息），会比SQL方法更快。
除了处理输入数据所花的时间，脚本还需要“保持”数组等的排序顺序……
以下是我对在SQL中应该能比较快工作的初步猜测，假设表的aa、bb、cc列上有一个索引（按这个顺序）。(一个可能的替代方案是“aa, bb DESC, cc”的索引)
(*) 这个索引可以是聚集的也可以不是，这不会影响后面的查询。选择是否聚集，以及是否需要单独的“aa,bb,cc”索引，取决于使用场景、表中行的大小等等。
SELECT T1.aa, T1.bb, T1.cc , COUNT(*)
FROM tblAbc T1
LEFT OUTER JOIN tblAbc T2 ON T1.aa = T2.aa AND
(T1.bb < T2.bb OR(T1.bb = T2.bb AND T1.cc < T2.cc))
GROUP BY T1.aa, T1.bb, T1.cc
HAVING COUNT(*) < 5 -- trick, remember COUNT(*) goes 1,1,2,3,...
ORDER BY T1.aa, T1.bb, T1.cc, COUNT(*) DESC
这个想法是计算在给定的aa值下，有多少记录比自己小。不过有一个小技巧：我们需要使用左外连接，以免丢掉bb值最大的记录或最后一条记录（这可能是前5名中的一条）。通过左连接，COUNT(*)的值会依次计算为1, 1, 2, 3, 4等等，因此HAVING测试是“<5”，以有效地选出前5名。
为了模拟OP的示例输出，ORDER BY使用了COUNT()的降序，这可以去掉，以获得更传统的前5名列表。如果需要，也可以去掉SELECT列表中的COUNT()，这不会影响查询的逻辑和排序能力。
还要注意，这个查询在处理平局时是确定性的，也就是说，当一组记录在aa组内有相同的bb值时；我认为Python程序在输入数据顺序改变时可能会提供稍微不同的输出，这是因为它偶尔会截断排序字典。
真正的解决方案：基于SQL的过程方法
上面描述的自连接方法展示了如何使用声明性语句来表达OP的需求。然而，这种方法在某种意义上是幼稚的，因为它的性能大致与每个aa“类别”内记录数量的平方和成正比。（不是O(n^2)，而是大致O((n/a)^2)，其中a是aa列的不同值的数量）换句话说，当与给定aa值相关的记录数量平均不超过几十条时，它表现良好。如果数据的aa列不具选择性，下面的方法会更适合。它利用了SQL高效的排序框架，同时实现了一个简单的算法，这在声明性方式中很难表达。对于每个aa“类别”有特别大量记录的数据集，这种方法可以通过在游标中向前（有时向后）查找下一个aa值来进一步改进简单的二分查找。对于aa“类别”相对于tblAbc的总行数较少的情况，请参见下一个方法。
DECLARE @aa AS VARCHAR(10), @bb AS INT, @cc AS VARCHAR(10)
DECLARE @curAa AS VARCHAR(10)
DECLARE @Ctr AS INT
DROP TABLE tblResults;
CREATE TABLE tblResults
( aa VARCHAR(10),
bb INT,
cc VARCHAR(10)
);
DECLARE abcCursor CURSOR
FOR SELECT aa, bb, cc
FROM tblABC
ORDER BY aa, bb DESC, cc
FOR READ ONLY;
OPEN abcCursor;
SET @curAa = ''
FETCH NEXT FROM abcCursor INTO @aa, @bb, @cc;
WHILE @@FETCH_STATUS = 0
BEGIN
IF @curAa <> @aa
BEGIN
SET @Ctr = 0
SET @curAa = @aa
END
IF @Ctr < 5
BEGIN
SET @Ctr = @Ctr + 1;
INSERT tblResults VALUES(@aa, @bb, @cc);
END
FETCH NEXT FROM AbcCursor INTO @aa, @bb, @cc;
END;
CLOSE abcCursor;
DEALLOCATE abcCursor;
SELECT * from tblResults
ORDER BY aa, bb, cc -- OR .. bb DESC ... for a more traditional order.
上述方法的替代方案，适用于aa非常不具选择性的情况。换句话说，当我们有相对较少的aa“类别”时。这个想法是遍历不同类别的列表，并对每个值运行一个“LIMIT”（MySql）或“TOP”（MSSQL）查询。
作为参考，以下在MSSQL 8.0上对61百万条记录的tblAbc运行了63秒，这些记录分为45个aa值，在一个相对较旧/较弱的主机上。
DECLARE @aa AS VARCHAR(10)
DECLARE @aaCount INT
DROP TABLE tblResults;
CREATE TABLE tblResults
( aa VARCHAR(10),
bb INT,
cc VARCHAR(10)
);
DECLARE aaCountCursor CURSOR
FOR SELECT aa, COUNT(*)
FROM tblABC
GROUP BY aa
ORDER BY aa
FOR READ ONLY;
OPEN aaCountCursor;
FETCH NEXT FROM aaCountCursor INTO @aa, @aaCount
WHILE @@FETCH_STATUS = 0
BEGIN
INSERT tblResults
SELECT TOP 5 aa, bb, cc
FROM tblproh
WHERE aa = @aa
ORDER BY aa, bb DESC, cc
FETCH NEXT FROM aaCountCursor INTO @aa, @aaCount;
END;
CLOSE aaCountCursor
DEALLOCATE aaCountCursor
SELECT * from tblResults
ORDER BY aa, bb, cc -- OR .. bb DESC ... for a more traditional order.
关于是否需要索引的问题。（参见OP的评论）当仅仅运行“SELECT * FROM myTable”时，表扫描实际上是最快的方法，不需要担心索引。然而，SQL通常更适合处理这类事情的主要原因是（除了它是数据最初积累的存储库，而任何外部解决方案都需要考虑导出相关数据的时间），它可以依赖索引来避免扫描。许多通用编程语言在处理原始数据时更为出色，但它们与SQL之间的竞争是不公平的，因为它们需要重新建立SQL在数据收集/导入阶段所积累的任何先前知识。由于排序通常是一个耗时且有时耗空间的任务，SQL及其相对较慢的处理能力往往在替代解决方案之前占据优势。
此外，即使没有预先构建的索引，现代查询优化器也可能决定创建一个临时索引的计划。而且，由于排序是DDMS的内在部分，SQL服务器在这方面通常是高效的。
那么……SQL更好吗？
也就是说，如果我们试图比较SQL和其他语言在纯ETL工作中的表现，即处理堆（未索引的表）作为输入以执行各种转换和过滤，使用C语言编写的多线程工具，利用高效的排序库，可能会更快。决定使用SQL还是非SQL方法的关键问题是数据的位置以及最终应该存放在哪里。如果我们只是想将一个文件转换为“链条”下游提供，外部程序更合适。如果我们需要在SQL服务器中拥有或需要数据，只有在极少数情况下，导出和外部处理才是值得的。