|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Igor Grigoriev 2:5030/861.21 11 Dec 2001 20:12:55 To : Alexander Chelmodeev Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- _______________________________________________________________________________ Так о чем мы болтали? 09 декабря 2001 года (а было тогда 17:01) Alexander Chelmodeev в своем письме к Kartohin Ruslan писал: AC> /Привет Kartohin!/ я KR>> procedure Define KR>> program AC> 1. Добавим 2-й файл к 1-му, при слиянии к каждой строке из 2-го AC> файла добавим хотя бы точку (.). AC> 2. Сортируем файл. AC> 3. Пробегаем от начала к концу, читая по паре строк [n] и [n+1]. AC> Если встретилась пара, в которой только одна строка с точкой, AC> сравниваем их (исключив точку). Сравнились - в выходной файл, иначе AC> продолжаем... Сортируем это ключевое слово? Я сейчас реализовывал метод встречи посередине для 32-х битного Люцифера и там надо искать сопадения шифротекстов из одного файла с шифротекстами в другом файле. Файлы содержат от 20000 до 60000 записей по 16 байт. Так я решил файлы в память не втягивать (для имитации варианта, когда это не реально), а сортировку делать qsort по след принципу: забить массив номерами 16-бит от 1 до числа записей и передать qsort функцию сравнения, которая будет считывать i-ый элемент базы, зная что длина записи постоянная и можно рассчитать смещение. Для функции сравнения перепробовал все функции типа fseek SetFilePos даже все и не вспомню. Так вот тормозит эта стадия сотировки со страшной силой. (дольше чем этот файл шифруется раз в 20 или 10) Хотя такой же массив просто случайных чисел сортирует моментально (естес-сно с другой cmp ф-ей). Есть подозрение, что этот fseek чуть ли не с самого начала до указанного смещения каждый раз файл просматривает. Дык как прикажете файл сортировать? Если школьник еще успеет функцию сортировки логарифмической сложности реализовать. np: Тишину За сим разрешите откланяться, Igor --- GoldED+/W32 1.1.5-20010807 [Team Hackers] * Origin: В любое время дня и суток! (2:5030/861.21) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38973c1634ab.html, оценка из 5, голосов 10
|