ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Интересный вопрос на оптимальный алгоритм
25 сообщений из 34, страница 1 из 2
  1  все
Интересный вопрос на оптимальный алгоритм
    #38612587
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:40
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612674
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Почитай про rsync
...
Рейтинг: 0 / 0
11.04.2014, 17:25
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612684
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Подозреваю что это копия какой-то базы. Если так - изучай встроенные средства резервного копирования и репликации СУБД от которой эта база. Не так - тоже самое, только от любой СУБД, например MSSQL.
...
Рейтинг: 0 / 0
11.04.2014, 17:34
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612687
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Dima TПодозреваю что это копия какой-то базы. Если так - изучай встроенные средства резервного копирования и репликации СУБД от которой эта база. Не так - тоже самое, только от любой СУБД, например MSSQL.

нет, не база. произвольный файл.

rsync алгоритм предлагает побайтно смещаться, про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб)
...
Рейтинг: 0 / 0
11.04.2014, 17:39
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612701
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Studentsнеоптимально (особенно для фильма MKV на 20Гб)
StudentsЕсли, например, изменится 5-10% файла
покажите мне тот фильм в котором что-то изменится. Оптимизацию сферических коней в вакууме обсуждают тут
...
Рейтинг: 0 / 0
11.04.2014, 17:45
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612706
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Dima TStudentsнеоптимально (особенно для фильма MKV на 20Гб)
StudentsЕсли, например, изменится 5-10% файла
покажите мне тот фильм в котором что-то изменится. Оптимизацию сферических коней в вакууме обсуждают тут

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


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

т.е. опять побайтное смещение. теперь представьте, что файл - трёхчасовой фильм MKV 1080 на 30Гб, сколько времени и ресурсов нужно, чтобы побайтно пройтись по такому файлу и для каждого смещения подсчитать хэш и ссравнить с хэшем на сервере ?

БЕЗУМИЕ
...
Рейтинг: 0 / 0
11.04.2014, 17:48
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612718
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Students rsync алгоритм предлагает побайтно смещаться , про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб)
Где это написано?
...
Рейтинг: 0 / 0
11.04.2014, 17:51
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612719
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Про diff почитай.

Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь?
...
Рейтинг: 0 / 0
11.04.2014, 17:52
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612722
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Studentsочень просто, добавится несколько звуковых дорожек в файл.
соответственно, блоки с видео, уже лежащие на серваке я не буду заливать второй раз (а это 90% от файла), залью только звуковые дорожкиТолько изменившиеся 10% будут равномерно замешаны по всему объему файла.
Так что будет выгоднее тупо залить файл заново.
...
Рейтинг: 0 / 0
11.04.2014, 17:52
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612725
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
miksoftТолько изменившиеся 10% будут равномерно замешаны по всему объему файла.
Так что будет выгоднее тупо залить файл заново.

Согласен! Или изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существует
...
Рейтинг: 0 / 0
11.04.2014, 17:54
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612728
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Dima TПро diff почитай.

Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь?

Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу
...
Рейтинг: 0 / 0
11.04.2014, 17:55
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612730
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
maytonStudents rsync алгоритм предлагает побайтно смещаться , про что я и написал, т.е. неоптимально (особенно для фильма MKV на 20Гб)
Где это написано?

здесь http://citforum.ru/nets/articles/rsync/
...
Рейтинг: 0 / 0
11.04.2014, 17:56
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612734
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
StudentsИли изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существуетА вот если изменился 1% в самом начале, то как раз rsync должен помочь.
...
Рейтинг: 0 / 0
11.04.2014, 17:56
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612736
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
StudentsDima TПро diff почитай.

Не совсем понятно в чем конкретно твои ограничения? что именно оптимизировать хочешь?

Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу
Гугл с яндексом забанили? https://www.google.ru/search?q=diff алгоритм
...
Рейтинг: 0 / 0
11.04.2014, 17:59
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612737
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
miksoftStudentsИли изменился 1% в самом начале. Я же заранее не знаю, нужен общий алгоритм, если существуетА вот если изменился 1% в самом начале, то как раз rsync должен помочь.

Согласен, но я же заранее не знаю, изменилось где и сколько.

И может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэши
...
Рейтинг: 0 / 0
11.04.2014, 18:00
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612738
Students
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Students
Участник
Dima TStudentsпропущено...


Да, спасибо. Только нужна не программа, а сам алгоритм, чтобы можно было внести в свою программу
Гугл с яндексом забанили? https://www.google.ru/search?q=diff алгоритм

ок, спасибо. сейчас почитаю
...
Рейтинг: 0 / 0
11.04.2014, 18:00
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612750
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
StudentsИ может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэши
Прошагать 30Гб по двум одинаковым файлам - это фигня (скорость чтения файла), а вот найти в них одинаковые места это сложно. Есть самодельный алгоритм подобного, использую для обновлений, работает минуты на 25-30 метровых файлах. На 20-30 Гб думаю быстрее паста на процессоре высохнет и проц сгорит
...
Рейтинг: 0 / 0
11.04.2014, 18:09
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612754
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Studentsmiksoftпропущено...
А вот если изменился 1% в самом начале, то как раз rsync должен помочь.

Согласен, но я же заранее не знаю, изменилось где и сколько.

И может получится так, что мы побайтно прошагаем 30Гб зря, каждый раз делая остановку и сравнивая хэшиТогда доверьте это дело rsync-у, он и проверит, и разницу перепишет, и весь файл, если есть необходимость.
...
Рейтинг: 0 / 0
11.04.2014, 18:13
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612756
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Studentsmaytonпропущено...

Где это написано?

здесь http://citforum.ru/nets/articles/rsync/
Есть только 1 способ сравнить изменения в двух файлах. Это полностью побайтно
их сравнить. Но rsync уменьшает объём трафика проходящего через сеть расчитывая
контрольные суммы блоков файла и синхронизируя блоки.

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

Здесь уж только rsync.
...
Рейтинг: 0 / 0
11.04.2014, 18:16
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612758
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
StudentsТолько нужна не программа, а сам алгоритм
Затести сначала готовый софт, поймешь насколько тебе алгоритм подойдет.
...
Рейтинг: 0 / 0
11.04.2014, 18:18
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612776
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
StudentsПривет всем.

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

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

ВОПРОС: есть ли более оптимальный алгоритм для моей задачи, чем ходить побайтно? Если, например, изменится 5-10% файла, то алгоритм выглядит неплохо (т.к. 90-95% уже хранится на сервере и не нужно заливать их), но если изменится 80%-90%, то быстрее будет не искать побайтно одинаковые блоки, а залить все блоки на сервер заново.Уже правильно сказали про rsync . Там 32-битная контрольная сумма Тридгела. В общем случае годится не обязательно Тридгел, но и любая контрольная сумма, которая одновременно и инкрементальна "вправо" и декрементальна "слева". Просто Тридгел --- самая простая из таких сумм, а её недостатки для вашего случая роли не играют.
...
Рейтинг: 0 / 0
11.04.2014, 18:43
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612780
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
iv_an_ruконтрольная сумма ТридгелаЧто-то не нагугливается ничего. Есть ссылочка или другое название?
...
Рейтинг: 0 / 0
11.04.2014, 18:46
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612783
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
miksoftiv_an_ruконтрольная сумма ТридгелаЧто-то не нагугливается ничего. Есть ссылочка или другое название?Ну вот, только написал и сразу нашел.
Это Триджелл.
...
Рейтинг: 0 / 0
11.04.2014, 18:47
| Ответить | Цитировать | Написать  
Интересный вопрос на оптимальный алгоритм
    #38612834
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
miksoft,

http://rsync.samba.org/tech_report/node3.html
...
Рейтинг: 0 / 0
11.04.2014, 20:17
| Ответить | Цитировать | Написать  
25 сообщений из 34, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Интересный вопрос на оптимальный алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&tid=1341400]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 152ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 223ms
total:  463ms
созд. / загр.: 463ms
x
x
Закрыть


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