Algorithme pour imprimer une liste mélangées, en lieu et O (1) La mémoire

https://stackoverflow.com/questions/1866684

18-09-2019
|

Question

Après avoir lu cette question je commençais à me demander: est-il possible de un algorithme de mélange qui ne modifie pas ou copier la liste initiale?

Pour préciser:

Imaginez que vous donne une liste d'objets. La taille de la liste peut être arbitraire, mais supposer qu'il est assez grand (disons, 10.000.000 articles). Vous devez imprimer les éléments de la liste dans un ordre aléatoire, et vous devez le faire aussi vite que possible. Cependant, vous ne devriez pas:

Copier la liste originale, car il est très grand et la copie serait perdre beaucoup de mémoire (probablement frapper les limites de la RAM disponible);
Modifier la liste originale, parce qu'il est trié d'une certaine façon et une autre partie plus tard dépend d'être triée.
Créer une liste d'index, parce que, encore une fois, la liste est très grande et la copie prend trop de temps et de la mémoire. . (Précision: cela signifie toute autre liste, qui a le même nombre d'éléments que la liste initiale)

Est-ce possible?

Ajouté: Plus clarifications

Je veux que la liste soit brassé dans la vraie façon aléatoire avec toutes les permutations aussi susceptibles (bien sûr, en supposant que nous avons une bonne fonction Rand () pour commencer).
Suggestions que je fais une liste de pointeurs, ou une liste d'indices ou de toute autre liste qui aurait le même nombre d'éléments que la liste initiale, est considérée explicitement comme inefficace par la question initiale. Vous pouvez créer des listes supplémentaires si vous voulez, mais ils devraient être des ordres de grandeur graves plus petite que la liste initiale.
La liste originale est comme un tableau, et vous pouvez récupérer tout élément de celui-ci par son index dans O (1). (Donc pas de choses de la liste doublement chaînée, où vous devez parcourir la liste pour arriver à l'élément désiré.)

Ajouté 2 : OK, nous allons le mettre de cette façon: Vous avez un disque dur 1To rempli d'éléments de données, chaque 512 octets de grande taille (un seul secteur). Vous souhaitez copier toutes ces données à un autre disque dur de 1 To en mélangeant le tous les articles. Vous voulez faire cela aussi vite que possible (un seul passage sur les données, etc.). Vous avez 512 Mo de RAM disponible, et ne comptez pas sur swap. (Ceci est un scénario théorique, je n'ai rien comme ça dans la pratique. Je veux juste trouver le algorithm.item parfait.)

La solution

Voici une preuve très simple qu'aucun système PRNG peut fonctionner:

L'idée PRNG comporte deux phases: tout d'abord sélectionner un PRNG et son état initial; D'autre part, utiliser le PRNG pour mélanger la sortie. Eh bien, il y a N permutations possibles, de sorte que vous avez besoin d'au moins N différents états de départ possibles, entrant dans la phase 2. Cela signifie que, au début de la phase 2, vous devez ont au moins log ₂ N bits d'état, ce qui est interdit.

Toutefois, cela ne règle pas les régimes où l'algorithme reçoit de nouveaux bits aléatoires de l'environnement comme il va. Il pourrait y avoir, par exemple, un PRNG qui lit son état initial paresseusement et pourtant est garanti de ne pas répéter. Peut-on prouver qu'il n'y a pas?

Supposons que nous avons un algorithme de mélange parfait. Imaginez que nous commençons à courir, et quand il est à mi-chemin fait, nous avons mis l'ordinateur en veille. Maintenant, l'état complet du programme a été enregistré quelque part. Laissez est l'ensemble de tous les états possibles du programme pourrait être à cette marque à mi-chemin.

Puisque l'algorithme est correct et garantie de mettre fin, il y a une fonction f qui, étant donné l'état du programme enregistré ainsi une chaîne assez longue de bits, produit une séquence valide de disque lit et écrit l'achèvement le shuffle. L'ordinateur lui-même met en œuvre cette fonction. Mais considérer comme une fonction mathématique:

f : (S × les bits) de la séquence de → de lecture et d'écriture

Alors, trivialement, il existe une fonction g qui, étant donné uniquement , produit l'ensemble des emplacements de disque encore être lu et écrit l'état du programme enregistré. (Il suffit de passer une chaîne arbitraire de bits à f , puis regardez les résultats.)

g : → ensemble d'emplacements pour lire et écrire

Le bit restant de la preuve est de montrer que le domaine de g contient au moins _N C _{N / 2} différents ensembles quel que soit le choix de l'algorithme. Si cela est vrai, il doit y avoir au moins que de nombreux éléments de , et ainsi de l'état du programme doit contenir au moins log ₂ _N C _{N / 2} bits à la mi-course, en violation des exigences.

Je ne sais pas comment prouver que le dernier morceau, bien que, depuis soit les set-de-à-emplacements lire ou les réglages de-lieux -À-écriture peut être faible entropie, en fonction de l'algorithme. Je pense qu'il ya un principe évident de la théorie de l'information qui peut couper le nœud. Marquage ce wiki communautaire dans la personne de l'espoir va fournir.

Autres conseils

Eh bien cela dépend un peu de ce genre de hasard vous, sauf pour le brassage, à savoir devraient tous être aussi probable tergiversations, ou peut être la distribution asymétrique.

Il existe des moyens mathématiques pour produire des permutations « aspect aléatoire » des entiers N, donc si P est une permutation de 0..N-1 à 0..N-1, vous pouvez simplement itérer x de 0 à N -1 et un élément de liste de sortie L (P (x)) à la place de L (x) et que vous avez obtenu un brassage. Ces permutations peuvent être obtenues par exemple en utilisant l'arithmétique modulaire. Par exemple, si N est premier, P (x) = (x * k) mod N est une permutation pour tout 0

Il convient de noter que exponentiation modulaire est la base de nombreux algorithmes de chiffrement (par exemple RSA, Diffie-Hellman) et est considéré comme une opération fortement pseudo-aléatoire par les experts dans le domaine.

Une autre façon facile (ne nécessitant pas des nombres premiers) est d'abord d'élargir le domaine de sorte qu'au lieu de N on considère M où M est la moins puissance de deux ci-dessus N. Ainsi, par exemple si N = 12 vous définissez M = 16. Ensuite, vous utilisez des opérations de bits bijectives, par exemple.

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

Ensuite, lorsque vous la sortie de votre liste, vous itérer x de 0 à M-1 et de sortie L (P (x)) que si P (x) est en fait

A « vrai, aléatoire biaisée » solution peut être construit en fixant un chiffrement par bloc cryptographiquement forte (par exemple AES) et une clé aléatoire (k) et ensuite itération de la séquence

AES(k, 0), AES(k, 1), ...

et délivrer en sortie l'élément correspondant de la séquence AES ssi (k, i)

Vous n'êtes pas autorisé à faire une copie, le modifier, ou garder une trace des éléments que vous avez visités? Je vais dire que ce n'est pas possible. À moins que je suis malentendu votre troisième critère.

Je le prends pour vous dire n'êtes pas autorisé à dire, faire un tableau de 10.000.000 booléens correspondant, la valeur true lorsque vous avez imprimé l'élément correspondant. Et vous n'êtes pas autorisé à faire une liste des indices 10.000.000, mélangez la liste, et imprimer les éléments dans cet ordre.

Les 10.000.000 éléments ne sont que des références (ou pointeurs) à des éléments réels, de sorte que votre liste ne sera pas si grande. Seulement ~ 40Mo sur l'architecture 32 bits pour toutes les références + taille des variables internes de cette liste. Dans le cas où vos articles sont plus petits que la taille de référence, vous venez de copier la liste entière.

Il est impossible de le faire avec vraiment générateur de nombres aléatoires puisque vous devez soit:

rappelez-vous que les numéros ont déjà été choisis et sauter (ce qui nécessite une O (n) liste des booléens et l'aggravation progressive temps d'exécution que vous sauter de plus en plus des numéros); ou
réduire la piscine après chaque sélection (ce qui nécessite soit des modifications de la liste originale ou une liste O (n) séparé à modifier).

Aucun de ceux-ci sont possibles dans votre question, donc je vais devoir dire « non, vous ne pouvez pas le faire ».

Ce que je aurais tendance à aller dans ce cas est un masque de bits des valeurs utilisées mais pas avec sauter puisque, comme mentionné, les temps de parcours se aggravent les valeurs utilisées accumulent.

Un masque de bits sera sensiblement mieux que la liste originale des 39FR (10 millions de bits est seulement d'environ 1,2 M), beaucoup moins un ordre de grandeur que vous avez demandé, même si elle est encore O (n).

Pour contourner le problème de l'exécution, générer un seul nombre aléatoire à chaque fois et, si le correspondant « utilisé » bit est déjà défini, balayage avant à travers le masque de bit jusqu'à ce que vous trouviez un qui est pas ensemble.

Cela signifie que vous ne serez pas traîner, désespérée pour le générateur de nombres aléatoires pour vous donner un chiffre qui n'a pas encore été utilisé. Les temps d'exécution ne sera jamais obtenir aussi mauvais que le temps nécessaire pour analyser des données 1.2M.

Bien sûr, cela signifie que le nombre spécifique choisi à tout moment est biaisé basé sur les chiffres qui ont déjà été choisis, mais, étant donné que ces chiffres étaient de toute façon aléatoire, le hasard est obliquité (et si les chiffres n'étaient pas vraiment aléatoire pour commencer, le désalignement ne sera pas question).

Et vous pouvez même alterner le sens de la recherche (balayage vers le haut ou vers le bas) si vous voulez un peu plus de variété.

Bottom line: Je ne crois pas ce que vous demandez est faisable, mais gardez à l'esprit que je suis mal avant que ma femme attestera, rapidement et souvent :-) Mais, comme toutes choses, il y a généralement des moyens de contourner ces problèmes.

Il semble impossible.

Mais 10.000.000 pointeurs 64 bits est seulement 76MB.

Un registre à décalage rebouclés peut faire à peu près ce que vous voulez - générer une liste de numéros jusqu'à une certaine limite, mais dans un ordre aléatoire (raisonnable). Les modèles qu'il produit sont statistiquement similaires à ce que vous attendez de hasard try, et il est même pas proche de cryptographiquement sécurisé. L'algorithme Berlekamp-Massey vous permet de reverse engineering d'un LFSR équivalent basé sur une séquence de sortie.

Compte tenu de vos besoins pour une liste de 10.000.000 ~ articles, vous voulez une LFSR longueur maximale de 24 bits, et défaussez simplement sorties plus grande que la taille de votre liste.

Pour ce que ça vaut, un LFSR est généralement assez rapide par rapport à un PRNG congruence linéaire typique de la même période. Dans le matériel, un LFSR est très simple, composé d'un registre N bits, et M de XOR 2 entrées (où M est le nombre de prises - parfois seulement un couple, et rarement plus d'un demi-douzaine).

S'il y a assez d'espace, vous pouvez stocker des pointeurs de noeuds les dans un tableau, créez un bitmap et obtenir ints aléatoires qui pointent à l'élément suivant choisi. Si déjà choisi (vous stockez que dans votre bitmap), puis obtenir le plus proche (à gauche ou à droite, vous pouvez randomiser que), jusqu'à ce qu'aucun élément ne gauche.

S'il n'y a pas assez d'espace, alors vous pourriez le faire même sans enregistrer les pointeurs de noeuds, mais le temps souffriront (c'est le compromis entre l'espace de temps ☺).

Vous pouvez créer un pseudo-aléatoire, permutation 'sécurisée' à l'aide d'un chiffrement par bloc - voir ici . Ils idée fondamentale est que, étant donné un chiffrement par bloc de longueur n bits, vous pouvez utiliser « pliage » pour le raccourcir à m

Essentiellement, ce que vous avez besoin est un générateur de nombres aléatoires qui produit les numéros 0..n-1 exactement une fois chacun.

Voilà une idée demi-cuite: Vous pourriez faire assez bien en choisissant un nombre premier p picking légèrement plus grand que n, puis un x aléatoire entre 1 et p-1 dont l'ordre dans le mod groupe multiplicatif p est p-1 (pick xs aléatoires et test qui satisfont les x ^ i! = 1 pour i = n et que vous donne une séquence d'index à imprimer.

Ce n'est pas très aléatoire, mais vous pouvez utiliser la même technique plusieurs fois, en prenant les indices ci-dessus (1) et en les utilisant comme les exposants d'un autre générateur x2 modulo un autre premier p2 (vous aurez besoin n

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow