Изпечатай

[Yasen6275]

Аз си мисля за аватара. Това не беше ли някаква ядрена електроцентрала след земетресение.

[gat3way]

Така е, 50% (ако игнорираме високосните години).

За колизиите обаче сметките не са правилни. 2^24 е около 16 милиона, но и да беше 100, пак не е правилно - така се смята каква е вероятността за един файл, някой от останалите 99,999,999 да извади същата хеш сума. Обаче това не включва вероятността измежду останалите 99.999.999 да има друга двойка файлове с еднакъв хеш. В смисъл, твоят отговор е валиден, ако задачата е зададена така: "имаме 99.999.999 файла и записваме нов. Каква е вероятността хешът на новия файл да съвпадне с хеша на някой от останалите".

Разбира се, както казваш, трябва да приемем че MD5 алгоритъма генерира стойности, които имат равномерно разпределение в интервала 0..2^128 - което надали е точно така.

[romeo_ninov]

Така е, 50% (ако игнорираме високосните години).

За колизиите обаче сметките не са правилни. 2^24 е около 16 милиона, но и да беше 100, пак не е правилно - така се смята каква е вероятността за един файл, някой от останалите 99,999,999 да извади същата хеш сума. Обаче това не включва вероятността измежду останалите 99.999.999 да има друга двойка файлове с еднакъв хеш. В смисъл, твоят отговор е валиден, ако задачата е зададена така: "имаме 99.999.999 файла и записваме нов. Каква е вероятността хешът на новия файл да съвпадне с хеша на някой от останалите".

Разбира се, както казваш, трябва да приемем че MD5 алгоритъма генерира стойности, които имат равномерно разпределение в интервала 0..2^128 - което надали е точно така.

Хм, мисля си че това, което дадох е по-скоро вероятността (наистина при разномерно разпределение на хеша) два файла от N  да са с еднакъв хеш
П.П. А ми излезе 2^24 защото го смятах по малко обратния начин и съм сметнал lg2, a трябва да е 1/lg2 t.e. 2^26.4, но според мен разликата е несъшествена за мащаба
П.П.П. Да си срещал някъде  вероятностното разпределението на хеш, все някой го е извел (надявам се)

[gat3way]

Мне, ако сведем задачата с хешовете до някой по-прост проблем, например този с рождените дни, тогава по същата логика ще имаш 1/(365/23) = 23/365 = 0.06 = 6% (а не 50% какъвто е отговора).

Иначе за разпределението на хеш стойностите нямам идея, не съм виждал. Според мен ще е ужасно сложно да се сметне нещо такова, ама знам ли...

[n00b]

Освен хеша добави и размера на файла. Така получаваш 100% съвпадение.

Колизия при еднакъв хеш, но различен размер ще е доста трудна за осъществяване.

[gat3way]

Математически погледнато, размера на файла няма значение. Преди известно време, даже ако не се лъжа точно в този форум, спорех с някого, че големината на файла има отношение към вероятността за колизия. Няма никакво отношение. Стига да са достатъчно големи файловете, за да може да има 100 милиона уникални такива, вероятността два файла да направят колизия на хеш сумите им е една и съща: 1^128. Ако от друга страна направим ограничение: два файла да дават еднакъв хеш и да имат еднаква големина, това е друго нещо. Тогава обаче трябва да имаме максимална големина на файла, иначе задачата няма да има решение.

[romeo_ninov]

Математически погледнато, размера на файла няма значение. Преди известно време, даже ако не се лъжа точно в този форум, спорех с някого, че големината на файла има отношение към вероятността за колизия. Няма никакво отношение. Стига да са достатъчно големи файловете, за да може да има 100 милиона уникални такива, вероятността два файла да направят колизия на хеш сумите им е една и съща: 1^128. Ако от друга страна направим ограничение: два файла да дават еднакъв хеш и да имат еднаква големина, това е друго нещо. Тогава обаче трябва да имаме максимална големина на файла, иначе задачата няма да има решение.

Така като си правя сметки наум размера на файловете (ако са двоични) е 4 байта, тогава уникалните биха били 4 милиарда. Друг е въпроса с именуването, но тогава даже и имената им да са само цифри и букви (малки) 7 символа биха били достатъчни
П.П. мисля че имаш предвид 2^128 Ако някой има интерес ще спретна md5 сумите на първите 4 милиарда файла

[gat3way]

Ох, да, 1/2^128 имах предвид.

[gat3way]

Обаче това с първите 4 милиарда файла ще се окаже доста интересна задача. Значи аз мога да сметна каква е вероятността за колизии (имайки предвид birthday paradox-a):

p=1-exp(-1*(4*10^9)^2/2^128*2) = 0.0000000000000000094%

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

Изпълнението е по-интересно. Генерирането на "първите" 4 милиарда файла не е такъв проблем, както и хешването им - резултатът ще е един файл с хешове с големина 4*16 = близо 64 гигабайта. Дотук няма проблеми - днешните харддискове са големи.

Обаче за да тръгнеш да търсиш колизия в тази база става малко сложно. Единият вариант е да имаш машина с над 64 гигабайта РАМ, за да качиш всичкото в паметта и да го обхождаш бързо. Това е идеален вариант, обаче такива системи с 64 гигабайта рам са скъпички и не всеки има под ръка такава.

Другият вариант е да тъпчеш в паметта някаква част от тях, да изчиташ от файла хеш по хеш и да сравняваш, после да тъпчеш в паметта следващата част и да изчиташ до края и такам...това обаче ще е ужасно бавно. Отделно, с 32-битова машина имаш ограничение откъм адресно пространство - повече от 3 гигабайта не можеш да вдигнеш в рамта по този начин (останалия 1 гигабайт се ползва от ядрото и се мапва на 0xC0000000 до 0xFFFFFFFF) - има друг вариант да се форкнат няколко процеса и да си правят IPC някакво, ама е сложно и пак не е много бързо.

Има и трети вариант - всичко да се натъпче в SQL база и да се напише някакво къдраво query по въпроса. Този вариант поне за мен е най странния (щото не разбирам много) - чудно ми е какво ли ще се получи? Обаче интуицията ми казва, че mysql таблица с 4 милиарда реда и един забавен SELECT отгоре ще отнеме доста време...чудно някой по-опитен с разните бази какво ли би казал по въпроса?

[romeo_ninov]

...
Има и трети вариант - всичко да се натъпче в SQL база и да се напише някакво къдраво query по въпроса. Този вариант поне за мен е най странния (щото не разбирам много) - чудно ми е какво ли ще се получи? Обаче интуицията ми казва, че mysql таблица с 4 милиарда реда и един забавен SELECT отгоре ще отнеме доста време...чудно някой по-опитен с разните бази какво ли би казал по въпроса?

Ще си спретна един Оракъл и ще го пробвам как ще се държи с такава "табличка"
Проблема е че партиционирането няма да е от полза, защото трябва да се пусне едно картезианско търсене и......

[gat3way]

Ще е забавно колко време ще отнеме...

[romeo_ninov]

Ще е забавно колко време ще отнеме...

Ха, очаквам да е от порядък на десетки часове и даже денонощия. Но сега съм в отпуска и не ми се мисли за такива неща

[remotex]

Няма да отнеме чак толкова време статистиката след това ..и с БД и без (т.е. някакаъв скрипт) защото има едно нещо т.нар. сорт+двоично търсене но в сл. даже няма нужда да се стига дотам - още при въвеждане на хеш гледаш дали вече го има и ако е така само му увеличава брояча т.е. втората(3тата) колона - нали табл. няма да е само с 1 колона?!
т.е. думарното време ми се чини че ще е само колкото да се генерират хешовете - вкарването в БД е пренебрежимо бързо :-) а и после заявката е доволно проста - Да вади само тези с бр. > 1

[gat3way]

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

Обаче ако имаш достатъчно много РАМ, тогава няма да се стигне дотам. Просто зависи колко хеша искаш да сметнеш.

[romeo_ninov]

като се замислих всичко може да се реши само с един ред без експлицитно да трябва да се указва сравнение на хешовете (то ще се прави вътрешно). И няма да има нужда от трета колона. Нещо от рода:

Код:

select value, hash, count (*) from table group by hash