Как быстро получить случайное слово из файла на 12 ГиБ?
Имеется файл на 12 ГиБ, содержащий по одному слову на каждой строке. Разные слова разной длины (от нескольких символов до нескольких десятков). Надо постоянно получать случайное слово из этого набора. Вариант загрузки файла целиком в память, в список, например, не подходит, т.к. это займёт слишком много памяти, да и придётся ждать несколько минут при каждом запуске программы.
Мне в голову пришёл вариант проиндексировать все строки файла (или несколько строк по всему файлу), т.е. хранить в памяти пары (<номер строки>, <смещение относительно начала файла>) и с помощью них ускорять чтение строки с нужным номером из файла.
Можно ли средствами стандартной библиотеки Python облегчить оптимизацию этого процесса?
Или кто-нибудь знает как решить это проще?
можно генерировать случайное число в интервале [0,размер файла[, искать конец строки начиная с этого смещения и читать слово следующее за найденным концом строки. Если найден конец файла -- читать самое первое слово.
Вариант с потолка: генерируйте случайную позиции в файле (от нуля до размера файла в байтах). Читаете все окружающие символы пока не найдете два символа новой строки ('\n') до и после исходной случайной позиции. Между этими символами новой строки и будет ваше случайное слово.
Рандом, конечно же, не совсем честный и сильно зависит от различия в длинах строк в файле.
Рандом, конечно же, не совсем честный и сильно зависит от различия в длинах строк в файле.
В виду того, что файл очень большой, различия в длинах строк становятся очень несущественными для такого рандома. Так что твой вариант идеально подойдёт для моей задачи.
Кирилл Гусарев, возьми самое длинное слово. Умножь его на 3. И читай чанк такой длинны. Найденные в нем слова помещай в список, и бери еще один рандом из этого списка.
Всё, рандом честный.
mayton2019, не понимаю, зачем такие сложности. Можно ведь просто взять следующее слово после найденного. Конечно, при условии, что файл надежно перемешан.
luaPower, подожди-подожди. Зачем я буду брать следующее слово? По какому закону или по какой формуле? Автор поставил задачу о случайности. Обычно имеется в виду линейное распределение вероятностей. Это означает что все слова - равновероятны.
Мне тут пока предлагают алгоритмы которые просто нарушают линейную вероятность.
mayton2019, так я же и говорю, когда будет найдено первое слово, то, как ты и заметил, рандом будет не совсем честный из-за перекоса в сторону длинных слов. Но, если взять следующее слово, которое располагается сразу после найденного, то вероятность будет уже соответствовать равномерности распределения строк в исходном файле. Насколько я понял, предполагается, что на входе у нас перемешанный файл.
luaPower, я думаю что твоя гипотеза требует какого-то доказательства. У меня нет сомнений в том что выбор слова из базы по порядковому номеру взятому из ГПСЧ будет соовтествовать линейному распределению.
Но у меня есть сомнения в том что все прочие методы дают нужное распределение. И почему мы решили что следующее число за длинным - будет правильным выбором. Может надо взять следующие 2 числа? Или может мы должны анализировать длину найденного числа и вести учёт уже найденных? Или может мы должны делать корректировочный выстрел?
mayton2019, что же тут доказывать-то? Сдается мне, вы просто не умеете признавать свои ошибки, поэтому у вас столько вопросов. Я ни в коем случае не хотел указывать на тот факт, что ваше решение неполное, я только сказал о том, что было итак очевидно. Вам нужно было подумать лишь на один шаг дальше.
Хорошо. Допустим, у нас на входе файл, строки в котором расположены в случайном порядке. Если мы возьмем любую из них, то, по определению, расположение этой строки относительно остальных будет случайным, так? Отсюда следует, что если взять следующую строку, идущую после этой случайной, то она так же будет случайной.
Ваше решение чаще находит строки, которые длиннее, чем те, которые короче. Это уже было отмечено выше и, я надеюсь, в доказательстве не нуждается. Однако, можно воспользоваться вашим решением, чтобы найти первую строку, а следующая за ней - будет случайной. Поскольку это было уже доказано в предыдущем абзаце.
mayton2019, извиняюсь, я спутал вас с автором текущего решения. Но первые мои сообщения были адресованы именно вам. Незачем создавать кучу файлов, если можно взять следующую строку после найденной.
luaPower, если брать слово, следующее за тем словом, которое содержит случайно выбранный символ/байт, то вероятность получить короткое слово станет выше вероятности получения длинного слова. Видимо об этом дефекте говорил mayton2019.
Какая максимальная длина слова? Ну допустим 20 символов.
Не в курсе насчет питона. Но я-бы убрал фактор плавающей длины. Например я-бы разбил
этот 12Гб файл на 20 файлов. Допустим в первом будут лежать все слова длиной в 1 символ.
Во втором 2 символа. И так далее.
Тогда формула будет такая. Считаем распределение слов по этим 20 файлам. Там гистограмма получается.
Типа допустим 5% на 8 символьные слова. 8% на 9 символьные и так далее. Выбираем случайный файл
ну как-бы учитывая "перекос". И потом уже внутри этого файла просто ищем случайное слово. Будет
быстро потому-что слова уже имеют фиксированную длину.
aleks-th, хранить длину каждого слова крайне затратно. Проще создать штук 100 индексов, которые будут указывать на некоторые слова по всему файлу, т.е. будут хранить позицию (смещение) слова, а не размер.
Кирилл Гусарев, я-бы посчитал накладные расходы на индексы. При 12 Гб файле нам удобно использовать целые числа формата long (64bit) для указания начала слова.
Далее - я бы посчитал среднюю длину слова. Допустим это 11 символов. Пускай слова разделяются переводом строки 0x0D тогда будет 12 байтов на слово. И 8 байтов на элемент индекса.
Считаем число слов 12 Gb == 12884901888 bytes
Или в 1 073 741 824 слов (1 миллиард).
Объем индексного файла будет - 8589934592 bytes ~ примерно 8 Гб.
Примерно подходит под требования автора.
На индексе можно сэкономить если взять скажем не long 64bit а int32 bit
Тогда надо базу слов разбить хотя-бына 3-4 части (одно целое число может адресовать
смещение до 4 млрд).
Или можно поступать с памятью как делает Java c heap. Выровнять слова по границе
параграфа (16 байт) и тогда можно лишние 4 бита с индексного элемента перенестсти
в старшие разряды. И тогда может быть хватит 32х бит. Тут надо посчитать вобщем
потери от такого округления. Вместо 12 Гб файла - может быть в полтора раз больше.
По мне, так проще всего импортировать как CSV в СУБД в таблицу с первичным ключом bigint и колонкой типа строка.
Зная общее количество записей, просто берем случайное число в диапазоне 1..count и с SQL ищем запись под этим первичным ключом.
Тогда ничего мудрить и не нужно.
Интересно что никому в голову не пришло просто в хеш-мапу это все загрузить. И решить проблему.
Накладные можно пообсуждать отдельно но в конце концов у любой задачи есть цена разработки
и цена эксплуатации
Может эта задача - одноразовая. Или запускается 1 раз в квартал. Или просто - временное решение.
Кирилл Гусарев,
Можно взять SQLITE в качестве СУБД. Если же импортировать из файла по какой-то причине нельзя, тогда при построчном чтении хранить смещение от начала файла вместе с длиной строки вместо самой строки. Получается, просто индекс. И это так же по эффективности. А сам индекс точно можно хранить в памяти.
Однако, придётся работать и с СУБД и и с файлом, что не так удобно (просто) как если при импорте.
