Я хотел бы создать случайную перестановку чисел [1,2,...,N], где N - большое количество. Поэтому я не хочу хранить все элементы перестановки в памяти, а скорее перебирать элементы моей конкретной перестановки без сохранения прежних значений в памяти.Создать произвольную перестановку огромного списка (в Python)
Любая идея, как это сделать в Python?
Одна из возможностей - использовать шифрование. Поскольку шифрование является обратимым, то есть индивидуально, для данного ключа вы получите те же номера, которые вы шифруете, но в другом порядке.
Вам нужен блок-шифр с размером блока, достаточным для включения вашего максимума N. Используйте DES в режиме ECB для N = 2^64 - 1. Используйте AES в режиме ECB для N = 2^128 - 1. Для другие размеры, либо используйте Hasty Pudding cipher, который имеет переменный размер блока, либо напишите свой собственный простой Feistel cipher. Я предполагаю, что вам просто нужно перетасовать, а не криптографически безопасную тасовку.
Если выход больше N, то просто повторно зашифруйте, пока он меньше N, свойство 1-to-1 гарантирует, что цепочка больших чисел также уникальна.
Нет необходимости хранить весь массив в памяти, каждый номер может быть зашифрован по мере необходимости. Требуется только ключ и алгоритм шифрования. Одно небольшое осложнение заключается в том, что блочные шифры работают на [0 ... N-1]; вам может понадобиться дополнительный код для устранения крайностей.
Похоже на рабочий подход, но есть ли более простая операция, чем стандартные алгоритмы шифрования? Я бы хотел закодировать его в Python. Также они обычно фиксируются как размер блоков размером 2^64. Похоже, что «a * n mod p» - хорошее начало. Спасибо за то, что вы указали хорошие методы шифрования, которые могут пригодиться! – Gerenuk
Вы можете написать очень простой шифр Feistel для любого размера блока. Он не будет криптографически безопасным, но с четырьмя раундами он будет быстрым. Четыре раунда - это минимум, чтобы сделать его разумным. – rossum
Это общая проблема, а не специфическая для Python. В большинстве языков, даже когда итераторы используются для использования структур, вся структура хранится в памяти. Таким образом, итераторы в основном используются как «функциональные» инструменты, а не как инструменты оптимизации памяти.
В python многие люди используют большую память из-за наличия действительно больших структур (словарей и т. Д.). Однако все переменные-объекты программы будут храниться в памяти любым способом. Единственным решением является сериализация данных (сохранение в файловой системе, база данных и т. Д.).
Итак, в вашем случае вы можете создать настраиваемую функцию, которая создаст список перестановок. Но вместо добавления каждого элемента перестановки в список он сохранил элемент либо в файле (или в базе данных с соответствующей структурой). Затем вы сможете получать по одной каждой перестановке из файла (или базы данных), не доводя весь список в памяти.
Однако, как уже упоминалось ранее, вам всегда нужно знать, в какой перестановке вы сейчас находитесь. Чтобы избежать извлечения всех созданных перестановок из базы данных (что создавало бы такое же узкое место), вы могли бы иметь индекс для каждого места, содержащего символ, используемый в ранее сгенерированной перестановке (и создавать перестановки, добавляющие символы и предопределенную последовательность) ,
Это может быть то, что вы ищете: http://stackoverflow.com/questions/976882/shuffling-a-list-of-objects-in-python? –
Он делает перестановку, но я специально хочу избежать хранения данных размера N в памяти. – Gerenuk
Плохая новость: вы не можете сделать это, не сохраняя данные: D. вам нужно знать, какой номер вы создали, если у вас нет машины для путешествий во времени: D. –