Поиск в множестве имен

Хеш и (или) бинарное дерево поиска
 

Floyd

аксакал

Господа, подскажите как правильно реализовать следующую задачку:
Есть некий процесс обработки значительного (условно около одной тысячи) файлов в директории.
Весь процес обработки журналируется для возможности его продолжения с момента остановки, плановой или аварийной не важно.

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

При запуске утилита проверяет наличие журналов (для каждого потока) и строит по ним бинарное дерево поиска на основе хеша со значением флагов.

Далее происходит чтение из потока директории и поиск по хешу на предмет завершенных операций на основании чего строятся списки для последующей обработки.


Как вам такой подход?
 34.034.0
+
-
edit
 

Balancer

администратор
★★★★☆
Floyd> Есть некий процесс обработки значительного (условно около одной тысячи) файлов в директории.

1000 — это же копейки. Зачем деревья, когда можно обойтись простым линейным списком? Или я задачу не понял?

...

Вообще, если есть куча файлов с индивидуальной обработкой, я бы тупо завёл БД хоть в том же sqlite (благо не требуется высокая параллельность), просканировал каталоги, внёс файлы в таблицу БД с соответствующими флагами и потом работал бы по этой таблице. Типа, выбрать первый (последний, случайный) необработанный файл, обработать, если всё ок или не ок, внести соответствующую пометку в БД. Плюс периодическое сканирование каталогов на тему обнаружения файлов, которых нет в БД.
 39.0.2171.7139.0.2171.71

AXT

инженер вольнодумец

Floyd> В журнал перед началом операции заносится ...

Журнал инкрементальный или с перезаписью?
 13.0.782.22013.0.782.220
RU спокойный тип #04.12.2014 10:39  @Sandro#04.12.2014 02:58
+
-
edit
 

спокойный тип
Спокойный_Тип

старожил

и что значит "для каждого потока" - это многопоточная обработка и все потоки пишут в один лог файл журнала?
собственно это ключевой вопрос - однопоточная или многопоточная и предполагается ли процесс-диспетчер или же потоки должны только через лог файл взаимодействовать

p.s.
[показать]
If plan A didn't work , the alphabet has 25 more letters ! so stay cool  31.931.9
Это сообщение редактировалось 04.12.2014 в 11:03

Floyd

аксакал

AXT> Журнал инкрементальный или с перезаписью?

Инкрементальный. Текстовый или бинарный.
 
RU Floyd #04.12.2014 11:14  @спокойный тип#04.12.2014 10:39
+
-
edit
 

Floyd

аксакал

с.т.> и что значит "для каждого потока" - это многопоточная обработка и все потоки пишут в один лог файл журнала?
Для каждого потока свой.
с.т.> собственно это ключевой вопрос - однопоточная или многопоточная и предполагается ли процесс-диспетчер или же потоки должны только через лог файл взаимодействовать

Все проще. Процесс распараллеливается на этапе построения списков обработки, по кругу (массив указателей на списки), далее для каждого списка создается собственный поток. Поскольку реализация именно многопоточная, то массив указателей доступен для всех (единая память). Взаимодействие ограничивается лишь ожиданием завершения всех потоков.
 
Это сообщение редактировалось 04.12.2014 в 12:35
+
-
edit
 

Floyd

аксакал

Balancer> 1000 — это же копейки. Зачем деревья, когда можно обойтись простым линейным списком? Или я задачу не понял?
Balancer> ...

Можно конечно, но не интересно.
 
RU спокойный тип #04.12.2014 13:41  @Floyd#04.12.2014 11:14
+
+1
-
edit
 

спокойный тип
Спокойный_Тип

старожил

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

проще ( и тупее конечно, UNIX way в чистом виде) это когда дочерний поток берет из пула первую свободную задачу , отработал - или убивается или берет следующую , опять же и по таймауту его проще прибивать если слишком долго работает и только результат обработки одной задачи потеряется и пулом задач можно управлять и число активных потоков менять на лету по необходимости

хотя в общем "и туда тоже можно" :D

ps или у тебя эта утилита которая смотрит логи и списки обработки делает - будет регулярно запускаться и подправлять списки?
If plan A didn't work , the alphabet has 25 more letters ! so stay cool  31.931.9
Это сообщение редактировалось 04.12.2014 в 13:51
RU Floyd #04.12.2014 15:14  @спокойный тип#04.12.2014 13:41
+
-
edit
 

Floyd

аксакал

с.т.> проще ( и тупее конечно, UNIX way в чистом виде) это когда дочерний поток берет из пула первую свободную задачу ...

Это очередь в чистом виде.

Можно конечно же и так, но в данном случае самая ресурсоемкая часть каждого процесса будет банальное сжатие.

Во всяком случае есть свои плюсы и минусы. В случае с единой очередью, структурно это предполагался связный список, нужно будет сериализовывать доступ к ней, т.е. вводить блокировку к тому же выполнять операции удаления из списка. Проблем это не вызовет, но стоит ли так делать - не очевидно.

с.т.> ps или у тебя эта утилита которая смотрит логи и списки обработки делает - будет регулярно запускаться и подправлять списки?

Запускаться она будет либо по шедулеру, либо по внешнему триггеру (типа пора ...). Журналы же предполагается читать, при их наличии, лишь один раз. Т.е. из потока директории выбирается имя файла, по этому имени происходит поиск в таблице построенной на основе журналов. Был ли это файл обработан или нет и если нет на каком этапе прервались.

Хотя, можно вообще подойти с другой стороны. Как заметил AXT сделать журнал перезаписываемым и удалять из него запись после успешной обработки. С учетом того что процесс, вернее экземпляр, последовательный, то при неожиданной остановки в журнале сохранится файл и этап на котором прервалась обработка.


ЗЫ Саму задачу можно реализовать гораздо проще банальным скриптом на bash, но в данном случае присутствует фактор получения опыта работы с сложными структурами данных. Я как бы не программист, хоть и близок к теме :)
 39.0.2171.7139.0.2171.71
+
+1
-
edit
 

digger

опытный

Обрабатывать по одному проще.Я не уверен,что надо распараллеливать : будет одновременное чтение из запись многих файлов из одного диска,которое будет его насиловать и замедлит процесс.Распараллеливание имеет смысл только если обработка в памяти медленная и хочется использовать многопроцессорность,либо обработка связана с получением информации из медленного внешнего источника.Журнал - надо закрывать файл после каждой записи или использовать соотвествующий флаг файловой операции.Проще всего для журналирования держать отдельный файлик на каждый обрабатываемый файл и стирать его,если обработка завершена, file.bin and file.bin.journal.
 33.033.0

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru