Работя върху приложение, което иска да анализира ~ един милиард 250 байта ключове, за да идентифицира подгрупата на тези ключове, които се появяват повече от веднъж в набора от данни.
В улова не всички клавиши се побират в главната памет наведнъж, така че аз се чудя: има ли ефективен алгоритъм или структура на размитите данни, които могат да идентифицират ключовете, които вероятно съдържат повече от една стойност?
Сегашният ми план е да използвам нещо подобноБлум филтър - Имам хеш всеки ключ, а след това съхранява, че хеш като показалец на цяло число в Редис. Първият път, когато виждаме хеш, задайте стойността му на 1, след това увеличение всеки път, когато хеш се вижда след това. В крайна сметка само клавишите, чиито хешове имат стойност> 1, трябва да влязат в Redis. Има ли по-добър начин да се идентифицират ключовете, които се появяват повече от веднъж? Ще бъда много благодарен за всички предложения, които другите могат да предложат!
Отговори:
2 за отговор № 1Аз ще опитам груба сила опция. Прочетете целия комплект и го разделете на 65536 различни файла на базата на първите два байта на всеки ключ, ако е достатъчно случайно, или на неговия хеш, ако не. (Всъщност можете да използвате повече от два байта).
Така че ключът 0a18abad1dea... отива в файл ./0a/18/0a18.dat , Цялата операция отнема около 250 гигабайта.
За оптимизиране на файловете се отваря / записва, може да искатепазете в паметта 65536 кофи с ключове и периодично ги промивате, вместо да правите файла отворен / прикрепен / затварящ за всеки нов ключ. Всеки гигабайт RAM позволява допълнителни 50 ключови размера за всяка кофа.
В края на краищата ще имате 65536 файла, всяко стопанствооколо (един милиард / 65536) = 15258 250-байтови ключове. На всеки от тези файлове изпълнявате пререждане или проверка за уникалност. Работата с множество ядра, това отново отнема едно и също време, като повторно четене на целия набор от данни за втори път. Тази втора част може да бъде разтоварена и на отделни машини, всяка от които управлява собствен набор от файлове.