Сортировка строк текстового файла.

Исходные данные:<ol type=1><li>текстовый файл в формате ASCII;<li>может содержать символы 09h, 0Ah, 0Dh, 0Ch и от 20h до FFh;<li>признак конца строки - пара 0Dh, 0Ah или отдельные 0Dh, 0Ah, 0Ch;<li>в конце последней строки обязательно должен быть признак конца строки, иначе если последняя строка исходного файла окажется не последней в результирующем, то к ней "приклеится" следующая строка результирующего файла;<li>размер строки не ограничен, т.е. файл может быть пуст, содержать только пустые строки, либо одну строку;<li>размер файла до 2^63, т.е. Signed 64-bit integer.</ol>



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



Критерий: скорость.



Дополнительная задача: написать программу для формирования тестовых исходных файлов:<ol type=1><li>пустой;<li>одна строка;<li>только пустые строки;<li>отсортированный;<li>отсортированный в обратном порядке;<li>не отсортированный.</ol>



Для начала решения на любом языке программирования.

В идеале на ассемблере с использованием только OS API.

Умение "прикрутить" к ассемблеру библиотеку, помогающую в решении задачи допустимо, но не идеально.



Комментарии, исправления, дополнения.

 

q_q

Если разумно ограничить размер файла сотней, другой мегабайт, то можно подумать. Иначе это что-то из области индексации таблиц баз данных. Тягаться с Oracle, MS или Borland не хочется, тем более не зная где это может пригодиться. Я, конечно, как всегда не прав, поэтому на ответ не расчитываю.

 

leo

разумно ограничить размер файла

Конкретнее.



[offtopic]

Я, конечно, как всегда не прав, поэтому на ответ не расчитываю.

Разве я где-либо это утверждал? Imho только высказывал сомнение в точности формулировок.

[/offtopic]

 

q_q

Мне понравилась Дополнительная задача, особенно первые 3-и пункта и 6-й

 

Asterix

Любая программа требует тестовых данных. Особенно важны пограничные варианты 1-3 пункты. 4-5 формируют файлы, которые будут являться одновременно файлами для проверки результатов только наоборот. Шестой пункт важен, так как необходимо, чтобы исходные данные были одинаковыми для всех вариантов (ты же не думаешь, что исходные данные будут выложены в виде файла).

 

q_q

У меня был такой вариант:

Код (Text):

1. На входе:
2.  
3.     Текстовый файл 300 000  строк
4.     Признак окончания строки 0D0A
5.     Состоит из 100 000 триад строк
6.     Триада: 1я строка - число от 0 до 65535
7.         2я строка - число от 0 до 65535
8.         3я строка - произвольный текст
9.    
10. На выходе:
11.    
12.     Файл, сортированный по следующему принципу:
13.     Триады выстроены в порядке возрастания разности значений 1 и 2 строк
14.         В случае нулевой разности сравнение по 3й строке
15.  
16. Примечание:
17.     Числа представлены как строки, но не как бинарные данные

 

q_q

Ты забыл указать критерии сортировки, ну там по алфавиту, по размеру строки, может ещё по чему-нибудь.

 

Пардон что вмешиваюсь, но:



>>Я и не сомневался, что адреса. Но когда ты добавляешь 240000-й указатель к массиву из N = 239999, и он в результате сортировки должен занять первую позицию, то ты будешь переписывать около 1 Мб данных. И такая ситуация возможна при добавлении любого указателя.

Другими словами, не нужно производить сортировку при добавлении каждого элемента. Нужно сначала загрузить все адреса и затем отсортировать все скопом - получим большую экономию времени.



и плясать надо от этого. Где здесь про файлы? Где здесь про пограничные варианты? Абсолютно похер откуда взялись строки - файл, сокет, или Кашпировский постарался. Прикрутить к пиписке какой-то девайс, и потом уже этим мерятся? Достаточно условий, что это обычные виндовые ANSI строки,диапазона длин строк, и количества строк. Проблема получения строк - это отдельная задача.



P.S

Надеюсь, это не из серии двое дерутся третий в ж..?

 

Берем файл размером 128Гб, в котором лежит 64 строки по 2Гб, различающиеся последним символом. Берем алгоритм который отсортирует этот файл, произведя 64*log(64)=384 сравнения, и получаем что для сортировки этого файла придется прочитать 384*2Гб*2(потому что даже одна строка в память не поместится). Никакое кеширование в таких случаях не поможет.



Вы все еще хотите сортировать 2^63 байт? 8)

 

q_q



Нигде не видел алгоритмов

<ol type=1>1. сортировки одной пустой строки

2. сортировки одной непустой строки

3. сортировки кучи пустых строк

4. сортировки отсортированных строк</ol>



То, что ты предлагаешь, к сортировке имеет весьма опосредованное отношение. Скорее это работа с файлами произвольного размера.

Если файл 2^63байт, то могу предположить, что на загрузку, составление таблицы адресов и выгрузку на винт строк в определенном порядке уйдет 99% времени работы программы. Собственно сортировка получается как бы ни при чём.

 

Тягаться с Oracle, MS или Borland не хочется, тем более не зная где это может пригодиться



и получаем что для сортировки этого файла придется прочитать 384*2Гб*2(потому что даже одна строка в память не поместится) Вы все еще хотите сортировать 2^63 байт? 8)



Black_mirror, я не могу поверить, что это _ты_ сказал!

А вы, алгоритмисты хреновы. Что, уже Кнута не модно читать? А что такое "внешняя сортировка" вы когда-нибудь слышали? На algolist не отправляю, там ребята просто перевели на русский мистера Нимана. Топаете в раздел "Алгоритмизация" в доках на сайте и подбираете оттуда английский вариант. Разбираетесь с тем, что такое Б-деревья. Потом идете в Кнута и читаете, что такое Б⁺-деревья. Сначала надо доки читать, а потом спорить. Блин.

 

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

 

Да ну? А это что:



Задача: написать подпрограмму сортировки строк

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



А это: размер файла до 2^63, т.е. Signed 64-bit integer?

 

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

 

cresta

У меня был такой вариант

Покажи пример до, и после сортировки.



Нигде не видел алгоритмов ...

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



Asterix

Ты забыл указать критерии сортировки

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



__Ranger > сначала загрузить все адреса и затем отсортировать все скопом - получим большую экономию времени ... Где здесь про файлы?

Black_mirror > для сортировки этого файла придется прочитать 384*2Гб*2(потому что даже одна строка в память не поместится).

cresta > То, что ты предлагаешь, к сортировке имеет весьма опосредованное отношение

По-вашему сортировать можно только то, что помещается в памяти. Это мне не интересно, потому что теория этого известна много лет.



__Ranger > В изначальном посте не было и речи о какой либо предварительной подготовке данных

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



Black_mirror > Вы все еще хотите сортировать 2^63 байт? 8)

cresta > Если файл 2^63байт, то могу предположить, что на загрузку, составление таблицы адресов и выгрузку на винт строк в определенном порядке уйдет 99% времени работы программы.

Этим я и хочу заняться. Зачем писать очередную реализацию QSORT? Гораздо интереснее научиться готовить данные для нее. Например, файл с миллионом пустых строк занимает 2 миллиона байт, а для тривиального хранения адресов каждой строки потребуется 4 миллиона байт. Разве это не накладно?



Я указал размер файла в 63 бита, чтобы не было соблазна загрузить все данные в память. Практически можно ограничиться 31 битом. Afaik даже MMF не предоставит окна такого размера.

 

__Ranger

изначальным_ я считаю пост, который приводил выше в этом топике

Если ты про Количество разделителей строк, то от туда же "Строки произвольной длины, до 2Гб." (C) cresta Авг 25, 2004 11:22:14.

 

q_q

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

Ну, в таком случае, задачу надо переименовать в "Индексация больших объёмов памяти" или что-то подобное. При чём здесь сортировка, не понял. Плиз объясни.

Не совсем моя идея, мне предложил Некто, не подозревая, куда это ведет. Я тоже сразу не подумал об этом.







1073931086__Sort.zip

 

q_q

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

 

cresta

переименовать в "Индексация больших объёмов памяти" ... При чём здесь сортировка ... объясни.

Наверное, индексацией можно назвать промежуточный этап любой сортировки, которая непосредственно перемещает данные только после выстраивания некой упорядоченной схемы (дерева, последовательности), причем упорядоченная схема может быть выстроена для части исходных данных и тогда действие построения такой схемы можно назвать частичной индексацией.



Что касается твоего задания, то разница с сортировкой строк не принципиальная, и касается только функции сравнения.



не подозревая, куда это ведет

Каков размер твоих исходных файлов?



ОК, делай программу, котороя составит такой тестовый файл

Это не проблема.

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

 

q_q

Ну-ну... Вообще-то неплохо было бы для начала взглянуть через калькулятор, что есть 2^63. Я уже поглядел. Погляди тоже. Если лень смотреть, то скажу тебе, что это около 9 млрд Гигабайт.

Ещё не пропало желание делать такой файл ?