Recherche rapide dans la plage en mémoire par rapport au tableau des enregistrements de + 5 millions

J’ai une table de firebase database avec + 5M d’enregistrements statiques en place. Structure simple: (début int, fin int, résultat int). Donc, j’ai un certain INT et j’ai besoin de trouver le résultat correspondant (int). Actuellement, la table de recherche est dans la firebase database, mais elle doit résider en mémoire, le plus souvent dans l’environnement sans access à la firebase database.

Ma solution doit exécuter cette logique sans access à la firebase database, en mémoire et très rapidement, car je dois traiter 1 000 transactions par seconde. La taille de l’ensemble étant légèrement supérieure à 50 Mo, je peux donc tout jeter dans la mémoire et lancer des recherches de plage pour la comparer, comme le décrit l’article suivant: Faire une recherche de plage en C # – comment l’implémenter . Mais je ne sais pas comment cela fonctionnera à une telle échelle.

  • Est-ce que je précharge cette table “au démarrage”? Ça peut prendre un moment.
  • Est-il possible de charger la table dans un fichier .dat et d’obtenir une recherche extrêmement efficace au moment de l’exécution?

BTW, je suis sur Azure, je ne suis pas sûr que l’utilisation de tables de stockage aide à la recherche …

les recherches binarys sont super rapides. Une recherche binary sur 50 millions d’enregistrements ne prend que 27 comparaisons pour trouver la réponse. Il suffit de le charger en mémoire et d’utiliser la recherche de plage que vous avez liée.

Si vous trouvez que c’est lent, commencez à optimiser:

  • Change l’object Range en struct au lieu de class
  • Codez manuellement votre propre algorithme de recherche binary qui (a) implémente directement le comparateur d’égalité au lieu d’appeler un IEqualityComparer et (b) utilise des pointeurs et autres astuces non sécuritaires pour désactiver la vérification des limites du tableau lors de la recherche.

Le code de recherche de plage auquel vous vous associez effectue une recherche binary. Les performances sont donc O(log n) . Je ne pense pas que vous puissiez faire mieux que cela pour une recherche de plage. La HashSet un HashSet est O (1), mais vous ne pouvez pas utiliser cette structure pour une recherche de plage.

5 millions d’albums, ce n’est pas énorme. Je vous suggère de mettre en œuvre une preuve de concept avec le code que vous associez au matériel que vous utiliserez en production et de mesurer les performances.

Vous pouvez certainement mettre cela dans un fichier séquentiel et le charger au démarrage. 50 Mo vont sortir du disque en moins d’une seconde. Et même si vous deviez l’parsingr sous forme de fichier texte, vous devriez pouvoir créer le tableau en une seconde. 5 millions d’enregistrements n’ont tout simplement pas une telle taille lorsque vous les traitez avec un processeur de 2 GHz (ou plus rapide).

La recherche binary de la liste est O (log n), donc le nombre maximal de sondes que vous ferez par recherche est de 24. Cela va être vachement rapide.

Il devrait être assez facile de charger en test quelque chose comme ça. Il suffit de le lancer et de voir combien de temps il faut pour effectuer, disons, 1 000 000 de recherches. Quelque chose comme:

 var clock = Stopwatch.StartNew(); for (int i = 0; i < NumIterations; ++i) { int val = GetRandomValueToSearchFor(); // however you do that Ranges.BinarySearch(val, RangeComparer); } clock.Stop(); // time per iteration is clock.TotalMilliseconds/NumIterations 

Cela vous permettra de déterminer le plus rapide possible pour interroger la chose. Je suppose que vous allez bien avec des milliers de transactions par seconde.