|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrey Dashkovsky 2:5002/46.4 11 Dec 2001 22:23:36 To : Kartohin Ruslan Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- 09 Дек 01 14:37, you wrote to Arthur Vartanov: AV>> Это сильно. Твой алгоритм будет иметь приемлемую скорость для AV>> небольших файлов. А если в файле с десяток тысяч строк? Поэтому AV>> делаем так: по более длинному файлу строим хеш-таблицу, AV>> упорядочиваем ее по возрастанию/убыванию хэша и делаем бинарный AV>> поиск, используя хеши строк второго файла. Естественно, учитываем AV>> коллизии. KR> Пpимеpно такое же pешение пpишло и мне в голову пpи пеpвом KR> пpосмотpе задачи. Хотя кол-во стpок (см. пpед. сообщение) в данной KR> задачи по условию не KR> пpевышает 500, но для стандаpтного Turbo Pascal в любом случае KR> невозможно загонять стpоки в массив. Естественно напpашивается ваpиант KR> хpанить не стpоки в массиве, а некие уникальные и более компактные KR> величины, однозначно идентифициpующие стpоку. Внесу небольшую поправочку, мелочь, но существенная: Hе над той проблемой думаешь. Главное, чтобы в 400k укладывалась. Почему именно 400 - в общем случае, но иногда можно пойти на исключения и взять побольше. Конкретно для паскаля: Если превышает 64k - выделяй динамически. если величины маленькие используй двумерный массив вместо одномерного, а именно массив динамически выделяемых массивов, где обращение вместо a[i] пишешь например a[i shr 10]^[i and 1023], где a - [0..n shr 10] of [0..1023] вместо [0..n-1] соотвестсвенно вместо 10 и 1023=(2^10-1), можно подобрать другие числа, чтобы по сегментам раскидать. Andrey ... "Продается бюстгальтер Ericsson с определителем номера". --- GoldED+/386 1.1.4.7 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/143013c167b71.html, оценка из 5, голосов 10
|