javascript - Trouvez la médiane d'entiers de 10 Go, la limite de mémoire est de 2 Go.

Question

Tencent a une telle question de recrutement scolaire :
Pour un PC avec seulement 2 Go de mémoire, trouvez la médiane dans un fichier contenant 10 Go d'entiers et écrivez un algorithme.

Il existe plusieurs solutions, telles que le tri par compartiment et le tri par base, mais j'ai trouvé une méthode qui utilise un tas pour le résoudre. Je ne la comprends pas très bien. Les mots originaux sont comme ceci :
Trouvez d'abord le. 1G le plus grand, puis utilisez cet élément pour trouver le plus grand 2G, puis utilisez le plus grand 2G pour trouver le plus grand 3G... Bien sûr, bien que cela ne nécessite pas de tri, il y aura plus d'opérations de disque et les détails doivent être être analysé. Lequel des tris inférieur et externe aura le plus d'E/S disque ?
Créez un tas maximum de 1 g d'entiers. Si l'élément est inférieur à la valeur maximale, placez-le dans le tas. De cette façon, vous pouvez obtenir le 1 gième. le plus grand élément, puis utilisez cet élément pour reconstruire un tas une fois, et ajoutez le 1ème plus grand élément supérieur aux conditions d'entrée dans le tas cette fois, de sorte qu'après avoir construit le tas, vous puissiez obtenir le 2ème plus grand élément.

J'étais confus quand je l'ai vu. Premièrement, je n'ai pas compris ce qu'était 1G. S'agit-il de diviser les données 10G en 10 parties, puis de trier les données 1G pour trouver la signification la plus large ?
J'espère que vous pourrez me donner quelques idées pour cette solution, merci.

Answer 1

Heap est une structure de données, qui est un arbre binaire complet (aucun pointeur n'est donc nécessaire pour enregistrer sa structure). Chaque nœud n'est ni plus grand ni plus petit que ses nœuds enfants, correspondant au grand tas supérieur et au petit tas supérieur. respectivement. Par exemple, dans un petit tas supérieur, l’élément racine est le plus petit. Il peut donc être utilisé comme O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N)).

Ce passage signifie qu'en créant d'abord un petit tas supérieur pouvant accueillir (1G+1) des données, vous pouvez rapidement y trouver le plus petit élément. Parcourez ensuite les 10 Go de données et insérez-les : si le tas est plein après l'insertion (il y a 1G+1 de données dans le tas). Supprimez simplement le plus petit. . . .
Le résultat final est que les données dans le tas sont les plus grandes données 1G, et le haut du tas est le plus petit, c'est-à-dire que si elles sont triées par ordre décroissant, la position de ces données est la position 1G, par exemple, ce nombre est x.
Ensuite, continuez à nouveau le processus ci-dessus, mais la différence est que seuls les éléments inférieurs à x sont insérés dans le tas et les éléments supérieurs ou égaux à x sont ignorés. Autrement dit, après avoir ignoré les données 1G que vous venez de trouver, trouvez le plus grand 1G. De cette façon, le sommet du tas final contient les données en position 2G après le tri. (Mais soyez prudent lorsque vous traitez des données en double). . . . Et ainsi de suite pour trouver la médiane.

Answer 2

J'ai une question, ce genre de question ne peut-il pas être réalisé en utilisant des bitmaps ? . .
1. Parcourez ces nombres 10G, marquez ceux qui sont apparus dans le bitmap et comptez combien de nombres différents sont apparus, enregistrez-le comme count
2 Parcourez le bitmap, trouvez le nombre/2ème bit, qui est ce nombre. . .

Si l'entier est de 4 octets comme 0 ~ 2 ^ 32-1. Ensuite, pour enregistrer sa plage de valeurs, vous n'avez besoin que d'un bitmap de 512 Mo de mémoire. . . . ?

Answer 3

J'ai encore quelques questions divergentes sur cette méthode. Si les maîtres la trouvent intéressante, vous pouvez y jeter un oeil :
Puisqu'elle est divisée en 10 tas, quelle est la valeur limite commune de chaque tas ?

Si divisé en dix piles, combien de jugements le tri rapide nécessite-t-il dans le pire des cas ?

Est-il possible de réduire le montant du calcul ?

@zonxin