Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
11.04.2014, 16:40
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Привет всем. Есть большой файл, например, 20Гб (я хочу залить его на сервак). Я бью этот файл на 10 равных блоков, соответственно, по 2Гб (10ый может получиться чуть меньше) и заливаю каждый блок по отдельности, храня только блоки. Далее я меняю файл, скажем, почти в самом начале и изменил во втором блоке 2 Гб на другие 3 Гб. Тогда, чтобы не заливать 3-10 блоки заново, я могу побайтно пройтись (каждый раз сравнивая хэш очередных 2Гб и 2Гб на сервере) и найти начало 3 неизменного блока. ВОПРОС: есть ли более оптимальный алгоритм для моей задачи, чем ходить побайтно? Если, например, изменится 5-10% файла, то алгоритм выглядит неплохо (т.к. 90-95% уже хранится на сервере и не нужно заливать их), но если изменится 80%-90%, то быстрее будет не искать побайтно одинаковые блоки, а залить все блоки на сервер заново. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:25
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Почитай про rsync ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:34
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Подозреваю что это копия какой-то базы. Если так - изучай встроенные средства резервного копирования и репликации СУБД от которой эта база. Не так - тоже самое, только от любой СУБД, например MSSQL. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:39
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Dima TПодозреваю что это копия какой-то базы. Если так - изучай встроенные средства резервного копирования и репликации СУБД от которой эта база. Не так - тоже самое, только от любой СУБД, например MSSQL. нет, не база. произвольный файл. rsync алгоритм предлагает побайтно смещаться, про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:45
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Studentsнеоптимально (особенно для фильма MKV на 20Гб) StudentsЕсли, например, изменится 5-10% файла покажите мне тот фильм в котором что-то изменится. Оптимизацию сферических коней в вакууме обсуждают тут ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:47
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Dima TStudentsнеоптимально (особенно для фильма MKV на 20Гб) StudentsЕсли, например, изменится 5-10% файла покажите мне тот фильм в котором что-то изменится. Оптимизацию сферических коней в вакууме обсуждают тут очень просто, добавится несколько звуковых дорожек в файл. соответственно, блоки с видео, уже лежащие на серваке я не буду заливать второй раз (а это 90% от файла), залью только звуковые дорожки ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:48
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
отсюда http://citforum.ru/nets/articles/rsync/ : Код: plaintext т.е. опять побайтное смещение. теперь представьте, что файл - трёхчасовой фильм MKV 1080 на 30Гб, сколько времени и ресурсов нужно, чтобы побайтно пройтись по такому файлу и для каждого смещения подсчитать хэш и ссравнить с хэшем на сервере ? БЕЗУМИЕ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:51
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Students rsync алгоритм предлагает побайтно смещаться , про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб) Где это написано? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:52
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Про diff почитай. Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:52
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Studentsочень просто, добавится несколько звуковых дорожек в файл. соответственно, блоки с видео, уже лежащие на серваке я не буду заливать второй раз (а это 90% от файла), залью только звуковые дорожкиТолько изменившиеся 10% будут равномерно замешаны по всему объему файла. Так что будет выгоднее тупо залить файл заново. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:54
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
miksoftТолько изменившиеся 10% будут равномерно замешаны по всему объему файла. Так что будет выгоднее тупо залить файл заново. Согласен! Или изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существует ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:55
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Dima TПро diff почитай. Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь? Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:56
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
maytonStudents rsync алгоритм предлагает побайтно смещаться , про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб) Где это написано? здесь http://citforum.ru/nets/articles/rsync/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:56
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
StudentsИли изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существуетА вот если изменился 1% в самом начале, то как раз rsync должен помочь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 17:59
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
StudentsDima TПро diff почитай. Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь? Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу Гугл с яндексом забанили? https://www.google.ru/search?q=diff алгоритм ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:00
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
miksoftStudentsИли изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существуетА вот если изменился 1% в самом начале, то как раз rsync должен помочь. Согласен, но я же заранее не знаю, изменилось где и сколько. И может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэши ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:00
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Dima TStudentsпропущено... Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу Гугл с яндексом забанили? https://www.google.ru/search?q=diff алгоритм ок, спасибо. сейчас почитаю ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:09
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
StudentsИ может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэши Прошагать 30Гб по двум одинаковым файлам - это фигня (скорость чтения файла), а вот найти в них одинаковые места это сложно. Есть самодельный алгоритм подобного, использую для обновлений, работает минуты на 25-30 метровых файлах. На 20-30 Гб думаю быстрее паста на процессоре высохнет и проц сгорит ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:13
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Studentsmiksoftпропущено... А вот если изменился 1% в самом начале, то как раз rsync должен помочь. Согласен, но я же заранее не знаю, изменилось где и сколько. И может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэшиТогда доверьте это дело rsync-у, он и проверит, и разницу перепишет, и весь файл, если есть необходимость. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:16
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
Studentsmaytonпропущено... Где это написано? здесь http://citforum.ru/nets/articles/rsync/ Есть только 1 способ сравнить изменения в двух файлах. Это полностью побайтно их сравнить. Но rsync уменьшает объём трафика проходящего через сеть расчитывая контрольные суммы блоков файла и синхронизируя блоки. Наверное есть и другие оптимальные подходы к сравнению основанные на журналировании изменений в файловой системе. Но я-бы не стал доверять этому механизму если точка отсчёта когда журнал был включен нам неизвеста и оба файла на разных неподконтрольных серверах и с разными файловыми системами. Здесь уж только rsync. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:18
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
StudentsТолько нужна не программа, а сам алгоритм Затести сначала готовый софт, поймешь насколько тебе алгоритм подойдет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:43
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
StudentsПривет всем. Есть большой файл, например, 20Гб (я хочу залить его на сервак). Я бью этот файл на 10 равных блоков, соответственно, по 2Гб (10ый может получиться чуть меньше) и заливаю каждый блок по отдельности, храня только блоки. Далее я меняю файл, скажем, почти в самом начале и изменил во втором блоке 2 Гб на другие 3 Гб. Тогда, чтобы не заливать 3-10 блоки заново, я могу побайтно пройтись (каждый раз сравнивая хэш очередных 2Гб и 2Гб на сервере) и найти начало 3 неизменного блока. ВОПРОС: есть ли более оптимальный алгоритм для моей задачи, чем ходить побайтно? Если, например, изменится 5-10% файла, то алгоритм выглядит неплохо (т.к. 90-95% уже хранится на сервере и не нужно заливать их), но если изменится 80%-90%, то быстрее будет не искать побайтно одинаковые блоки, а залить все блоки на сервер заново.Уже правильно сказали про rsync . Там 32-битная контрольная сумма Тридгела. В общем случае годится не обязательно Тридгел, но и любая контрольная сумма, которая одновременно и инкрементальна "вправо" и декрементальна "слева". Просто Тридгел --- самая простая из таких сумм, а её недостатки для вашего случая роли не играют. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:46
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
iv_an_ruконтрольная сумма ТридгелаЧто-то не нагугливается ничего. Есть ссылочка или другое название? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.04.2014, 18:47
|
|||
|---|---|---|---|
Интересный вопрос на оптимальный алгоритм |
|||
|
#18+
miksoftiv_an_ruконтрольная сумма ТридгелаЧто-то не нагугливается ничего. Есть ссылочка или другое название?Ну вот, только написал и сразу нашел. Это Триджелл. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&mobile=1&tid=1341400]: |
0ms |
get settings: |
9ms |
get forum list: |
20ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
50ms |
get topic data: |
14ms |
get forum data: |
3ms |
get page messages: |
80ms |
get tp. blocked users: |
2ms |
| others: | 275ms |
| total: | 459ms |
| 0 / 0 |
