задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 12:38
Оценка:
приветы.

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

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

пасиба.
Re: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 12:49
Оценка:
Здравствуйте, sinmaster, Вы писали:

S>понятно, что пачками грузить быстрее, но в таком случае потребуются повторные закачки в случае обнаружения кривых файлов.

S>первое что приходит на ум -- заюзать метод половинного сечения. есть ли др. решения?

Посчитать вероятность встретить в пачке размера N битый файл и прикинуть количество действий в случае если он там есть. Общее время это что-то типа:

Сумма_по_всем_пачкам ( P(в_пачке_есть_битый_файл) * время_работы_с_такой_пачкой + P(в_пачке_нет_битых файлов) * время_работы_с_такой_пачкой )


Минимизировать по параметру "размер пачки".
Делай что должно, и будь что будет
Re: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 12:58
Оценка:
Здравствуйте, sinmaster, Вы писали:

S>первое что приходит на ум -- заюзать метод половинного сечения. есть ли др. решения?


Если у нас, допустим, 1000 файлов и 10 битых, и они распределены равномерно (важное условие! если не так, то, вероятно, теория вероятностей идёт лесом или как минимум все вероятностные рассуждения усложняются), то вероятность того, что в половине не окажется ни одного -- 1/1024. То есть, я бы сказал, можно даже и не пытаться.

Ещё можно прикинуть среднее время обнаружения битого файла. Т.е. обнаружим мы его, когда передадутся 499 файлов и всё придётся отменять, или скорее всё-таки раньше. Но это мне сходу не посчитать, тут надо подумать.
Делай что должно, и будь что будет
Re[2]: задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 13:00
Оценка:
SH>Минимизировать по параметру "размер пачки".
спасибо! не соображу как минимизировать эту ф-цию. допустим, имеем сл. данные:

P(в_пачке_есть_битый_файл) = 0.03
P(в_пачке_нет_битых_файлов) = 0.97
время_работы_с_битой_пачкой = 10 мин (ессно, зависит от нашего алгоритма обработки такой пачки, а потому, может разниться очень сильно)
время_работы_с_пачкой_без_битых_файлов = 2 мин

как осуществить минимизирование? спасибо, можно просто ткнуть носом.
Re[2]: задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 13:02
Оценка:
Здравствуйте, SergH, Вы писали:

SH>Если у нас, допустим, 1000 файлов и 10 битых, и они распределены равномерно (важное условие! если не так, то, вероятно, теория вероятностей идёт лесом или как минимум все вероятностные рассуждения усложняются)


в моем случае как раз таки битые файлы распределены неравномерно. т.е. скажем из этой 1000 файлов, битые файлы идут друг за другом, скажем, 679-ый, 680-ый,..., 689-ый.
Re[3]: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 13:10
Оценка:
Здравствуйте, sinmaster, Вы писали:

SH>>Минимизировать по параметру "размер пачки".

S>спасибо! не соображу как минимизировать эту ф-цию. допустим, имеем сл. данные:
S>P(в_пачке_есть_битый_файл) = 0.03
S>P(в_пачке_нет_битых_файлов) = 0.97

Ммм.. Смотри. Эти параметры не задаются так, они все зависят от размера. От размера пачки зависит:

— количество пачек, т.е. сколько у нас элементов в сумме
— вероятность, что все файлы целые. Считается так: P(один_файл_целый)^N. Т.е. если битых файлов 1%, вероятность того, что конкретный файл нормальный -- 0.99, вероятность того, что 10 файлов нормальные -- 0.99^10 = 0.90, вероятность того, что, 30 файлов нормальные -- 0.99^30 = 0,73 и т.п.
— соответственно же и вероятность того, что хотя бы один файл битый.
— среднее время обнаружения сбоя (это думать надо)
— время обработки битой пачки (чем больше пачка, тем дольше ты будешь искать в ней тот единственный, а может и не единственный, битый файл)

Вот примерно так.
Делай что должно, и будь что будет
Re[3]: задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 13:11
Оценка:
и еще -- предположим что мы пишем широко используемую тулзу, и в таком случае нам ничего не известно о каждом характере распределения битых файлов, т.е. закладываться на это мы не можем. какого workaround-а в таком случае нам придерживаться? значит ли это что нам придется решить задачу в общем виде?

спасибо за размышления.
Re[3]: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 13:12
Оценка:
Здравствуйте, sinmaster, Вы писали:

S>в моем случае как раз таки битые файлы распределены неравномерно. т.е. скажем из этой 1000 файлов, битые файлы идут друг за другом, скажем, 679-ый, 680-ый,..., 689-ый.


Ага. Ну так это совсем другое дело. Да, тогда сечение пополам будет отлично работать.
Делай что должно, и будь что будет
Re[4]: задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 13:17
Оценка:
Здравствуйте, SergH, Вы писали:

SH>Ага. Ну так это совсем другое дело. Да, тогда сечение пополам будет отлично работать.


например, пускай имеем 8 файлов. из них битые все 8. в случае поштучно загружаемых файлов имеем 8 загрузок.
в случае метода сечения имеем 15 попыток загрузки. или некорректно такие частности сравнивать?
Re[4]: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 13:20
Оценка:
Здравствуйте, sinmaster, Вы писали:

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


S>спасибо за размышления.


Ну тут не надо решать задачу на самом деле Обычно нужно чтобы не было слишком медленно на типичных наборах данных. Так что на пальцах можно прикинуть, что слишком маленькие пачки это медленно, слишком большие -- часто придётся повторять и передавать их частями. Т.е. нужно что-то среднее. Дальше можно либо что-то прикидывать математически, либо написать симулятор, и поставить несколько опытов с разными размерами.
Делай что должно, и будь что будет
Re[5]: задача о закачке файлов
От: SergH Россия  
Дата: 30.06.10 13:24
Оценка:
Здравствуйте, sinmaster, Вы писали:

S>например, пускай имеем 8 файлов. из них битые все 8. в случае поштучно загружаемых файлов имеем 8 загрузок.

S>в случае метода сечения имеем 15 попыток загрузки. или некорректно такие частности сравнивать?

Тут не выполняется условие, что битых мало.

Или имеется ввиду, что это половинным делением мы пришли к такой ситуации, что осталось восемь битых файлов?

Когда размер области становится достаточно маленьким, видимо, нужно переходить на пофайловую загрузку (или там группами по два -- как-то так).
Делай что должно, и будь что будет
Re[6]: задача о закачке файлов
От: sinmaster  
Дата: 30.06.10 17:07
Оценка:
занятный момент -- в случае когда storage выбрасывает исключение из-за битого файла в storage уже были загружены все предыдущие файлы из этой пачки. при последующих попытках перезалива этой пачки дробя ее методом половинного деления получается что некоторые файлы будут перезаливаться заново. это конечно нехорошо, но что делать.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.