Dev Faq
8
votes

En C #, y a-t-il une sorte d'une sorte de tri qui permet une interrogation rapide (avec linq) pour la valeur la plus proche?

Je cherche une structure qui contient un jeu de double valeurs trié. Je veux interroger cet ensemble pour trouver la valeur la plus proche d'une valeur de référence spécifiée.

J'ai examiné la catégorie tritedlist , et cela me fait très bien. Cependant, puisque je n'ai pas besoin de paires de clé / valeur explicites. Cela semble être surchargé pour moi et je me demande si je pouvais faire plus vite.

Conditions:

  • La structure est initialisée une seule fois et ne change jamais (pas d'insertion / suppression)
  • La quantité de valeurs est comprise entre 100k.
  • La structure est interrogée souvent avec de nouvelles références, qui doivent exécuter rapide .
  • Pour la simplicité et la vitesse, la valeur de l'ensemble juste ci-dessous de la référence peut être renvoyée, pas en réalité la valeur la plus proche
  • Je veux utiliser LINQ pour la requête, si possible, pour la simplicité du code.
  • Je veux utiliser aucun code 3ème partie si possible. .NET 3.5 est disponible.
  • la vitesse est plus importée que l'empreinte mémoire

    i Utilisez actuellement le code suivant, où triéValues ​​ est le suivi précitée sortidlist xxx

    < Strong> Puis-je faire plus vite?

    Je ne suis pas sûr de 100% sûr, si ce code est vraiment sûr. IEnumerable , le type de retour de ma requête n'est plus défini par définition. Toutefois, un test d'unité avec une base de données de test importante a montré que c'est en pratique, cela fonctionne donc pour moi. Avez-vous des notes concernant cet aspect?

    p. Je sais qu'il existe de nombreuses questions similaires, mais aucune ne répond à mes besoins spécifiques. Surtout, il y a ce structure de données C # Dictionnaire mais sans valeur , mais le questionneur veut simplement vérifier l'existence de ne rien trouver.

0 commentaires

3 Réponses :

10
votes

La façon dont vous le faites est incroyablement lente car elle doit rechercher dès le début de la liste à chaque fois donnant O (n) performance.

Un meilleur moyen est de mettre les éléments dans une liste, puis Trier la liste. Vous dites que vous n'avez pas besoin de changer le contenu une fois initialisé, alors le tri une fois suffit.

Ensuite, vous pouvez utiliser Liste .binaireSearch pour trouver des éléments ou trouver le point d'insertion d'un élément s'il n'existe pas déjà dans la liste.

de la DOCS:

Valeur de retour

L'indice zéro de Article dans la liste triée , Si l'article est trouvé; Sinon, un nombre négatif qui est le bitwise complément de l'indice de la prochaine élément qui est plus grand que l'article ou, S'il n'y a pas d'élément plus grand, le complément bitwise du nombre.

Une fois que vous avez le point d'insertion, vous devez vérifier les éléments de chaque côté pour voir ce qui est le plus proche.

4 commentaires

Dépend de la fréquence à laquelle vous souhaitez trouver un élément le plus proche contre la fréquence à laquelle la liste est actualisée.

Voir la question. La liste n'aura jamais d'insertions ni de déménagements.

WOW, parlez de la violation de valeurs de retour.

Mark, ur da homme! Cela exécute environ 200 fois plus vite que ma version fournie.

1
votes

Pourriez-vous ne pas vous être utile en ce moment, mais .net 4 a un SITEDSET classe dans la BCL.

2 commentaires

Comment utiliser un tri pour trouver l'élément le plus proche dans le cas où l'élément exact n'existe pas?

De la même manière qu'il le fait actuellement. Je ne répondais pas à l'aspect de la question de la question, car vous avez déjà répondu. Ma réponse était destinée à pointer l'OP à une structure de données non KVP qu'il pourrait trouver utile.

-1
votes

Je pense que cela peut être plus élégant comme suit: Si vos articles ne sont pas triés: 

double nearest = values.OrderBy(x => x.Key).Last(x => x.Key <= requestedValue);

1 commentaires

Ce serait plus élégant, mais pas plus rapide que j'ai demandé. -1 pour ne pas répondre à la question.

Articles qui pourrait vous intéresser :

Calculer la différence dans l'échelle d'évaluation alphabétique
Ignorer la propriété de l'interface utilisateur Swagger
Comment détruire les éléments dynamiques du panneau dans le script Unity C #
Entity Framework Core 3.1 avec NetTopologySuite.Geometries.Point: SqlException: la valeur fournie n'est pas une instance valide de la géographie du type de données