Поэтому я написал программу на Python для выполнения небольшой задачи по обработке данных.
Вот очень краткая спецификация на выдуманном языке вычислений, которые мне нужны:
parse "%s %lf %s" aa bb cc | group_by aa | quickselect --key=bb 0:5 | \
flatten | format "%s %lf %s" aa bb cc
То есть для каждой строки разберите слово, число с плавающей запятой и еще одно слово. Думайте о них как об идентификаторе игрока, счете и дате. Мне нужны пять лучших результатов и даты для каждого игрока. Размер данных не тривиален, но и не огромен; около 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()
, сортировка списка из двух кортежей и создание хеш-таблицы требуют написания некоторого кода, которого нет в стандартной библиотеке, поэтому в итоге я получил бы 100 или более строк кода вместо 14. .
Кажется, что C++ может быть лучшим выбором (в стандартной библиотеке есть строки, карты, пары и векторы), но кажется, что код с STL будет намного более запутанным.
OCaml подойдет, но есть ли у него эквивалент line.split()
, и не буду ли я грустить по поводу производительности его карты?
Common Lisp может работать?
Есть ли какой-то эквивалент Matlab для вычислений в базе данных, который позволяет мне переводить циклы в быстрый код? Кто-нибудь пробовал Свинья?
(Редактировать: ответил на комментарий davethegr8, предоставив несколько примеров входных и выходных данных, и исправил ошибку в программе Python!)
(Дополнительное редактирование: Вау, эта ветка комментариев действительно превосходна. Всем спасибо!)
Редактировать:
Был ужасно похожий вопрос задавали на sbcl-devel в 2007 (спасибо, Райнер!), и вот awk
скрипт от Уилла Хартунга для создания некоторого теста данные (хотя у него нет Zipfian распределения реальных данных):
BEGIN {
for (i = 0; i < 27000000; i++) {
v = rand();
k = int(rand() * 100);
print k " " v " " i;
}
exit;
}