Здравствуйте, gandjustas, Вы писали:

A>>Мое: https://github.com/artelk/RowsSort
A>>Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
G>Кстати почему выбрано 256? Если будет не 265, а 1024 на что повлияет?

У меня тоже 1024. Это необходимо, что бы выбрать буфер подходящего развера для вычитывания строк. Мне использование подобной константы (или параметра) кажется оправданным.

Здравствуйте, Shmj, Вы писали:

S>Проверил ваше решение в сравнении с https://rsdn.org/forum/job/8349836.1

Автор: gandjustas
Дата: 02.09.22

S>На 13,8 Гб. — у него 15,5 мин., у вас 6,36 мин.

Спасибо. Подозреваю, что основной эффект дало именно сжатие за счет бинарного формата. На файле FREDа, с огромными числами слева, чанки сжимались примерно в два раза.
У bucket+merge sort потенциала в этом смысле больше. После сортировки чанка там могут подряд идти много строк с одним довольно длинным префиксом, что можно как-то более компактно упаковать.

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, artelk, Вы писали:

A>>Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
A>>Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.

_FR>Мне кажется, это довольно вольная трактовка задания, про случайность строк ничего сказано не было.
В треде в dotnet форуме вроде было

A>>На моем железе сортировшик FREDа на файле 1Гб работает за 2 минуты, а мой за 40 секунд.
A>>Возможно, на другом железе будет обратная картина, т.к. я ничего не параллелил и на моем ноуте узкое место это HDD (хотя саму сортировку можно было бы как-то в параллель IO сделать).

_FR>О, это уже похоже на то, что было у проверяющих.
_FR>Вы запускали релиз?
да

_FR>С каким файлом (созданным моим же генератором или) или другой?
вашим

_FR>По сколько строк разбивали исходный файл?
не ограничивал, сколько получилось после разбиения по первому символу + 3 бита второго символа. На 1Гб файле там нескольно мегабайт на чанк было.

_FR>Можете показать вывод программы и расход памяти (гистограмму из процесс эксплорера или таск менеджера)?
покажу на днях

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, artelk, Вы писали:

A>>Здравствуйте, _FRED_, Вы писали:

A>>Мое: https://github.com/artelk/RowsSort
A>>Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
A>>Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.
G>Имхо слишком сильные допущения. Что будет если попробовать отсортировать файл в 50ГБ одинаковых строк?
умрет
G>Кстати почему выбрано 256? Если будет не 265, а 1024 на что повлияет?
в бинарном формате чанка отдаю только один байт на длину каждой строки

Здравствуйте, artelk, Вы писали:

_FR>>По сколько строк разбивали исходный файл?
A>не ограничивал, сколько получилось после разбиения по первому символу + 3 бита второго символа. На 1Гб файле там нескольно мегабайт на чанк было.

Я имею в виду мою реализацию — с какими параметрами запускали? Не указывать число строк, на которые нужно сначала попилить исходный файл моей программе нельзя (параметр MaxReadLines).

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, artelk, Вы писали:

_FR>>>По сколько строк разбивали исходный файл?
A>>не ограничивал, сколько получилось после разбиения по первому символу + 3 бита второго символа. На 1Гб файле там нескольно мегабайт на чанк было.

_FR>Я имею в виду мою реализацию — с какими параметрами запускали? Не указывать число строк, на которые нужно сначала попилить исходный файл моей программе нельзя (параметр MaxReadLines).
Аа, 50000, как в SortFile.cmd было

Я не знаю, чего именно от тебя хотели.

Но мне таки кажется, что правильный способ взять RDBMS, создать базу с двумя таблицами.
Первая таблица с одной колонкой для строк, она же primary key.
Вторая колонка с foreign key на первую таблицу, int32 или int64 колонкой для чисел, и например secondary key из колонки для чисел.

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

Для RDBMS лучше всего взять SQLite, потому что оно in-process, и в идеале понастраивать его для максимальной производительности и минимальной durability.
Или если не хочется тащить dependencies, а на компьютере Windows, можно ESENT ещё.

Остальные способы изрядно хуже.

Стандартные коллекции вроде List или Dictionary поддерживают максимум 2 миллиарда значений (потому что число элементов int32), 100GB файл скорее всего будет больше.
Кроме того, даже если хранить по 8 байт на строчку, для объёмов в той задаче вероятно падение с out of memory.

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

Здравствуйте, Константин, Вы писали:

К>Я не знаю, чего именно от тебя хотели.

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

К>Но мне таки кажется, что правильный способ взять RDBMS, создать базу с двумя таблицами.

Тут тоже, мне кажется, возможны ньюансы, так что самое простое — взять и продемонстрировать

Здравствуйте, _FRED_, Вы писали:

Вообще то для этого существуют индексы а в частности Б++ деревья http://rsdn.org/article/alg/tlsd.xml

Автор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.

Здравствуйте, Константин, Вы писали:

К>Я не знаю, чего именно от тебя хотели.

К>Но мне таки кажется, что правильный способ взять RDBMS, создать базу с двумя таблицами.
К>Первая таблица с одной колонкой для строк, она же primary key.
К>Вторая колонка с foreign key на первую таблицу, int32 или int64 колонкой для чисел, и например secondary key из колонки для чисел.
Тебе кажется.


К>Последовательно прочитать один раз файл.
Это O(N) чтений

К>Для каждой строки найти или добавить её в первую таблицу, потом добавить строку во вторую таблицу.
Это O(N * log N) чтений для поиска места вставки + O(N*log N) записей, так как древовидный индекс будет перестраиваться (правда логарифм будет по большому основанию)

К>Потом один раз прочитать всю базу, и в цикле написать выходной файл.
Это O(N) чтений из таблиц + O(N) записей в результирующий файл

К>Если что-то самому колхозить на тему временных файлов на диске, скорее всего получится или сильно медленнее, или адски сложное.
Покочто все решения где "самому колхозить" получаются быстрее так как требуют:
Это O(N) чтений для исходного файла
+ O(N) записей в промежуточный файл + O(N*Log N) операций сравнения в памяти для сортировки
+ O(N) записей в файл результата * O(Log K) сравнений в памяти для операций слияния

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

К>Таблицы в базах данных состоят из B-trees, хорошо подходят для задачи, но самому их запилить изрядно сложно.
Есть готовая эффективная реализация B-деревьев в .NET ?

Вообще рассуди логически:
БД это индекс. Построение индекса в том или ином виде это сортировка. Но так как размер индекса заведомо превышает размер ОП, то сортировать записи надо будет на диске, что даст минимум O(N*log N) записей. Тогда как алгоритмы внешней сортировки сортируют куски в памяти, то записей будет всего O(N), а сортировка и слияние отсортированных кусков будет выполняться в памяти без дополнительных записей на диск.

Здравствуйте, gandjustas, Вы писали:

G>Даже сравнение асимптотик говорит что рукопашный алгоритм будет быстрее.
Сам же написал выше, что не будет: то же самое O(N*Log N) в обоих случаях.

G>А реальные накладные расходы
Да, и вот тут будет win у традиционных баз данных.
У них под капотом B-trees, которые десятилетиями оптимизированы для таких случаев, как запись строки в середину таблицы.

Сортировка слиянием скорее всего будет медленнее из-за I/O bandwidth.

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

Если разбить данные на куски влезующие в память и потом мёрджить отсортированные куски, если такая строчка уже была в предыдущем куске данных, код её не найдёт.
Будут идентичные строчки в двух кусках данных.
Merge понятно потом уберёт дубликаты, но эти дубликаты занимают место на диске и жгут IO bandwidth.

Здравствуйте, Константин, Вы писали:

К>Здравствуйте, gandjustas, Вы писали:

G>>Даже сравнение асимптотик говорит что рукопашный алгоритм будет быстрее.
К>Сам же написал выше, что не будет: то же самое O(N*Log N) в обоих случаях.
Только в случае БД на диске, а в случае внешней сортировки — в памяти. Разница примерно в 100 000 раз.
Это как бы не tradeoff, а просто замедление работы.

G>>А реальные накладные расходы
К>Да, и вот тут будет win у традиционных баз данных.
К>У них под капотом B-trees, которые десятилетиями оптимизированы для таких случаев, как запись строки в середину таблицы.
Ну как не оптимизируй, а сортировка в памяти будет быстрее, чем на диске. То есть база данных будет на диск писать гарантированно не меньше лююбого варианта внешней сортировки.

К>Сортировка слиянием скорее всего будет медленнее из-за I/O bandwidth.
Нет конечно. Потому что решение с БД будет больше писать на диск. При чем тут I/O bandwidth — не понятно.

К>Когда вставляем строчку в SQL таблицу, если такая строчка уже была в базе, SQL найдёт в таблице старую, даже несмотря на то, что таблица не влезает в память.
Это O(logN) чтений с диска. Хоть и логарифм будет по большом основанию, все равно поиск места вставки потребует чтений.

К>На практике это очень быстро потому что кеш диска во всех современных ОС использует всю свободную оперативную память. Верхние уровни того дерева попадут в кеш и останутся там на время работы программы, потому что из них читают постоянно.
И что?

К>Если разбить данные на куски влезующие в память и потом мёрджить отсортированные куски, если такая строчка уже была в предыдущем куске данных, код её не найдёт.
А вы точно знаете как B-деревья работают, особенно в случаях вставки не в конец? Про page split не слышали? И какие затраты на вставку в произвольное место в B-дереве?

К>Будут идентичные строчки в двух кусках данных.
Считайте для верности что строчек идентичных не будет. По факту в исходной задаче число в начале делает все строки уникальными.

К>Merge понятно потом уберёт дубликаты, но эти дубликаты занимают место на диске и жгут IO bandwidth.
А вы точно знаете как merge sort работает?

бредовей вариант не придумать. особенно с однопоточным sqllite, он многие часы будет загружать 14 гб csv и раздует до 50 гб датафайлы и индексы, после чего до кого-то дойдет, что никто не обещал уникальность в строках файла.
даже тупой мап-редюс на пару дней обгонит вариант с однопоточным sqllite.

Здравствуйте, _FRED_, Вы писали:

_FR>А попробуйте сгенерить файл моей же и на нём проверить?

Проверил с новой версией. Общее время 13:44 с тем же файлом данных и вашими настройками для 10 Гб.

Т.е. у вас быстрее чем версия gandjustas (15,5 мин), но медленнее чем artelk (6,36 мин). Хотя это все условно — artelk жестко привязался к ASCII.

Мое мнение как это может выглядеть со стороны.

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

Слишком много чести, как по мне. Вряд ли это было оценено.

Скорее всего победила какая-то версия типа artelk, только еще и с 4 байтными числами, ведь в Т.З. не указывали размерность чисел и ничего не сказали про кодировку. Притом что вашу версию могли запустить не в той конфигурации и не с теми параметрами, которые подходят 10 Гб файлов.

Здравствуйте, Shmj, Вы писали:

S>Проверил с новой версией. Общее время 13:44 с тем же файлом данных и вашими настройками для 10 Гб.
S>Т.е. у вас быстрее чем версия gandjustas (15,5 мин), но медленнее чем artelk (6,36 мин). Хотя это все условно — artelk жестко привязался к ASCII.
Я немного оптимизировал алгоритмы и параметры чтения\записи, запусти на том же файле на своей машине актуальную версию https://github.com/gandjustas/HugeFileSort, сколько покажет по времени?
В режиме сортировки ordinal используется RadixSort (подсмотрел у artelk), которая опирается на то что строки равномерно распределены и количество разных символов небольшое.

с такими "оптимизациями" я на своей машине смог за 57 мин отсортировать 104 гб, генерация файла заняла 20 минут.

S>Скорее всего победила какая-то версия типа artelk, только еще и с 4 байтными числами, ведь в Т.З. не указывали размерность чисел и ничего не сказали про кодировку. Притом что вашу версию могли запустить не в той конфигурации и не с теми параметрами, которые подходят 10 Гб файлов.
Это зависело бы от файла. Если программе artelk скормить файл из 100гб одинаковых строк, то упадет.

Какими критериями руководствовались те, кто проверял тестовое задание, мы не узнаем. Но в любом случае было бы неплохо уточнить требования — какие строки имеются ввиду, и какие требования по быстродействию и использованию ресурсов.

Здравствуйте, Shmj, Вы писали:

_FR>>А попробуйте сгенерить файл моей же и на нём проверить?
S>Проверил с новой версией. Общее время 13:44 с тем же файлом данных и вашими настройками для 10 Гб.
S>Т.е. у вас быстрее чем версия gandjustas (15,5 мин), но медленнее чем artelk (6,36 мин). Хотя это все условно — artelk жестко привязался к ASCII.

А на расход памяти вы не посмотрели?
Все эти скорости без привязки к тому, сколько памяти потребовалось ничего не стоят

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Shmj, Вы писали:

_FR>>>А попробуйте сгенерить файл моей же и на нём проверить?
S>>Проверил с новой версией. Общее время 13:44 с тем же файлом данных и вашими настройками для 10 Гб.
S>>Т.е. у вас быстрее чем версия gandjustas (15,5 мин), но медленнее чем artelk (6,36 мин). Хотя это все условно — artelk жестко привязался к ASCII.

_FR>А на расход памяти вы не посмотрели?
_FR>Все эти скорости без привязки к тому, сколько памяти потребовалось ничего не стоят

Да, нужно договорится об условиях и ограничениях, чтобы было интересно сравнивать.
Предлагаю такие:

1. Строки Utf-8 со случайной (равномерно распределенной) длиной [0, 1024). Состоят из символов, которые, после декодирования, укладываются в двухбайтный char. Почти все символы ASCII-7. Закладываться на случайность и равномерную распределенность символов нельзя
   
2. Числа слева тоже случайны в интервале [0, UInt64.Max)
   
3. Разделитель строк: \n
   
4. Нужно уметь сравнивать строки разными компарерами. При сравнении реализаций проверяем время для Ordinal и InvariantCultureIgnoreCase.
   
5. Ограничение на память "живых" объектов (мусор GC не включаем): 200Мб (должно передаваться параметром командной строки).
   
   • Включая 24..26-байтные заголовки у объектов в куче (для .Net) и 8-байтные ссылки на них.
     
   • Включая память на буферы чтения\записи файлов.
   Ограничение не слишком жесткое, можно, например, закладываться на среднюю длину строки и что почти все символы ASCII-7.

PS
Думаю, что строки в памяти можно хранить как utf-8 массивы байт. А простое их побайтное сравнение эквивалентно Ordinal сравнению, так?

Здравствуйте, artelk, Вы писали:

A>Мое: https://github.com/artelk/RowsSort
A>Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
A>Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.

Вот ещё на что обратил внимание — у меня в задании явно было сказано, что

Обе части могут в пределах файла повторяться.

И мой генератор как раз такой файл генерит (сто строк пробублированы).

A>Просьба кому не лень погонять у себя и рассказать

Вообще, скорость и потребление памяти у меня в тестах оказались суперскими

Тестировал на файле со 100М строк, сгенерированным программой Стаса, раз уж и ваше и его задание понимают только этот формат (у меня строки подлинее, чем ваше решение ожидает и числа 64 бита, чего не ожидает решение Стаса). Диск SSD.

Моё (памяти 2Г, не подбирал параметры, сразу так получилось, что расход чуть меньше, чем у Стаса):

Split:  00:01:47.5316319
Merge:  00:04:55.1813633
Total:  00:06:48.3150451 (это суммарно разбивка / слияние плюс ещё всякие мелкие операции типа удаление временных файлов)

HugeFileSort (памяти 2,1G)

Split:  00:03:00.6197825
Merge:  00:01:23.0949052
Total:  00:07:14.2840555

Ваше (памяти 220M):

Split:  00:01:28.4247188
Merge:  00:01:50.3711060
Total:  00:03:18.8076781

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

Что смутило: отсортированный файл у нас с вами получился похожим:

1575399668. 0       ipAo897o0SQCH PvhO eqQqifGCSqokwZ6jAp0Lt7I9EdlMN 9zi5IXnRzZK c cNiXCzBo9cVs  7 7 PtPrq sSJ2Opx Al r  pFo J9 aic QMlMOAVD9 yZWw4wF iX 8IdsAk 2 X2Jk B 7 T911M j UQ2UiHyrWz2YFuI5  0rDNu 0Pek6c6z GsZ f1n Q3X2G3r b4kfo9iv XupONj fYnuHh X
1960802704. 0      BYFo5dqJzrDa67vJTNQ 8H2B1ZgoNu uWsLeBogbRTUYN m0 Bx1 QNYS4wGEHZpCSiBTBE2He4U2xncm1HKO7K6nFCZTmm 0lsJlmY VwVN ODH h3sQtf Ybf35eCxaBHfVtaWnp iZZ vBP
1029441457. 0      HXTtM 5ScPB51y5R0kR JqoVYWCQBZojI Tqwsg1 LUZp6qK e S4Xalb 7sGpyu yBmpFlWFF02h Lp7 B00pnLV8yJkwWgc  px3DR6JPZYoj8MQwIE sT Kug BKu HvuWmCT zgaD1vuB pUHMG9mjJn4
218998971. 0      IOsJymXGecMsGev AF4l  CohACapuf GRbJxBHqFbeFE s1wSI8Q1ScLhz1E89c 7mZ1gIVxR t654F8 qA8aOlNi Zac
69500093. 0      T3O8cNRNPdzSmcgJ4kGBjtYQR3cEO9pplec1pe0 qz0A07h1YePb8jiEnOx wtTSZ  iIOTPyhsKT9 kh YnsCCjwzD H UoXBO4vT 8i95bJit4d xxJUTp8LY oATYaQ v  Z0GY1sHK5Y4cHzLawhkXDM 8tEIikie1 X1xCzKNkx sM 1KesIITA4RGQ Uy kGwNzrY m0keM 06 LsGcxKyuP
…
2009983243. zzzzgrgCD K1y  uLcw4trIwETR2sa7PrE4e3rQG Eh4nWzfhrO  rMR G tEHg vL 9SVo3DDmqcfpAQsOAFbG4aNk7oNVQOXZT6EcGUg 1677FIB6S AYo d icqppohXors3uzU3 n6a Yg  G6w OgXegkDWO rqSp9NUZj shej5XaUA
19509282. zzzzl BLqUiyz4Y 5 UlX V5QNcQKodT w LIpJArcFvgoG   aupAPkFYYYK9  UL8BmYJgO q 5 iIkKYk0 eLQo   nJKyqZ o Bzk8 988 Y nK U8Kz0KuC17VVQ7
661649546. zzzzrE9TYEZ7xI qKHEF8hmqD1SL sm9o W eQ  lIWnuENs03f3RJ
673120082. zzzzttmlaSyWDolu R45aVKf1 L1e 2NWcKEdobEo9arL ed  pchwSQ VHoEilc 6gXmMC5plaT4 i6jkLT RBS5
486393267. zzzzwTqF55fuu bE3F4 cY dqrzXDrRPhi5TkUzHpRpoe ESnH W n 7j 7NexNHbf i  NbLCRBfw n PnyipETUDRD0xTeXLEby0xeh8LY2

А у Стаса другой (вроде как тот же дефолтовый Ordinal компаратор используется)

1029441457. 0      HXTtM 5ScPB51y5R0kR JqoVYWCQBZojI Tqwsg1 LUZp6qK e S4Xalb 7sGpyu yBmpFlWFF02h Lp7 B00pnLV8yJkwWgc  px3DR6JPZYoj8MQwIE sT Kug BKu HvuWmCT zgaD1vuB pUHMG9mjJn4
1602172648. 0     1Gw Ql8bof I jMe9qx 9wc dk QNl NtDzjrM5g 26rR87gVLReF4 knv sg80 w8r6 5Opi 2ERX1jEIN ccg9umf2q f1XE WQTNtnvkl mjSCJCVTTf svNqN9QEy0rD jsYf3 jNjvo4mDqns0m 485fjITPOh Su wROnfTyWhO6RH6xz5 Bvmy19 eVy  3xXN8 XVyvmvKoqD8wdBE8zDpgqClqWN
642615666. 0     AbLJz rmAe b s HftsOwuIG 6FMt6Dxz aVJaCnvxxQxrnsHHtdMHbPqe  0Na5 w oFv4nEc w2VZ6RSJAarLBjDa1XLkKm3QonmYjBxB39jDxOIZLqVrD rZbfjeX E Gzt3f e5i lS L4UUjCD O Ui oLQmhWdymxFLax  BKkPiqDUKn BKgMH8Nu OOVS
350610828. 0     PFRbc2BArP DeqB jVEyaVHif VZi fwQ A4 RiDD b HDE8CTSFm  43DKAjcyU 3 9dEKz0FVHOtz79zjE ETlB97TJ0WXkHYQcguukSHl1Z2q4lZynPCb6O BD1Evn MLuN58Gz5U5tfH 5 93Uqw
677987283. 0     T3 5DNLp9 X9wLdTL4X6wTtMrkQ5HawfcGi uN9bc  1eD4 iS P9  V6Itgtg M3iOk9mXLpD4 5  A3mhnAzs   YeN8iaB N 4Nhqv4nT vsi2 ONbVmNPOq1Vhrlg5 R5 vCR0cbHejuwnctJSPd7h OL4wy Cuj ilcFOXr5miHu a5y FK8OXvuMve  Iehwu7
…
661649546. zzzzrE9TYEZ7xI qKHEF8hmqD1SL sm9o W eQ  lIWnuENs03f3RJ
19509282. zzzzl BLqUiyz4Y 5 UlX V5QNcQKodT w LIpJArcFvgoG   aupAPkFYYYK9  UL8BmYJgO q 5 iIkKYk0 eLQo   nJKyqZ o Bzk8 988 Y nK U8Kz0KuC17VVQ7
673120082. zzzzttmlaSyWDolu R45aVKf1 L1e 2NWcKEdobEo9arL ed  pchwSQ VHoEilc 6gXmMC5plaT4 i6jkLT RBS5
451221061. zzzwzDQVrX OLTYpDbbRLCNej38d cY8aC0 Z1h626NCsblbH GQL za VxpjZ Mt tCJzNPIN2FDBpU1FSMgOMHauIaQEa lu 70vVmFPPogU6 28g aoOLkTneKK jIluHEILuJm gk
486393267. zzzzwTqF55fuu bE3F4 cY dqrzXDrRPhi5TkUzHpRpoe ESnH W n 7j 7NexNHbf i  NbLCRBfw n PnyipETUDRD0xTeXLEby0xeh8LY2

Здравствуйте, _FRED_, Вы писали:

_FR>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Я по этому поводу даже статью на хабр запилил https://habr.com/ru/post/714524/

В целом вот чего сделал:
1) FileStream для чтения (не учитывает преамбулу для UTF-16, но это легко добавить)
2) Программа получает ключи сортировки строк и сохраняет их во временном файле
3) Применяет сжатие временных файлов
4) Параллельно выполняет шаги алгоритма разбиения

Здравствуйте, _FRED_, Вы писали:

Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xml

Автор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.

А по индексам создаем новый файл.

индекс= Строка,смещение. Сортировка по строка.

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