Исходные данные:

1. текстовый файл в формате ASCII;
2. может содержать символы 09h, 0Ah, 0Dh, 0Ch и от 20h до FFh;
3. признак конца строки - пара 0Dh, 0Ah или отдельные 0Dh, 0Ah, 0Ch;
4. в конце последней строки обязательно должен быть признак конца строки, иначе если последняя строка исходного файла окажется не последней в результирующем, то к ней "приклеится" следующая строка результирующего файла;
5. размер строки не ограничен, т.е. файл может быть пуст, содержать только пустые строки, либо одну строку;
6. размер файла до 2^63, т.е. Signed 64-bit integer.

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

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

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

1. пустой;
2. одна строка;
3. только пустые строки;
4. отсортированный;
5. отсортированный в обратном порядке;
6. не отсортированный.

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

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

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

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

[offtopic]
Я, конечно, как всегда не прав, поэтому на ответ не расчитываю.
Разве я где-либо это утверждал? Imho только высказывал сомнение в точности формулировок.
[/offtopic]

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

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

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

На входе:

	Текстовый файл 300 000  строк
	Признак окончания строки 0D0A
	Состоит из 100 000 триад строк
	Триада: 1я строка - число от 0 до 65535
		2я строка - число от 0 до 65535
		3я строка - произвольный текст
	
На выходе:
	
	Файл, сортированный по следующему принципу:
	Триады выстроены в порядке возрастания разности значений 1 и 2 строк
        В случае нулевой разности сравнение по 3й строке

Примечание:
	Числа представлены как строки, но не как бинарные данные

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

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

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

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

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

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

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

q_q

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

1. сортировки одной пустой строки
2. сортировки одной непустой строки
3. сортировки кучи пустых строк
4. сортировки отсортированных строк

То, что ты предлагаешь, к сортировке имеет весьма опосредованное отношение. Скорее это работа с файлами произвольного размера.
Если файл 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 не предоставит окна такого размера.