Изпечатай

[remotex]

Това ще работи добре до момента в който не генерираш прекалено много хешове ....Първоначално, това няма да отнема много време, но в последствие ще стане доста бавно (за всеки новогенериран хеш примерно да трябва да изчиташ няколко гигабайта от диска).

gat3way има едни неща наричат се индекси  и НЕ трябва цялото нещо да се пази в паметта - по индекса с двоично търсене (т.е. зареждат се само тези части които му трябват) става доста бързо а и ако избереш правилната БД освен индекса може и да не ти трябва още едно изчитане за реалните данни (т.е. при някой БД само индекса е достатъчен ако е по цялото поле напр. InnoDB но пък при MyISAM не е така)
П.П. За по-простичко обяснение (cpp код) може да погледнеш kbgoffice assistant-а как го прави 

[gat3way]

Добре, съгласен съм - ще спестиш изчитането на всичко така, всеки път, твърде вероятно ще стане по-бързо. Може би има доста смисъл, при положение че хеш сумите се очаква да са *почти* равномерно разпределени.

[romeo_ninov]

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл. Мисля си че във втория случай ако сме дефинирали стойността (0 до 2^32-1) като индекс процеса на създаване на индекса няма да е за всяка стойност а на по-крупни парчета

[remotex]

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл.

Естествено Ромео е прав - повече БД правят точно така при вкарване на много голям обем данни наведнъж - явно или неявно забраняват индексите => импортират данните и ре-генерират индекса наново за по-бързо... само че така остава гадната бавна заявка после а аз имах предвид по-скоро че докато се изпълнява смятането на мд5 на следващ файл т.е. процесороемка процедура едновременно ще се за генерира и записва и индекса в/у диска и ще се броят еднаквите. 4 Гб днес нищо не са - ако искаш може и програмка да си напишеш (не за ВМ освен ако нямаш излишна такава с 4 Гб ОП) но ..като се замисля и тя може да се окаже излишна - записваш ги във файл по 1 на ред после sort ; sort -u и накрая с diff сравняваш 2та и броиш различните редове ;-)

П.П. Извинявам се предварително - в момента не се сещам за по-елегантно решение с една команда което от вече сортиран файл да брои само повтарящите се редове (освен със собственоръчно написана програмка)

[gat3way]

Само да вметна, че не става въпрос за 4 гигабайта, а за 64 гигабайта - хеш сумите са 16-байтови.

[romeo_ninov]

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл.

Естествено Ромео е прав - повече БД правят точно така при вкарване на много голям обем данни наведнъж - явно или неявно забраняват индексите => импортират данните и ре-генерират индекса наново за по-бързо... само че така остава гадната бавна заявка после а аз имах предвид по-скоро че докато се изпълнява смятането на мд5 на следващ файл т.е. процесороемка процедура едновременно ще се за генерира и записва и индекса в/у диска и ще се броят еднаквите. 4 Гб днес нищо не са - ако искаш може и програмка да си напишеш (не за ВМ освен ако нямаш излишна такава с 4 Гб ОП) но ..като се замисля и тя може да се окаже излишна - записваш ги във файл по 1 на ред после sort ; sort -u и накрая с diff сравняваш 2та и броиш различните редове ;-)

П.П. Извинявам се предварително - в момента не се сещам за по-елегантно решение с една команда което от вече сортиран файл да брои само повтарящите се редове (освен със собственоръчно написана програмка)

няколко бързи вметвания:
1. не мисля че операцията по смятането на хеша ще е много трудоемка, защото дължината на текста е 4 байта
2. за да е налична пълната картина и за да може да се сметне разпределението е нужно да има информация за всички хешове: този се среща веднъж, този този два пъти, този три
3. мисля си че diff, sort няма да са много по-бързи от база данни (ако са по-бързи)
4. файла за зареждане ще е 84 гигабайта: 4 байта стойност (от 0 до (2^32)-1), разделител, 16 байта (за md5, които стават 20 за sha1)

[gat3way]

Мисля, че разделителя може да се спести - все пак всяка входна стойност е с фиксирана дължина (32 бита) и всеки хеш тоже. Не че ще спестим кой знае колко - 4 гигабайта не са кой знае колко на фона на останалото.

В крайна сметка обаче мисля, че експериментът ще е неуспешен, защото 4 милиарда хеша са прекалено малко, за да си изградим някаква представа (на фона на множеството от 2^128 възможни стойности).  Чисто статистически, вероятността да се получи колизия е 0.0000000000000000094%, това ако стойностите са разпределени равномерно разбира се. Трябва да са ужасно неравномерно разпределени, за да имаме вероятност примерно от 1% да имаме  една колизия (един процент е 106 квадратилиона пъти по-висока вероятност). Това не означава, че ще ни трябват 106 квадратилиона пъти повече хешове, за да достигнем 1% вероятност, разбира се, защото според birthday paradox-a, зависимостта между броя хешове и вероятността за колизия не е линейна.

Имам ужасно силно усещане, че няма да открием нито една колизия за 4-те милиарда входни стойности. Ако открием, това ще бъде или невероятен късмет, или просто MD5 алгоритъмът ще излезе невероятно криво направен. Но за да се разбере кое от двете е, трябва да повторим същата операция за много по-голяма извадка от входни стойности и техните хешове.

Поне така си мисля де.

[romeo_ninov]

...
Имам ужасно силно усещане, че няма да открием нито една колизия за 4-те милиарда входни стойности. Ако открием, това ще бъде или невероятен късмет, или просто MD5 алгоритъмът ще излезе невероятно криво направен. Но за да се разбере кое от двете е, трябва да повторим същата операция за много по-голяма извадка от входни стойности и техните хешове.

Поне така си мисля де.

Не знам дали ще открием дублираща се стойност, но и на мен ми се струва че ще трябва да заложим поне на десетина порядъка повече данни примерно 2^64, но нещо не ми се мисли за пълно търсене там

[go_fire]

В тая схема, защо никой не се запита, абе аджеба няма ли да се намерят двама потребителя да качът един и същ файл и тогава обезателно имаме повтаряне на хеша

[gat3way]

Теоретично, би трябвало да се очаква съвпадение на файловете да се случва с много по-малка вероятност, отколкото колизия на хешове. Обаче реално, това не става така поради ред причини. А иначе, съвпадението на файлове не е предмет на задачата, става въпрос за колизии на хешове. Ако въведем възможността файловете да съвпадат, тогава задачата няма решение, защото никой не може да ти каже с каква вероятност някой файл ще съвпадне с друг - теоретично възможните файлове клонят към безкрайност, реално погледнато обаче хората имат навика да слушат едни и същи мп3-ки например. Та моя е грешката че не съм поставил това ясно в условието, явно съм мислел че са подразбира.