Kra*_*ker 9 lisp python sql ocaml apache-pig
所以我写了一个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值将它们排除在前5之外.因为4只有一个值,它的"前5"只包含那个值.
这比在MySQL中执行相同的查询运行得更快(至少,我们发现查询的方式),但我很确定它将大部分时间花在Python字节码解释器上.我认为在另一种语言中,我可能会让它每秒处理数十万行而不是每分钟.所以我想用一种执行速度更快的语言编写它.
但我不确定选择哪种语言.
我无法弄清楚如何在SQL中将其表达为单个查询,实际上我对MySQL的能力甚至只select * from foo into outfile 'bar';对输入数据感到不满
.
C是一个显而易见的选择,但是诸如line.split()排序2元组列表和制作哈希表之类的东西需要编写一些不在标准库中的代码,因此我最终会得到100行代码或更多代码而不是14代码.
C++似乎可能是一个更好的选择(它在标准库中有字符串,映射,对和向量),但似乎代码对STL来说会更加混乱.
OCaml会很好,但它有相同的line.split(),我会对它的地图表现感到悲伤吗？
Common Lisp可能有用吗？
是否有一些Matlab用于数据库计算,这样可以让我将循环推送到快速代码中？有人试过猪吗？
(编辑:通过提供一些示例输入和输出数据来响应davethegr8的评论,并修复了Python程序中的错误!)
(附加编辑:哇,到目前为止,这个评论主题非常出色.谢谢,大家!)
编辑:
2007年sbcl-devel上有一个类似的问题(感谢,Rainer!),这是awkWill Hartung 的一个脚本,用于生成一些测试数据(尽管它没有Zipfian分布的真实数据):
BEGIN {
for (i = 0; i < 27000000; i++) {
v = rand();
k = int(rand() * 100);
print k " " v " " i;
}
exit;
}
我很难相信任何没有任何数据先验知识的脚本(不像预装了这样的信息的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值中的记录数小于self的记录数.然而,有一个小技巧:我们需要使用LEFT OUTER连接,以免丢弃具有最大bb值或最后一个(可能恰好是前5个之一)的记录.由于左连接它,COUNT(*)值计数1,1,2,3,4等因此HAVING测试为"<5"以有效地选择前5.
为了模拟OP的示例输出,ORDER BY在COUNT()上使用DESC,可以删除它以获得更传统的前5种类型的列表.此外,如果需要,可以删除选择列表中的COUNT(),这不会影响查询的逻辑和正确排序的能力.
还要注意,这个查询在处理关系方面是确定性的,即,当一组给定的记录具有相同的bb值(在aa组内)时; 我认为当输入数据的顺序发生变化时,Python程序可能会提供稍微不同的输出,这是因为它偶尔会截断排序字典.
真正的解决方案:基于SQL的程序方法
上面描述的自联接方法演示了如何使用声明性语句来表达OP的要求.然而,这种方法在某种意义上是天真的,因为它的表现大致与每个"类别"中记录计数的平方和相关.(不是O(n ^ 2),而是大致为O((n/a)^ 2),其中a是aa列的不同值的数量)换句话说,它对数据表现良好,使得平均相关的记录数量给定的aa值不超过几十.如果数据是aa列不是选择性的,那么下面的方法非常多! - 更适合.它利用了SQL的高效排序框架,同时实现了一种难以以声明方式表达的简单算法.通过在光标中向前看(有时返回...),通过引入下一个aa值的简单二进制搜索,可以进一步改进具有特别大量记录的数据集的方法/每个"类别".对于相对于tblAbc中总行数的aa'类别'的数量较少的情况,请参见下一个方法之后的另一种方法.
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上以45个aa值划分的61万个记录的tblAbc以下运行时间为63秒.
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"时,表扫描实际上是最快的appraoch,无需费心索引.但是,SQL通常更适合这种事情的主要原因(除了数据首先积累的存储库,而任何外部解决方案需要考虑导出相关数据的时间),是它可以依靠索引来避免扫描.许多通用语言更适合处理原始处理,但它们正在与SQL进行不公平的斗争,因为它们需要重建SQL在数据收集/导入阶段收集的数据的任何先前知识.由于排序通常是一个时间,有时是占用空间的任务,因此SQL及其相对较慢的处理能力通常会先于替代解决方案.
此外,即使没有预先构建的索引,现代查询优化器也可以决定涉及创建临时索引的计划.而且,因为排序是DDMS的固有部分,所以SQL服务器在该领域通常是高效的.
那么...... SQL更好吗？
这就是说,如果我们试图比较SQL和其他语言的纯ETL作业,即处理堆(未编制索引的表)作为执行各种转换和过滤的输入,那么编写的多线程实用程序可能会说C,并利用有效的排序库,可能会更快.决定SQL与非SQL方法的决定性问题是数据的位置以及最终应驻留的位置.如果我们只是将要提供的文件转换为"链",则外部程序更适合.如果我们在SQL服务器中拥有或需要数据,那么只有极少数情况才能使其在外部进行导出和处理.
您可以使用更智能的数据结构,仍然使用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
更新:了解你的极限.我还计划了一个noop代码,知道最快的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