Цитата:
|
Сообщение от lor2
ну 2 миллиарда записей где всего один байт на запись ты ж понимаешь там всё просто делается перебором. или пока до конца списка не дошли или пока 256 элементов не выбрали - что раньше. итого комплексити о эн. можно распараллелить легко. можно на куски разбить легко.
ну ок. хорошо что можно почти не беспокоиться за коллизии. и да.. я не думал что вероятность умеет НАКАПЛИВАТЬСЯ. типа купил миллион лотерейных билетов - гарантированно получил выигрышный. хотя ты Доктор - тебе виднее.
в любом случае к решению задачи мы пока не приблизились. давай думать дальше. вот как программисты а не математики. какие нам могут помочь инструменты или подходы, чтоб это просчитать? согласен по ша - он поможет (наверное) сэкономить память если исходная запись больше чем 160 бит (или 256?), он поможет срезать ее до этих размеров.
|
Причем тут накопление? Я тебе нижнюю оценку посчитал, исходя из предположения, что тебе нужно иметь 2^256 + 1 разных записей, чтобы гарантированно получить хотя бы одну коллизию. Если хочешь с вероятностями, пожалуйста:
вероятность коллизии для SHA256 оценивается, как 4.3*e-60. Для того, чтобы получить коллизию с вероятностью 0.1%, тебе надо будет прогнать log(4.3*e+57)/log(1-4.3e-60) повторений. Это практическая бесконечность, сколько бы "террабайтов" ты не гонял. Так что по сути SHA256 здесь не только "уменьшает объем памяти", необходимый для хранения одного элемента, но и позволяет легко вытащить уникальные элементы из списка (поскольку сравнивать ты будешь только 256-битные числа, а знать, из каких элементов они получились, можешь, тривиально храня ссылку на исходную запись вместе с хэшем).
Сложность будет в любом случае O(n), если в данных отсутствует структура. Если очень хочется, то можно это примитивно распараллелить, разбивая на куски и сливая промежуточные результаты. Это уже совсем скучно.
Ну, если совсем паранойя насчет коллизий, то можно сделать perfect hashing.
По выделенному: в чем именно задача выглядит нерешенной? И о каких еще интструментах идет речь. Если поговорить о библитеках и фреймворках, то это не со мной, т.к. эта ерунда вообще обсуждения не стоит и подбирается, исходя из контекста решаемой задачи. |
