ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничная huge-сортировка
133 сообщений из 133, показаны все 6 страниц
  все  
Тяпничная huge-сортировка
    #39417383
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет друзья.

Как обычно Илья, Сова, Саша, Чингиз и все остальные.
 
Прошу прощения что отсутстовал почти 3 недели. Были овертаймы и завалы на
проекте. Но щас вроде разгреб.

В последнее время до меня долетает великий плач и стенания со стороны junior-девелоперов
о том что то тут, то там они были завалены на собеседованиях вопросом о сортировке толстых
текстовых файлов.

Давайте в форуме один раз и навсегда закодим решение и поставим точку в этих трудностях.

Буду краток. Надоело растекаться по дереву.

Вобщем дано:

Input:
Код: sql
1.
$ hugesort <inputFile.txt> [<outputFile.txt]



Output:
Код: sql
1.
outputFile.txt


Комментарии к ТЗ:
1) Предполагается любая операционная система Windows/Linux/BSD.
2) DBMS не установлен и не используется.
3) Исходный текстовый файл минимум четырёхкратно превышает доступную физическую память.
4) Результатом является - лексикографически отсортированный текстовый файл
5) Кодировки - опциональны. Тоесть мы на них пока забиваем болт. Символы - однобайтные.

Приветствуется:
1) C/C++/Rust/D
2) Delphi/FPC
3) Ассемблер. Хардкод и всякие там MMX/SSE1,2,3,4,5/AVX.

Что будем обсуждать:
1) Ваши идеи и сорцы.
2) Кардинальность. Структуры данных. Подсчет. Сжатие (возможно?).
3) Дисковая оптимизация. 1,2,3 физических дисковых устройства.

Что мы не будем обсуждать.
1) Чужие сорцы. Здесь я поясню что
в рамках форума Программирование,
лично мне, а также сообществу, интересно говорить с автором
и задавать вопросы по исходникам. Поэтому ссылка на
github "канает" только в одном случае - если вы автор
или участник разработки.
2) Готовые коробочные продукты.

Особо также приглашаю в топик Диму-Т т.к. слыхал что у него есть идеи по поводу сортировок. Ау, чел!

С уважением, ваш покорный слуга,
а также большой ворчун и бухтелка
mayton.
...
Рейтинг: 0 / 0
11.03.2017, 17:10
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417406
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХО тут самое узкое место файловый IO, его и надо оптимизировать. В каком-то топике это уже обсуждали.

Читаем сколько влезет в память, сортируем, скидываем во временный файл и так по кругу пока все не прочитаем.
Затем слияние временных файлов.

У этого метода даже название есть, только не помню, т.к. задача разве что для собеседований, в реальной жизни оптимизация начинается до получения этого биг-файла.
...
Рейтинг: 0 / 0
11.03.2017, 20:01
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417408
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.

Код: sql
1.
2.
3.
/mnt/disk1
/mnt/disk2
/mnt/disk3



При таком раскладе в фазе 2 merge-sort мы имеем

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
inputFile.part0001.txt (чтение)
inputFile.part0002.txt (чтение)
inputFile.part001.txt (запись)

inputFile.part0003.txt (чтение)
inputFile.part0004.txt (чтение)
inputFile.part002.txt (запись)
...



Возможны варианты с компромиссом. Когда у нас (0001) и (0002) читаются с устройства /mnt/disk1, и пишуться в /mnt/disk2

+Надо еще подумать как быть с третьей фазой. По сути решать пасьянс с файловой нагрузкой.
...
Рейтинг: 0 / 0
11.03.2017, 20:11
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417412
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TУ этого метода даже название есть, только не помню
сортировка слиянием - так и называется . у Кнута хорошо описана
...
Рейтинг: 0 / 0
11.03.2017, 20:21
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417415
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИзопропилDima TУ этого метода даже название есть, только не помню
сортировка слиянием - так и называется . у Кнута хорошо описана
Не, это другое , тут слияния сразу начинаются, а там слияние уже сортированных массивов. Пофиг как оно называется.
...
Рейтинг: 0 / 0
11.03.2017, 20:33
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417416
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.
Ерунду написал. Нет смысла рассматривать оптимизацию железа для решения данной задачи.

Я уже писал "в реальной жизни оптимизация начинается до получения этого биг-файла"

Если у тебя эта сортировка происходит регулярно и требует оптимизации, то оптимизацию надо начинать в источнике возникновения файла, т.к. их много, так нагрузку проще распределить.
...
Рейтинг: 0 / 0
11.03.2017, 20:40
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417425
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonМой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.
Ерунду написал. Нет смысла рассматривать оптимизацию железа для решения данной задачи.

Я уже писал "в реальной жизни оптимизация начинается до получения этого биг-файла"

Если у тебя эта сортировка происходит регулярно и требует оптимизации, то оптимизацию надо начинать в источнике возникновения файла, т.к. их много, так нагрузку проще распределить.
ОК. Поговорим тогда про оптимизаци в источнике.

Кардинальность. В теории (я не уверен стоит уточнить) это количество уникальных записей.

Допустим нам на вход идут данные следующего рода.
Код: sql
1.
2.
3.
0001,Arni,Arnold Shwarzennegger
0002,Jay,Jason Statham
0001,Arni,Arnold Shwarzennegger


Можно сказать что уникальных записей всего две хотя из текстового файла пришло 3 штуки.

Для сортировки и слияния совершенно нет необходимости многократно копировать повторения
если на 1-й фазе мы их слегка преобразуем. Мы учтем повторы в виде специального счетчика.
Код: sql
1.
2.
2,0001,Arni,Arnold Shwarzennegger
1,0002,Jay,Jason Statham



Счетчик удобно укладывается в алгоритм слияния. Подобно сортировке подсчетом. Его можно тащить аж до последней фазы
где два файла сливаются в один равный по размеру исходным данным. По сути это нечто вроде
RLE (run-length-encoding).

Когда принимать решение о введении счетчика или об отказе от него? Это вопрос.
Но в любом случае решение этой задачи потребует хотя-бы одного full-scan текстового
файла. И уж коли мы решили это делать то лучше собрать на этом шаге максимум
сведений.
...
Рейтинг: 0 / 0
11.03.2017, 21:09
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417427
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TЕрунду написал. Нет смысла рассматривать оптимизацию железа для решения данной задачи.
Еще дам один комментарий. Речь не идет об оптимизации железа. А скорее о сборе сведений
о конфигурации. И если конфигурация позволяет - то почему этим не воспользоваться?
Разумеется я не предлагаю форматировать и монтировать диски. Но разве ты, когда экспериментировал
с акторами не опрашивал систему на имеющиеся на борту количество CPU-s/Hyper-Threads?
...
Рейтинг: 0 / 0
11.03.2017, 21:12
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417459
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima TИМХО тут самое узкое место файловый IO, его и надо оптимизировать. В каком-то топике это уже обсуждали.

Читаем сколько влезет в память, сортируем, скидываем во временный файл и так по кругу пока все не прочитаем.
Затем слияние временных файлов.

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

Дисковий ввод вывод вторичен.

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

Поэтому первое, о чем должен позаботится программист, открыть
все файлы в режиме directio.
...
Рейтинг: 0 / 0
11.03.2017, 23:33
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417467
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Замётано док. Будем форсировать директ. Я уже название придумал.

Roilling-triplet algorithm. Типа крутящийся треугольник. А мои сомнения
по поводу дискового пасьянса - только что развеялись.

Псевдокод.

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
main(inputFile){

  devices = {"/mnt/disk1","/mnt/disk2","/mnt/disk3"};

  // Phase 1
  preparePartitions(devices, inputFile);

  // Phase 2
  while(existPartitions){
     mergeTriplet(devices);
  }

}
...
Рейтинг: 0 / 0
11.03.2017, 23:50
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417469
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonМой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.

Код: sql
1.
2.
3.
/mnt/disk1
/mnt/disk2
/mnt/disk3



При таком раскладе в фазе 2 merge-sort мы имеем

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
inputFile.part0001.txt (чтение)
inputFile.part0002.txt (чтение)
inputFile.part001.txt (запись)

inputFile.part0003.txt (чтение)
inputFile.part0004.txt (чтение)
inputFile.part002.txt (запись)
...



Возможны варианты с компромиссом. Когда у нас (0001) и (0002) читаются с устройства /mnt/disk1, и пишуться в /mnt/disk2

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


Так не интересно , с очень высокой вероятность я выиграю имея не лучший алгоритм сортировки
)

Я себе могу подключить в полигон для тестов
терабайт дискового пространства 50 000 iops и трансфером 2400 МБайт/сек
...
Рейтинг: 0 / 0
11.03.2017, 23:52
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417476
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХЯ себе могу подключить в полигон для тестов
терабайт дискового пространства 50 000 iops и трансфером 2400 МБайт/сек
Да подключай хоть амазон.

По сути здесь топик - про собеседование и рассуждения о том как решить данную задачу.

Но поскольку я - бухтелка и перфекционист, то я ставлю сверх-задачу, а именно оптимизацию merge-sort
при условии что она УЖЕ реализована и корректно работает на 1 локальном дисковом устройстве.
...
Рейтинг: 0 / 0
12.03.2017, 00:03
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417498
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
mayton

По сути здесь топик - про собеседование и рассуждения о том как решить данную задачу.

...... а именно оптимизацию merge-sort
при условии что она УЖЕ реализована и корректно работает на 1 локальном дисковом устройстве.

я не понимаю такую задачу.

Если реализована , давай посмотрим код, будем сомтреть как ее улучшать
по оптимизации ввода вывода.

или мы сначала делаем свою реализацию адаптированную под 1 дисковое устройство ?

мне кажется задачу нужно формулировать так.

Соровка текстового файлф размером 4 RAM используя
минимальное количество операций дискового ввода вывода.


ИМХО это задача не сколько для программистов , а больше для математиков.
...
Рейтинг: 0 / 0
12.03.2017, 01:17
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417500
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я думаю что лучше все таки такая форма

Соровка текстового файла размером 4 RAM
за минимальное время.
...
Рейтинг: 0 / 0
12.03.2017, 01:26
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417502
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonЯ думаю что лучше все таки такая форма

Соровка текстового файла размером 4 RAM
за минимальное время.



Для минимизации времени нужно выравнять условия .

1. Либо должна быть группа эталонных файлов.

2 Либо в алгоритме обязательно должны присутсовать счетчики
сравнений, объема и количества пермещений в памяти и дисковых операций.
Которые потом будут сравниваться.

а скорость должна меряться в попугаях телодвижений системы .
...
Рейтинг: 0 / 0
12.03.2017, 01:39
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417508
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
С эталонными файлами - проблема.

Пожалуй это главный косяк этой задачи на собесе.
Мы о них ничего не знаем. Это может быть текстовый файл.
CSV-экспорт из БД. HTML. И вообще все что угодно.

В некоторых постановках максимальная длина строки
ограничивалась в 255 символов. В некоторых в 2Г.

О кардинальности также нет сведений.

Вобщем вот такие вот условия.
...
Рейтинг: 0 / 0
12.03.2017, 02:12
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417509
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Кстате еще не маловажный критерий - длина строки.

Я чесно сказать изначально подумал что речь идет о сортировке произвольного
текстового файла по словам, а не строкам.

Если длина строк одинакова ( в идеале) или разумно детерминирована
то скорость можно будет увеличить в несколько разза счет следующего алгоритма.


1. разбиваем файл на блоки.
2. Блок в памяти содержит
строки из файла

метаструктуру - массив ячеек локации строк
struct str_lctn
{
int block_num; // номер блока загружаемого в память
int offset; // смещение строки в файле ( в памяти вычисляется через размер и номер блока )
int size; // размер строки ( опционально )
};

3 В памяти всегда лежат дискрипторы блоков

str_lctn min_lctn ; // локация минимальной строки блока
str_lctn max_lctn; // лолкация максимальной строки блока
На основании этой информации принимается решение
какой блок с каким мержить.


4. сортировка в памяти сводится к сортировке массива str_box.

5. В темповый файл пишутся массивы str_box-ов.

6 . если строки в файле одинаковой длины ,
то запись финального отсортированного файла
производится блоками строк по новому смещению.
И вобще без создания нового сортированного
файла , а заменой строк местами в имеющемся файле.


Не идеально, если не обнаружится критических подводных камней
то этот алгоритм - заявка на победу.
...
Рейтинг: 0 / 0
12.03.2017, 02:27
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417541
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХ,

я не совсем понял, по какому принципу мы будем бить файл на блоки.
(Сорян у меня c блоком - ассоциации c 8K Oracle db_block).
...
Рейтинг: 0 / 0
12.03.2017, 11:29
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417554
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonд0kХ,

я не совсем понял, по какому принципу мы будем бить файл на блоки.
(Сорян у меня c блоком - ассоциации c 8K Oracle db_block).

Импирически подбирать под число ядер, объем памяти, темпака и струкруру файла.
...
Рейтинг: 0 / 0
12.03.2017, 11:53
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417559
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Будет сложно просить пользователя вводить эти цифры. Часть из них лучше получить
из API по аналогии с lscpu, free, df.
...
Рейтинг: 0 / 0
12.03.2017, 12:08
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417570
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Слияние двух сортированных последовательностей делается в один проход, и памяти не требует.
Просто читаем последовательно два источника и пишем в приемник.
 
пример
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
		/// <summary>Объединение сортированных массивов</summary>
		public static List<T> ClueOrdered<T>(List<T> a1, List<T> a2) where T : IComparable<T> {
			Int32 cnt1 = a1.Count, cnt2 = a2.Count, i1 = 0, i2 = 0;
			var ret = new List<T>(cnt1 + cnt2);
			while(i2 < cnt2 || i1 < cnt1) {
				if(i2 == cnt2 || (i1 < cnt1 && a1[i1].CompareTo(a2[i2]) < 0)) {
					ret.Add(a1[i1]);
					i1++;
				} else if(i2 < cnt2) {
					ret.Add(a2[i2]);
					i2++;
				}
			}
			return ret;
		}


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

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

Т.е. если считаем что файл не сортированный, то одно ядро отдаем под слияния, а все остальные под сортировку блоков. Размер блока надо исходя из количества ядер выбирать, думаю чтобы 4-8 блоков на ядро получалось, чтобы слияния как можно раньше начались.
...
Рейтинг: 0 / 0
12.03.2017, 12:54
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417572
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TТ.е. если считаем что файл не сортированный, то одно ядро отдаем под слияния, а все остальные под сортировку блоков. Размер блока надо исходя из количества ядер выбирать, думаю чтобы 4-8 блоков на ядро получалось, чтобы слияния как можно раньше начались.
Я не просто так делаю акценты на дисковой подсистеме.

Если в 1-й фазе для тебя важна скорость сортировки блока в оперативке (можно поискать мультипоточный хоар)
То в фазе №2 у нас будет суровое физическое ограничение. Вы хоть в 16 ядер запускайте merge двух блоков (файлов)
но события ожидания у вас выстроятся в очередь на канале вашего жесткого диска.

Фактически фаза 2 представляет из себя сплошное дисковое копирование. И если кто-то из вас часто и много
копировал большие файлы (бэкапы) а я - много копировал, то вы представляете себе масштаб трагедии.

Если у вас не RAID стойка - а обычная рабочая станция то никакого масштабирования не будет.
...
Рейтинг: 0 / 0
12.03.2017, 13:01
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417579
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonDima TТ.е. если считаем что файл не сортированный, то одно ядро отдаем под слияния, а все остальные под сортировку блоков. Размер блока надо исходя из количества ядер выбирать, думаю чтобы 4-8 блоков на ядро получалось, чтобы слияния как можно раньше начались.
Я не просто так делаю акценты на дисковой подсистеме.

Если в 1-й фазе для тебя важна скорость сортировки блока в оперативке (можно поискать мультипоточный хоар)
То в фазе №2 у нас будет суровое физическое ограничение. Вы хоть в 16 ядер запускайте merge двух блоков (файлов)
но события ожидания у вас выстроятся в очередь на канале вашего жесткого диска.

Фактически фаза 2 представляет из себя сплошное дисковое копирование. И если кто-то из вас часто и много
копировал большие файлы (бэкапы) а я - много копировал, то вы представляете себе масштаб трагедии.

Если у вас не RAID стойка - а обычная рабочая станция то никакого масштабирования не будет.

У меня есть другой более наглядный пример.
и кстате о праметрах.
Есть одна такая распальцованная СУБД Оракл, ей сколько памяти не давай
она за сортировками при постройке индексов в темп залазит раньше.
чем другие СУБД с аналогичными объемами на аналогичном железе
соотвественно разница в десятки раз быстрее., за счет более
оптимального использования доступной оперативной памяти и ядер.
...
Рейтинг: 0 / 0
12.03.2017, 13:31
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417582
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonБудет сложно просить пользователя вводить эти цифры. Часть из них лучше получить
из API по аналогии с lscpu, free, df.

С этим нет проблем , есть проблемы со абстрактной структурой файла,
и невнятной постановкой задачи.
Под которую нужно писать сборщик статистики.

То есть как минимум +1 сканирование, и непонятный объем метаданных в оперативной памяти,
для создания универсальной серебрянной пули из говна .
...
Рейтинг: 0 / 0
12.03.2017, 13:37
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417586
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Есть 1 сканирование. Это факт. Предлагаю его взять на вооружение.
...
Рейтинг: 0 / 0
12.03.2017, 13:49
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417589
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
[quot mayton]maytonЯ не просто так делаю акценты на дисковой подсистеме.

Если в 1-й фазе для тебя важна скорость сортировки блока в оперативке (можно поискать мультипоточный хоар)
То в фазе №2 у нас будет суровое физическое ограничение. Вы хоть в 16 ядер запускайте merge двух блоков (файлов)
но события ожидания у вас выстроятся в очередь на канале вашего жесткого диска.
Задача первой фазы максимально быстро подготовить работу для начала второй.
Первые слияния можно сделать в памяти. Например:
3 ядра сортируют, двое выдали по сортированному блоку, запускаем слияние их в памяти, получаем слитый результат, третий выдал свой блок, запускаем слияние во временный файл. Точнее запуск слияния в файл надо по доступной оперативке подгонять, как только ее не хватает для слияния то лить результат в файл, т.к. слияние в памяти требует места столько же сколько исходные блоки занимают.

Как только образовалось два файла - начинаем слияния на уровне файлов.
maytonФактически фаза 2 представляет из себя сплошное дисковое копирование. И если кто-то из вас часто и много
копировал большие файлы (бэкапы) а я - много копировал, то вы представляете себе масштаб трагедии.

Если у вас не RAID стойка - а обычная рабочая станция то никакого масштабирования не будет.
Не забывай: сортировка еще идет.
В твоей постановке (данные в 4 раза больше) первые два файла мы получим обработав примерно 5-ю часть исходных данных.

В реальной задаче (из за которой я в тот топик и писал): сортировка почти сортированной таблицы ~15 тыс. строк, 200 таблиц сортировались 5 сек. однопоточно, в файле одна таблица занимала ~1,5 Мб, т.е. скорость сортировки всего 60 Мб/сек (300 Мб / 5 сек) Какие рэйды? Рядовой HDD на 100% загрузить бы.
Допустим у нас 4 ядра с HT (+60% дает, в топике про акторы мерили), т.е. пиковая скорость сортировки 60 * 4 * 1.6 = 384 Мб/сек.
Обычный домашний SSD, 500 Мб/сек чтение и запись. Т.е. скидать все на диск успеваем пока сортировка идет.

В итоге по окончании сортировки имеем последний отсортированный кусок в памяти и кучку сортированных файлов.

Сливать их по два переливая с диска на диск не вариант, много переливаний, тут надо делать слияние из всех сразу. Не намного сложнее по коду. В итоге каждый временный файл будет прочитан однократно и результат записан на диск. Для ускорения этой фазы можно второй диск использовать.
...
Рейтинг: 0 / 0
12.03.2017, 14:02
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417591
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonЕсть 1 сканирование. Это факт. Предлагаю его взять на вооружение.


Окей :)

Я предлагаю прокатиться на велоОЛАПе
и собрать гистограмную статистику.

Какие будут варианты ?

Предлагаю получить распределение селективности внутри строки.
Для случая когда 90% строк в файле имею одинаковый префикс.
...
Рейтинг: 0 / 0
12.03.2017, 14:14
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХmaytonЕсть 1 сканирование. Это факт. Предлагаю его взять на вооружение.


Окей :)

Я предлагаю прокатиться на велоОЛАПе
и собрать гистограмную статистику.

Какие будут варианты ?

Предлагаю получить распределение селективности внутри строки.
Для случая когда 90% строк в файле имею одинаковый префикс.
Добавлю.

На 1-м проходе мы можем

1) Сделать общий подсчет строк (N).
2) Используя хеш таблички, контрольные суммы или карту блума сделать count distinct.
Здесь я сделаю оговорку что нам не нужен точный подсчет. Можно даже сделать estimation.
Пускай это называется (M).
3) Если соотношение M/N близко к 1 - то делаем вывод что строки уникальны и упрощаем алгоритм.
Если M/N близко к 0 то делаем вывод что дублей много и форсируем дедупликацию в алгоритме merge.
4) Префиксы. Мне здесь на ум приходит дерево trie и его различные модификации.
Здесь я ставлю TODO: research на исследование как префиксное дерево поможет
прижать текстовый файл. В некотором гипотетическом варианте если на 1-м проходе
данные будут иметь благоприятный расклад - то мы уже получили сортировку деревом
и алгоритм закончен. Если мы вываливаемся по OutOfMemory - то надо проанализировать
полезную инфу которая пришли из trie и заюзать ее в алгоритме.
В этом-же пункте можно развернуть строки в "обратку" и посмотреть суффиксы.
5) Есть смешной (гипотетический вариант) когда на вход нам подали apache или jboss логи
и они де-факто уже сортированы (по timestamp) и нам остается просто правильно
принять решение о том что сортировка вообще не нужна. Понятно что это нивелирует
разработку но согласитесь такой кейс тоже надо рассмотреть.
...
Рейтинг: 0 / 0
12.03.2017, 15:20
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417598
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TЗадача первой фазы максимально быстро подготовить работу для начала второй.
Первые слияния можно сделать в памяти. Например:
3 ядра сортируют, двое выдали по сортированному блоку, запускаем слияние их в памяти, получаем слитый результат, третий выдал свой блок, запускаем слияние во временный файл. Точнее запуск слияния в файл надо по доступной оперативке подгонять, как только ее не хватает для слияния то лить результат в файл, т.к. слияние в памяти требует места столько же сколько исходные блоки занимают.
Да верно. После того как 1-я фаза подготавливает 2 файла (partitions) то 2-я фаза может приступать к слиянию.
Я чуть позже нарисую картинкой как я себе это вижу на временной диаграмме а также нарисую своя алгоритм
rolling-triangle (это оптимизация дисковой нагрузки).
...
Рейтинг: 0 / 0
12.03.2017, 15:29
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417601
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TНе забывай: сортировка еще идет.
В твоей постановке (данные в 4 раза больше) первые два файла мы получим обработав примерно 5-ю часть исходных данных.

В исходной постановке я предполагал что не в 4 раза. А более чем в 4 раза.
Считай что это big-data. Цифру 4 я просто взял с потолка чтобы отбить желание
воспользоваться page/swap технологиями и выдать фейковое решение.
...
Рейтинг: 0 / 0
12.03.2017, 15:39
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417608
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonд0kХпропущено...
Я предлагаю прокатиться на велоОЛАПе
и собрать гистограмную статистику.

Какие будут варианты ?

Предлагаю получить распределение селективности внутри строки.
Для случая когда 90% строк в файле имею одинаковый префикс.
Добавлю.

На 1-м проходе мы можем ...
На первом проходе надо искать сортированные последовательности, запоминать смещение {начало, размер}. Найти 4-8 самых больших и их не трогать, а чтобы время не терять - мелкие можно сразу в память загонять и по накоплению минимального блока запускать поток сортировки. Если результаты сортировки большие и не умещаются в память, то скидывать во временный файл.

По итогу получим N блоков:
1. 4-8 последовательностей из исходного файла
2. сортированный кусок в памяти
3. кучку сортированных временных файлов

Дальше принимать решение как смерживать: все сразу или какие-то промежуточные смерживания наименьших кусков сделать.

С таким подходом значительно сократится время сортировки, т.к. не будет сортировки сортированного.
...
Рейтинг: 0 / 0
12.03.2017, 16:08
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417611
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Смерживание N последовательностей можно свести к многоуровневому смерживанию:
Каждый смерживатель имеет на входе две последовательности и выдает на выход минимальный элемент.
Далее строим дерево смерживателей в соответствии с количеством входов. По мере заканчивания последовательностей дерево можно перестраивать.
Например для 4 последовательностей дерево будет из 3х смерживателей
Код: plaintext
1.
2.
3.
1  2  3  4
 \/    \/

    \/
\/ это смерживатели
...
Рейтинг: 0 / 0
12.03.2017, 16:20
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417625
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Dima TИМХО тут самое узкое место файловый IO, его и надо оптимизировать. В каком-то топике это уже обсуждали.

IMHO тут самое узкое место - не конкретное ТЗ. Т.к. в случае если файл 1 Тб и представляет из себя одну очень длинную строчку (или десяток строк по 100 Gb каждая) ... боюсь, файловый IO будет минимальной проблемой )))

maytonДопустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.

IMHO & AFAIK пофиг. Буферизация рулит.

При большом размере буфера, время последовательной чтения/записи + обработка + накладные расходы ОС в какой-то момент превысят потерю времени от перемещения головок.

AFAIK Обычно при объеме буфера за 16-64 Mb уже время перемещения головок становится не настолько значимо. Современная RAM вполне позволяет безболезненно под блоки ввода-вывода отдать несколько сотен мегабайт и не париться.
...
Рейтинг: 0 / 0
12.03.2017, 17:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417630
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonДавайте в форуме один раз и навсегда закодим решение и поставим точку в этих трудностях.
https://www.ozon.ru/context/detail/id/2527036/

 
Более 800 страниц печатного черного по белой бумаге текста. А мы возьмем и "один раз и навсегда закодим" !

Модератор: Просьба прятать картинки с оффтопом под спойлер
...
Рейтинг: 0 / 0
12.03.2017, 17:27
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417647
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevПри большом размере буфера, время последовательной чтения/записи + обработка + накладные расходы ОС в какой-то момент превысят потерю времени от перемещения головок.

Нет. Речь идет не о накладных расходах на seek, а именно о дисковом параллелизме.
Какие буферы не ставь - если у тебя 1 физический диск - пропускная способность
сортировки слиянием будет ограничена скоростью твоего канала 1 диска.
Причем фактически скорость merge будет менее чем 33% от этой пропускной способности.
...
Рейтинг: 0 / 0
12.03.2017, 18:28
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417650
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmaytonпропущено...

Добавлю.

На 1-м проходе мы можем ...
На первом проходе надо искать сортированные последовательности, запоминать смещение {начало, размер}. Найти 4-8 самых больших и их не трогать, а чтобы время не терять - мелкие можно сразу в память загонять и по накоплению минимального блока запускать поток сортировки. Если результаты сортировки большие и не умещаются в память, то скидывать во временный файл.

Согласен. Добавлю что нас будут интересовать крупные под-последовательности (явно больше чем 10 - 100 строк).
И таким образом если логи jboss или apache попадают под это определение - тогда этот исключительный случай
будет обобщен как отработка под-последовательности.

И не 4-8 а можно и больше. Главное чтоб partitions были крупные.
...
Рейтинг: 0 / 0
12.03.2017, 18:35
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417659
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T\/ это смерживатели
В моей терминологии это triplet. Тройка. Потому-что две вершины - это как-бы каналы
чтения. И одна вершина - это канал записи.
...
Рейтинг: 0 / 0
12.03.2017, 19:10
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417683
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonLeonid KudryavtsevПри большом размере буфера, время последовательной чтения/записи + обработка + накладные расходы ОС в какой-то момент превысят потерю времени от перемещения головок.

Нет. Речь идет не о накладных расходах на seek, а именно о дисковом параллелизме.
Какие буферы не ставь - если у тебя 1 физический диск - пропускная способность
сортировки слиянием будет ограничена скоростью твоего канала 1 диска.
Причем фактически скорость merge будет менее чем 33% от этой пропускной способности.
Тогда мне не понятно при чем тут "сортировка слиянием" и "3 диска"

Сортировка слиянием крайне замечательно по дискам "размазывается". Ну и понятно, что если есть 10-ть дисков, то скорость явно будет в 10 раз выше, чем с 1 диском.

Опять таки, сортировка слиянием эффективна на устройствах с последовательным доступом. На устройствах со случайным доступом ( RAM, SSD ) она большую часть своей прелести теряет. Предположу, что для таких устройств, эффективные алгоритмы (или как минимум параметры алгоритма) будут совершенно другие.
...
Рейтинг: 0 / 0
12.03.2017, 20:20
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417685
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsevmaytonпропущено...

Нет. Речь идет не о накладных расходах на seek, а именно о дисковом параллелизме.
Какие буферы не ставь - если у тебя 1 физический диск - пропускная способность
сортировки слиянием будет ограничена скоростью твоего канала 1 диска.
Причем фактически скорость merge будет менее чем 33% от этой пропускной способности.
Тогда мне не понятно при чем тут "сортировка слиянием" и "3 диска"
Давай пока отложим в сторону 3 диска.
...
Рейтинг: 0 / 0
12.03.2017, 20:26
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417689
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСогласен. Добавлю что нас будут интересовать крупные под-последовательности (явно больше чем 10 - 100 строк).
И таким образом если логи jboss или apache попадают под это определение - тогда этот исключительный случай
будет обобщен как отработка под-последовательности.

И не 4-8 а можно и больше. Главное чтоб partitions были крупные.
ИМХО это продолжение темы сортировки, т.е. сортировка склееных сортированных последовательностей.

Но тема тупиковая, надо по другому решать: индексы, просто выносить порядок сортировки в отдельный файл, там могут быть просто указатели (смешения) на начала строк исходного биг-файла. Я с DBF много работал, там никто не заморачивается физической сортировкой, только индексы.
...
Рейтинг: 0 / 0
12.03.2017, 20:45
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417692
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
На правах топик-стартера я все таки настаиваю на том что в данном топике
мы все таки создадим это решение.

Индексирование и базы данных - это все-таки отдельная тема.
...
Рейтинг: 0 / 0
12.03.2017, 20:53
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417695
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВ последнее время до меня долетает великий плач и стенания со стороны junior-девелоперов
о том что то тут, то там они были завалены на собеседованиях вопросом о сортировке толстых
текстовых файлов.
Правильный ответ: "Зачем надо сортировать?" Пусть спрашивающий опишет всю глубину жопы родившей этот файл, а отвечающий подумает надо ли ему работу в этой жопе.
...
Рейтинг: 0 / 0
12.03.2017, 20:59
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417696
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ЕМНИП это был вопрос из Microsoft-а.
...
Рейтинг: 0 / 0
12.03.2017, 21:01
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417698
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
mayton
 
д0kХпропущено...



Окей :)

Я предлагаю прокатиться на велоОЛАПе
и собрать гистограмную статистику.

Какие будут варианты ?

Предлагаю получить распределение селективности внутри строки.
Для случая когда 90% строк в файле имею одинаковый префикс.

Добавлю.

На 1-м проходе мы можем

1) Сделать общий подсчет строк (N).
2) Используя хеш таблички, контрольные суммы или карту блума сделать count distinct.
Здесь я сделаю оговорку что нам не нужен точный подсчет. Можно даже сделать estimation.
Пускай это называется (M).
3) Если соотношение M/N близко к 1 - то делаем вывод что строки уникальны и упрощаем алгоритм.
Если M/N близко к 0 то делаем вывод что дублей много и форсируем дедупликацию в алгоритме merge.
4) Префиксы. Мне здесь на ум приходит дерево trie и его различные модификации.
Здесь я ставлю TODO: research на исследование как префиксное дерево поможет
прижать текстовый файл. В некотором гипотетическом варианте если на 1-м проходе
данные будут иметь благоприятный расклад - то мы уже получили сортировку деревом
и алгоритм закончен. Если мы вываливаемся по OutOfMemory - то надо проанализировать
полезную инфу которая пришли из trie и заюзать ее в алгоритме.
В этом-же пункте можно развернуть строки в "обратку" и посмотреть суффиксы.
5) Есть смешной (гипотетический вариант) когда на вход нам подали apache или jboss логи
и они де-факто уже сортированы (по timestamp) и нам остается просто правильно
принять решение о том что сортировка вообще не нужна. Понятно что это нивелирует
разработку но согласитесь такой кейс тоже надо рассмотреть.




Предлагаю Step-by-step. Предположу, что у нас есть 3-и шага:
1. Сортировка РАЗлиянием.
Разделение файла на N-частей. На данном этапе мы уже можем проводить сортировку (например по первой букве, префексу).
2. Сортировка/досортировка получившихся отдельных частей
3. Сортировка слиянием

Есть следующие базовые параметры алгоритма
1. Кол-во частей которые одновременно сливаем/разливаем. В случае классического HDD или магнитной ленты (Кнут) - ограничено кол-вом устройств
2. Эффективный размер буфера для ввода/вывода с устройства.
Пункт 1 * 2 желательно должно помещаться в ОП
3. Максимальный размер одного атомарного файла
Желательно должен помещаться в ОП
4. "Стоимость" CPU vs IO. Например, в момент записи временного файла его можно сжимать (даже банальным LZW). Экономим IO, тратим CPU/RAM.

Вариант с "префиксами" мне кажется наиболее интересен в реальной жизни. Хотя... фиг знает... когда это реально критично.

IMHO Вполне можно на дереве найти такую функцию, что если x < y то и f(x) < f(y)

Т.е., если у нас все уникальный строки/префиксы помещаются в обычное binary tree и в RAM, то вполне можно кодировать строки их путем по дереву, это дает следующий профит:

1. Префик на дереве будет определять в какой временный файл мы пишем данные при "разлиянии". Т.е. сортировка произойдет уже на данном этапе. (а надо ли?)
2. Сортировать можно прямо "сжатые" данные.
3. Собственно компрессия, т.е. удаление дублей

Но это хорошо, если у нас есть отдельный проход для построения дерева. Но хочется обойтись без такого прохода, а некий алгоритм который позволит онлайн и строить дерево и выполнять "разлияние". При этом, не портя уже построенные данные. А как этого добиться - мне не очень понятно.

Т.е. помесь:
стандартного binary tree (отсортированность)
Хафмана (путь по дереву короче для часто встречающихся префиксов/строк)
Возможность построения онлайн, без порчи пред. данных и без вырождения (в случае если исходная последовательность уже отсортирована)

Но вот над чем я думаю... Технически, мы можем передвинуть работу с последнего шага на первый. Но нужно ли? Для одного устройства - скорее всего нет. Мы сокращаем параллельные чтения, но за счет параллельной записи ((( А что HDD, что SDD обеспечивают перформанс по чтению лучше, чем по записи. Для большого кол-ва накопителей - на каком шаге у нас будет возникать параллелизм, фиолетово. Выигрыша и тут не будет.

Единственный выигрыш - возможная компрессия. Но если диски сильно медленнее CPU, то тогда достаточно жать временные файлы максимального эффективными алгоритмами (a la LZW) и нафиг какой-то свой самопал.

В общем.... практический смысл и возможность использования в мирных целях ... от меня ускользает.
...
Рейтинг: 0 / 0
12.03.2017, 21:06
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417699
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Dima TНо тема тупиковая, надо по другому решать: индексы, просто выносить порядок сортировки в отдельный файл, там могут быть просто указатели (смешения) на начала строк исходного биг-файла. Я с DBF много работал, там никто не заморачивается физической сортировкой, только индексы.

Для Subj (СОРТИРОВКА huge файл) и устройств с последовательным/рядом последовательным доступом (диски) - это тупик.

Вариант 300 Mb - когда все влезает в RAM, даже не интересно. Отсортировать хоть банальным пузырьком и не париться ))).

IMHO
...
Рейтинг: 0 / 0
12.03.2017, 21:10
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417703
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,
обычно ещё есть ограничение на использование рам, н-р 1 Мб

делал такую задачку так (в принципе, классическая схема):
читал блоками по установленному лимиту

сортировал блок (QSort) и сохранял в файл

дальше над блоками обычная сортировка слияниями(объединение равноценных блоков)

делал сначал на fpc под Linux Min 16, ext4, i7 4710HQ, ноут
тот же код под Windows на NTFS работал раза в 3-4 медленнее

под linux диск был под завязку занят даже при однопоточной модели, собственно всё упёрлось в производительность диска
под Windows диск был более менее доступен, я так понимаю он на каждый IO забирал время у текущей задачи, что и привело к деградации производительности

на всякий случай попробовал с потоками, ускорение было только под Windows и то незначительно - Linux всё равно догнать не удалось

из маргинальных вариантов:

предварительную разивку делать по первой букве

делать предварительную разбивку по сортированным кускам (достаточно проверять предыдущую строку)

на аморфной массе в 10 гб все эти способы фактически проваливаются, первый из-за деградации IO, второй - тупо таких внушительных блоков нет
...
Рейтинг: 0 / 0
12.03.2017, 21:17
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417705
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev1. Сортировка РАЗлиянием.
Разделение файла на N-частей. На данном этапе мы уже можем проводить сортировку (например по первой букве, префексу).
2. Сортировка/досортировка получившихся отдельных частей
3. Сортировка слиянием
Нужно делить не на N частей а на partitions по размеру близкие к тому что выдает
утилита free. Сортировать каждый parition отдельно quick-sort и сохранять его как файл на диск.
Здесь-же можно провести дедупликацию.
...
Рейтинг: 0 / 0
12.03.2017, 21:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417711
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)делал такую задачку так (в принципе, классическая схема):
читал блоками по установленному лимиту

сортировал блок (QSort) и сохранял в файл

дальше над блоками обычная сортировка слияниями(объединение равноценных блоков)


В 2003-м я делал это на C# с XML документами. Но постановка была посложнее
т.к сложно было оценить сколько XML-records загонять в 1 блок и сервер периодически
падал. А XMLReader не обладал API для подсчета символов. Вобщем делал partitions
на глаз. По количеству тегов.
...
Рейтинг: 0 / 0
12.03.2017, 21:23
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417718
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonНа правах топик-стартера я все таки настаиваю на том что в данном топике
мы все таки создадим это решение.
Я бы все таки определился, что такое "текстовый". И что такое "строка"

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

Предлагаю понятие строка, в ТЗ хотя бы 256 или пусть даже 1024 символами ограничить. А то ТЗ, совершенно не ТЗ )))

maytonDima T\/ это смерживатели
В моей терминологии это triplet. Тройка. Потому-что две вершины - это как-бы каналы
чтения. И одна вершина - это канал записи.
Почему две вершины?

Насколько я помню Кнута (читал лет 25 назад!), кол-во каналов чтения предлагалось выбирать по кол-ву устройств. Если брать современных SDD / HDD, то грубо говоря, кол-во RAM / размер буфера выделенного для последовательного много блочного чтения/записи.

Предположим, что у нас huge файл 1 Tb и 1 Gb RAM. Буфер IO пусть 64 Mb, тогда одновременно сливаем до 16 файлов.

Первый проход по диску (разлияние + сортировка) - чтение 1 Tb и запись 1024 отсортированных частей
Второй проход 1024 / 16 = 64
Третий проход 64 / 16 = 4
Четвертый проход - завершили обработку

Т.е. IO 4 Tb чтения, 4 Tb записи. В случае triplet, нужно было бы 10-11 проходов.

Все же, современные HDD (а тем более SSD), это не магнитные ленты.

Подозреваю, что для SSD можно было бы и буфером < 1 Mb обойтись и все выполнить в 2 прохода. Разлияние + сортировка, слияние в один проход из 1024 файлов одновременно.

Т.е., есть подозрение, что для SSD и улучшать особо нечего, да и не нужно.

Чисто теоретически. IMHO & AFAIK
...
Рейтинг: 0 / 0
12.03.2017, 21:29
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417719
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevВариант с "префиксами" мне кажется наиболее интересен в реальной жизни. Хотя... фиг знает... когда это реально критично.

IMHO Вполне можно на дереве найти такую функцию, что если x < y то и f(x) < f(y)

Т.е., если у нас все уникальный строки/префиксы помещаются в обычное binary tree и в RAM, то вполне можно кодировать строки их путем по дереву, это дает следующий профит:

1. Префик на дереве будет определять в какой временный файл мы пишем данные при "разлиянии". Т.е. сортировка произойдет уже на данном этапе. (а надо ли?)
2. Сортировать можно прямо "сжатые" данные.
3. Собственно компрессия, т.е. удаление дублей

Давай бинарное или красно-черное или АВЛ сразу выбросим в топку. Они хранят ключи
в первичном виде и нем не хватит места.

Нам нужно дерево поджимающее ключи. Из таковых я могу вспомнить trie (prefix-tree), radix e.t.c.
...
Рейтинг: 0 / 0
12.03.2017, 21:29
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417723
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonkealon(Ruslan)делал такую задачку так (в принципе, классическая схема):
читал блоками по установленному лимиту

сортировал блок (QSort) и сохранял в файл

дальше над блоками обычная сортировка слияниями(объединение равноценных блоков)


В 2003-м я делал это на C# с XML документами. Но постановка была посложнее
т.к сложно было оценить сколько XML-records загонять в 1 блок и сервер периодически
падал. А XMLReader не обладал API для подсчета символов. Вобщем делал partitions
на глаз. По количеству тегов.
SAX в этом случае надо бы использовать - обычно у этих парсеров есть поблочное добавление RAW данных, которые собственно и лимитируешь
ну а периодические падения окружения, наверное, не должны включаться в условие тестового задания

или это реальная задача?
...
Рейтинг: 0 / 0
12.03.2017, 21:31
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417726
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevЕдинственный выигрыш - возможная компрессия. Но если диски сильно медленнее CPU, то тогда достаточно жать временные файлы максимального эффективными алгоритмами (a la LZW) и нафиг какой-то свой самопал.

Про компрессию я упоминал выше одобрительно. Но лучше без LZW. Для объемов
которыми оперирует big-data нам достаточно хотя-бы поджать дубли и это уже
будет огромный плюч к самой процедуре merge.

А LZW на больших объемах теряет эффективность особенно когда после 50% файла
меняется кодировка или энтропия потока. LZW уже не может перестроить справочник
и становится балластом.
...
Рейтинг: 0 / 0
12.03.2017, 21:34
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417728
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)maytonпропущено...

В 2003-м я делал это на C# с XML документами. Но постановка была посложнее
т.к сложно было оценить сколько XML-records загонять в 1 блок и сервер периодически
падал. А XMLReader не обладал API для подсчета символов. Вобщем делал partitions
на глаз. По количеству тегов.
SAX в этом случае надо бы использовать - обычно у этих парсеров есть поблочное добавление RAW данных, которые собственно и лимитируешь
ну а периодические падения окружения, наверное, не должны включаться в условие тестового задания

или это реальная задача?
XMLReader не виноват. Собственно это почти и есть SAX если посмотреть на его юзкейсы.
И память не он потреблял а коллекция куда я складывал теги перед тем как подать их
на вход QuickSort.
...
Рейтинг: 0 / 0
12.03.2017, 21:36
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417729
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Такую задачу не делал, т.к. было не нужно.

И стандартными методами (СУБД) данные в единицы / сотни Гигабайт обрабатывались вполне нормальное время. Подождать десяток секунд - минута для сортировки реальных данных 8 Gb в банальном PostgreSQL - не проблема.

Программно (JDBC) переливал в многопотоке данные под сотни Гб, но и там, за пару часов все вполне себе строилось )))

Работал с БД в 15 Tb, но она крутились на железке с дисками FC и со скоростью full scan в 2-4 Gb в секунду )))
...
Рейтинг: 0 / 0
12.03.2017, 21:36
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417733
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevЯ бы все таки определился, что такое "текстовый". И что такое "строка"

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

Предлагаю понятие строка, в ТЗ хотя бы 256 или пусть даже 1024 символами ограничить. А то ТЗ, совершенно не ТЗ )))

Я согласен. Нам сложно будет вычислять разрядность смещения если не знаем какая длина строки. Зайдем в тупик нахер...

Давайте обсудим. ИМХО 256 - это маловато. Кажется у меня есть исходники
в которых длина строки поболее.

Вот 64K символов это уже ближе к реалу. Вроде как длина сегментика. Или близко к Oracle VARCHAR2(32000).

Или можно в 4Гига. Вроде как уже ограничение 32х битной машинки.

Вобщем скажите ваше имхо.
...
Рейтинг: 0 / 0
12.03.2017, 21:42
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417738
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Леонид, забегая вперед я скажу что штатная тулза от windows
уже умеет смотреть в temp но я не ищу легких путей. Я ставлю сверх
задачи с оптимизациями которые штатные утилиты скорее всего (99%)
проигнорировали.
Код: sql
1.
2.
3.
4.
5.
6.
  /T[EMPORARY]

    [диск2:][путь2]           Определяет путь к папке, содержащей рабочие
                              файлы сортировки, в том случае, когда данные
                              не помещаются в основной памяти. По умолчанию
                              используется системная временная папка.
...
Рейтинг: 0 / 0
12.03.2017, 21:46
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417740
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonДля объемов
которыми оперирует big-data нам достаточно хотя-бы поджать дубли и это уже
будет огромный плюч к самой процедуре merge.

а настолько ли это критично и какое железо / данные.

А тогда возникает вопрос, насколько все "пляски с бубном" это могут ускорить? На 20-30%, на 50%... А это спасет "отца русской демократии"?
...
Рейтинг: 0 / 0
12.03.2017, 21:53
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417743
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevПредположим, что у нас huge файл 1 Tb и 1 Gb RAM. Буфер IO пусть 64 Mb, тогда одновременно сливаем до 16 файлов.

Первый проход по диску (разлияние + сортировка) - чтение 1 Tb и запись 1024 отсортированных частей
Второй проход 1024 / 16 = 64
Третий проход 64 / 16 = 4
Четвертый проход - завершили обработку

Честно говоря я не очень понял твою арифметику. Сколько-бы у тебя буферов не стояло,
ты не можешь превысить паспортную скорость канала взаимодействия c HDD.

Тоесть в прямом (direct) алгоритме сортировки слиянием с 1 Tb HDD, 1 Gb RAM.
Мы делаем
1) 1024 partitions, и столько-же quick-sorts
2) 512 merges 1+1 = 1
3) 256 merges
4) 128
5) 64
6) 32
7) 16
8) 8
9) 4
10) 2
11) Алгоритм завершен. Мы получили отсортированный терабайт.

(в скобках замечу что требуется дополнительная дисковая память)

Далее. Я опираюсь на инженерное предположение что файл не всегда лежит на HDD/SDD.
Он может лежать на абстрактных устройствах с ярко выраженным последовательным
доступом WebDav/HTTP, и вообще я считаю что устройства последовательног доступа
сокеты, каналы передачи данных, и даже жлобские unixoвые stdin/stdout
всегда были есть и будут неотъемлемым элементом It-вселенной.

Поэтому Я и старина Кнут могут не беспокоится по поводу девальвации
алгорима. Он по прежнему будет востребован. Хотя и не так сильно
как в эпоху магнитных лент и перфолент.
...
Рейтинг: 0 / 0
12.03.2017, 21:59
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevmaytonДля объемов
которыми оперирует big-data нам достаточно хотя-бы поджать дубли и это уже
будет огромный плюч к самой процедуре merge.

а настолько ли это критично и какое железо / данные.

А тогда возникает вопрос, насколько все "пляски с бубном" это могут ускорить? На 20-30%, на 50%... А это спасет "отца русской демократии"?
Ну представь себе график. Типа по горизонтали эффективность алгоритма (в нашем
случае пропускная способность в строках) а по вертикали - complexity алгоиима.

Так вот. Если мы просто включим RLE, или подсчет повторов строк - это даст
+10% к сложности алгоритма мержа. И с другой стороны даст х..й его знает
сколько эффективности. Может 0%. А может 1000%. Все зависит от числа дублей
в файле.

Стоит ли игра свеч? ХЗ. Я считаю что при включении этого жлобского RLE - стоит.
На графике будет резкий излом.

А вот LZW я-бы уже не включал. Просто мне так кааааатся.
...
Рейтинг: 0 / 0
12.03.2017, 22:03
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417754
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonЧестно говоря я не очень понял твою арифметику. Сколько-бы у тебя буферов не стояло,
ты не можешь превысить паспортную скорость канала взаимодействия c HDD.
...
11) Алгоритм завершен. Мы получили отсортированный терабайт.

Да. Классический. Работающий на чисто последовательной магнитной ленте (3 штуки).

Но если магнитных лент не 3, а больше - то никто не мешает за один шаг обработки сразу делать merge нескольких файлов.

Т.к. доступ к HDD, а тем более к SSD, все же НЕ "ярко выраженный последовательный", то никто не мешает на HDD, а тем более SSD (!) мерж выполнять за значительно меньшее число проходов.

maytonДалее. Я опираюсь на инженерное предположение что файл не всегда лежит на HDD/SDD.
Он может лежать на абстрактных устройствах с ярко выраженным последовательным
доступом WebDav/HTTP, и вообще я считаю что устройства последовательног доступа
....
Файл или ВРЕМЕННЫЕ файлы?

Конечно, можно и swap на WebDav / HTTP положить, но нужно ли и насколько часто это требуется?
...
Рейтинг: 0 / 0
12.03.2017, 22:17
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417764
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevНо если магнитных лент не 3, а больше - то никто не мешает за один шаг обработки сразу делать merge нескольких файлов.

Т.к. доступ к HDD, а тем более к SSD, все же НЕ "ярко выраженный последовательный", то никто не мешает на HDD, а тем более SSD (!) мерж выполнять за значительно меньшее число проходов.

Я не очень понимаю зачем ты так зацепился за SSD.

Ну ОК. Давай так. Две опции алгоритма. Первый летает по классической схеме которую я описал.
А второй попробуй реализовать сам опираясь на свойства SDD.
Код: sql
1.
$ hugesort --hdd  ...



Код: sql
1.
$ hugesort --sdd  ...
...
Рейтинг: 0 / 0
12.03.2017, 22:33
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417769
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonЯ не очень понимаю зачем ты так зацепился за SSD.

Я зацепился за сферичность задачи.

Можно обсуждать сферичную сортировку, но обсуждать сферичную ОПТИМАЛЬНУЮ сортировку - это уже за гранью добра и зла.

Т.к. понятие оптимальности будут разные. Особенно если мы говорим про ОПТИМИЗАЦИЮ. Магнитные ленты это одно, RAM это другое, SSD где-то посередине.

Ээээх!... Давай....

Только у меня на домашнем компе с местом не все хорошо. 20 Gb на SSD, 100 Gb на Seagate + есть WD Green. Пошел запускать Eclipse.
...
Рейтинг: 0 / 0
12.03.2017, 22:44
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid KudryavtsevmaytonЯ не очень понимаю зачем ты так зацепился за SSD.

Я зацепился за сферичность задачи.
И не говори. Чортов Microsoft. Поубивать бы таких собеседователей... Мдя.
...
Рейтинг: 0 / 0
12.03.2017, 22:52
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417833
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Leonid Kudryavtsevmaytonпропущено...

В моей терминологии это triplet. Тройка. Потому-что две вершины - это как-бы каналы
чтения. И одна вершина - это канал записи.
Почему две вершины?

Насколько я помню Кнута (читал лет 25 назад!), кол-во каналов чтения предлагалось выбирать по кол-ву устройств. Если брать современных SDD / HDD, то грубо говоря, кол-во RAM / размер буфера выделенного для последовательного много блочного чтения/записи.
ИМХО дерево из триплетов эффективнее. Закэшировал в триплите минимальный из 2-х, забрали, закэшировал следующий и т.д.
А если все входы собрать в один массив, то каждый раз скан всех входов в поисках минимального.
...
Рейтинг: 0 / 0
13.03.2017, 07:12
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417846
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
парни, задача тестовая и обычно для системщиков

ограничения обычно на RAM - пусть мегабайт, два; длина строки путь до 256 - 1000 символов, диски абсолютно неизвестный (но памяти там с большим запасом)

нравится это или нет, все вопли и фантазии про SQL сервер и пр., которые что-то могут - не в тему. То что могут выжать такого рода системы относится к другим вопросам и задаются другим людям.
...
Рейтинг: 0 / 0
13.03.2017, 08:40
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417850
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИМХО дерево из триплетов эффективнее.
Вот с этого момента - непонятно.
...
Рейтинг: 0 / 0
13.03.2017, 08:57
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417856
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima TИМХО дерево из триплетов эффективнее.
Вот с этого момента - непонятно.
Что такое слияние сортированных последовательностей:
берем головы последовательностей, т.е. первый элемент каждой и выбираем минимальный, его отправляем на выход, в той последовательности из которой он был берем следующий и так по кругу пока все элементы не кончатся.

Если у нас N последовательностей, то каждый проход N-1 сравнений.

Если дерево то log 2 (N), т.к. верхний триплет извлекая элемент со входа заставляет извлечь следующий элемент только один нижестоящий триплет и т.д. по цепочке.

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

В случае с твоим биг-файлом это два чтения исходного файла: первый проход инициализация триплетов, второй запись результата.
...
Рейтинг: 0 / 0
13.03.2017, 09:12
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417885
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ладно. Беру рекламную паузу. Вечером нарисую картинку.
...
Рейтинг: 0 / 0
13.03.2017, 10:22
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39417898
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В принципе можно без сортировок, на одних триплетах:

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

Как все последовательности вошли в дерево - слив результата.
...
Рейтинг: 0 / 0
13.03.2017, 10:36
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418133
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тут можно взять файлик для тестов 1.2 Гб неупорядоченного текста, местами сортированного.
...
Рейтинг: 0 / 0
13.03.2017, 14:33
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418153
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Dima T.....
А если все входы собрать в один массив, то каждый раз скан всех входов в поисках минимального.
Да хоть по сто раз скан всех входов...

Разница скана в RAM и доступ к диску/ленте - не порядки, а несколько порядков (тысячи, десятки тысяч раз, а может и больше).

Сейчас код допишу и на SSD протестю. Сможет ли на __самом__ дешевом SSD (покупал пару лет назад за 2 тыс. рублей ))) ) сливать пару сотен файлов одновременно.

Сложность алгоритма в виде логарифма от степени двойки - это конечно хорошо. Но логарифм от сотни/тысячи - выглядит намного лучше ))) IMHO & AFAIK
...
Рейтинг: 0 / 0
13.03.2017, 14:54
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418175
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Leonid KudryavtsevDima T.....
А если все входы собрать в один массив, то каждый раз скан всех входов в поисках минимального.
Разница скана в RAM и доступ к диску/ленте - не порядки, а несколько порядков (тысячи, десятки тысяч раз, а может и больше).
DDR4 - 4,5 Гб/сек, SSD - 0,5 Гб/сек всего в 9 раз, даже одного порядка не набирается.
...
Рейтинг: 0 / 0
13.03.2017, 15:15
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418177
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Leonid KudryavtsevСейчас код допишу и на SSD протестю.
Интересно не скорость SSD померить, а скорость алгоритма, т.е. сколько IO в байтах. Встрой счетчики: сколько байт записано во временные файлы и сколько всего прочитано из всех файлов включая исходный.
...
Рейтинг: 0 / 0
13.03.2017, 15:20
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418378
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

есть серьёзные основания полагать, что производительность HDD очень зависит от порядка доступа к файлу

н-р сливать в один файл последовательно гораздо быстрее , чем в несколько разных файлов
...
Рейтинг: 0 / 0
13.03.2017, 19:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418402
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,

есть серьёзные основания полагать, что производительность HDD очень зависит от порядка доступа к файлу
Нет оснований. По середине между прогой и HDD стоит ОС со своим кэшем и боле-мене выравнивает эту проблему.

kealon(Ruslan)н-р сливать в один файл последовательно гораздо быстрее , чем в несколько разных файлов
Мой алгоритм предполагает random-read и последовательный write.

 
PS Сортировка деревом триплетов пока не взлетела. Перегруз проца. Дерево из 1024 триплетов (10 уровней) сортировало 68 кб несколько минут :(
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
/*

Сортировка файла построчно слияниями сортированных последовательностей. 

1й проход: Поиск возрастающих участков файла. Построение списка источников.
В случае заполнения списка источников до достижения конца файла слияние 
половины меньших по размеру источников во временный файл и подключение его
как источника. И т.д. до завершения прохода.

2й проход: Слияние в выходной файл.


*/

#define SOURCE_MAX 1024 // Максимальное количество источников, кратно степени 2
#define STRING_MAX 256 // Максимальный размер строки файла

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdint.h>

// Буфер для кэширования одной строки
struct item_t {
	char data[STRING_MAX];

	bool operator < (item_t const &b) const { return memcmp(data, b.data, STRING_MAX) < 0; }

};

// Интерфейс источника последовательности
class source_t {
	item_t* first;		// Первый элемент в последовательности

public:
	source_t() : first(NULL) {}

	virtual ~source_t() {}

	// Первый элемент в очереди, NULL если пусто
	virtual const item_t* front() {
		if(first == NULL) {
			pop();
		}
		return first;
	}

	// Извлечение следующего элемента
	virtual void pop() {
		first = next();
	}

	// Считывание следующего элемента последовательности, NULL если читать нечего
	virtual item_t* next() {
		return NULL;
	}

	// Общая длина последовательности в любых попугаях, используется для сравнения размеров последовательностей
	virtual size_t size() {
		return 0;
	}
};

// Интерфейс приемника
class destination_t {
public:
	virtual ~destination_t() {}

	// Установка источника
	void source_set(source_t* src) {
		assert(src != NULL);
		// Запись всего что есть в источнике
		const item_t* i;
		while(i = src->front()) {
			write(i);
			src->pop();
		}
	}

	// Запись элемента
	virtual void write(const item_t* item) {

	}
};

// Последовательность из файла или куска файла
class file_t : public source_t, public destination_t {
	item_t item;	// Последняя прочитанная запись
	size_t offset;	// Смешение для чтения следующей строки
	size_t end;		// Конец блока
	FILE* f;		// Файл

public:
	file_t() : f(NULL), offset(0), end(0) {}

	~file_t() {
		assert(end == offset); // Прочитан не полностью
	}

	void init(FILE* f) {
		this->f = f;
	}

	// Чтение ---------------------------------------------
	void init_read(size_t offset, size_t end) {
		this->offset = offset;
		this->end = end;
	}

	// Чтение файла целиком
	void init_read() {
		offset = 0;
		fseek(f, 0, SEEK_END);
		end = ftell(f);
	}

	item_t* next() override {
		if (end <= offset) return NULL;
		if (offset != ftell(f)) {
			// Установка указателя для чтения строки
			if (fseek(f, offset, SEEK_SET) != 0) {
				assert(false); // Невозможно установить позицию в файле
			}
		}
		if (fgets(item.data, STRING_MAX, f) < 0) {
			offset = ftell(f);
			return NULL;
		}
		offset = ftell(f);
		return &item;
	}

	size_t size() override {
		if (end <= offset) return 0;
		return end - offset;
	}

	void print() {
		item_t* i;
		while(i = next()) {
			printf(i->data);
		}
	}

	// Запись ----------------------------------------------
	//void end_write(const item_t* item) {
	//	offset = 0;
	//	fseek(0, 0, SEEK_SET);
	//}

	void write(const item_t* item) override {
		fputs(item->data, f);
	}
};

// Слияние двух последовательностей, выдает общую на выходе
class triplet_t : public source_t {
	source_t* src[2] = {0};	// Источники
	size_t idx = {0};		// Индекс меньшего
	size_t num;
public:

	void init(source_t* src1, source_t* src2, size_t num) {
		assert(src1 != NULL);
		src[0] = src1;
		src[1] = src2;
		this->num = num;
	}

	// Первый элемент в очереди, NULL если пусто
	const item_t* front() override {
		assert(src[0] != NULL);
		if (src[1] == NULL || src[1]->front() == NULL) {
			idx = 0;
		} else if (src[0]->front() == NULL) {
			idx = 1;
		} else if(*src[0]->front() < *src[1]->front()) {
			idx = 0;
		} else {
			idx = 1;
		}
		return src[idx]->front();
	}

	// Извлечение следующего
	void pop() override {
		src[idx]->pop();
	}
};

// Слияние массива src в dest деревом триплетов
void triplet_store(source_t** src, size_t src_size, destination_t& dest) {
	triplet_t trp[SOURCE_MAX];
	assert(src_size != 0 || src_size >= SOURCE_MAX);
	// Инициализация первых триплетов на src_size входов
	size_t cnt = 0;
	for(size_t i = 0; i < src_size + src_size % 2; i += 2) {
		if(i < src_size - 1) {
			trp[cnt].init(src[i], src[i + 1], cnt);
		} else {
			trp[cnt].init(src[i], NULL, cnt);
		}
		cnt++;
	}
	// Инициализация остального дерева
	size_t first = 0, last = cnt;
	while(last - first > 1) {
		for (size_t i = first; i < last + (last - first) % 2; i += 2) {
			if (i < last - 1) {
				trp[cnt].init(&trp[i], &trp[i + 1], cnt);
			} else {
				trp[cnt].init(&trp[i], NULL, cnt);
			}
			cnt++;
			assert(cnt < SOURCE_MAX);
		}
		first = last;
		last = cnt;
	}
	// Сохранение
	dest.source_set(&trp[first]);
}

// Слияние
void triplet_sort(const char* file_source, const char* file_dest) {
	FILE* in = fopen(file_source, "rb");
	assert(in != NULL);
	FILE* out = fopen(file_dest, "wb");
	assert(out != NULL);
	file_t dest;
	dest.init(out);
	// Заполнение источников
	file_t fs[SOURCE_MAX];
	source_t* src[SOURCE_MAX] = {0};
	size_t start = 0;
	item_t item[2];
	size_t idx = 1;
	size_t cnt = 0; // Количество последовательностей
	if(fgets(item[0].data, STRING_MAX, in) >= 0) { // Чтение первого элемента
		for(; cnt < SOURCE_MAX; cnt++) {
			size_t end = ftell(in);
			// Вычитывание возрастающей последовательности
			while(fgets(item[idx].data, STRING_MAX, in) >= 0) {
				idx = 1 - idx;
				// Проверка возрастания, idx предыдуший элемент
				if (item[1 - idx] < item[idx]) {
					break;
				}
				end = ftell(in);
			}
			fs[cnt].init(in);
			fs[cnt].init_read(start, end);
			src[cnt] = &fs[cnt];
			start = end;
		}
		printf("cnt = %d\n", (int)cnt);
	}
	// Слияние в конечный файл
	triplet_store(src, cnt, dest);


	for (size_t i = 0; i < SOURCE_MAX; i++) {
		printf("---- %lld -----\n", (int64_t) i);
		fs[i].print();
	}
	fclose(in);
	fclose(out);
}


// Файл для сортировки можно тут взять http://services.fms.gov.ru/info-service.htm?sid=2000 1.2Гб неупорядоченного текста.
int main() {
	triplet_sort("c:/download/list_of_expired_passports.csv", "c:/download/list_of_expired_passports-sort.csv");
#ifdef _DEBUG
	printf("Press any key ...\n");
	getchar();
#endif
	return 0;
}

...
Рейтинг: 0 / 0
13.03.2017, 19:54
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418440
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, втянул все-таки в атаку на на сферических коней

Одно радует, у Леонида тоже не не взлетело 20289897
Leonid KudryavtsevСейчас код допишу и на SSD протестю.
...
Рейтинг: 0 / 0
13.03.2017, 20:39
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418470
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TНет оснований. По середине между прогой и HDD стоит ОС со своим кэшем и боле-мене выравнивает эту проблему.
10Гб очень скажем хорошо выравниватель ломает - ACID для файловой системы никто не отменял
...
Рейтинг: 0 / 0
13.03.2017, 21:32
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418500
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmayton, втянул все-таки в атаку на на сферических коней

Одно радует, у Леонида тоже не не взлетело 20289897
Leonid KudryavtsevСейчас код допишу и на SSD протестю.
Не втянул. А заинтересовал. :)

А я из-за чортовых акторов полез обновлять свой MinGw.
...
Рейтинг: 0 / 0
13.03.2017, 22:51
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418504
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TLeonid Kudryavtsevпропущено...

Разница скана в RAM и доступ к диску/ленте - не порядки, а несколько порядков (тысячи, десятки тысяч раз, а может и больше).
DDR4 - 4,5 Гб/сек, SSD - 0,5 Гб/сек всего в 9 раз, даже одного порядка не набирается.
Когда мы читаем файл или просто byte array последовательно (merge) с нулевого элемента
по последний - то работает одна магия. Эта магия обычно указана на коробке устройства
и она близка (с оговорками) к throughput.

Когда мы делаем random-access чтение или чтения в обатную сторону с обменом (quick-sort)
то может внезапно (!) так случится что включится другая магия и ваши предположения
о скорости доступа могут внезапно стать неверными. SSD - это не плоская матрица битов.
Это сложная структура со своими характеристиками. С гистерезисом (отклик нагрузки - не линейный
а изломаный). С гранулярностью (удобно читать не байты а какие-то порции покрупнее, секторы,
db_blocsk). С кешами (повторное чтение порций). На этом уровне обычно меряют IOP-s
для баз данных и их индексов.

Поэтому уж коли вы взялись за SSD - то давайте подойдем к ней как инженеры.
Возможно имеет смысл для начала ее отформатировать в Ext4 с соотв. опцией.
...
Рейтинг: 0 / 0
13.03.2017, 23:04
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418574
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Посчитал статистику дерева триплетов. Вычитываю максимум последовательностей и запускаю их совместное слияние.

ПоследовательностейУровней дереваСравненийСтрок на выходе128711`822`3207332568111`952`766141251291`100`351`9552784
Файл похоже слабосортированный, средний размер последовательности 5.5 строк.

Слишком много сравнений. При двухкратном увеличении выборки десятикратное увеличение сравнений.

ИМХО Полноценную сортировку на триплетах не сделать. Поэтому нет смысла более 4-8 последовательностей сливать одновременно, а может и меньше, тут надо от скорости IO памяти и диска отталкиваться.

PS Надо std::sort подключать и акторы :)
...
Рейтинг: 0 / 0
14.03.2017, 08:15
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418577
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Про random-read: он не случайный, а в основном последовательный. Запись только последовательная.

Алгоритм такой:
Последовательно читаем исходный файл запоминая координаты сортированных последовательностей, набираем N последовательностей, затем берем эти последовательности и сливаем, т.е. читаем последовательно но из разных мест файла. Как вариант можно не в одном файле указателем скакать, а открыть N раз файл. Не знаю как для ОС удобнее, возможно без разницы, т.к. там идет постраничное проецирование файла в кэш ОС, а дальше работа с кэшем.

После промежуточного слияния во временный файл он будет читаться полностью последовательно.
...
Рейтинг: 0 / 0
14.03.2017, 08:40
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418655
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?
...
Рейтинг: 0 / 0
14.03.2017, 10:58
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418670
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonDima Tпропущено...

DDR4 - 4,5 Гб/сек, SSD - 0,5 Гб/сек всего в 9 раз, даже одного порядка не набирается.
Когда мы читаем файл или просто byte array последовательно (merge) с нулевого элемента
по последний - то работает одна магия. Эта магия обычно указана на коробке устройства
и она близка (с оговорками) к throughput.

Когда мы делаем random-access чтение или чтения в обатную сторону с обменом (quick-sort)
то может внезапно (!) так случится что включится другая магия и ваши предположения
о скорости доступа могут внезапно стать неверными. SSD - это не плоская матрица битов.
Это сложная структура со своими характеристиками. С гистерезисом (отклик нагрузки - не линейный
а изломаный). С гранулярностью (удобно читать не байты а какие-то порции покрупнее, секторы,
db_blocsk). С кешами (повторное чтение порций). На этом уровне обычно меряют IOP-s
для баз данных и их индексов.

Поэтому уж коли вы взялись за SSD - то давайте подойдем к ней как инженеры.
Возможно имеет смысл для начала ее отформатировать в Ext4 с соотв. опцией.

+ лайк.
...
Рейтинг: 0 / 0
14.03.2017, 11:09
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418679
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
kealon(Ruslan)Dima TНет оснований. По середине между прогой и HDD стоит ОС со своим кэшем и боле-мене выравнивает эту проблему.
10Гб очень скажем хорошо выравниватель ломает - ACID для файловой системы никто не отменял

У файловой системы нет ACID.

Если болле точно, то ACID ФС распостраняется на один файл .
Если приложение работает с несколькими файлами , то никакая ФС
не гарантирует логическую консистентность файлов между собой.
...
Рейтинг: 0 / 0
14.03.2017, 11:15
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418694
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonDima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?

Афигеть :)

А ты какую структуру имел ввиду когда начинал топик ?
...
Рейтинг: 0 / 0
14.03.2017, 11:32
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418705
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХmaytonпропущено...

Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?

Афигеть :)

А ты какую структуру имел ввиду когда начинал топик ?
О дереве триплетов я не говорил.

Моя предлагаемая оптимизация "rolling-triplet" (крутящийся треугольник) касалась
вобщем-то стандартного алгоритма сортировки на диске слиянием который
вы все знаете.

Но я не хоче никого ограничивать. Welcome! Только кидайте ссылки на источники.
...
Рейтинг: 0 / 0
14.03.2017, 11:38
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418730
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?
О такой

Код: plaintext
1.
2.
3.
1234
\/\/
 \/
Выход

1234 это источники последовательностей, т.е. 4 упорядоченные последовательности выдающие элементы по возрастанию.

У каждой последовательности есть два метода:
Код: plaintext
1.
2.
3.
4.
5.
// Интерфейс источника последовательности
class source_t {
	virtual const item_t* front() {// Первый элемент в очереди, NULL если пусто
	
	virtual void pop() { // Извлечение следующего элемента


Приемник просто вычитывет инфу пока последовательность не опустеет.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
// Интерфейс приемника
class destination_t {
	// Установка источника
	void source_set(source_t*& src) {
		assert(src != NULL);
		// Запись всего что есть в источнике
		const item_t* i;
		while(i = src->front()) {
			write(i);
			src->pop();
		}
	}



\/ это триплет. На входе две последовательности, на выходе одна. Он проверяет front() входов, и отдает тот что меньше и делает для того входа pop()

 
PS Пока писал как работает понял где я накосячил в коде :)
Я в триплете коряво перегрузил front(), он каждый раз проходит все дерево, опрашивая нижестоящих.
Надо кэшировать в триплете ответы нижних, а не опрашивать нижние каждый раз.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
	// Первый элемент в очереди, NULL если пусто
	const item_t* front() override {
		if (src[1]->front() == NULL) {
			*next_src = src[0];
			idx = 0;
		} else if (src[0]->front() == NULL) {
			*next_src = src[1];
			idx = 1;
		} else if(*src[0]->front() < *src[1]->front()) { // Сравнение
			idx = 0;
		} else {
			idx = 1;
		}
		return src[idx]->front();
	}


PPS Вечером будут новые замеры.
...
Рейтинг: 0 / 0
14.03.2017, 11:54
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39418745
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, ок. Сорян. А-то я грешным делом подумал что ты решил использовать тернарные деревья.
...
Рейтинг: 0 / 0
14.03.2017, 12:04
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419157
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Починил дерево, триплеты оправданы :)

4096 триплетов сортируют 23000 строк за 290`000 сравнений. Чтение из файла 2 раза на каждую строку.

Памяти занято всего:
триплеты 114`688 байт
источники 655`360 байт (в каждом кэш под одну строку 128 байт)
...
Рейтинг: 0 / 0
14.03.2017, 17:51
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419171
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Может кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.
...
Рейтинг: 0 / 0
14.03.2017, 18:05
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419231
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima TМожет кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.

Акторами решаешь ?

откуда взялось число 4096 ?
...
Рейтинг: 0 / 0
14.03.2017, 19:00
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419239
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
д0kХАкторами решаешь ?
Однопоточно. Файловый IO не распараллелишь. Черновик тут давал 20291151

д0kХоткуда взялось число 4096 ?
2^12 = 4096
Чтобы дерево триплетов строить проще было.
Код: plaintext
1.
	triplet_t trp[SOURCE_MAX];


Основание 2048, все остальное 2047, один лишний, да и фиг с ним, зато с размером массива не надо заморачиваться.
...
Рейтинг: 0 / 0
14.03.2017, 19:08
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419270
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima Tд0kХАкторами решаешь ?
Однопоточно. Файловый IO не распараллелишь. Черновик тут давал 20291151



Это наверное в винде
в линуксе аж на расс, как 2 пальца

 
офтопик
весь сок тут
в каждом акторном потоке нужно завести актор ввода вывода
который для своих акторов ( привязанный к ресурсу ядро)
будет заказывать ввод вывод у ОС
и по факту завершения операции ставить соотвествующий актор
а очередь на свое ядро или на соседнее , если оно гуляет
...
Рейтинг: 0 / 0
14.03.2017, 19:39
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419290
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
д0kХЭто наверное в винде
в линуксе аж на расс, как 2 пальца
И в винде это есть, но шнурок к диску все равно один, я из этого исхожу, т.е. или читать или писать в один момент времени. Тормоз там.
Запись я размазываю по времени, т.е. пишется по чуть-чуть но постоянно, дальше пусть ОС оптимизирует.

Задача стояла минимум памяти, я вписался в 1 Мб стэка, поэтому магическое число 4096, а не 8192, 16384, 65536 и т.д.

Допишу, скорость IO посчитаю и тогда будет понятно надо ли что-то параллелить.
...
Рейтинг: 0 / 0
14.03.2017, 20:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419296
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TМожет кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.

Совсем необязательно иметь такую кучу файлов.
По идее, можно обойтись количеством, равным количеству устройств.
Т.е. на каждом устройстве - один файл, состоящий из K отсортированных кусков по N записей.
...
Рейтинг: 0 / 0
14.03.2017, 20:26
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419309
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima Tд0kХЭто наверное в винде
в линуксе аж на расс, как 2 пальца
И в винде это есть, но шнурок к диску все равно один, я из этого исхожу, т.е. или читать или писать в один момент времени. Тормоз там.
Запись я размазываю по времени, т.е. пишется по чуть-чуть но постоянно, дальше пусть ОС оптимизирует.

Задача стояла минимум памяти, я вписался в 1 Мб стэка, поэтому магическое число 4096, а не 8192, 16384, 65536 и т.д.

Допишу, скорость IO посчитаю и тогда будет понятно надо ли что-то параллелить.



1. Не было ограничей по памяти,
было ограничение что размер файла минимум в 4 раза больше размера памяти.
То есть зависимость роста объема файла, размара требуемой
памяти и скорости сортировки должны иметь линейную зависимость.

2. Если ты используешь кеширование ФС , ты и нас и себя обманываешь .
И очень даже может быть в худшую сторону , если программа сортировки и кеш фс
не помещаются в оперативке.

3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)
...
Рейтинг: 0 / 0
14.03.2017, 20:37
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419316
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХ,

я задачу не придумывал, такая была 20288078
учитывай что читать нужно весь объём Ln(S/MemBlockSize) раз

10 гб у меня сортировалось где то 4-5 минут, с учётом O(ln(n) * N) вроде как в твои параметры вписывается
...
Рейтинг: 0 / 0
14.03.2017, 20:48
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419317
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Ln2(S/MemBlockSize) раз
...
Рейтинг: 0 / 0
14.03.2017, 20:49
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419319
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
ИМХО .
Для того что бы получить скорость на современных многоядерных и многосокетных
системах нужно понимать какое соотношение полледовательного ввода вывода
и оперций seek является оптимальным для каждого диска к количеству ядер в системе.

Учитывая абстракность постановки, алгоритм должен быть
авто адаптивным по этим парамерам.
...
Рейтинг: 0 / 0
14.03.2017, 20:52
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419322
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
д0kХ1. Не было ограничей по памяти,
20286712

д0kХ3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)
Мне не интересна стандартная сортировка, которая O(N*log(N)) даже на сортированном файле. На сортированном хочу O(N), не надо мне *log 2 (N), log 2 (1Гб) = 30. Тут оно и есть, поэтому интересно.
...
Рейтинг: 0 / 0
14.03.2017, 21:08
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419325
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
kealon(Ruslan)д0kХ,

я задачу не придумывал, такая была 20288078
учитывай что читать нужно весь объём Ln(S/MemBlockSize) раз

10 гб у меня сортировалось где то 4-5 минут, с учётом O(ln(n) * N) вроде как в твои параметры вписывается

Какой у тебя MemBlockSize ?
...
Рейтинг: 0 / 0
14.03.2017, 21:19
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419327
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima Tд0kХ1. Не было ограничей по памяти,
20286712

д0kХ3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)
Мне не интересна стандартная сортировка, которая O(N*log(N)) даже на сортированном файле. На сортированном хочу O(N), не надо мне *log 2 (N), log 2 (1Гб) = 30. Тут оно и есть, поэтому интересно.

Я не много о другом и
Я не понял причем тут вычислительная сложность к параметрам параллелизма ?

Я поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).

То есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.
...
Рейтинг: 0 / 0
14.03.2017, 21:27
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419333
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Майтон ,

д0kХЯ поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).

То есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.

А дальше использовать наиболле оптимальный для имеющихся условий алгоритм
сортировки.


вот что нужно говорить майкрософту на собеседовании в ответ на постановку
задачи об абстрактной сортировке в вакуме )
...
Рейтинг: 0 / 0
14.03.2017, 21:40
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419339
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХ
Какой у тебя MemBlockSize ? 1 Мб Ram больше использовать по условиям задачи нельзя
...
Рейтинг: 0 / 0
14.03.2017, 21:56
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419346
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
kealon(Ruslan)д0kХ Какой у тебя MemBlockSize ? 1 Мб Ram больше использовать по условиям задачи нельзя

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

Я не помню что бы Майтон озвучивал однозначное
числовое ограничение на объем памяти.
...
Рейтинг: 0 / 0
14.03.2017, 22:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419362
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХ,

он много что не озвучил, я озвучил 20288078 , какая разница?
задача стала не такая абстрактная и сразу видно на что обратить внимание
обычно её варьируют кто как хочет

ну а кэш FS какой-бы волшебный не был, убьётся нужным входным объёмом
...
Рейтинг: 0 / 0
14.03.2017, 22:56
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419368
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
2 All
д0kХЕсли задаче не определен режим открытия файлов и используется кеш файловой системы ,
то это не чесный тест.

1 Мб - это очень странная цифра. Она растет ногами разве-что из MS-DOS или Windows-95/98.
Да и вообще, в современных ОС и фреймворках все меньше и меньше возможностей
контролировать или явно разграничивать использование памяти. Неявных способов
выделить ее - вагон и маленькая тележка.

Я не помню что бы Майтон озвучивал однозначное
числовое ограничение на объем памяти.

(потирая лоб)

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

Тут важна не цифра. А само понимание стека технологий и подход. К примеру если имеем
1 ядро + 1Гиг памяти + 1Терабайт диска = можем отсортировать (грубо) 500 Гиговый
текстовый файл за N секунд времени.

Имеем ту-же конфигурацию но 2 диска по 500 Гигов. То-же самое. Но степень
параллелизма для merge - будет выше. Докинем перформанса (грубо) порядка +30%.
(Разумеется если мы сумеем эту степень параллелизма грамотно подать на вход
алгоритму).

Имеем на том-же стеке 3 диска по 330 Гигов. То-же самое. +60% перформанса
на слияниях.

И это все без конкретных цифр. А только на соотношениях. 1:1000 в моем примере.
...
Рейтинг: 0 / 0
14.03.2017, 23:15
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419369
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TМожет кто идею подкинет как сливать во временные файлы?
А в чем сложность? Диском ты не ограничен. Бези себе /tmp или как
там в Windows... GetTempPath(..) и погнал.

P.S. Пока тары-бары да я всем отвечаю уже в 4х топиках - ни пса ни скомпилировал
твои акторы.
...
Рейтинг: 0 / 0
14.03.2017, 23:21
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419371
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
"640 Kb должно хватить всем" ( C )
...
Рейтинг: 0 / 0
14.03.2017, 23:31
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419409
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

что-то пятая страница уже, а сколько-нибудь вменяемой постановки задачи не видать.
Но, раз о "собеседовании" речь идет - вроде как и не надо.
А в плане собеседования - на собеседовании я бы в близком контексте рассказу про приделывание солитерной ( она же терпеливая - patience) сортировки как первой фазе для внешней сортировки по формированию набора сливаемых файлов, вероятно радовался,
в комбинации с последующим внешним слиянием.
Она (терпеливая), кстати, еще и модная стала в последнее время.

https://en.wikipedia.org/wiki/Patience_sorting

Там в ссылках занятная статья от Microsoft на солитерную тему.
...
Рейтинг: 0 / 0
15.03.2017, 03:52
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419428
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
д0kХЯ не много о другом и
Я не понял причем тут вычислительная сложность к параметрам параллелизма ?

Я поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).
Я тоже немного о другом, меня сам алгоритм с деревом триплетов заинтересовал, я его попутно исследую:
1. Это отличный способ для решения задач типа "получить N минимальных элементов из несортированного массива". По сути в один проход строится дерево триплетов, а потом извлекай из него N элементов. Вычислительных операций будет пропорционально N, а не размеру всего массива, т.к. вычисление происходит в момент извлечения минимального.
2. Потом хочу сюда 20170548 добавить дерево триплетов. Я там как-раз искал что подобное, порешал уже, но пусть будет про запас.

д0kХТо есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.
Чтобы что-то определить надо сначала дорешать запустить и посмотреть что получилось. Может проц и не загрузится на 100%.
А потом уже рефакторингом заниматься.
...
Рейтинг: 0 / 0
15.03.2017, 07:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419431
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Многофазная сортировка слиянием
...
Рейтинг: 0 / 0
15.03.2017, 07:35
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419631
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima Tд0kХЯ не много о другом и
Я не понял причем тут вычислительная сложность к параметрам параллелизма ?

Я поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).
Я тоже немного о другом, меня сам алгоритм с деревом триплетов заинтересовал, я его попутно исследую:
1. Это отличный способ для решения задач типа "получить N минимальных элементов из несортированного массива". По сути в один проход строится дерево триплетов, а потом извлекай из него N элементов. Вычислительных операций будет пропорционально N, а не размеру всего массива, т.к. вычисление происходит в момент извлечения минимального.
2. Потом хочу сюда 20170548 добавить дерево триплетов. Я там как-раз искал что подобное, порешал уже, но пусть будет про запас.

д0kХТо есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.
Чтобы что-то определить надо сначала дорешать запустить и посмотреть что получилось. Может проц и не загрузится на 100%.
А потом уже рефакторингом заниматься.

Дима, я тебя не понимаю , ты говоришь о другом, а цитируешь размышления
об адаптивных параметрах параллелизма.

Если пишется ПО то подразумевается , что оно будет выполняться
тысячи раз на железе куда его проинсталили.
Я предполагаю что после первого запуска
ПО сортировки себя адаптирует под железо на котором выполняется.
что бы скорость и использование ресурсов в следующих запусках
было более оптимальным.
...
Рейтинг: 0 / 0
15.03.2017, 11:17
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419757
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
mayton2 All
д0kХЕсли задаче не определен режим открытия файлов и используется кеш файловой системы ,
то это не чесный тест.

1 Мб - это очень странная цифра. Она растет ногами разве-что из MS-DOS или Windows-95/98.
Да и вообще, в современных ОС и фреймворках все меньше и меньше возможностей
контролировать или явно разграничивать использование памяти. Неявных способов
выделить ее - вагон и маленькая тележка.

Я не помню что бы Майтон озвучивал однозначное
числовое ограничение на объем памяти.

(потирая лоб)

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

Тут важна не цифра. А само понимание стека технологий и подход. К примеру если имеем
1 ядро + 1Гиг памяти + 1Терабайт диска = можем отсортировать (грубо) 500 Гиговый
текстовый файл за N секунд времени.

Имеем ту-же конфигурацию но 2 диска по 500 Гигов. То-же самое. Но степень
параллелизма для merge - будет выше. Докинем перформанса (грубо) порядка +30%.
(Разумеется если мы сумеем эту степень параллелизма грамотно подать на вход
алгоритму).

Имеем на том-же стеке 3 диска по 330 Гигов. То-же самое. +60% перформанса
на слияниях.

И это все без конкретных цифр. А только на соотношениях. 1:1000 в моем примере.

mayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
Эта тенденция не меняется как минимум 15 лет

На один шпиндельный диск нужно в ~2 ядра , что бы система
была сбалансированной по производительности.
На SSD диск 3-4-5 ядер.
...
Рейтинг: 0 / 0
15.03.2017, 12:21
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419774
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХmayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
в сортировке слияними фактически нет вычислений, так что процессор будет практически стоять
что я собственно и наблюдал, минимальна загрузка проца, 100% - диска
...
Рейтинг: 0 / 0
15.03.2017, 12:28
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419790
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
kealon(Ruslan)д0kХmayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
в сортировке слияними фактически нет вычислений, так что процессор будет практически стоять
что я собственно и наблюдал, минимальна загрузка проца, 100% - диска

100% нагрузки на диске вы видели потому что у вас вероятнее
всего чтение было не последовательным.
я выше говорил о балансе последовательного чтения и количест операций seek ( позиционирование головок).

Позиционирование головок очень дорогая операция , поэтому мне показалось странным
устанавливать ограничение на блок памяти 1 Мб.
Это не оптимально с точки зрения использования дисковгого ресурса,
я думаю нужно хотя бы 20 Мб , а лучше 50 ,
что бы уменьшить количество перемещений головок по поверхности шпинделей.
...
Рейтинг: 0 / 0
15.03.2017, 12:34
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419837
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
 
офтопик

Вот пример тонкого тюнинга управления раскладки
по поврехростям шпинделей датафайлов оракла
в энтерпрайз системе

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
lspv -p hdisk32
hdisk32:
PP RANGE  STATE   REGION        LV NAME             TYPE       MOUNT POINT
  1-27    used    outer edge    df27           raw        N/A
 28-54    used    outer middle  df14           raw        N/A
 55-67    used    center        df01           raw        N/A
 68-80    used    center        df01           raw        N/A
 81-106   used    inner middle  df14           raw        N/A
107-107   used    inner edge    df14           raw        N/A
108-120   used    inner edge    df27           raw        N/A
121-133   free    inner edge


Если надо , то любой датафайл можно подвинуть
по поврехностям шпинделей или вынести на отдельных шпиндель
незаметно для оракла на лету в зависимости от нагрузки на ввод вывод
...
Рейтинг: 0 / 0
15.03.2017, 12:57
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419844
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
д0kХ
 
офтопик

Вот пример тонкого тюнинга управления раскладки
по поврехростям шпинделей датафайлов оракла
в энтерпрайз системе

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
lspv -p hdisk32
hdisk32:
PP RANGE  STATE   REGION        LV NAME             TYPE       MOUNT POINT
  1-27    used    outer edge    df27           raw        N/A
 28-54    used    outer middle  df14           raw        N/A
 55-67    used    center        df01           raw        N/A
 68-80    used    center        df01           raw        N/A
 81-106   used    inner middle  df14           raw        N/A
107-107   used    inner edge    df14           raw        N/A
108-120   used    inner edge    df27           raw        N/A
121-133   free    inner edge


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


Это я к тому что на скорость дискового ввода вывода и баланса нагрузок
может влиять даже место размещения файлов на поверхрости шпинделя
center - самое быстрое позиционирование
inner edge и outer edge более медленное позиционирование.
в center укладываются файлы с рандомным характером доступа ,
в edge с последовательным.
...
Рейтинг: 0 / 0
15.03.2017, 13:04
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419862
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХПозиционирование головок очень дорогая операция , поэтому мне показалось странным
устанавливать ограничение на блок памяти 1 Мб.
Это не оптимально с точки зрения использования дисковгого ресурса,
я думаю нужно хотя бы 20 Мб , а лучше 50 ,
что бы уменьшить количество перемещений головок по поверхности шпинделей.
усложнение жизни кандидату вопреки принятым практикам вполне согласуется с тем, что это тестовое задание, а не использование в продакшене
...
Рейтинг: 0 / 0
15.03.2017, 13:13
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419984
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Доделал, сортирует но очень медленно. Переливает туда-сюда во временных файлах.
Исходный файл не айс. Срока 12 байт, строки в разнобой. Средняя последовательность 5.5 строк.

Статистика 18 минут работы, обработано 82,8 Мб исходного файла:
Записано во временные: 15 252 Мб
Прочитано с диска всего: 15 335 Мб
Прочитано из исходного файла: 82,8 Мб
Сравнений: 12 158 млн.

Но сам алгоритм смотрится неплохо по количеству сравнений:
15 252 Мб это 1 271 млн. строк
Обычная сортировка будет 1271 млн. * log 2 (1271 млн.) = 38 438 млн.

Надо на сортировочных тестах его сравнивать с другими.
...
Рейтинг: 0 / 0
15.03.2017, 14:25
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39419992
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

очень дофига по времени для алгоритма, мне кажется в 20295980 именно та идея которую ты пытаешься реализовать
...
Рейтинг: 0 / 0
15.03.2017, 14:32
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39420019
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,

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

Исходный файл 100 млн.строк, средняя последовательность 5.5 строк.

За раз берется 2048 последовательностей, т.е. 2048*5,5 = 11 тыс. строк. и сливается с предыдущим результатом. Т.е. надо ~9000 переливаний. При этом все накопленное участвует во всех переливаниях. Т.е. чем дальше тем тормознее.

Надо алгоритм слияния пересмотреть: если файл за один проход не разобрался, то лить все в другой, затем его на вход и т.д. пока за раз целиком не сольется. Тогда будет 2 переливания, т.е. исходный в промежуточный где станет 900 последовательностей по 11 тыс. строк, затем его в результат. Так всего 2.4 Гб записи. минуты за 3 отсортируется.

Еще тормоз из-за того что у меня указатель в файле постоянно скачет (fseek()) надо попробовать схитрить, открыть файл 2048 раз, правда тут далеко не 1 Мб будет, о чем д0kХ писал.
...
Рейтинг: 0 / 0
15.03.2017, 14:52
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39420091
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)д0kХmayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
в сортировке слияними фактически нет вычислений, так что процессор будет практически стоять
что я собственно и наблюдал, минимальна загрузка проца, 100% - диска
Да. Все верно. Именно так я и предполагал.
...
Рейтинг: 0 / 0
15.03.2017, 15:40
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39420097
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХЭто я к тому что на скорость дискового ввода вывода и баланса нагрузок
может влиять даже место размещения файлов на поверхрости шпинделя
center - самое быстрое позиционирование
inner edge и outer edge более медленное позиционирование.
в center укладываются файлы с рандомным характером доступа ,
в edge с последовательным.
Я учту это замечание на будущее. Но давай пока стартанём просто
с разделов в /ext3, ext4 без привязки в расстоянию до шпинделя.

Допилим чуть позже когда будет более-менее работающий код.

В алгориме триплетов, каждый триплет будет создать неодинаковую
нагрузку. Потоки читатели будут делить по 50% трафика а поток-писатель
будет делать почти "горизонтальную полку" и оптимизировать это сейчас
сложно т.к. на следующем step фазы №2 их роли меняются и тот файл
который был создан писателем станет снова читаемым. И ситуация
перевернётся. Как быстро двигать файлы по поверхности шпинделя
так чтобы это не влияло на основной алгоитм - я пока не знаю.
...
Рейтинг: 0 / 0
15.03.2017, 15:46
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39420098
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TДоделал, сортирует но очень медленно. Переливает туда-сюда во временных файлах.
Исходный файл не айс. Срока 12 байт, строки в разнобой. Средняя последовательность 5.5 строк.

Статистика 18 минут работы, обработано 82,8 Мб исходного файла:
Записано во временные: 15 252 Мб
Прочитано с диска всего: 15 335 Мб
Прочитано из исходного файла: 82,8 Мб
Сравнений: 12 158 млн.

Но сам алгоритм смотрится неплохо по количеству сравнений:
15 252 Мб это 1 271 млн. строк
Обычная сортировка будет 1271 млн. * log 2 (1271 млн.) = 38 438 млн.

Надо на сортировочных тестах его сравнивать с другими.
Дима. Как всегда респект. У тебя - легкая рука и ты очень быстро выдаешь бета-версии
пока мы только кумекаем чо и как сделать.
...
Рейтинг: 0 / 0
15.03.2017, 15:47
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39420146
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonд0kХЭто я к тому что на скорость дискового ввода вывода и баланса нагрузок
может влиять даже место размещения файлов на поверхрости шпинделя
center - самое быстрое позиционирование
inner edge и outer edge более медленное позиционирование.
в center укладываются файлы с рандомным характером доступа ,
в edge с последовательным.
Я учту это замечание на будущее. Но давай пока стартанём просто
с разделов в /ext3, ext4 без привязки в расстоянию до шпинделя.

Допилим чуть позже когда будет более-менее работающий код.

В алгориме триплетов, каждый триплет будет создать неодинаковую
нагрузку. Потоки читатели будут делить по 50% трафика а поток-писатель
будет делать почти "горизонтальную полку" и оптимизировать это сейчас
сложно т.к. на следующем step фазы №2 их роли меняются и тот файл
который был создан писателем станет снова читаемым. И ситуация
перевернётся. Как быстро двигать файлы по поверхности шпинделя
так чтобы это не влияло на основной алгоитм - я пока не знаю.


Движение файла по поверхности имеет смысл если это файл
известной структуры с которого читается и в нем же делаются изменения.
темповые файлы двигать по поверхности смысла не имеет.

правила размещения простые , мелкие темповые файлы ложатся в центр ,
большие и результат ближе к edge.
...
Рейтинг: 0 / 0
15.03.2017, 16:34
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39421011
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Затестил дерево триплетов на массивах 20303177 . Копирование в разы меньше других, т.е. переливание всего массива 1-2 раза. Сравнений сопоставимо с другими алгоритмами.
Т.е. для биг файла самое то что надо.
...
Рейтинг: 0 / 0
16.03.2017, 17:49
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39421087
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЗатестил дерево триплетов на массивах 20303177 . Копирование в разы меньше других, т.е. переливание всего массива 1-2 раза. Сравнений сопоставимо с другими алгоритмами.
Т.е. для биг файла самое то что надо.

На мой взгляд, дерево не самый лучший выбор.
Фактически чтение происходит по одной записи из случайного файла (или части файла).
Алгоритм более-менее работает только за счет блокирования и опережающего чтения ОС.

Пирамида подошла бы лучше.
На этапе загрузки данных в пирамиду читаем большими блоками записей.
Сначала по одному блоку из каждого файла (или части файла),
потом читаем очередной блок оттуда, где текущий ключ меньше.
Выгружаем пирамиду до минимального текущего ключа или полностью, если файлы исчерпаны.
...
Рейтинг: 0 / 0
16.03.2017, 22:19
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39425119
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Не впадая с указателями в погоню за гигфлоппами решение на языке высокого уровня.
ИМХО для сравнения приемлемое.
Студентам не показывать.

 

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
// Copyright 2017 by Mikron
// This piece of code distributed under terms of BSD License and without any warranty.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace MergeSort
{
    class Program
    {

        const int MAX_TEMP_FILES = 14;                  // Prefered size must be 2^n - 2, n > 1
        const int MAX_HEAP_SIZE = (1 << 16) - 1;        // Adjust accordingly to available memmory 

        static readonly Comparison<string> StringComparison = string.CompareOrdinal;
        static readonly Comparison<IEnumerator<string>> StringEnumeratorComparison = (x, y) => string.CompareOrdinal(x.Current, y.Current);

        static void Main(string[] args)
        {
            if (args.Length < 2)
            {
                Console.WriteLine("Usage: {0} <source:_file> <target_file>");
                return;
            }
            var target = new Lazy<FileStream>[MAX_TEMP_FILES / 2];
            var source = new Lazy<FileStream>[MAX_TEMP_FILES - target.Length];
            try
            {
                Func<FileStream> createTempFile = () => new FileStream(Path.GetTempFileName(), FileMode.Create, FileAccess.ReadWrite, FileShare.Read);
                for (var i = 0; i < target.Length; i += 1)
                {
                    target[i] = new Lazy<FileStream>(createTempFile);
                }
                for (var i = 0; i < source.Length; i += 1)
                {
                    source[i] = new Lazy<FileStream>(createTempFile);
                }
                int splitter;
                var timer = new Stopwatch();
                timer.Start();
                using (var sourceFile = new FileStream(args[0], FileMode.Open, FileAccess.Read, FileShare.Read))
                {
                    splitter = Split(MAX_HEAP_SIZE, ReadLines(sourceFile), source);
                }
                int runNo = 0;
                while (splitter > 1)
                {
                    var sourceReq = from s in source select ReadLines(s.Value);
                    splitter = Split(MAX_HEAP_SIZE, Merge(sourceReq.ToArray()), target);
                    var swapTmp = source;
                    source = target;
                    target = swapTmp;
                    foreach (var f in target)
                    {
                        if (f.IsValueCreated)
                        {
                            f.Value.Seek(0, SeekOrigin.Begin);
                            f.Value.SetLength(0);
                        }
                    }
                    runNo += 1;
                }
                timer.Stop();
                Console.WriteLine("Total number of Split/Merge runs: {0,8} in {1} ", runNo, timer.Elapsed);

                source[0].Value.Close();
                File.Move(source[0].Value.Name, args[1]);
                source[0].Value.Dispose();
                source[0] = null;
            }
            finally
            {
                Action<Lazy<FileStream>> cleanUp = (f) =>
                {
                    if (f != null && f.IsValueCreated)
                    {
                        f.Value.Close();
                        File.Delete(f.Value.Name);
                        f.Value.Dispose();
                    }
                };
                foreach (var f in source)
                    cleanUp(f);
                foreach (var f in target)
                    cleanUp(f);
            }
        }

        static IEnumerable<string> ReadLines(FileStream fileStream)
        {
            fileStream.Seek(0, SeekOrigin.Begin);
            using (var reader = new StreamReader(fileStream, Encoding.Default, true, 4096, true))
            {
                string line;
                while ((line = reader.ReadLine()) != null)
                    yield return line;
            }
        }

        static int Split(int heapCapacity, IEnumerable<string> source, Lazy<FileStream>[] destination)
        {
            var heap = new string[heapCapacity];
            var writers = new StreamWriter[destination.Length];
            int targets = 0;
            var ii = source.GetEnumerator();
            try
            {
                int writerIndex = 0;
                long numberOfReadLines = 0L;
                long numberOfSwitches = 0L;
                long longestStrip = 0L;
                long shortestStrip = long.MaxValue;
                int heapSize = 0;
                while (true)
                {
                    // Fill heap
                    while (heapSize < heapCapacity && ii.MoveNext())
                    {
                        heap[heapSize] = ii.Current;
                        BubbleUp(heap, heapSize, StringComparison);
                        heapSize += 1;
                    }
                    if (heapSize == 0)
                        break;
                    // Prepare for wrining next strip
                    long stripLength = 0L;
                    var writer = writers[writerIndex];
                    if (writer == null)
                    {
                        targets += 1;
                        var stream = destination[writerIndex].Value;
                        stream.Seek(0, SeekOrigin.Begin);
                        stream.SetLength(0);
                        writer = writers[writerIndex] = new StreamWriter(stream, Encoding.Default, 4096, true);
                    }
                    writerIndex = (writerIndex + 1) % writers.Length;

                    // Process lines
                    string priorLine = null;
                    while (true)
                    {
                        var line = heap[0];
                        var gapPos = RemoveHead(heap, heapSize, StringComparison);
                        if (priorLine != null && StringComparison(priorLine, line) > 0)
                        {
                            // Here I can be sure, all other elements in heap are above of priorLine
                            // So just flush them out and put line again in heap for begining of the next strip
                            heap[gapPos] = heap[--heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                            priorLine = line;       
                            break;
                        }
                        writer.WriteLine(line);
                        stripLength += 1L;
                        priorLine = line;
                        if (!ii.MoveNext())
                        {
                            heap[gapPos] = heap[--heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                            priorLine = null;       // Don't put prior line into heap again
                            break;
                        }
                        heap[gapPos] = ii.Current;
                        BubbleUp(heap, gapPos, StringComparison);
                    }

                    // Empty heap
                    if (heapSize > 0)
                    {
                        stripLength += heapSize;
                        while (true)
                        {
                            writer.WriteLine(heap[0]);
                            var gapPos = RemoveHead(heap, heapSize, StringComparison);
                            if (--heapSize <= 0)
                                break;
                            heap[gapPos] = heap[heapSize];
                            BubbleUp(heap, gapPos, StringComparison);
                        }
                    }
                    longestStrip = Math.Max(longestStrip, stripLength);
                    shortestStrip = Math.Min(shortestStrip, stripLength);
                    numberOfReadLines += stripLength;
                    numberOfSwitches += 1;
                    if (priorLine != null)
                    {
                        heap[heapSize] = priorLine;
                        BubbleUp(heap, heapSize, StringComparison);
                        heapSize += 1;
                    }
                }
                Console.WriteLine("Lines {0,8} Switches {1,8} Strip Min {2,8} Max {3,8} Avg {4,9:F5}", numberOfReadLines, numberOfSwitches,
                    shortestStrip, longestStrip, numberOfReadLines / (double) numberOfSwitches);
            }
            finally
            {
                ii.Dispose();
                foreach(var w in writers)
                {
                    if (w != null)
                        w.Dispose();
                }
            }
            return targets;
        }

        static int Split(IEnumerable<string> source, Lazy<FileStream>[] destination)
        {
            var writers = new StreamWriter[destination.Length];
            int targets = 0;
            try
            {
                int writerIndex = 0;
                StreamWriter writer = null;
                long numberOfReadLines = 0L;
                long numberOfSwitches = 0L;
                long longestStrip = 0L;
                long shortestStrip = long.MaxValue;
                long stripLength = 0L;
                string priorLine = null;
                foreach (var line in source)
                {
                    numberOfReadLines += 1;
                    if (writer == null || string.CompareOrdinal(priorLine, line) > 0)
                    {
                        if (stripLength > 0)
                        {
                            longestStrip = Math.Max(longestStrip, stripLength);
                            shortestStrip = Math.Min(shortestStrip, stripLength);
                        }
                        stripLength = 0L;
                        numberOfSwitches += 1;
                        writer = writers[writerIndex];
                        if (writer == null)
                        {
                            targets += 1;
                            var stream = destination[writerIndex].Value;
                            stream.Seek(0, SeekOrigin.Begin);
                            stream.SetLength(0);
                            writer = writers[writerIndex] = new StreamWriter(stream, Encoding.Default, 4096, true);
                        }
                        writerIndex = (writerIndex + 1) % writers.Length;
                    }
                    priorLine = line;
                    writer.WriteLine(line);
                    stripLength += 1L;
                }
                longestStrip = Math.Max(longestStrip, stripLength);
                shortestStrip = Math.Min(shortestStrip, stripLength);
                Console.WriteLine("Lines {0,8} Switches {1,8} Strip Min {2,8} Max {3,8} Avg {4,9:F5}", numberOfReadLines, numberOfSwitches,
                    shortestStrip, longestStrip, numberOfReadLines / (double)numberOfSwitches);
            }
            finally
            {
                foreach (var w in writers)
                {
                    if (w != null)
                        w.Dispose();
                }
            }
            return targets;
        }

        static IEnumerable<string> Merge(params IEnumerable<string>[] sources)
        {
            if (sources == null || sources.Length == 0)
                yield break;
            // Init heap
            var heap = new IEnumerator<string>[sources.Length];
            var length = 0;
            for (int i = 0; i < sources.Length; i += 1)
            {
                var s = sources[i].GetEnumerator();
                if (!s.MoveNext())
                {
                    s.Dispose();
                }
                else
                {
                    heap[length] = s;
                    BubbleUp(heap, length, StringEnumeratorComparison);
                    length += 1;
                }
            }
            // Enumerate
            while(true)
            {
                var s = heap[0];
                yield return s.Current;
                var gapPos = RemoveHead(heap, length, StringEnumeratorComparison);
                if (!s.MoveNext())
                {
                    s.Dispose();
                    if (--length <= 0)
                        break;
                    s = heap[length];
                }
                heap[gapPos] = s;
                BubbleUp(heap, gapPos, StringEnumeratorComparison);
            }
        }


        static int RemoveHead<T>(T[] heap, int length, Comparison<T> comparer)
        {
            int gap = 0;
            while (true)
            {
                var child = 1 + (gap << 1);
                if (child >= length)
                    break;
                if (child + 1 < length && comparer(heap[child], heap[child + 1]) >= 0)
                {
                    child += 1;
                }
                heap[gap] = heap[child];
                gap = child;
            }
            return gap;
        }

        static int BubbleUp<T>(T[] heap, int i, Comparison<T> comparer)
        {
            var s = heap[i];
            while (i > 0)
            {
                int parent = (i - 1) >> 1;
                if (comparer(heap[parent], s) < 0)
                    break;
                heap[i] = heap[parent];
                heap[parent] = s;
                i = parent;
            }
            return i;
        }

    }
}


...
Рейтинг: 0 / 0
22.03.2017, 17:23
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39425278
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mikron, спасибо.
...
Рейтинг: 0 / 0
22.03.2017, 22:28
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39425402
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Алгоритм кстати не оптимальный.
Используется две кучи/пирамиды: первая для слияния данных из многих источников и образования единого потока данных,
вторая для сортировки потока данных в памяти.
Заметил важную деталь:
Использование второй кучи/пирамиды только вредит, т.к. увеличивает затраты на сравнения но улутшает длину сортированной последовательности только на +размер кучи за проход.
Основная же "ошибка" если так можно сказать в том что слияние потоков всегда берёт наименьшее текущее значение из всех потоков.
...
Рейтинг: 0 / 0
23.03.2017, 09:18
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39425409
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Тестовый файл сортировался 50 минут с 62 временными файлами и буфером на 2^18 строк. Т.к. Строки короткие это соответсвует 16 Мб памяти.
...
Рейтинг: 0 / 0
23.03.2017, 09:23
| Ответить | Цитировать | Написать  
Тяпничная huge-сортировка
    #39425493
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Последние штрихи и можно сравнивать, с C++

// splitter = Split(MAX_HEAP_SIZE, Merge(sourceReq.ToArray()), target);
splitter = Split(Merge(sourceReq.ToArray()), target);

 
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
        static IEnumerable<string> Merge(params IEnumerable<string>[] sources)
        {
            if (sources == null || sources.Length == 0)
                yield break;
            // Init heap
            var heap = new IEnumerator<string>[sources.Length];
            var size = 0;
            for (int i = 0; i < sources.Length; i += 1)
            {
                var s = sources[i].GetEnumerator();
                if (!s.MoveNext())
                {
                    s.Dispose();
                }
                else
                {
                    heap[size] = s;
                    BubbleUp(heap, size, StringEnumeratorComparison);
                    size += 1;
                }
            }
            // Enumerate
            var nextHeap = new IEnumerator<string>[size];
            while (true)
            {
                var nextSize = 0;
                while (true)
                {
                    var h = heap[0];
                    var s = h.Current;
                    yield return s;
                    var gapPos = RemoveHead(heap, size, StringEnumeratorComparison);
                    if (!h.MoveNext())
                    {
                        h.Dispose();
                        if (--size <= 0)
                            break;
                        h = heap[size];
                    }
                    else if (StringComparison(h.Current, s) < 0)
                    {
                        nextHeap[nextSize] = h;
                        BubbleUp(nextHeap, nextSize, StringEnumeratorComparison);
                        nextSize += 1;
                        if (--size <= 0)
                            break;
                        h = heap[size];
                    }
                    heap[gapPos] = h;
                    BubbleUp(heap, gapPos, StringEnumeratorComparison);
                }
                if (nextSize == 0)
                    break;
                size = nextSize;
                var tmp = heap;
                heap = nextHeap;
                nextHeap = tmp;
            }
        }

...
Рейтинг: 0 / 0
23.03.2017, 10:41
| Ответить | Цитировать | Написать  
133 сообщений из 133, показаны все 6 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничная huge-сортировка
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1340453]:
 0ms
get settings:
 6ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 1156ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 290ms
get tp. blocked users:
 2ms
others: 237ms
total:  1720ms
созд. / загр.: 1720ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]