Création d'une liste unique à partir d'un jeu de données trop volumineux pour tenir en mémoire

Question

J'ai une liste de 120 millions d'enregistrements d'environ 40/50 octets chacun, soit environ 5,5/6 gigaoctets d'espace mémoire brut, sans stockage supplémentaire requis pour conserver tableau en mémoire. Je voudrais m'assurer que cette liste est unique. La façon dont j'ai essayé de le faire est de créer une chaîne <Hashset> et d'y ajouter toutes les entrées une par une. Quand j'ai environ 33 millions d'enregistrements, je n'ai plus assez de mémoire et la création de liste ralentit.

Y a-t-il une meilleure façon de trier cette liste massive d'entrées en temps opportun? La seule solution que je peux penser est d'utiliser une instance extra-large quadruple de mémoire haute mémoire Amazon EC2 pendant une heure.

Merci

Answer 1

Si vous êtes juste essayer de vérifier l'unicité, je voudrais simplement diviser la séquence d'entrée dans des seaux, puis vérifiez chaque seau séparément. Par exemple, en supposant que vous chargiez les données d'un fichier, vous pouvez diffuser l'entrée et l'écrire dans 26 fichiers différents, un pour chaque lettre commençant par l'enregistrement (j'assume naïvement chaque enregistrement commence par AZ - s'il vous plaît ajuster pour votre situation réelle). Ensuite, vous pouvez vérifier l'unicité de chacun de ces petits fichiers en utilisant quelque chose comme votre code existant - car aucun d'entre eux ne sera trop grand pour tenir dans la mémoire à la fois. Le compartimentage initial garantit qu'il n'y aura pas d'entrées en double dans des compartiments différents.

Bien sûr, il existe différentes façons d'effectuer le compartimentage, et différentes approches seront efficaces pour différents ensembles de données. Vous pouvez utiliser un code de hachage, par exemple - prenez les 5 derniers bits du code de hachage pour créer 32 compartiments différents. Cela est susceptible d'obtenir une raisonnablement répartition égale des enregistrements entre les compartiments, et ne fait aucune hypothèse sur les données d'entrée. Je n'ai mentionné que l'approche "prendre la première lettre" ci-dessus car c'est une façon plus simple de saisir le concept :)

Answer 2

Utilisez bucket sort pour trier la liste, en vidant régulièrement une partie du contenu des seaux sur le disque pour éviter de manquer de la mémoire. Ensuite, chargez chaque seau rincé dans l'ordre et utilisez votre approche HashSet ou triez-le et vérifiez-le de cette façon.

Answer 3

Vous pouvez toujours travailler dans une base de données sqlite avec un index unique, car cela peut faciliter le traitement ultérieur de l'ensemble de données.