Один программист задал мне простой вопрос: «Как отсортировать файл на диске?» Прежде чем я расскажу о своей первой ошибке, попробуйте ответить на этот вопрос лучше, чем в свое время это сделал я. Итак, что бы вы сказали?
1.1. Дружеский разговор
Моя ошибка состояла в том, что я ответил на вопрос, вкратце объяснив, как надо выполнять сортировку записей в дисковом файле слиянием (merge sort). Предложение углубиться в тонкости теории алгоритмов было встречено без энтузиазма — для него было важнее решить задачу, чем повысить уровень собственного образования. Тогда я рассказал ему о программе сортировки дисковых файлов из одной известной книги по программированию. В этой программе было около 200 строк кода, разбитого на 12 функций; по моим прикидкам, на написание и тестирование такой программы у этого программиста ушло бы не больше недели.
Сомнения моего собеседника в том, что я решил его проблему, привели меня на правильный путь. В дальнейшем наша беседа протекала так (мои вопросы выделены курсивом):
— Зачем вам понадобилось писать собственную программу сортировки?Почему для этой цели не воспользоваться системными средствами?
— Мне необходимо встроить функцию сортировки в большую программу, и по некоторым причинам я не могу воспользоваться системной программой для сортировки файла на диске.
— Что именно вы сортируете? Сколько записей в файле и каков их формат?
— Файл содержит не более десяти миллионов записей, каждая из которых представляет собой семизначное целое число.
— Подождите минутку. Если файл настолько мал, зачем‘вообще связываться с диском? Почему бы не отсортировать его в оперативной памяти?
— Хотя используемый компьютер и оснащен достаточно большим количеством оперативной памяти, эта функция сортировки является лишь малой частью большой программы. К моменту ее выполнения свободно будет лишь около мегабайта оперативной памяти.
— Что-нибудь еще можно сказать об этих записях?
— Каждая из них представляет собой положительное семизначное целое число без каких-либо связанных с ним дополнительных данных, и каждое число встречается в файле только один раз.
Теперь задача проясняется. В Соединенных Штатах номера телефонов состоят из трехзначного кода города (area code), за которым следуют семь цифр местного номера. Звонки по номерам с кодом 800 (единственным в то время) были бесплатными (toll-free). Существующие базы бесплатных номеров включали достаточно большое количество информации: бесплатный номер телефона, реальный номер, на который перенаправляется вызов (иногда несколько номеров с установленными правилами отбора), имя и адрес абонента и так далее.
Программист занимался созданием небольшого блока системы обработки такой базы данных, а сортировать он должен был именно эти телефонные номера. Входные данные представляли собой файл со списком телефонных номеров (вся прочая информация из файла удалялась), причем повторение какого-либо номера было бы ошибкой. На выходе нужно было получить отсортированный по возрастанию файл с номерами телефонов. Контекст задачи определяет также требования к производительности программы. Во время работы с системой пользователь должен был обращаться к этому файлу приблизительно раз в час, и до завершения операции сортировки он не мог бы продолжить работу. Следовательно, время, отведенное для сортировки, должно было быть минимальным, оптимально — не более десяти секунд.
Опубликовал vovan666
April 16 2013 23:33:58 ·
0 Комментариев ·
3652 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
