Dima TИМХО тут самое узкое место файловый IO, его и надо оптимизировать. В каком-то топике это уже обсуждали.

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

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

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

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

AFAIK Обычно при объеме буфера за 16-64 Mb уже время перемещения головок становится не настолько значимо. Современная RAM вполне позволяет безболезненно под блоки ввода-вывода отдать несколько сотен мегабайт и не париться.

maytonДавайте в форуме один раз и навсегда закодим решение и поставим точку в этих трудностях.
https://www.ozon.ru/context/detail/id/2527036/

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

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

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

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

mayton
Добавлю.

На 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) и нафиг какой-то свой самопал.

В общем.... практический смысл и возможность использования в мирных целях ... от меня ускользает.

Dima TНо тема тупиковая, надо по другому решать: индексы, просто выносить порядок сортировки в отдельный файл, там могут быть просто указатели (смешения) на начала строк исходного биг-файла. Я с DBF много работал, там никто не заморачивается физической сортировкой, только индексы.

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

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

IMHO

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