Filtrage d'un sous-ensemble de (potentiellement) 1.000.000+ éléments

Question

J'ai un grand dataset avec éventuellement plus d'un million d'entrées. Tous les éléments ont un horodatage assigné et les éléments sont ajoutés à l'ensemble au moment de l'exécution (généralement, mais pas toujours, avec un horodatage plus récent). Je dois montrer un sous-ensemble de ces données pour une certaine plage de temps. Cette plage de temps est généralement relativement petite par rapport à l'ensemble de données total, c'est-à-dire que parmi les 1.000.000+ articles, pas plus d'environ 1000 sont dans cette plage de temps donnée. Cette plage de temps se déplace à un rythme constant, par ex. chaque seconde, la plage de temps est déplacée d'une seconde. En outre, l'utilisateur peut ajuster la plage de temps à tout moment ("se déplacer" dans l'ensemble de données) ou définir des filtres supplémentaires (par exemple, filtrer par du texte). Jusqu'ici je n'étais pas inquiet au sujet de la performance, essayant d'obtenir les autres choses correctes, et seulement travaillé avec de plus petits ensembles de test. Je ne suis pas sûr de savoir comment aborder ce problème efficacement et je serais heureux pour chaque contribution. Merci.

Edit: Le langage utilisé est C# 4.

Mise à jour: Je suis maintenant en utilisant un arbre intervalle, la mise en œuvre peut être trouvée ici: https://github.com/mbuchetics/RangeTree

Il est également livré avec une version asynchrone qui reconstruit l'arbre à l'aide la bibliothèque parallèle de tâches (TPL).

Answer 1

Insère de nouveaux éléments dans une liste triée. Cela vous permettrait de sélectionner une gamme assez facilement. Vous pouvez aussi utiliser linq si vous le connaissez.

Answer 2

Utilisez SortedList en fonction de l'horodatage.

Tout ce que vous avez à faire est de mettre en œuvre une recherche binaire sur les clés triées dans la liste triée pour trouver la limite de votre sélection qui est assez facile.

Answer 3

Nous avons eu un problème similaire dans notre développement - nous avons dû collecter plusieurs millions d'éléments triés par une clé puis exporter une page à la demande. Je vois que votre problème est similaire.

Aux fins, nous avons adapté la structure red-black tree, de la manière suivante:

• nous avons ajouté l'itérateur, donc nous pourrions obtenir un objet « next » o (1)
• nous avons ajouté trouver le iterator du 'index', et a réussi à le faire en O (log n)

RB Tree a O (log n) la complexité d'insertion, donc je suppose que vos insertions tiennent dans bien là.

next() sur l'itérateur a été implémenté en ajoutant et en maintenant la liste chaînée de tous les nœuds feuilles - notre implémentation initiale RB Tree adoptée ne l'incluait pas.

RB Tree est également cool car il vous permet d'affiner la taille du nœud en fonction de vos besoins. En expérimentant, vous serez en mesure de trouver les bons chiffres qui correspondent à votre problème.