0
votes

Dictionnaire à la fois sensible à la casse et insensible

J'ai besoin d'une structure de données comme Dictionnaire où je pouvais faire à la fois des recherches sensibles à la casse et insensibles.

Je cherche à améliorer la durée O (n) que je peux obtenir avec une liste > en itérant avec une affaire avec une casse sensible ou insensible stringcomparer .

Ceci est destiné à une bibliothèque où je souhaite que l'utilisateur final sélectionne une sensibilité de cas sur l'appel de la méthode . (Sinon, je pourrais créer un dictionnaire différent avec la sensibilité activée / désactivée dans le constructeur de classe)

Des idées?


18 commentaires

Vous pouvez créer 2 dictionnaires. Celui qui stocke les clés toutes majuscules (ou minuscules) et une qui stocke les clés dans la forme sensible à la case.


Droite, mais comment quantifier combien d'entrées si cette double structure doit-elle avoir pour bénéficier de la performance plus importante que de doubler les coûts de la mémoire et de l'augmentation du coût (2x) ajout ().


Je ne comprends pas - pourquoi ne pouvez-vous pas transmettre le type de comparateur que vous souhaitez utiliser? Dis-vous que le dictionnaire conçu a des clés différentes avec des caractères similaires, comme "premier" et "premier" ? Ou est-ce juste pour la recherche?


@Rufusl i Recevez d'abord la liste des valeurs avec un boîtier inconnu et la plus tard, l'utilisateur effectue des recherches sensibles à la casse ou insensibles. Dictionnaire permet uniquement de définir la sensibilité lorsque vous créez le dictionnaire. Une fois créé, il est sensible ou insensible.


var comparateur = stringcomparer.ordininignorecase; var coédictionnerdictionner = nouveau dictionnaire (comparateur); définit essentiellement le comparateur à utiliser


NVM ... vient de voir votre autre commentaire


Droite, mais comment quantifier combien d'entrées si cette double structure doit-elle avoir pour bénéficier de la performance plus importante que le coût de la mémoire de doublage et le coût augmenté (2x) ajoutez (code> "https://ericlippert.com/2012/12/17/performance-rant/" rel = "nOfollow Noreferrer"> Ericlippert.com/2012/12/17/performance-Rant


Je suggérerais de créer un dictionnaire insensible à un cas, de faire toutes les recherches initialement, et lorsqu'on nécessite une recherche sensible à la casse, filtrez les résultats en effectuant une comparaison sensible à la casse.


Honnêtement, si la recherche est par entrée de l'utilisateur, je ne suis pas convaincu un dictionnaire est la bonne structure de données. La plupart des gens s'attendront à une recherche de chaîne correspondant à une sous-chaîne, par exemple, selon laquelle un dictionnaire ne gère pas bien. Y a-t-il une raison particulière pour laquelle vous ne stockez pas ces données dans une base de données et utilisez SQL pour la questionner?


Vous allez contourner votre propre dictionnaire. Le premier type est une clé, pas une recherche de recherche. Donc, les règles à ce sujet sont assez réparées. Le gros problème est que cela vous coûtera la performance. Comme je l'ai récemment appris, la dictioanerie utilise la mécanique de la haquetable pour accélérer la comparaison clé et votre approche éviterait que la moitié du temps.


Peut-être que cela fonctionnerait: Valeur Var = dict.firstambordefault (kvp => kvp.key.equals ("Recherche", StringComParonS.ordinalInignorecase)). Valeur; ne va pas être super rapide, cependant.


@Rufusl & Netmage Vos propositions (utilisation du dictionnaire pour la sensibilité O (n * log) et pour les entrées o (n)) au moins améliorent l'un des deux scénarios sans coûts nouveaux. Merci


Pouvez-vous en dire plus sur le nombre d'entrées de ce dictionnaire seront des collisions sous l'insensibilité des cas? C'est-à-dire que vous attendez-vous à avoir japon et japon dans le dictionnaire, comme, deux ou trois collisions, ou si vous attendez d'avoir bananarama , bananarama , bananarama , ... avec des dizaines ou des centaines ou des milliers de collisions? Cela fait une différence quel algorithme vous devriez choisir.


@ERICLIPPERT Comme ce code est une bibliothèque, cela dépend de l'utilisateur final. Typiquement, il s'agirait de moins de 100 éléments sans collision (des cas différents doivent être résolus avec la recherche insensible à l'insensibilité, mais une utilisation inappropriée pourrait être à 100 000 collisions)


@mjwills Malheureusement, cela ne fonctionnera pas car vous devez conserver la clé de la casse originale, vous avez donc besoin de quelque chose comme Dictionnaire > ou j'ai choisi d'utiliser Dictionnaire > Envelopper un dictionnaire externe insensible à une casse autour de plusieurs dictionnaires intérieurs sensibles à la casse.


@Gerardogrignoli: Pourquoi vous souciez-vous si une utilisation "inappropriée" donne de mauvais résultats? Si les utilisateurs abusent de votre outil, ils ont choisi le mauvais outil pour le travail. Si vous vous souciez de ce scénario, vous avez un problème assez difficile à résoudre et vous ne devez pas utiliser un dictionnaire hors du plateau. Vous devriez rechercher des affaires abusives que vous vous souciez de créer un dictionnaire spécial conçu pour avoir un bon comportement face à la maltraitance.


Après avoir pensé de plus en plus de commentaires, je pense qu'une classe appropriée devrait avoir une abstraction en face de la mise en œuvre - elle devrait présenter comme un dictionnaire sensible à la casse même s'il est implémenté comme un dictionnaire insensible à la casse enveloppé autour des dictionnaires sensibles à la casse. Je vais mettre à jour ma réponse.


J'ai ré-écrit ma réponse basée sur mes nouvelles pensées.


5 Réponses :


1
votes

Vous pouvez simplement utiliser un dictionnaire ordinaire mais définir une méthode d'extension pour effectuer une recherche insensible à une casse-insensible: xxx

ou, si vous voulez vraiment, vous pouvez sous-classer le dictionnaire et faire ce qui précède un membre d'instance approprié.


2 commentaires

Cela fonctionnerait mais afaict, c'est toujours O (n) comme la liste > Mise en œuvre, non?


(errata) Cela me permet d'utiliser le dictionnaire de manière régulière pour la sensibilité des cas, O (1). Et retomber à O (n) pour l'insensibilité au cas par cas, sans doubler les structures de données. C'est une amélioration!



-1
votes

Vous ne serez certainement pas autour de votre propre dictioanry (dérivé). La première valeur est une clé. En tant que tel, il est destiné uniquement à correspondance exacte , pas comme une correspondance non-sensible. En fait, c'est encore pire que:

J'ai récemment appris que le dictionnaire est aussi notre hashtable générique. Il utilise l'approche Hashtable (obtenir un hash pour chaque clé et chaque entrée et comparant celui-ci d'abord), pour accélérer la comparaison, surtout sur des trucs comme des cordes. Donc, lorsque vous regardez une clé, il passe à travers la collecte de clé et:

  1. comparez les hachages. S'ils ne correspondent pas, cela ne peut pas être la clé.
  2. S'ils correspondent, faites la comparaison complète du type. Les colissions de hachage sont une chose, de sorte que le hachage ne peut être utilisé que pour un filtrage précoce "pas un match".

    Vos exigences pausent un peu cela. Tout à fait. En fait, vous vous retrouveriez avec des matchs non remerciements au hasch, quand il devrait match.

    La la première solution serait d'arrêter d'essayer de le faire en code et d'aller à un SGBD approprié à la place. Ils ont tendance à avoir un soutien à toutes les comparaisons bizarres que vous pourriez penser. Avec de nombreuses façons de les accélérer, comme des index. Il devrait y avoir une base de données en cours de traitement là-bas. Mais peu de gens sont désireux d'aller cette route.

    La solution Deuxième solution Je peux penser que vous pouvez essayer de réécrire le dictionnaire, avec aussi peu de travail que Nessaisery. Quelques idées:

    • La clé ne doit être stockée intermédiaire que dans la majuscules ou les minuscules, les ragardles que l'utilisateur entra. Je vais asposer minuscule, car il semble intuitif pour moi et juste un appel de .ToLower () Away.
    • Vous devez stocker la clé complète, le boîtier et tous. Pour la simplicité, je voudrais ajouter un champ pour HTAT à la valeur, vous asmant que vous êtes vraiment certain que personne ne le modifiera.
    • Lorsque vous recherchez une clé, utilisez d'abord le match de construction pour la version Lowcase de l'entrée. Ensuite (si Nesseary) Vérifiez également la clé d'origine, avant de signaler une correspondance / non.

      Vous ajoutez essentiellement une étape 3 à ma liste ci-dessus:

      1. Si le boîtier minuscule de l'entrée correspond à la clé (minuscule) et que la sensibilité de la case est requise, vérifiez maintenant la touche de boîtite stockée par rapport à l'entrée en panne

        J'espère que quelque chose que de modifier les routines Ajouter et à trouver. Des trucs comme supprimer doivent utiliser la fonction de recherche pour trouver d'abord l'élément. C'est un peu hacky. Idéalement, vous souhaitez masquer les internes de la manière dont vous faites cela de l'utilisateur, de sorte que la liste des clés enchevêtrées devrait être privée. De corbe qui signifie avoir à toucher plus de code.


0 commentaires

2
votes

Après avoir pensé encore et lire les commentaires, je pense que la meilleure implémentation consiste à étendre ce qui semble être un dictionnaire sensible à la casse code> avec de nouvelles propriétés et méthodes insensibles. Étant donné que la mise en œuvre est basée sur un dictionnaire insensible à une casse-insensible CODE> détenant des sous-dictionnaires sensibles à la casse, et c # n'a pas d'héritage privé, il semble préférable de simplement implémenter un nouveau dictionnaire code > Wrapper.

True
False
True
4
6

6
5


0 commentaires

0
votes

Vous pouvez utiliser nouveau dictionnaire où les touches sont toujours minuscules (voir ci-dessous), mais ...

a. UTILISATEUR RECHERCHE RECHERCHE STRING.CONTAINES CODE> ou REGEX.Amatch CODE> H1>

(j'ai ajouté cela plus tard) EM> P> P> P> P> P> P> P > Je pense que vous pouvez finir par utiliser string.Contains code> (ou peut-être même regex.ismatch code>) afin que vos recherches puissent attraper des correspondances partielles. P>

REGEX.AISMATCH H2>
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp4
{

    class SO
    {
        public int Number { get; set; }

        public int Rep { get; set; }
    }

  class Program
  {
      public static void Main(string[] args)
      {
        // Preload linq
        var _ = new []{"•`_´•"}.FirstOrDefault( k => k == "(O_O)" );

        foreach( int noOfSearches in new []{1000, 10000, 100000, 1000000} ) 
          foreach( int noOfItems in new []{100, 1000} ) 
          {
            var d1 = new Dictionary<string, SO>();

            for(int i = 0; i < noOfItems; i++) {
              d1.Add($"Name {i}", new SO {Number = i, Rep = i *2});
            }

            var d2 = new Dictionary<string, (string CaseSensitiveKey, SO Data)>();
            foreach (var entry in d1)
            {
                d2.Add(entry.Key.ToLower(), (entry.Key, entry.Value));
            }


            Console.WriteLine($"noOfSearches: {noOfSearches}");
            Console.WriteLine($"  noOfItems: {noOfItems}");

            Console.Write("    Lowercase key way:".PadRight(30));
            PrimitiveSpeedTest( (term, isCS) => LowerCaseKeyWay(d2, term, isCS), noOfItems, noOfSearches);
            Console.Write("    Linq way".PadRight(30));
            PrimitiveSpeedTest( (term, isCS) => LinqWay(d1, term, isCS), noOfItems, noOfSearches);
          }

      }

      private static void PrimitiveSpeedTest(Func<string, bool, SO> search, int noOfItems, int noOfSearches)
      {
          var count = 0;
          Stopwatch sw = Stopwatch.StartNew();
          for (int i = 0; i < noOfSearches; i++)
          {
            var originalTerm = $"Name {i % (noOfItems*2)}"; // Some found, some not found
              foreach (var term in new[] { originalTerm, originalTerm.ToLower() })
                  foreach (var isCS in new[] { true, false })
                  {
                      var so = search(term, isCS);
                      if (so != null) count++;
                      //Console.WriteLine($"{term}/case-sensitive:{isCS}: {Search(d, term, isCS)?.Rep}");
                  }

          }
          var elapsed = sw.Elapsed;

          Console.WriteLine($"Elapsed {sw.ElapsedMilliseconds}ms, count found: {count} ");
      }

      public static SO LowerCaseKeyWay(Dictionary<string, (string CaseSensitiveKey, SO Data)> d, string term, bool isCS)
        => d.TryGetValue(term.ToLower(), out var item)
                ? !isCS
                      ? item.Data
                      : term == item.CaseSensitiveKey ? item.Data : null
                : null;

      static public T LinqWay<T>(Dictionary<string,T> source, string key, bool caseSensitive)
      {
          //Original: if (caseSensitive) return source[key];
          if(caseSensitive) return source.ContainsKey(key) ? source[key] : default;
          key = source.Keys.FirstOrDefault( k => String.Compare(key, k, StringComparison.CurrentCultureIgnoreCase) == 0);
          //Original: if (key == null) throw new KeyNotFoundException();
          if (key == null) return default;
          return source[key];
      }
  }
}


0 commentaires

0
votes

Depuis le dictionnaire hachage la clé, vous devez utiliser un dictionnaire Dictionary > .


Ajout d'une clé:

  • Convertissez la clé de la casse mixte donnée à tous les minuscules;
  • Obtenez le dictionnaire à la clé minuscule;
  • ajoutez-le à ce dictionnaire.

    Recherche insensible à la casse:

    • Convertissez la clé mixte en minuscules;
    • Obtenez le dictionnaire pour cette clé minuscule;
    • itérer sur les valeurs du dictionnaire.

      recherche sensible à la casse

      • Convertissez la clé mixte en minuscules;
      • Obtenez le dictionnaire pour cette clé minuscule;
      • recherche une clé de cassette dans le dictionnaire obtenu dans l'étape ci-dessus.

3 commentaires

Je ne suis jamais un fan d'avoir à tolower la clé, puisque quelqu'un peut oublier de le faire. Je préférerais que le dictionnaire externe ait un comparateur insensible à la casse à la place selon le commentaire de @ Netmage.


@mjwills: Je suis d'accord. J'aime écrire mon code imbécile aussi bien. J'ai figuré une solution plus détaillée obfusquer l'idée. Une autre solution détaillée consiste à créer une classe wrapper qui encapsule toutes ces fonctionnalités et permet un paramètre booléen pour la sensibilité à la casse.


@mjwills: Une autre bonne solution, qui s'étendrait également aux détails de la surcharge mentales consiste à modifier cet algorithme de hachage. Nous pouvons écrire notre propre implémentation de hachage qui prend en compte la taille de la structure sous-jacente. Cela pourrait permettre l'itération sur toutes les clés identiques en cas d'ignorée.