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

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

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

„Гораздо интереснее научиться готовить данные для нее“

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

„(C) cresta Авг 25, 2004 11:22:14.“

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



1073931086__Sort.zip

q_q
„Я указал размер файла в 63 бита, чтобы не было соблазна загрузить все данные в память“

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

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

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

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

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

q_q

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

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

cresta
Не надо понимать все в буквальном смысле.
Я очередной раз повторяю, что не собираюсь делать физический файл больше 5Гб. А цифру 63 предложил чтобы не было соблазна использовать dword для хранения размера файла и смещения строки от начала файла.

Или ты подкалываешь? :(

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

1 строка - доходы человека
2 строка - расходы человека
3 строка - имя(фамилия)

100000 человек. 300000 строк. Выстроить их в порядке возрастания разности между доходами и расходами.

Такова была задача, плюс строка "фамилия" могла быть до 2 Гб. Правда не знаю, где предложивший задачу видел такие фамилии. Это более щадящий режим, "всего лишь" 100000 Гигабайт. Но и он неосуществим.
Можно ограничиться реальной цифрой, к примеру 256 символов, увеличив количество строк. К примеру, в 10 раз.

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

Чел, который предложил мне это, файлов или программы для их подготовки не предоставил, я по своему разумению составил файл 300000 строк - 13,8 Мб. На большем пока не пробовал.

q_q

Я не понял, что нельзя использовать dword ptr? А как же ты собираешься адресовать память? Ну давай тогда число размером dword будем таскать в паре регистров, один из них будет пустой. Или в таблице указателей под каждый указатель зарезервирую 8 байт вместо 4. Что это даёт? Или ты предполагаешь, что твой алгоритм обойдётся без dword ptr? Не вижу, что тебе это может дать.

Или добираться до указателя через byte ptr, а затем побайтно собирать его в кучу, так что-ли. Чего-то я недопонимаю :(

Если запрет на dword ptr, то как мне адресовать 32-разрядную шину адресов. Это ведь не 8-разрядный Z80.

Как-то это не очень понятно :(

p.s. не подкалываю я тебя. Ты написал 2^63, я прочел.

volodya
"...вы когда-нибудь слышали? ... Сначала надо доки читать, а потом спорить."
(это по поводу внешней сортировки и B-деревьев)

Слышать-то слышали, а вот своими ручками делать не приходилось. В моем ответе насчет Oracle и др. именно внешняя сортировка и подразумевалась. Но углубляться в это дело ради надуманного домашнего задания (2^64) я не собираюсь. Так что, до встречи "в новой жизни", то бишь теме. С нетерпением буду следить за развитием событий и за рекордами создания и обработки тестовых файлов размером > 1Gb (думаю за меньшие значения и браться не стоит). Удачи и попутного ветра.
И напоследок. Кроме искусства программирования по Кнуту неплохо было бы ознакомиться с искусством системотехники по Холлу и либо не браться за бестолковые проекты, либо переформулировать задачу, подойдя к проблеме с другой стороны. Гига-тексты именно из этой области.

PS. Может я запоздал с ответом и намечаются какие-то конструктивные сдвиги ?

cresta
если ты действительно хочешь сравнить свой метод с другими
Не столько сравнить, сколько найти хороший.

я по своему разумению составил файл 300000 строк - 13,8 Мб.
Тогда не подписывайся на 2Gb, а MMF'ь свои 15М в память и QSORT'ируй спокойно.

Я не понял, что нельзя использовать dword ptr?
Он тоже 32 бита, а я хочу чтобы программа оперировала 64-х разрядными, смещениями в файле. Это будет работать и с маленькими файлами, конечно не так эффективно, как сортировки полностью загружающие исходные данные в память.

leo
ради надуманного домашнего задания
Расскажу историю, а ты решишь надуманное задание или нет.
95/96 год, 486DX33, DOS. Стоит компьютер на него поступает информация с разных эл.подстанций, он пишет ежедневный лог-файл (в пределах 1.5M и 30т. строк). Если связи с кем-то не было (а не посланная информация хранится на подстанции и ждет связи), то информация предыдущего дня могла попасть в текущий. Сидит человек, открывает ежедневный лог-файл в multiedit'e (другого редактора, который бы смог открыть большой файл тогда не было) и запускает сортировку (благо такая возможность в редакторе есть). Приходится ждать минут 40. Написал я ему программу на BC++v3.1. Сортировала в пределах 6 минут. Позже вспомнил о наличии sort.exe, он сортировал быстрее меня, но иногда отказывался из-за нехватки памяти. Моя программа дополнительно резервировала ~70кб и в ней действительно адреса всех строк хранились в памяти, но читать из файла строки для сравнения все равно приходилось.

Увидев тему, в которой упомянули файл размером 2Gb, я подумал почему бы не заняться сортировкой файла, который будет большим для сегодняшней техники и ОС.

q_q
"Зачем писать очередную реализацию QSORT? Гораздо интереснее научиться готовить данные для нее. Например, файл с миллионом пустых строк..."
По видимому вместо очередной реализации QSORT вы вместе с volodya хотите написать столь же "оригинальную" реализацию поиска по дереву. Чтож, "Кнут вам в руки".
Вот если изначально не отказываться от идеи сортировки по массиву, то наверное можно придумать что-то оригинальное - некий гибрид древовидного и векторного поиска. В частности, ссылки на пустые строки вообще незачем хранить, достаточно подсчитать их количество (если они вообще нужны в выходном файле).

cresta, q_q
Все-таки, вы не ответили на вопрос, а что вы собираетесь потом делать с отсортированным файлом. Пример, который привел cresta, больше смахивает на школьное задание, чем на реальную задачу. Ну отсортировали, ну и что. Распечатать на рулоне и удалить файл за ненадобностью ? А если нужна не разность доходов, а сами доходы или расходы ? В нормальной жизни такие вещи хранят в базе данных и получают из нее все что нужно в любой последовательности.

q_q
Извини, я опять торможу. Спасибо за пример.
Но ты учти, что сейчас на дворе 2004-й. Подобные задачки из области СУБД. А log по-видимому и раньше писался и сейчас пишется не в один файл. У меня коллеги по работе тоже на протяжении 10 лет ведут круглосуточные наблюдения и запись данных. Но сшивать их в один гига-файл никому в голову не пришло. Нужно либо перекачивать данные в БД, либо создавать свою программу для индексации и просмотра\распечатки исходных данных по запросу. При таком подходе сшивать разные файлы или вообще не нужно, или до определенных оптимальных размеров (при этом индекс, конечно будет составным: файл+смещение).
И еще пример, по поводу размера файла и предподготовки. Когда я занимался загрузкой мусорных текстовых данных в БД для земельного учета, выяснилось что оптимальный размер для визульного просмотра и интерактивного разбора текста по столбцам - это 8-10 тыс. строк. Поэтому для ускорения работы приходилось маленькие файлы сшивать в один, а большие - делить на несколько.
Ну и последнее. При общении с заказчиками нельзя бросаться исполнять желания всезнающих офис-менеджеров или скромных операторов - как правило они сами не знают чего им надо. Посмотришь на задачу с другой стороны, предложишь свое решение - получишь выигрыш (либо бабки, либо время, либо удовольствие, а лучше все вместе).

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

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

Но ты учти, что сейчас на дворе 2004-й. Подобные задачки из области СУБД.
Я уже писал, что в теории это так, а на практике не всегда.

А log по-видимому и раньше писался и сейчас пишется не в один файл.
Я так и сказал: "ежедневный log-файл", т.е. один день - один файл.

меня коллеги ... сшивать их в один гига-файл никому в голову не пришло
А почему? Потому что нет инструментов обработки такого файла.

q_q
"Потому что нет инструментов обработки такого файла."
Да нет брат, потому что это не удобно. Представь себе, что собрание сочинений В.И.Ленина выпустят одним томом. Я уже представил... Текстовые гига-файлы - из той же области. СУБД отличается тем, что это не только способ хранения и сортировки, но и еще и специальный инструмент для извлечения нужных данных в нужной последовательности.

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

leo
Почему апеллируя ко мне, ты постоянно противопоставляешь гига-файлы и СУБД? Разве я где-то писал, что, опираясь на программу сортировки большого файла, собираюсь создать инструмент альтернативный СУБД, единственное практическое применение, которое я упоминал - это единоразовая обработка большого файла?

Вывод напрашивается простой - логичнее ...
Imho с такой логикой остается пользоваться плодами труда разработчиков СУБД для больших объемов информации, и своими наработками основанными на плодах труда разработчиков VCL для маленьких объемов информации. А со временем и свои наработки не понадобятся.