Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Сортировка длинного списка.  (Прочитано 8161 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mtyn
Гость
« : 02-07-2008 07:12 » 

Здраствуйте,помогите мне пожалуйста разобраться  с программой.
Написать программу которая сортирует длинный список (файл прилагается),причем ф-цию сортировки нужно писать самому(
Если список очень длинный,то получается создать новый список и занести из файла данные в него не хватит памяти,если писать под Doc,подскажите возможные пути решения этой проблемы.
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 02-07-2008 07:24 » 

Не совсем понял - нужно сортировать очень большой файл, не помещающийся в памяти? Сортировка слиянием?
И при чём тут Borland C/C++?
« Последнее редактирование: 02-07-2008 07:25 от Вад » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #2 : 02-07-2008 08:43 » 

стандартные методы не ведаю, а на ум приходит:

написать класс-менеджер, который позволит работать с файлом как с огромным байтовым массивом. Класс будет открывать файл страницами, при чтении тормозов будет мало, а вот при менянии строк местами будут небольшие тормоза (так как , возможно, придётся страницы активно переключать). Но зато - не зависим от размера озу )
Записан

Mtyn
Гость
« Ответ #3 : 02-07-2008 12:35 » 

Список огромен представим что к примеру 100000 фамилий,главное что б работала быстро и жрала мало памяти.Есть предположени сначала сортировать по 1-й букве,потом по 2-ой и так далеее.
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #4 : 02-07-2008 18:18 » 

Mtyn, Разбиваеш файл на несколько фрагментов. Отсортировываеш их, И затем как сказал Вад сортировка слиянием. Это же классика. Дональд Кнут "Искусство программирования" 3 том.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 02-07-2008 18:22 » 

Mtyn, во, ещё вариант - организовать связанный список

 перебрать файл по записи и составить новый по принципу:
Код:
\r\n
#num1|next|prev|text\r\n
#num2|next|prev|text\r\n
#num3|next|prev|text\r\n

где
numX - идентификатор строки (например, поиск 57-й строки будет осуществляться как поиск строки "\r\n#57" ) !=0
next - идентификатор предыдущей строки (если не 0)
prev - идентификатор следующей строки (если не 0)

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

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 02-07-2008 18:31 » 

Алексей1153++, А как ты примерно собираешся раздвигать файл. Mtyn, сказал, что у него 100 тысяч примерно записей. Отведем под каждую запись скажем 80 символов итого примерно 8 мегабайт только исходного файла. Кстати Mtyn 8 мегов это не слишком большой объем информации для современных компов, можно и напрямую в пасять полностью все считать, и затем сортировать.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 02-07-2008 18:38 » 

Finch, только новый файл создавать, видимо

А насчёт размера в 8 метров - он же написал

Код:
если писать под Doc
полагаю, DOS имеется в виду
Записан

Mtyn
Гость
« Ответ #8 : 03-07-2008 07:04 » 

думал,думал придумал,нужно создать N бинарных файлов,в каждый из которых заносить фамилии на одинаковую букву,я думаю это облегчит задачу,а потом производить сортировку в этих файлах
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 03-07-2008 07:10 » 

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

Тут я согласен с Finch, лучше (и надёжнее с точки зрения налагаемых тобой ограничений по памяти) разделить файл на блоки фиксированного размера (+- погрешность в 1 запись), сортировать каждый блок отдельно внутри себя (тем же quicksort, например), а потом сливать результат сортированных блоков воедино (возможно, установив ограничение на число одновременно сливаемых блоков - в каких-то случаях может потребоваться несколько итераций слияния, если уж очень много данных по отношению к объёму памяти).
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 03-07-2008 07:30 » 

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

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #11 : 03-07-2008 09:51 » 

Леш не будет такой же фигни. С каждого отсортированного блока ты считываеш несколько первых записей. Потом береш первые записи со всех блоков. Записываеш самое наименьшее (наибольшее) значение. перемешаеш курсор блока на следуюшую запись. Если закончился лимит считанных записей в блоке, то просто дочитываеш блок дальше.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #12 : 03-07-2008 10:02 » 

то есть это сначала надо много маленьких промежуточных файлов создать
Записан

Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #13 : 03-07-2008 11:22 » 

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

Программа – это мысли спрессованные в код.
Mtyn
Гость
« Ответ #14 : 03-07-2008 15:02 » 

Спасиб за оказанную помощь,подскажите где найти справочник в котором описаны действия с бинарными файлами(чтение из файла,запись,вставка в файл и т.д
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #15 : 03-07-2008 20:12 » 

Mtyn, любой нормальный учебник по С++ тебе поможет. Самое главное, чтоб этот учебник не был из серии "С++ для чайников за 21 день". Там кроме "Взлет и посадка" (с) ничего и нет.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines