Bitcoin Forum
November 22, 2017, 05:26:42 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Утилита сравнения больших файлов  (Read 1771 times)
ArsenShnurkov
Legendary
*
Offline Offline

Activity: 1386



View Profile
January 17, 2013, 10:12:21 PM
 #1

Есть разные крупные корпорации (телекоммуникационные, например), которые создают огромные log-файлы (по 14GB и более)
Иногда надо проводить сравнение таких файлов, в случае если там различаются всего несколько строк (какой-то студент руками исправил, надо найти что именно)
Обычная утилита diff не справляется, так как стандартному быстрому алгоритму требуется квадратичная память.

Идея:

1) пишем реализацию алгоритма с линейной памятью
вот тут даже код есть:
In 1975, Hirschberg developed an elegant divide-and-conquer (D&C) algorithm (HLCS) for LCS retrieval in O(m+n) or linear space and in O(mn), two-pass quadratic time.
http://en.wikipedia.org/wiki/Hirschberg%27s_algorithm
http://k2code.blogspot.ru/2010/08/hirschbergs-linear-space-algorithm-in-c.html

квадратичное время можно распараллелить на многопроцессорной машине.
кроме того, т.к. операции - простые сравнения, то можно загрузить видеокарты (там больше ALU)
https://www.google.ru/search?q=Hirschberg+GPU

2) делаем сайт, прописываем в википедию и везде-везде

3) продаем корпоративным клиентам

4) ...

5) профит

при чем тут биткоин?

можно, сделать интернет сервис, принимающий рубли,
конвертирующий их в биткоины и арендующий мощности у майнеров
1511371602
Hero Member
*
Offline Offline

Posts: 1511371602

View Profile Personal Message (Offline)

Ignore
1511371602
Reply with quote  #2

1511371602
Report to moderator
1511371602
Hero Member
*
Offline Offline

Posts: 1511371602

View Profile Personal Message (Offline)

Ignore
1511371602
Reply with quote  #2

1511371602
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511371602
Hero Member
*
Offline Offline

Posts: 1511371602

View Profile Personal Message (Offline)

Ignore
1511371602
Reply with quote  #2

1511371602
Report to moderator
1511371602
Hero Member
*
Offline Offline

Posts: 1511371602

View Profile Personal Message (Offline)

Ignore
1511371602
Reply with quote  #2

1511371602
Report to moderator
Robinovich
Hero Member
*****
Offline Offline

Activity: 679

Semux


View Profile
January 17, 2013, 10:33:50 PM
 #2

Есть разные крупные корпорации (телекоммуникационные, например), которые создают огромные log-файлы (по 14GB и более)
Иногда надо проводить сравнение таких файлов, в случае если там различаются всего несколько строк (какой-то студент руками исправил, надо найти что именно)
Обычная утилита diff не справляется, так как стандартному быстрому алгоритму требуется квадратичная память.

Идея:

1) пишем реализацию алгоритма с линейной памятью
вот тут даже код есть:
In 1975, Hirschberg developed an elegant divide-and-conquer (D&C) algorithm (HLCS) for LCS retrieval in O(m+n) or linear space and in O(mn), two-pass quadratic time.
http://en.wikipedia.org/wiki/Hirschberg%27s_algorithm
http://k2code.blogspot.ru/2010/08/hirschbergs-linear-space-algorithm-in-c.html

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

2) делаем сайт, прописываем в википедию и везде-везде

3) продаем корпоративным клиентам

4) ...

5) профит

одно не понятно: при чем тут биткоин?

Эту идею можно спроецировать на любую легко распаралеливаемую задачу.
Торгововой площадкой для покупки\продажи мощностей запросто станет биржа, на подобии биржи фриланса.

Но есть определенные вопросы,
доверие, (кто доверит свои лог файлы либо прочую информацию, которая наверняка является конфеденциальной неизвестно кому?)
спрос, (будет ли это выгодно обеем сторонам? в стоимость улуги будет включаться и написание алгоритма определенного вида расчетов и работа, назовем их по привычке "майнеров" )

А так идея не нова.

ArsenShnurkov
Legendary
*
Offline Offline

Activity: 1386



View Profile
January 17, 2013, 10:42:01 PM
 #3

А так идея не нова.

И как у неё с реализациями? Что-то я не вижу много альтернативных майнеров для такого вида задач...
Robinovich
Hero Member
*****
Offline Offline

Activity: 679

Semux


View Profile
January 17, 2013, 11:14:06 PM
 #4

А так идея не нова.

И как у неё с реализациями? Что-то я не вижу много альтернативных майнеров для такого вида задач...

Идея, но не реализация.
Предложение рождается спросом...
Вероятно, в этом пока нет необходимости...Либо просто нет достойной реализации.

Просто майнер (причем, вероятно биржа должна заниматься написанием и поддержание работоспособности майнеров) это только часть схемы, нужна еще и биржа и заинтересованность(включает в себя рекламу и разъяснение почему так лучше\выгоднее) обоих сторон для участия в процессе. Т.е 3 составляющих.

Тем не менее, если ее конечно так можно назвать, есть биржа http://www.rublik.com/. Но она скорее показывает только одну сторону медали, то что люди готовы ставить себе программы "генерирующие" деньги, не вникая в подробности.
Осталось определить потенциальных заказчиков. Думаю это будет им интересно если цена окажется сильно выгоднее(хотя бы на начальном этапе) централизованных предложений.

Вот аналогия-есть облачные хранилища основанные на p2p и есть централизованные. В первых цена ниже раз в 10, но почему то все пользуются централизованными.

loga
Member
**
Offline Offline

Activity: 70



View Profile
January 18, 2013, 09:03:54 PM
 #5

Обычная утилита diff не справляется, так как стандартному быстрому алгоритму требуется квадратичная память.
Если даже с --speed-large-files не справляется то можно файлы splitом порезать на куски и сравнивать уже по кускам.

12S3cd5Z6XNroAmDg6Zk7CVv8paYEQi2pA
ArsenShnurkov
Legendary
*
Offline Offline

Activity: 1386



View Profile
January 19, 2013, 03:13:28 PM
 #6

Если даже с --speed-large-files не справляется то можно файлы splitом порезать на куски и сравнивать уже по кускам.

Да, это известный подход, его реализует Hadoop
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!