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

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 для маленьких объемов информации. А со временем и свои наработки не понадобятся.

 

q_q

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



Все же, мне думается, разговор не перейдет в конструктивное русло, пока ты, как инициатор, или кто другой не предложат для обсуждения конкретные частные подзадачи. А пока получается, что-то типа объявления конкурса с неизвестным итогом. И время убъешь и поймешь, что ты лох - надо было бы все не так (это я про себя). Это все таки форум, здесь люди обсуждают проблемы, а не соревнуются. Или я неправильно понимаю (это уже к "подстрекателю" volodya).



PS: в частности, не понимаю почему для начала не взять размер < 4Gb и использовать все таки dword-ы. Суть ограничения, как я понимаю, в том, что нельзя целиком хранить в памяти ни сам файл, ни индексы. А > 4GB достаточно иметь ввиду, чтобы алгоритм позволял произвести доработку до qword (а нет, так и фиг с ним).

 

Или я неправильно понимаю (это уже к "подстрекателю" volodya).



Во. Теперь еще и меня виноватым сделали. Вы, сперва, с условиями задачи разберитесь. С формулировками разберитесь, а потом пылить начинайте.

 

У меня есть предложение выбрать какой либо один байт для обозначения конца строки, в противном случае не ясно что делать с двумя пустыми строками, если одна из них оканчивалась на 0A, а другая на 0D. Как встретив 0A0D в отсортированном файле определить это одна пустая строка или две? Вобщем я склоняюсь к мысли что перед сортировкой стоит преобразовать исходный файл, заменив все tab'ы на пробелы, а в конце строки оставить только один 0A или 0D.

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

 

volodya

"Во. Теперь еще и меня виноватым сделали"



Чего-то мы запарились. Вот для развлечения funny story:



Летают фанеры над столицами мира. Одна и говорит: "..эх, заняться чем что-ли.." Мол, все летаем, летаем, пора бы и приземлиться, на мир вблизи посмотреть... Идея было понравилась, стали приглядывать место для посадки. Но тут вдруг высший разум с ясного неба: "займитесь, займитесь..." и пальцем у виска крутит, мол "вы че, ку-ку ? пролетите и мокрого места не останется". Да, озадачил. Нет, видать, уж лучше в облаках витать (поэзия, однако). С отцем небесным общаться. Ну а тот и рад, давай им истории всяки про деревья райские сказывать, ну те, что с Кнутом вместе зажали. А то говорит, зачахли деревья без внимания-то, окучивать надо, одни злые орклы над ними вьются. Посмотрел народ на поле непаханное да немерянное - это сколько ж Га здеся буде. Взялися подсчитывать, кто в уме, кто на пальцах - не хватат пальцев то. А отец - хитер, давай стыдить их: "О мир, говорит, не могу поверить, что это ты !". Вот так, и Кнутом, и Пряником. Пробил час, кажися с 26-го на 27-е по новому стилю, и молвил он наказ: сортировать поле размером до 2^63 и баста. И еще пилюли прописал: Signed 64-bit и два параметра, три раза в день. Ну, народ давай те пилюли жевать да выплевывать - глотать-то такую нечисть кому охота. Топчутся вокруг, да около - такая пылища поднялась. А око никогда не дремлет, пылить не разрешает и на какие-то разборки посылает. Ну и правильно. Потому что оно ясное и справедливое, а во всем гнусный микрософт и его шайка виноваты. Разрешили такие поля сеять, вот народ и давай стараться: а что если все это сорняками да пустостроками засадить, во весело будет. Не, если конечно как попало, то это просто мусор, а вот если в определенном порядке, то это сортированный мусор. Генератор гигамусора смастерим, в хозяйстве сгодится - можно его потом нехорошим соседям на винт подбрасывать - все же польза. Эх-ма-а... "О мир, не могу поверить, что это ты !"



PS: улыбайтесь, вас снимает скрытая камера !

 

Честно говоря, я уже устал прикалываться. Но все-таки предлагаю тем, кто возьмется за реализацию проекта перед сортировкой проверить свободное место на диске. Дерево это вам не массив. Это как минимум две ссылки + ключ. Две ссылки qword это уже 16 байт - а это уже может быть сравнимо со средней длиной строки в самом файле. Если ключи по большей части уникальны (как в задачке cresta), то размер индексного файла может быть сравним с размером исходника + еще отсортированный надо сохранить.

 

Black_mirror

что делать с двумя пустыми строками, если одна из них оканчивалась на 0A, а другая на 0D ... Как встретив 0A0D в отсортированном файле определить это одна пустая строка или две?

Очень просто. Если первый найденный символ 0Dh, то за ним проверяется наличие 0Ah, за 0Ah ничего не проверяется.



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

Если ты полагаешь, что предварительная обработка увеличит скорость, то сделай это.



Так же неплохо было бы оговорить сколько можно ...

Зачем вносить ограничение?



leo

Сказки придумываешь, что же о своей роли скромно умолчал?



Честно говоря, я уже устал прикалываться.

А как тогда расценивать советы: "... проверить свободное место на диске ... 16 байт - а это уже может быть сравнимо со средней длиной строки ..."?

 

q_q



Для сортировки больших объемов данных не умещающихся в памяти используют т.н. внешнюю сортировку.

(выбор с замещением, мнофазное слияние, челночное слияние)

См. Кнут, например.