Le moyen le plus efficace de rechercher une chaîne dans une liste de chaînes?

Question

Je développe un client de messagerie personnalisé en C#. L'une des exigences évidentes est que je ne télécharge pas les messages déjà téléchargés. Ceci est fait en comparant une chaîne d'identification unique aux messages stockés dans ma base de données.

La base de données stocke les e-mails pour plusieurs utilisateurs et plusieurs comptes afin que l'ID unique ne soit pas nécessairement unique dans ma base de données.

Actuellement, j'ai quelque chose comme ceci:

List<String> DownloadedUIDs = BLL.EmailsDataSource.ViewEmailUIDs(AccountNo);  
foreach (string uid in serveruids) { 
    if (DownloadedUIDs.Contains(uid)) continue; // don't download messages we already have 
    ... 
} 

Je sais que la méthode contains() effectue une recherche linéaire qui est très inefficace. Si 5000 courriels sont stockés sur le serveur, 5000 recherches linéaires doivent être faites sur une liste de 5000 courriels pour déterminer si le courriel existe déjà. Est-ce que je verrais de meilleures performances demandant à SQL Server de commander les ID uniques, puis d'effectuer une recherche binaire ou de stocker les ID uniques dans une table de hachage? Ou en utilisant une autre structure de données?

Quelqu'un connaît-il des comparaisons de performance similaires qui ont été faites?

Answer 1

j'ai décidé de faire des tests de performance et ce sont les résultats que j'ai eu (de se connecter au serveur de messagerie pour vérifier tous les 3000 e-mails a été téléchargé):

1. Unsorted List = 418ms
2. Liste Trier = 329ms
3. Set = 312ms Classé
4. Trier la liste + binaire Recherche = 310ms
5. HashSet = 305ms

Il semble donc donné mes données au moins que HashSet sont plus rapides à faire cela mais il y a peu à choisir entre les 4 méthodes optimisées.

Answer 2

Ma suggestion est l'un des deux éléments suivants:

1. Effectuer la recherche dans la base de données à l'aide d'un index qui contient toutes les colonnes qui, ensemble, un identifiant unique. La recherche est alors une sélection simple.
2. Utilisez une Hashmap.

Answer 3

Vous pouvez stocker les messages dans une structure arborescente binaire indexée par son ID utilisateur. De cette façon, si vous finissez par essayer d'ajouter un message qui existe déjà, vous frappez le cas current_node.uid == new_node.uid et il peut être supprimé en tant que doublon.

De cette façon, votre système subit moins de changements et vous profitez des performances de b-trees! = D

Answer 4

Je suis conscient que la réponse suivante ne répond pas explicitement à vos questions. Cependant, je crois que cela répond au cœur de votre question qui est de ne pas autoriser les enregistrements en double dans la table db tout en maintenant les performances du système de qualité.

Au lieu de vérifier les e-mails en double avant d'insérer un e-mail, pensez/tester la logique suivante:

1. Spécifiez une contrainte de clé unique sur votre table email db
2. try/catch votre instruction INSERT pour une violation unique,

Cette méthode non seulement garantit éviter les e-mails en double, mais évite aussi le searc linéaire h préoccupation que vous avez mentionné.

Bien que cette méthode puisse entraîner une légère baisse des performances par rapport à une vérification SELECT, elle ne le fera que si une violation est détectée. Donc, si vous pensez que le risque de courriels en double est très faible (une véritable exception), alors vous pouvez trouver que cette méthode est la plus efficace (et infaillible) par rapport à une vérification SELECT.

Pour sauvegarder mon point, un peu, consultez « Leçon n ° 4 » de la liste de Paul Nielsen de « 10 Lessons from 35k tps »