Сортировка больших файлов

Кто быстрее?

Pure C // thread

Выложи сам файл или способ его генерации. Так, чтобы он у всех был одинаковый и можно было сравнивать решения.

да нет смысла выкладывать файл
генеришь тупо 10 метров, в одной строке - одно число
в мс его можно сделать за 5 секунд

быстрее sort из coreutils, должен быть.

Я наваял решение на питоне, которое выложу чуть попозже.

Гвидо? http://neopythonic.blogspot.ru/2008/10/sorting-million-32-bit-integers-in-2mb...

К тому же man 1 sort прекрасно может сортировать не только в памяти.

Я думаю, ты не первый, кто пишет mergesort на пистоне.

быстрее sort из coreutils

а кто сказал, что оно не жрет память на полную катушку ?

Гвидо?

оно
только я его переправил под 2-й питон

а кто сказал, что оно не жрет память на полную катушку ?

Там есть параметр --buffer-size

а кто сказал, что оно не жрет память на полную катушку ?

Дык это ж прекрасно)) Меньше диском будет шуршать. К тому же там ограничение вроде есть.

а кто сказал, что оно не жрет память на полную катушку ?

Я. Но можно ещё в ман заглянуть. Внешнюю сортировку он делать умеет.

Вот, товарищи даже точно говорят что есть.

Во первых лень думать, как его генерить. Во втрорых, что бы что-то сравнивать, нужны идентичные исходные данные. Т.ч. давай, выкладывай.

таки - да
с буффер-сайз утилита сорт шуршит раз в 5 быстрее, чем питон
было бы полезно сравнить производительность
я не сомневаюсь, что плюсы уделают питон
интересно было бы посмотреть на решение от жабы и - на чем тут народ еще пишет - и сравнить

ТС этого треда так пытается найти оптимальный вариант рассортировать мыла с яндекса и мылрушки. Помогите ему, аноны!

хыыы .. у меня товарищ устраивался в яндех ему такое задание давали. тоже туда подался?

да, это хорошее тестовое задание
мой питоновский вариант кстати укладывается в 50 строк кода

Хотя бы скажи, цифры целые? unsigned?

целые, целые положительные :-)

мой питоновский вариант кстати укладывается в 50 строк кода

но если не ошибаюсь bottleneck это таки память ? а то bash-скрипт делает ваш питон раз в пятьдесят :-) там всего-то одна строка из четырёх символов..

и да! исходный файл или способ генерации приложить и озвучить ограничения по памяти и прочему

Если перегнать исходный файл в бинарный mmap'нутный, и сортировать его алгоритмом с хорошей локальностью (тот же мерджсорт) получится быстро и эффективно по памяти.

ограничение не столько на память, сколько на число считываемых строк из исходного файла - читаем порциями по миллиону строк, то бишь по миллиону чисел - и эту - внимание - предварительно отсортированную - порцию пишем во временный файл

я понимаю, но исходное условие - формат исходного файла - текстовой

Так перегоняем той же программой.

хочется увидеть не-питоновское решение и сравнить

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

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

Он будет их кешировать в любом случае если есть куда. Нужно перед использованием делать posix_fadvise(...,POSIX_FADV_DONTNEED) или использовать заведомо большие файлы.

Это же известная задача: external merge sort + priority queue = O(n log n). В чём загвоздка?

загвозда видимо в том, что ТС не знает чего он хочет...

при отсутствии ограничений по памяти, сортировка множества целых занимает O(1). И похрен какими порциями и в каком формате они считываются/записываются

$ time java -cp out/production/ExternalSort Main

real    0m7.106s
user    0m3.330s
sys     0m4.327s

Кстати 1000000 чисел это как раз примерно 11 мегабайт текста.

сортировка множества целых занимает O(1)

С O(kn) не попутал ли? На деле она довольно тормозная, кстати, её ещё нужно умудриться реализовать её быстрее std::sort. Ещё одна задача из яндекса, ага :D

А я обычно в таком случае просто делаю mmap и не парюсь, потому как ведро само быстрей справится с задачей, нежели велосипедить!!!

у меня
time ./test-merge-sort.py
real 1m31.100s
user 1m25.284s
sys 0m4.876s

кстати, у меня в файле оказывается 5 миллионов чисел
они все в диапазоне от 0 до 100

Выложи сам файл или способ его генерации. Так, чтобы он у всех был одинаковый и можно было сравнивать решения.

Давай я вместо него.

#!/usr/bin/env python3
import random
MAXSIZE = 10 * 10 ** 6
size = 0
while(True):
	s = str(random.randrange(-(2 ** 66) + 1, 2 ** 66))
	size += len(s) + 1 #+1 for \n
	print(s)
	if size >= MAXSIZE:
		break

Эдди, ты не программист, помни это. Со своим mmap ты эпичнейшим образом всосёшь на дисковых операциях и cache locality всех уровней. А ещё если твоя прога внезапно упадёт в середине процесса, то это будет весьма забавно.

0 до 100

Тогда можно сделать сортировку подсчетом.

Давай я вместо него.

Давай я немного оптимизирую твой код (будем работать с uint32):

dd if=/dev/urandom bs=1024 count=$((1024*1024))

они все в диапазоне от 0 до 100

Если бы у тебя было 10 ** 12 чисел 0 и 1 ты бы их тоже сортировал внешней сортировкой?

будем работать с uint32

Не-не-не, Дэвид Блейн, в оригинале были числа текстом по одному на строку, и тем более никто не говорил про uint32.

Не, ну пожалуйста, я не против. Просто с интами фиксированного размера у всякой скриптопетушни хоть какой-то шанс ещё бы был.

кстати, у меня в файле оказывается 5 миллионов чисел
они все в диапазоне от 0 до 100

А нахрена тебе тогда ваще что-то сложнее массива со счетчиком?

Давай лучше уж с бигинтами играться, чтоб ни в какой uint64 даже не входили.

Да и насрать. Зато работает. И без проблем.

я закачал твой test_data_for_kto_tama.txt.xz
результат:

real 0m10.737s
user 0m9.928s
sys 0m0.660s


там всего 500000 чисел

А мы здесь чиселками меряемся. Кстати, насчёт отсутствия проблем это ты очень сильно сомневаешься. Достаточно иметь разрядность адресного пространства меньше или равной 32 и сразу же приехали. Ты, случаем, не на x86 сидишь? Ты же у нас знатный некрофил.

Не, ну пожалуйста, я не против. Просто с интами фиксированного размера у всякой скриптопетушни хоть какой-то шанс ещё бы был.

Наоборот же, у скриптовых яп очень большой оверхед на маленькие объекты. Шансы есть если работать с длинными строками

Просто с интами фиксированного размера у всякой скриптопетушни хоть какой-то шанс ещё бы был.

Не уверен... плохая работа с числами большого объёма, а особенно их парсинг из текста, в наколеночной программе на сях может быть хуже.

P.S.Правда, у автора надо читать по миллиону строк, а у меня их всего менее 500.000... ну, можно читать по 100.000.

Выкладываю свой код:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
  
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4

iters = []
f_input = open('input2.txt', 'r')

def intsfromfile(name):
  f_temp = open(name, 'r')
  while True:
     #a = array.array('d')
     a=[]
     for ii in xrange(0,100000):
	line = f_temp.readline()
	if line != '':
          a.append(long(str(line).strip()))
     if not a:
         break
     for x in a:
         yield x
  f_temp.close()

iii=0
while True:
  #a = array.array('d')
  a=[]
  for ii in xrange(0,100000):
    line = f_input.readline()
    if line != '':
      a.append(long(str(line).strip()))
  if not a:
      break
  f_name = 'tempfile%d' % iii    
  f_temp = open(f_name, 'a')
  iii +=1
  b = sorted(a)
  for yy in b:
    f_temp.write(str(yy)+'\n')
  f_temp.close()
  iters.append(intsfromfile(f_name))


f_output = open('output.txt', 'a')
for x in heapq.merge(*iters):
  f_output.write(str(x)+'\n')
f_output.close()

там всего 500000 чисел

Ну, я хотел уложиться в 10 мегабайт, но при этом получить диапазон от -2⁶⁶ + 1 до 2⁶⁶ - 1, чтобы uint64 не хватило.

да, я так и прописал кстати - по 100000 строк

Влазят в 32бита? В 64?