| TiGeR |
 Отправлено: 19.07.2006, 12:57 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
Короче есть очень много файлов размером от 1ГБ нужно найти в нём строчку и сохранить в новом файле ... помогите найти самый быстрый алгоритм решающий подобную задачу... вообще я буду делать это в несколько потоков кто реализовывал подобные задачи??? |
|
| Shagg |
| Отправлено: 27.07.2006, 12:04 |
|
Дежурный стрелочник
Группа: Участник
Сообщений: 69
|
Читать из файла блоками размер которых равен длине искомой строки и сравнивать. Думаю быстрее не получится, т.к все равно придется читать весь файл. |
|
| GoodWin |
| Отправлено: 28.07.2006, 14:21 |
|
Дежурный стрелочник
Группа: Участник
Сообщений: 50
|
Основная проблема состоит в низкой скорости винта. Если сделать несколько потоков которые читают с винта и тут же производят поиск в считанном блоке данных, то скорость винта упадет еще в несколько раз, т.к головка диска будет метаться как сумашедшая )).
Если сделать один поток чтения и поиска, то скорость так же снизится, т.к. в моменты поиска в блоках памяти винт будет простаивать.
Т.к. скорость поиска больше скорости чтения( т.к. проц и оператива быстрее винта будут )) ), то целесообразнее всего распаллелить след. образом:
- поток чтения блока памяти( max размер кеша лучше подобрать вручную, или сделать настраиваемым ), поиск "простаивающего" потока поиска, либо ожидание первого освободившегося.
- потока поиска в считанном кеше 0
...........
- потока поиска в считанном кеше N-1
Количество потоков поиска можно определить экпериментально или ( это даже лучше ) сделать динамическим.
С уважением, GoodWin. |
|
| TiGeR |
| Отправлено: 29.07.2006, 19:42 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
[B]GoodWin[B], Эммм очень ... предположим если сделать Buffer переменную или определёную структуру к примеру массив с колличеством элиментов N то по скольку лучше брать элементов ??? есть ли способ как определить ? вообще есть такая тема если загрузить к примеру 5000 строк и начинать в них искать нужную строку тем временем запустить поток который будет считывать следущие 5000 строк ... но тут надо будет каждый раз ждать момента когда поток поиска закончит работу ??? как вы думаете что можно будет ещё сделать что бы ускорить работу ?????
|
|
| Doga |
| Отправлено: 31.07.2006, 14:53 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Создайте список буферов и два потока. Первый поток будет читать блоки из файла (пока не прочитает весь) и добавлять их в конец списка. Второй поток будет производить поиск в первом буфере списка, а после окончания поиска будет удалять этот буфер из списка, вновь начиная поиск в первом буфере. И так пока они не кочатся. Если первый поток не успевает, второй ждёт. И наоборот, если закончилась доступная память, ждёт первый поток пока второй не освободит требуемую для следующего блока память. Размер болков лучше расчитывать динамически в процессе работы.
|
|
| Shagg |
| Отправлено: 01.08.2006, 06:59 |
|
Дежурный стрелочник
Группа: Участник
Сообщений: 69
|
 а если читать блоками кратными размеру кластера? Тогда количество движений головки можно значительно уменьшить. |
|
| TiGeR |
| Отправлено: 03.08.2006, 15:15 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
ну тоесть тут ещё критично перед поиском лучше сделать дефрагментацию что бы поиск был быстрее .... и далее головка будет по порядку по всему диску идти читая по кластеру построчно и будет добавляь в буфер ... |
|
