ReSQL.ru
     
powered by simpleCommunicator - 2.0.56     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Интересный вопрос на оптимальный алгоритм
25 сообщений из 30, страница 1 из 2
  1  все
Интересный вопрос на оптимальный алгоритм
    #38612556
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Привет всем.

Есть большой файл, например, 20Гб (я хочу залить его на сервак).
Я бью этот файл на 10 равных блоков, соответственно, по 2Гб (10ый может получиться чуть меньше) и заливаю каждый блок по отдельности, храня только блоки.

Далее я меняю файл, скажем, почти в самом начале и изменил во втором блоке 2 Гб на другие 3 Гб.
Тогда, чтобы не заливать 3-10 блоки заново, я могу побайтно пройтись (каждый раз сравнивая хэш очередных 2Гб и 2Гб на сервере) и найти начало 3 неизменного блока.

ВОПРОС: есть ли более оптимальный алгоритм для моей задачи, чем ходить побайтно? Если, например, изменится 5-10% файла, то алгоритм выглядит неплохо (т.к. 90-95% уже хранится на сервере и не нужно заливать их), но если изменится 80%-90%, то быстрее будет не искать побайтно одинаковые блоки, а залить все блоки на сервер заново.
...
Рейтинг: 0 / 0
11.04.2014, 16:19
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612588
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arm79
Участник
Students,

Да. Блоки по 2 МБ. + Md5 хэш каждого блока.
...
Рейтинг: 0 / 0
11.04.2014, 16:40
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612600
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Arm79Students,

Да. Блоки по 2 МБ. + Md5 хэш каждого блока.

грубо говоря так и есть (я просто для вопроса упростил).

проблема в том, что если в файле на 20Гб изменилось АБСОЛЮТНО ВСЁ , т.е. файл стал другим (название только сохранилось), то мы будем 20Гб ходить побайтно и искать Md5 хэш каждого блока , т.е. алгоритм становится совсем неоптимальным .


с другой стороны, если к файлу добавился с самого начала только 1 байт, то этот алгоритм будет очень хорош . мы зальем только этот 1 байт, а остальные все блоки по 2 МБ уже на сервере есть
...
Рейтинг: 0 / 0
11.04.2014, 16:45
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612602
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
может какой-то другой алгоритм есть, кроме "побайтного перебора"?
...
Рейтинг: 0 / 0
11.04.2014, 16:46
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612610
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arm79
Участник
Конечно есть. Если стоит задача поменять все блоки, то проще создать новый файл, а старый грохнуть.
...
Рейтинг: 0 / 0
11.04.2014, 16:52
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612614
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Shocker.Pro
Участник
Arm79Конечно есть. Если стоит задача поменять все блоки, то проще создать новый файл, а старый грохнуть.человек о другом спрашивает. КАК УЗНАТЬ, что нужно поменять все блоки?

А как именно вносятся изменения в исходный файл?
...
Рейтинг: 0 / 0
11.04.2014, 16:55
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612617
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Arm79проще создать новый файл, а старый грохнуть.

не проще. если файл 20 Гб и если к файлу добавился с самого начала только 1 байт, то этот алгоритм будет очень хорош. мы зальем только этот 1 байт, а остальные все блоки по 2 МБ уже на сервере есть.

проще только если вообще 100% поменялось у файла, но мы же заранее не знаем, так? поэтому я и спрашиваю, есть ли более быстрые алгоритмы. вполне возможно, что есть и тут кто-то знает
...
Рейтинг: 0 / 0
11.04.2014, 16:57
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612623
bazile
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
bazile
Участник
Students, почитай про алгоритм утитилиты rsync . Там
...
Рейтинг: 0 / 0
11.04.2014, 17:01
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612624
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
например, алгоритм сортировки Хоара значительно быстрее, чем пузырьком. Возможно, для моей задачи, тоже есть другой алгоритм, а не обычный побайтный перебор.
...
Рейтинг: 0 / 0
11.04.2014, 17:02
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612625
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
bazileStudents, почитай про алгоритм утитилиты rsync . Там

Спасибо! Сейчас посмотрю
...
Рейтинг: 0 / 0
11.04.2014, 17:02
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612627
Фотография buser
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
buser
Участник
Students, что для вас критерий оптимальности и чем в угоду этому вы готовы жертвовать?
Экономите сетевой трафик? - ищите по словам deduplication algorithm
Хотите распараллелить закачку? - ищите по словам sparse file
ну и т.п. и т.д.
P.S.: ну и вообще это не такая уж и тривиальная задача... а казалось бы...
...
Рейтинг: 0 / 0
11.04.2014, 17:02
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612631
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
buserP.S.: ну и вообще это не такая уж и тривиальная задача... а казалось бы...

так и я о том же, просто если алгоритмы сортировки массива нагуглить можно очень быстро, то алгоритмы для моей задачи нагуглить не так просто.
...
Рейтинг: 0 / 0
11.04.2014, 17:04
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612632
bazile
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
bazile
Участник
bazile, случайно отправил предыдущее сообщение не закончив его.

Если речь идет о файле который меняет другой процесс, то нам в любом случае придется пробежаться по всему файлу в поисках изменений. Соответственно вопрос в выборе оптимального алгоритма поиска блоков и определения что именно нужно передавать. Алгоритм rsync в этом плане оптимален.
...
Рейтинг: 0 / 0
11.04.2014, 17:04
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612636
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
bazilebazile, случайно отправил предыдущее сообщение не закончив его.

Если речь идет о файле который меняет другой процесс, то нам в любом случае придется пробежаться по всему файлу в поисках изменений. Соответственно вопрос в выборе оптимального алгоритма поиска блоков и определения что именно нужно передавать. Алгоритм rsync в этом плане оптимален.

Хорошо, спасибо. Вот ссылка на русском языке, может кому понадобится.
http://citforum.ru/nets/articles/rsync/
...
Рейтинг: 0 / 0
11.04.2014, 17:09
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612654
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arm79
Участник
Studentsпроще только если вообще 100% поменялось у файла, но мы же заранее не знаем, так? поэтому я и спрашиваю, есть ли более быстрые алгоритмы. вполне возможно, что есть и тут кто-то знает

rsync и есть разбиение поблочно и обмен хешами.

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

Варианты оптимизации есть, если файлы текстовые или тем или иным способом структурированные (например, вставка одного символа в середину). Но ваш случай кажется не такой.
...
Рейтинг: 0 / 0
11.04.2014, 17:20
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612664
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
buserStudents, что для вас критерий оптимальности и чем в угоду этому вы готовы жертвовать?
Экономите сетевой трафик? - ищите по словам deduplication algorithm
Хотите распараллелить закачку? - ищите по словам sparse file
ну и т.п. и т.д.

Хочу не заливать абсолютно одинаковые 2Мб блоки на сервер каждый раз. Если пользователь жмет "сохранить на сервер" уже сохраненный фильм, никакого смысла перезаписывать одинаковые блоки нет. И экономим время, и экономим сетевой трафик пользователя.
...
Рейтинг: 0 / 0
11.04.2014, 17:22
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612700
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
отсюда http://citforum.ru/nets/articles/rsync/ :


Код: plaintext
Если совпадения найдено не было для текущего смещения в файле A , вычисляется быстрая сигнатура для следующего байтового смещения и процедура поиска повторяется. При совпадении, смещение увеличивается на размер совпавшего блока и поиск продолжается.

т.е. опять побайтное смещение . теперь представьте, что файл - трёхчасовой фильм MKV 1080 на 30Гб , сколько времени и ресурсов нужно, чтобы побайтно пройтись по такому файлу и для каждого смещения подсчитать хэш и ссравнить с хэшем на сервере ?
...
Рейтинг: 0 / 0
11.04.2014, 17:44
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612723
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Arm79rsync и есть разбиение поблочно и обмен хешами.

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

Варианты оптимизации есть, если файлы текстовые или тем или иным способом структурированные (например, вставка одного символа в середину).

1)алгоритм rsync не подходит, т.к. побайтно смещаться, каждый раз считая хэш и сравнивая эти 2 Мбайтные блоки с серверными для 30 Гб для MKV фильма БЕЗУМИЕ

2)да, это просто. а вот если мы спереди к файлу приклеили 1 байт, то тогда будет смещение на 1 байт и все хэши будут другими, в этом случае побайтный проход по 1 байту будет очень кстати

3)файлы произвольные
...
Рейтинг: 0 / 0
11.04.2014, 17:52
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612797
bazile
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
bazile
Участник
Students, ты сначала реализуй алгоритм посчета "быстрой сигнатары" и только после этого делай выводы насколько это эффективно. Для сравнения двух произвольных файлов в любом случае требуется пробежать по обоим файлам от начала до конца.
...
Рейтинг: 0 / 0
11.04.2014, 19:01
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612819
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arm79
Участник
Students2)да, это просто. а вот если мы спереди к файлу приклеили 1 байт, то тогда будет смещение на 1 байт и все хэши будут другими, в этом случае побайтный проход по 1 байту будет очень кстати
так доработай. блоки по N байт, но пиши в них M байт, причем M < N. Тогда будет некоторый запас по байтам...

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

Два подхода можно совместить.
...
Рейтинг: 0 / 0
11.04.2014, 19:52
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612820
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arm79
Участник
а скорость - MemoryMappedFiles тебе в помощь
...
Рейтинг: 0 / 0
11.04.2014, 19:53
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612883
Фотография Нахлобуч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахлобуч
Участник
rsync тут по делу предлагают.

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

Из альтернатив можешь посмотреть на zsync .
...
Рейтинг: 0 / 0
11.04.2014, 21:33
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612938
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
StudentsArm79rsync и есть разбиение поблочно и обмен хешами.

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

Варианты оптимизации есть, если файлы текстовые или тем или иным способом структурированные (например, вставка одного символа в середину).

1)алгоритм rsync не подходит, т.к. побайтно смещаться, каждый раз считая хэш и сравнивая эти 2 Мбайтные блоки с серверными для 30 Гб для MKV фильма БЕЗУМИЕ

2)да, это просто. а вот если мы спереди к файлу приклеили 1 байт, то тогда будет смещение на 1 байт и все хэши будут другими, в этом случае побайтный проход по 1 байту будет очень кстати

3)файлы произвольные
А тут у меня такой наивный вопрос, а как ты узнаешь что у тебя файл вырос на один байт, и как ты узнаешь, что он вырос в начале а не в середине скажем.

IMO Автор, начни всё с начала. Бредовая идея не заслуживает обсуждения.
...
Рейтинг: 0 / 0
11.04.2014, 23:23
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38614106
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
алгоритм есть здесь
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem


Кто-нибудь знает, как он по-русски называется?
...
Рейтинг: 0 / 0
14.04.2014, 12:44
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38614111
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
в этом алгоритме идёт поиск наибольшей общей подпоследовательности и работает быстрее, чем перебор байт-за-байтом.
...
Рейтинг: 0 / 0
14.04.2014, 12:47
| Ответить | Цитировать | Написать  
25 сообщений из 30, страница 1 из 2
  1  все
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Интересный вопрос на оптимальный алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=20&msg=38612624&tid=1403041]:
 0ms
get settings:
 9ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 86ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 1ms
others: 352ms
total:  526ms
созд. / загр.: 526ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]