Какой язык я мог использовать для быстрого выполнения этой задачи реферирования базы данных?

Это:

delete[] foo;

Изменить: современные компиляторы действительно нуждаются в используйте правильный оператор delete , иначе они могут потерять память или не запустить правильные деструкторы.

(ранее я заявлял, что на практике это не имело значения. Около 10 лет назад я пытался много разных компиляторов и не удалось найти тот, который действительно утекал память, если вы по ошибке пропустили []. Однако вой толпы - см. ниже - заставил меня снова попробовать свои эксперименты, и кажется, что современные компиляторы / libc + + мне действительно не все равно.)

SELECT * FROM top ORDER BY key,value;

Как видите, вычисление top-n происходит очень быстро (при условии, что n мало), но создание (обязательного) индекса происходит очень медленно, поскольку включает в себя полную сортировку.

Лучше всего использовать формат, который быстро анализируется (либо двоичный, либо напишите собственный агрегат C для вашей базы данных, что было бы лучшим выбором IMHO). Время выполнения в программе на C не должно превышать 1 с, если Python может сделать это за 1 с.

Я люблю решать задачи во время обеденного перерыва. Вот реализация за 1 час.

Хорошо, если вы не хотите делать какую-то чрезвычайно экзотическую чушь вроде дополнений, ничто не мешает вам использовать собственный формат с плавающей запятой base-10, единственный реализованный оператор которого - сравнение, верно? lol.

У меня валялся некоторый код fast-atoi из предыдущего проекта, поэтому я просто импортировал его.

http://www.copypastecode.com/11541/

Этот исходный код на C занимает около 6,6 секунд на синтаксический анализ 580 МБ входящего текста (27 миллионов строк), половина этого времени уходит на fgets, смеется. Тогда для вычисления top-n требуется примерно 0,05 секунды, но я не знаю наверняка, поскольку время, необходимое для top-n, меньше шума таймера.

Вы будете тем, кто будет тестировать это для правильности хоть XDDDDDDDDDDD

Интересно а?

That was a nice lunch break challenge, he, he.

Top-N is a well-known database killer. As shown by the post above, there is no way to efficiently express it in common SQL.

As for the various implementations, you got to keep in mind that the slow part in this is not the sorting or the top-N, it's the parsing of text. Have you looked at the source code for glibc's strtod() lately ?

For instance, I get, using Python :

Read data : 80.5  s
My TopN   : 34.41 s
HeapTopN  : 30.34 s

It is quite likely that you'll never get very fast timings, no matter what language you use, unless your data is in some format that is a lot faster to parse than text. For instance, loading the test data into postgres takes 70 s, and the majority of that is text parsing, too.

If the N in your topN is small, like 5, a C implementation of my algorithm below would probably be the fastest. If N can be larger, heaps are a much better option.

So, since your data is probably in a database, and your problem is getting at the data, not the actual processing, if you're really in need of a super fast TopN engine, what you should do is write a C module for your database of choice. Since postgres is faster for about anything, I suggest using postgres, plus it isn't difficult to write a C module for it.

Here's my Python code :

import random, sys, time, heapq

ROWS = 27000000

def make_data( fname ):
    f = open( fname, "w" )
    r = random.Random()
    for i in xrange( 0, ROWS, 10000 ):
        for j in xrange( i,i+10000 ):
            f.write( "%d    %f    %d\n" % (r.randint(0,100), r.uniform(0,1000), j))
        print ("write: %d\r" % i),
        sys.stdout.flush()
    print

def read_data( fname ):
    for n, line in enumerate( open( fname ) ):
        r = line.strip().split()
        yield int(r[0]),float(r[1]),r[2]
        if not (n % 10000 ):
            print ("read: %d\r" % n),
            sys.stdout.flush()
    print

def topn( ntop, data ):
    ntop -= 1
    assert ntop > 0
    min_by_key = {}
    top_by_key = {}
    for key,value,label in data:
        tup = (value,label)
        if key not in top_by_key:
            # initialize
            top_by_key[key] = [ tup ]
        else:
            top = top_by_key[ key ]
            l    = len( top )
            if l > ntop:
                # replace minimum value in top if it is lower than current value
                idx = min_by_key[ key ]
                if top[idx] < tup:
                    top[idx] = tup
                    min_by_key[ key ] = top.index( min( top ) )
            elif l < ntop:
                # fill until we have ntop entries
                top.append( tup )
            else:
                # we have ntop entries in list, we'll have ntop+1
                top.append( tup )
                # initialize minimum to keep
                min_by_key[ key ] = top.index( min( top ) )

    # finalize:
    return dict( (key, sorted( values, reverse=True )) for key,values in top_by_key.iteritems() )

def grouptopn( ntop, data ):
    top_by_key = {}
    for key,value,label in data:
        if key in top_by_key:
            top_by_key[ key ].append( (value,label) )
        else:
            top_by_key[ key ] = [ (value,label) ]

    return dict( (key, sorted( values, reverse=True )[:ntop]) for key,values in top_by_key.iteritems() )

def heaptopn( ntop, data ):
    top_by_key = {}
    for key,value,label in data:
        tup = (value,label)
        if key not in top_by_key:
            top_by_key[ key ] = [ tup ]
        else:
            top = top_by_key[ key ]
            if len(top) < ntop:
                heapq.heappush(top, tup)
            else:
                if top[0] < tup:
                    heapq.heapreplace(top, tup)

    return dict( (key, sorted( values, reverse=True )) for key,values in top_by_key.iteritems() )

def dummy( data ):
    for row in data:
        pass

make_data( "data.txt" )

t = time.clock()
dummy( read_data( "data.txt" ) )
t_read = time.clock() - t

t = time.clock()
top_result = topn( 5, read_data( "data.txt" ) )
t_topn = time.clock() - t

t = time.clock()
htop_result = heaptopn( 5, read_data( "data.txt" ) )
t_htopn = time.clock() - t

# correctness checking :
for key in top_result:
    print key, " : ", "        ".join (("%f:%s"%(value,label)) for (value,label) in    top_result[key])
    print key, " : ", "        ".join (("%f:%s"%(value,label)) for (value,label) in htop_result[key])

print
print "Read data :", t_read
print "TopN :     ", t_topn - t_read
print "HeapTopN : ", t_htopn - t_read

for key in top_result:
    assert top_result[key] == htop_result[key]

The Pig version would go something like this (untested):

 Data = LOAD '/my/data' using PigStorage() as (aa:int, bb:float, cc:chararray);
 grp = GROUP Data by aa;
 topK = FOREACH grp (
     sorted = ORDER Data by bb DESC;
     lim = LIMIT sorted 5;
     GENERATE group as aa, lim;
)
STORE topK INTO '/my/output' using PigStorage();

Pig isn't optimized for performance; it's goal is to enable processing of multi-terabyte datasets using parallel execution frameworks. It does have a local mode, so you can try it, but I doubt it will beat your script.

Мне трудно поверить, что любой сценарий без каких-либо предварительных знаний о данных (в отличие от 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 join, чтобы не отбросить запись с самым большим значением bb или последней (которая может оказаться одной из 5 лучших). В результате присоединения к нему слева значение COUNT (*) считается 1, 1, 2, 3, 4 и т. Д., И, следовательно, тест HAVING будет «<5», чтобы эффективно выбрать верхний 5.

Для эмуляции образца вывод OP, ORDER BY использует DESC для COUNT (), который можно удалить, чтобы получить более традиционный тип листинга 5 лучших. Кроме того, COUNT () в списке выбора при желании можно удалить, это не влияет на логику запроса и возможность правильной сортировки.

Также обратите внимание, что этот запрос является детерминированным с точки зрения работы с Связи, i, e, когда данный набор записей имеет одинаковое значение для bb (внутри группы aa); Я думаю, что программа Python может выдавать несколько иные результаты при изменении порядка входных данных, то есть из-за случайного усечения словаря сортировки.

Реальное решение: процедурный подход на основе SQL

Самостоятельная работа. Описанный выше подход соединения демонстрирует, как декларативные операторы могут использоваться для выражения требований OP. Однако этот подход наивен в том смысле, что его производительность примерно связана с суммой квадратов счетчиков записей в каждой «категории». (не O (n ^ 2), а примерно O ((n / a) ^ 2), где a - количество различных значений для столбца aa) Другими словами, он хорошо работает с данными, так что в среднем количество связанных записей с заданным значением aa не превышает нескольких десятков. Если данные таковы, что столбец aa не является выборочным, следующий подход гораздо лучше подходит. Он использует эффективную структуру сортировки SQL и реализует простой алгоритм, который сложно выразить декларативно. Этот подход может быть дополнительно улучшен для наборов данных с особенно большим количеством записей в каждой / большинстве «категорий», введя простой двоичный поиск следующего значения 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 очень неселективный. Другими словами, когда у нас относительно мало аа «категорий». Идея состоит в том, чтобы просмотреть список отдельных категорий и запустить «LIMIT» (MySql) «TOP» Для справки, следующее было выполнено за 63 секунды для tblAbc из 61 миллиона записей, разделенных на 45 значений AA, на MSSQL 8.0, на относительно старом / слабом хосте.

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.

По вопросу о необходимости индекса . (см. замечание ОП) При простом выполнении команды «SELECT * FROM myTable» сканирование таблицы - это, по сути, самая быстрая оценка, без необходимости возиться с индексами. Однако основная причина, по которой SQL обычно лучше подходит для такого рода вещей (помимо того, что он является репозиторием, в котором в первую очередь накапливаются данные, тогда как любое внешнее решение должно учитывать время для экспорта соответствующих данных), в том, что он может полагаться на индексы, чтобы избежать сканирования. Многие языки общего назначения гораздо лучше подходят для обработки необработанных данных, но они ведут несправедливую битву с SQL, потому что им необходимо восстановить все предыдущие знания о данных, которые SQL собрал в ходе фазы сбора / импорта данных. Поскольку сортировка обычно занимает много времени, а иногда и места, SQL и его относительно более медленная вычислительная мощность часто опережает альтернативные решения.

Кроме того, даже без предварительно созданных индексов современные оптимизаторы запросов могут принять решение о плане, который включает создание временного индекса. И поскольку сортировка является неотъемлемой частью DDMS, серверы SQL обычно эффективны в этой области.

Итак ... SQL лучше?

Это говорит о том, что если мы пытаемся сравнить SQL и другие языки на чистом уровне Задания ETL, то есть для работы с кучами (неиндексированными таблицами) в качестве входных данных для выполнения различных преобразований и фильтрации, вполне вероятно, что многопоточные утилиты, написанные, скажем, на C, и использующие эффективные библиотеки сортировки, скорее всего будет быстрее. Решающий вопрос при выборе подхода SQL или не-SQL заключается в том, где находятся данные и где они в конечном итоге должны находиться. Если мы просто конвертируем файл, который будет передаваться по «цепочке», лучше подходят внешние программы. Если у нас есть или нужны данные на сервере SQL, только в редких случаях их стоит экспортировать и обрабатывать извне.

Выбор «пятерки лучших» будет выглядеть примерно так. Обратите внимание, что сортировки нет. Ни один список в словаре top_5 никогда не превышает 5 элементов.

from collections import defaultdict
import sys

def keep_5( aList, aPair ):
    minbb= min( bb for bb,cc in aList )
    bb, cc = aPair
    if bb < minbb: return aList
    aList.append( aPair )
    min_i= 0
    for i in xrange(1,6):
        if aList[i][0] < aList[min_i][0]
            min_i= i
    aList.pop(min_i)
    return aList


top_5= defaultdict(list)
for row in sys.stdin:
    aa, bb, cc = row.split()
    bb = float(bb)
    if len(top_5[aa]) < 5:
        top_5[aa].append( (bb,cc) )
    else:
        top_5[aa]= keep_5( top_5[aa], (bb,cc) )

Разве это не так просто, как

 SELECT DISTINCT aa, bb, cc FROM tablename ORDER BY bb DESC LIMIT 5

?

Конечно, трудно сказать, что было бы самым быстрым, не сравнивая его с данными. И если это то, что вам нужно сделать очень быстро, возможно, имеет смысл оптимизировать вашу базу данных, чтобы сделать запрос быстрее, а не оптимизировать запрос.

И, конечно, если вам все равно нужен плоский файл, вы можете также используйте это.

Поскольку вы спросили о Matlab, вот как я сделал что-то вроде того, о чем вы просите. Я попытался сделать это без каких-либо циклов for, но он у меня есть, потому что я не хотел тратить на него много времени. Если вас беспокоит память, вы можете извлекать данные из потока по частям с помощью fscanf, а не читать весь буфер.

fid = fopen('fakedata.txt','r');
tic
A=fscanf(fid,'%d %d %d\n');
A=reshape(A,3,length(A)/3)';  %Matlab reads the data into one long column'
Names = unique(A(:,1));
for i=1:length(Names)
    indices = find(A(:,1)==Names(i));   %Grab all instances of key i
    [Y,I] = sort(A(indices,2),1,'descend'); %sort in descending order of 2nd record
    A(indices(I(1:min([5,length(indices(I))]))),:) %Print the top five
end
toc
fclose(fid)

Пробовал ли кто-нибудь решить эту проблему с помощью только awk. Конкретно «пасть»? Согласно этому сообщению в блоге, он должен быть быстрее даже Java и C ++: http://anyall.org/blog/2009/09/dont-mawk-awk-the-fastest-and-most-elegant-big -data-munging-language /

РЕДАКТИРОВАТЬ: Просто хотел уточнить, что единственное утверждение, сделанное в этом сообщении в блоге, состоит в том, что для определенного класса проблем, которые специально подходят для обработки в стиле awk, виртуальная машина mawk может победить «ванильные» реализации на Java и C ++.

Вот решение на C ++. Однако у меня не было большого количества данных, чтобы проверить это, поэтому я не знаю, насколько он быстр на самом деле.

[править] Благодаря тестовым данным, предоставленным сценарием awk в этом потоке, я удалось немного очистить и ускорить код. Я не пытаюсь найти максимально быструю версию - цель состоит в том, чтобы предоставить достаточно быструю версию, которая не так уродлива, как люди думают, могут быть решения STL.

Эта версия должна быть примерно в два раза быстрее, чем первая версия (проходит 27 миллионов строк примерно за 35 секунд). Пользователи Gcc, не забудьте скомпилируйте это с помощью -O2.

#include <map>
#include <iostream>
#include <functional>
#include <utility>
#include <string>
int main() {
  using namespace std;
  typedef std::map<string, std::multimap<double, string> > Map;
  Map m;
  string aa, cc;
  double bb;
  std::cin.sync_with_stdio(false); // Dunno if this has any effect, but anyways.

  while (std::cin >> aa >> bb >> cc)
    {
      if (m[aa].size() == 5)
        {
          Map::mapped_type::iterator iter = m[aa].begin();
          if (bb < iter->first)
            continue;
          m[aa].erase(iter);
        }
      m[aa].insert(make_pair(bb, cc));
    }
  for (Map::const_iterator iter = m.begin(); iter != m.end(); ++iter)
    for (Map::mapped_type::const_iterator iter2 = iter->second.begin();
         iter2 != iter->second.end();
         ++iter2)
      std::cout << iter->first << " " << iter2->first << " " << iter2->second <<
 std::endl;

}

Довольно простой Caml (27 * 10 ^ 6 строк - 27 секунд, C ++ по hrnt - 29 секунд)

open Printf
open ExtLib

let (>>) x f = f x
let cmp x y = compare (fst x : float) (fst y)
let wsp = Str.regexp "[ \t]+"

let () =
  let all = Hashtbl.create 1024 in
  Std.input_lines stdin >> Enum.iter (fun line ->
    let [a;b;c] = Str.split wsp line in
    let b = float_of_string b in
    try
      match Hashtbl.find all a with
      | [] -> assert false
      | (bmin,_) as prev::tl -> if b > bmin then
        begin
          let m = List.sort ~cmp ((b,c)::tl) in
          Hashtbl.replace all a (if List.length tl < 4 then prev::m else m)
        end
    with Not_found -> Hashtbl.add all a [b,c]
  );
  all >> Hashtbl.iter (fun a -> List.iter (fun (b,c) -> printf "%s %f %s\n" a b c))

Это набросок в 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, в противном случае - общий CL.

(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))))    

Это заняло 45,7 секунды на моем компьютере с 27M строками данных, которые выглядели следующим образом:

42 0.49357 0
96 0.48075 1
27 0.640761 2
8 0.389128 3
75 0.395476 4
24 0.212069 5
80 0.121367 6
81 0.271959 7
91 0.18581 8
69 0.258922 9

Ваш сценарий занял 1m42 на этих данных, пример c ++ тоже 1m46 (g ++ t.cpp -ot, чтобы скомпилировать, я ничего не знаю о C ++).

Java 6, не то чтобы это действительно важно. Вывод не идеален, но это легко исправить.

package top5;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) throws Exception {
        long start  = System.currentTimeMillis();
        Map<String, Pair[]> top5map = new TreeMap<String, Pair[]>();
        BufferedReader br = new BufferedReader(new FileReader("/tmp/file.dat"));

        String line = br.readLine();
        while(line != null) {
            String parts[] = line.split(" ");

            String key = parts[0];
            double score = Double.valueOf(parts[1]);
            String value = parts[2];
            Pair[] pairs = top5map.get(key);

            boolean insert = false;
            Pair p = null;
            if (pairs != null) {
                insert = (score > pairs[pairs.length - 1].score) || pairs.length < 5;
            } else {
                insert = true;
            }
            if (insert) {
                p = new Pair(score, value);
                if (pairs == null) {
                    pairs = new Pair[1];
                    pairs[0] = new Pair(score, value);
                } else {
                    if (pairs.length < 5) {
                        Pair[] newpairs = new Pair[pairs.length + 1];
                        System.arraycopy(pairs, 0, newpairs, 0, pairs.length);
                        pairs = newpairs;
                    }
                    int k = 0;
                    for(int i = pairs.length - 2; i >= 0; i--) {
                        if (pairs[i].score <= p.score) {
                            pairs[i + 1] = pairs[i];
                        } else {
                            k = i + 1;
                            break;
                        }
                    }
                    pairs[k] = p;
                }
                top5map.put(key, pairs);
            }
            line = br.readLine();
        }
        for(Map.Entry<String, Pair[]> e : top5map.entrySet()) {
            System.out.print(e.getKey());
            System.out.print(" ");
            System.out.println(Arrays.toString(e.getValue()));
        }
        System.out.println(System.currentTimeMillis() - start);
    }

    static class Pair {
        double score;
        String value;

        public Pair(double score, String value) {
            this.score = score;
            this.value = value;
        }

        public int compareTo(Object o) {
            Pair p = (Pair) o;
            return (int)Math.signum(score - p.score);
        }

        public String toString() {
            return String.valueOf(score) + ", " + value;
        }
    }
}

Сценарий AWK для подделки данных:

BEGIN {
 for (i = 0; i < 27000000; i++) {
  v = rand();
  k = int(rand() * 100);
  print k " " v " " i;
 }
 exit;
}

Из всех программ в этом потоке, которые я По результатам тестирования версия OCaml является самой быстрой и одной из самых коротких . (Измерения на основе строк кода немного нечеткие, но они не явно длиннее , чем версия Python или версии C или C ++, и явно быстрее.)

Примечание. Я понял, почему мои ранние среды выполнения были такими недетерминированными! Радиатор моего процессора был забит пылью, и в результате мой процессор перегрелся. Теперь я получаю хорошие детерминированные результаты тестов. Я думаю, что теперь я переделал все измерения времени в этой цепочке, теперь, когда у меня есть надежный способ измерения времени.

Вот временные параметры для разных версий на данный момент, работающих на 630-мегабайтах с 27 миллионами строк файл входных данных. Я использую Ubuntu Intrepid Ibex на двухъядерном Celeron 1,6 ГГц, работающем под управлением 32-разрядной версии ОС (драйвер Ethernet был сломан в 64-разрядной версии). Я запускал каждую программу пять раз и сообщал, сколько раз были предприняты эти пять попыток. Я использую Python 2.5.2, OpenJDK 1.6.0.0, OCaml 3.10.2, GCC 4.3.2, SBCL 1.0.8.debian и Octave 3.0.1.

• Версия SquareCog's Pig: еще не проверена (потому что я не могу просто apt-get install pig ), 7 строк кода.
• Чистая версия SQL от mjv: еще не тестировалась, но я прогнозирую время выполнения в несколько дней; 7 строк кода.
• Версия OCaml ygrek: 68,7 секунды ± 0,9 в 15 строках кода.
• Моя версия Python: 169 секунд ± 4 или 86 секунд ± 2 с Psyco, в 16 строках кода.
• версия Python на основе кучи abbot: 177 секунд ] ± 5 в 18 строках кода, или 83 секунды ± 5 с Psyco.
• Моя версия C ниже, составленная с помощью GNU sort -n : 90 + 5,5 секунды (± 3, ± 0,1), но дает неправильный ответ из-за недостатка в GNU sort , в 22 строках кода (включая одна строка оболочки.)
• Версия hrnt C ++: 74 строк кода.
• Версия Matlab Грега: не работает.
• Предложение Шайлер Эрле об использовании Pyrex в одной из версий Python: еще не пробовалось.

Я полагаю, что версия аббата для меня получается хуже, чем для них, потому что реальный набор данных имеет крайне неравномерное распределение: как я уже сказал, некоторые aa значения («игроки») содержат тысячи строк, а другие - только одну

. ] О Psyco: Я применил Psyco к своему исходному коду (и версии аббата), поместив его в функцию main , которая сама по себе сократила время примерно до 140 секунд, и вызвав psyco.full () перед вызовом main () . Это добавило около четырех строк кода.

Я могу почти решить проблему с помощью GNU sort следующим образом:

kragen@inexorable:~/devel$ time LANG=C sort -nr infile -o sorted

real    1m27.476s
user    0m59.472s
sys 0m8.549s
kragen@inexorable:~/devel$ time ./top5_sorted_c < sorted > outfile

real    0m5.515s
user    0m4.868s
sys 0m0.452s

Здесь top5_sorted_c - это короткая программа на C:

#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum { linesize = 1024 };

char buf[linesize];
char key[linesize];             /* last key seen */

int main() {
  int n = 0;
  char *p;

  while (fgets(buf, linesize, stdin)) {
    for (p = buf; *p && !isspace(*p); p++) /* find end of key on this line */
      ;
    if (p - buf != strlen(key) || 0 != memcmp(buf, key, p - buf)) 
      n = 0;                    /* this is a new key */
    n++;

    if (n <= 5)               /* copy up to five lines for each key */
      if (fputs(buf, stdout) == EOF) abort();

    if (n == 1) {               /* save new key in `key` */
      memcpy(key, buf, p - buf);
      key[p-buf] = '\0';
    }
  }
  return 0;
}

Сначала я попытался написать эту программу на C ++ следующим образом, и у меня время выполнения было значительно ниже, 33,6 ± 2,3 секунды вместо 5,5 ± 0,1. секунды:

#include <map>
#include <iostream>
#include <string>

int main() {
  using namespace std;
  int n = 0;
  string prev, aa, bb, cc;

  while (cin >> aa >> bb >> cc) {
    if (aa != prev) n = 0;
    ++n;
    if (n <= 5) cout << aa << " " << bb << " " << cc << endl;
    prev = aa;
  }
  return 0;
}

Я сказал почти . Проблема в том, что sort -n подходит для большинства данных, но не удается сравнить 0,33 с 3.78168e-05 . Так что, чтобы добиться такой производительности и решить проблему, мне нужна сортировка получше.

В любом случае, мне кажется, что я ною, но подход сортировки и фильтрации примерно в 5 раз быстрее, чем Python программа, в то время как элегантная программа STL от hrnt на самом деле немного медленнее - похоже, в есть какая-то грубая неэффективность. Я не Я не знаю, куда уходят остальные 83% времени выполнения в этой маленькой версии фильтра на C ++, но от этого нет ничего полезного, что заставляет меня подозревать, что я не знаю, куда он идет в hrnt std :: map версии тоже. Можно ли ускорить эту версию в 5 раз? Потому что это было бы круто. Его рабочий набор может быть больше, чем мой кеш L2, но, как оказалось, это, вероятно, не так.

Некоторые исследования с callgrind говорят, что моя программа фильтрации на C ++ выполняет 97% своих инструкций внутри оператор >> . Я могу идентифицировать как минимум 10 вызовов функций на входной байт, и cin.sync_with_stdio (false); не помогает. Это, вероятно, означает, что я мог бы заставить программу hrnt на C работать значительно быстрее, если бы анализировал входные строки более эффективно.

Изменить: kcachegrind утверждает, что программа hrnt выполняет 62% своих инструкций (в небольшом входном файле на 157000 строк), извлекая double s из istream . Существенная часть этого связана с тем, что библиотека istreams, по-видимому, выполняет около 13 вызовов функций на входной байт при попытке проанализировать double . Безумие. Могу я неправильно понять вывод kcachegrind?

В любом случае, есть другие предложения?

You could use smarter data structures and still use python. I've ran your reference implementation and my python implementation on my machine and even compared the output to be sure in results.

This is yours:

$ time python ./ref.py  < data-large.txt  > ref-large.txt

real 1m57.689s
user 1m56.104s
sys 0m0.573s

This is mine:

$ 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

And this is the source:

#!/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

Update: Know your limits. I've also timed a noop code, to know the fastest possible python solution with code similar to the original:

$ time python noop.py < data-large.txt  > noop-large.txt

real    1m20.143s
user    1m19.846s
sys 0m0.267s

And the noop.py itself:

#!/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

Here is one more OCaml version - targeted for speed - with custom parser on Streams. Too long, but parts of the parser are reusable. Thanks peufeu for triggering competition :)

Speed :

• simple ocaml - 27 sec
• ocaml with Stream parser - 15 sec
• c with manual parser - 5 sec

Compile with :

ocamlopt -pp camlp4o code.ml -o caml

Code :

open Printf

let cmp x y = compare (fst x : float) (fst y)
let digit c = Char.code c - Char.code '0'

let rec parse f = parser
  | [< a=int; _=spaces; b=float; _=spaces; 
       c=rest (Buffer.create 100); t >] -> f a b c; parse f t
  | [< >] -> ()
and int = parser
  | [< ''0'..'9' as c; t >] -> int_ (digit c) t
  | [< ''-'; ''0'..'9' as c; t >] -> - (int_ (digit c) t)
and int_ n = parser
  | [< ''0'..'9' as c; t >] -> int_ (n * 10 + digit c) t
  | [< >] -> n
and float = parser
  | [< n=int; t=frem; e=fexp >] -> (float_of_int n +. t) *. (10. ** e)
and frem = parser
  | [< ''.'; r=frem_ 0.0 10. >] -> r
  | [< >] -> 0.0
and frem_ f base = parser
  | [< ''0'..'9' as c; t >] -> 
      frem_ (float_of_int (digit c) /. base +. f) (base *. 10.) t
  | [< >] -> f
and fexp = parser
  | [< ''e'; e=int >] -> float_of_int e
  | [< >] -> 0.0
and spaces = parser
  | [< '' '; t >] -> spaces t
  | [< ''\t'; t >] -> spaces t
  | [< >] -> ()
and crlf = parser
  | [< ''\r'; t >] -> crlf t
  | [< ''\n'; t >] -> crlf t
  | [< >] -> ()
and rest b = parser
  | [< ''\r'; _=crlf >] -> Buffer.contents b
  | [< ''\n'; _=crlf >] -> Buffer.contents b
  | [< 'c; t >] -> Buffer.add_char b c; rest b t
  | [< >] -> Buffer.contents b

let () =
  let all = Array.make 200 [] in
  let each a b c =
    assert (a >= 0 && a < 200);
    match all.(a) with
    | [] -> all.(a) <- [b,c]
    | (bmin,_) as prev::tl -> if b > bmin then
      begin
        let m = List.sort cmp ((b,c)::tl) in
        all.(a) <- if List.length tl < 4 then prev::m else m
      end
  in
  parse each (Stream.of_channel stdin);
  Array.iteri 
    (fun a -> List.iter (fun (b,c) -> printf "%i %f %s\n" a b c))
    all

Говоря о нижних границах времени вычислений:

Давайте проанализируем мой алгоритм выше:

for each row (key,score,id) :
    create or fetch a list of top scores for the row's key
    if len( this list ) < N
        append current
    else if current score > minimum score in list
        replace minimum of list with current row
        update minimum of all lists if needed

Пусть N будет N в верхнем N Пусть R будет количеством строк в вашем наборе данных Пусть K будет числом различных ключей

Какие предположения мы можем сделать?

R * sizeof (row)> RAM или, по крайней мере, он достаточно большой, чтобы мы не хотели загружать все это, используйте хеш для группировки по ключу и отсортируйте каждую корзину. По той же причине мы не сортируем весь материал.

Крагену нравятся хэш-таблицы, поэтому K * sizeof (состояние для каждого ключа) << RAM, скорее всего, он помещается в кеш L2 / 3

Kragen не сортирует , поэтому K * N << R, т.е. каждый ключ имеет гораздо больше, чем N записей

(примечание: A << B означает, что A мало относительно B)

Если данные имеют случайное распределение, то

после небольшого количества строк большинство строк будет отклонено условием минимума для каждого ключа, стоимость составляет 1 сравнение на строку.

Таким образом, стоимость одной строки составляет 1 поиск по хешу + 1 сравнение + эпсилон * (вставка списка + (N + 1) сравнения для минимума)

Если оценки имеют случайное распределение (скажем, от 0 до 1) и условия, указанные выше, выполняются, оба эпсилона будут очень маленькими.

Экспериментальное доказательство:

Набор данных из 27 миллионов строк выше производит 5933 вставки в первые N списков. Все остальные строки отклоняются простым поиском и сравнением ключей. epsilon = 0,0001

Таким образом, примерно стоимость составляет 1 поиск + сравнение на строку, что занимает несколько наносекунд.

На текущем оборудовании нет способа, которым это не будет пренебрежимо мало по сравнению с затратами на ввод-вывод и особенно затратами на синтаксический анализ. .

Приведенный выше набор данных из 27 миллионов строк дает 5933 вставки в первые N списков. Все остальные строки отклоняются простым поиском и сравнением ключей. epsilon = 0,0001

Таким образом, примерно стоимость составляет 1 поиск + сопоставление на строку, что занимает несколько наносекунд.

На текущем оборудовании нет возможности пренебречь этим по сравнению с затратами на ввод-вывод и особенно затратами на синтаксический анализ. .

Приведенный выше набор данных из 27 миллионов строк дает 5933 вставки в первые N списков. Все остальные строки отклоняются простым поиском и сравнением ключей. epsilon = 0,0001

Таким образом, примерно стоимость составляет 1 поиск + сопоставление на строку, что занимает несколько наносекунд.

На текущем оборудовании нет возможности пренебречь этим по сравнению с затратами на ввод-вывод и особенно затратами на синтаксический анализ. .

Интересно, что исходное решение Python на сегодняшний день является самым чистым выглядящим (хотя пример C ++ приходит Закрыть).

Как насчет использования Pyrex или Psyco в исходном коде?