alternative à la classe de chaîne .net

Étant donné que je planifie une application qui contiendra ENCORE une grande partie de ses données en mémoire, j’aimerais avoir une sorte de classe de chaîne «compacte», dont une au moins contiendra une chaîne au format non supérieur à la version ASCII de la chaîne terminée par zéro.

Connaissez-vous une telle implémentation de classe de chaînes – elle devrait avoir des fonctions utilitaires comme la classe de chaîne d’origine.

MODIFIER:

Je dois sortinger les chaînes et pouvoir les parcourir, pour ne citer que quelques opérations que je vais utiliser.

Idéalement, il serait compatible avec System.Ssortingng, de sorte que les actions de recherche et de remplacement de base optimiseraient l’empreinte mémoire de l’application.

NOMBRES:

Je pourrais avoir 100 000 enregistrements de chaque enregistrement ayant jusqu’à 10 chaînes de 30 à 60 caractères. Alors:

100000x10x60 = 60000000 = 57 caractères Méga. Pourquoi ne pas utiliser 60 Mo de RAM pour cela au lieu de 120 Mo de RAM? Les opérations seront plus rapides, tout sera plus serré.

Les arbres seront utilisés pour la recherche, mais ne seront pas utiles dans les parsings de regex que je compte faire.

J’ai en fait eu un problème similaire, mais avec des parameters de problèmes quelque peu différents. Mon application traite de deux types de chaînes – les chaînes relativement courtes mesurant entre 60 et 100 caractères et les plus longues ayant entre 100 et 1000 octets (moyennes d’environ 300).

Mon cas d’utilisation doit également prendre en charge le texte Unicode, mais un pourcentage relativement faible des chaînes comporte des caractères non anglais.

Dans mon cas d’utilisation, j’exposais chaque propriété Ssortingng en tant que chaîne native, mais la structure de données sous-jacente était un octet [] contenant des octets Unicode.

Mon cas d’utilisation nécessite également de rechercher et de sortinger ces chaînes, d’obtenir des sous-chaînes et d’autres opérations de chaîne courantes. Mon dataset mesure par millions.

L’implémentation de base ressemble à ceci:

byte[] _myProperty; public Ssortingng MyProperty { get { if (_myProperty== null) return null; return Encoding.UTF8.GetSsortingng(value); } set { _myProperty = Encoding.UTF8.GetBytes(value); } } 

Les performances ont été atteintes pour ces conversions, même lorsque la recherche et le sorting étaient relativement faibles (environ 10 à 15%).

Ce fut bien pendant un moment, mais je voulais réduire davantage les frais généraux. L’étape suivante consistait à créer un tableau fusionné pour toutes les chaînes d’un object donné (un object contiendrait une chaîne courte et une chaîne longue, ou quatre chaînes courtes et une chaîne longue). il y aurait donc un octet [] pour chaque object et ne nécessiterait que 1 octet pour chacune des chaînes (sauf leurs longueurs qui sont toujours <256). même si vos chaînes peuvent être plus longues que 256 et que int est toujours moins chère que la surcharge de 12-16 octets pour l'octet [].

Cela réduisait une grande partie de la surcharge d’octets, et ajoutait un peu de complexité, mais pas d’impact supplémentaire sur les performances (la passe d’encodage est relativement coûteuse par rapport à la copie de tableau impliquée).

cette implémentation ressemble à ceci:

 byte _property1; byte _property2; byte _proeprty3; private byte[] _data; byte[] data; //i actually used an Enum to indicate which property, but i am sure you get the idea private int GetStartIndex(int propertyIndex) { int result = 0; switch(propertyIndex) { //the fallthrough is on purpose case 2: result+=property2; case 1: result+=property1; } return result; } private int GetLength(int propertyIndex) { switch (propertyIndex) { case 0: return _property1; case 1: return _property2; case 2: return _property3; } return -1; } private Ssortingng GetSsortingng(int propertyIndex) { int startIndex = GetStartIndex(propertyIndex); int length = GetLength(propertyIndex); byte[] result = new byte[length]; Array.Copy(data,startIndex,result,0,length); return Encoding.UTF8.GetSsortingng(result); } 

Le getter ressemble donc à ceci:

 public Ssortingng Property1 { get{ return GetSsortingng(0);} } 

Le setter est dans le même esprit – copiez les données originales dans deux tableaux (entre 0 start à startIndex et entre startIndex + length à length), et créez un nouveau tableau avec les 3 tableaux (dataAtStart + NewData + EndData) et définissez le longueur du tableau à la variable locale appropriée.

Je n’étais toujours pas satisfait de la mémoire sauvegardée et du travail très dur de l’implémentation manuelle de chaque propriété. J’ai donc conçu un système de pagination compressée en mémoire qui utilise QuickLZ incroyablement rapide pour compresser une page entière. Cela m’a donné beaucoup de contrôle sur le compromis temps-mémoire (qui est essentiellement la taille de la page).

Le taux de compression pour mon cas d’utilisation (comparé au byte [] plus efficace store) s’approche de 50% (!). J’ai utilisé une taille de page d’environ 10 chaînes par page et regroupé des propriétés similaires (qui ont tendance à avoir des données similaires). Cela a ajouté un surcoût supplémentaire de 10-20% (en plus de la passe d’encodage / décodage qui est toujours requirejse). Le mécanisme de pagination met en cache les pages récemment accédées jusqu’à une taille configurable. Même sans compression, cette implémentation vous permet de définir un facteur fixe sur la surcharge pour chaque page. L’inconvénient majeur de mon implémentation actuelle du cache de page est qu’avec la compression, il n’est pas compatible avec les threads (sans ce problème, il n’y en a pas).

Si vous êtes intéressé par le mécanisme de pagination compressé, faites-le moi savoir (j’ai cherché une excuse pour l’ouvrir).

EDIT: J’ai maintenant un article sur ce sujet qui contient beaucoup plus de détails.


En fonction de vos chiffres:

Je pourrais avoir 100 000 enregistrements de chaque enregistrement ayant jusqu’à 10 chaînes de 30 à 60 caractères.

Commençons par append la surcharge de l’object – une chaîne prend environ 20 octets (IIRC – peut-être plus sur un CLR 64 bits) plus les données réelles, en raison de la surcharge inévitable des objects et de leur longueur. Faisons les maths à nouveau:

Utilisation de ssortingng: 1 million d’objects à 20 + 120 octets = 140 Mo

Utilisation d’une nouvelle classe: 1 million d’objects à 20 + 60 octets = 80 Mo

Toujours une différence de 60 Mo, mais proportionnellement moins que ce à quoi vous vous attendiez. Vous n’économisez que 42% de l’espace au lieu de 50%.

Maintenant, vous parlez de choses plus rapides: étant donné que le CLR est nativement conscient de la ssortingng , je pense qu’une classe tierce ne sera pas capable de faire correspondre la vitesse de certaines de ses opérations, et vous devrez en mettre beaucoup. de travailler pour que beaucoup d’autres aient la même vitesse. Certes, vous aurez une meilleure cohérence du cache et si vous pouvez ignorer les problèmes de culture, cela devrait vous faire gagner un peu de temps en rendant toutes les comparaisons ordinales.

Pour des raisons de 60MB, je ne m’embêterais pas. C’est une toute petite différence de nos jours – pensez au nombre de clients supplémentaires que vous devrez gagner en réalisant ces petites économies afin de compenser le coût supplémentaire considérable lié au travail avec deux types de chaînes différents.

Cela étant dit, je suis assez tenté de l’implémenter moi-même comme un projet de blog comme Edulinq. Ne vous attendez à aucun résultat pendant des semaines ou des mois cependant 🙂

EDIT: Je viens de penser à un autre problème. Les nombres que nous avons ci-dessus ne sont pas vraiment corrects … parce que la classe de chaîne est spéciale. Il incorpore ses données directement dans l’object – contrairement aux autres types de données, à l’exception des tableaux, la taille d’une instance de ssortingng n’est pas fixe. il varie en fonction des données qu’il contient.

En écrivant votre propre classe AsciiSsortingng , vous ne seriez pas capable de faire cela – vous devriez incorporer une référence de tableau dans la classe:

 public class AsciiSsortingng { private readonly byte[] data; } 

Cela signifie que vous auriez besoin de 4 ou 8 octets supplémentaires pour la référence (CLR 32 ou 64 bits) et de la surcharge supplémentaire d’un object tableau (16 octets, IIRC) par chaîne.

Si vous l’avez conçu comme Java, prendre une sous-chaîne peut réutiliser le tableau d’octets existant (deux chaînes peuvent être partagées), mais vous aurez besoin d’une longueur et d’un décalage supplémentaires dans AsciiSsortingng . Vous perdriez également certains des avantages de la cohérence du cache.

Vous pouvez utiliser uniquement des tableaux d’octets bruts comme structure de données et écrire un tas de méthodes d’extension pour y agir … mais ce serait horrible, car vous ne pourriez pas faire la différence entre un tableau d’octets normal et un autre pour représenter une chaîne ASCII.

Une autre possibilité serait de créer une structure comme celle-ci:

 struct AsciiSsortingng { private readonly byte[] data; ... } 

Cela vous permettrait effectivement de taper à nouveau, mais vous devriez penser à des choses comme:

 AsciiSsortingng x = new AsciiSsortingng(); 

qui se retrouverait avec une référence de data nulle. Vous pourriez effectivement traiter cela comme si x était une valeur nulle, mais ce serait plutôt non idiomatique.

Autres structures de données

Je suggère que, étant donné votre désir de rechercher également à travers les valeurs de «chaîne» stockées, vous devriez envisager soit une structure Trie telle que Pasortingcia Trie ou, pour un meilleur amortissement de la mémoire, un graphique Word acyclique dirigé (désigné sous le nom DAWG) fonctionnerait mieux.

Leur construction prendrait plus de temps (bien qu’ils soient souvent utilisés dans les cas où le stockage sous-jacent lui-même représente assez bien cette forme pour permettre une construction rapide) et même si certaines opérations sont algorithmiquement supérieures, sont en fait plus lents, ils réduisent de manière significative l’empreinte mémoire de vos données tant qu’il ya une quantité raisonnable de répétitions.

Celles-ci peuvent être considérées comme des généralisations de la duplication (intégrée) fournie dans .net (et java et de nombreux autres langages gérés) d’internement de chaînes.

Si vous souhaitez spécifiquement conserver un ordre des chaînes de manière lexicographique (vous ne devez donc considérer qu’un seul caractère ou sharepoint code à la fois), le Pasortingcia Trie est probablement l’option préférable, en mettant en œuvre la commande par-dessus le DAWG. serait problématique.

Des solutions alternatives et plus ésotériques peuvent fonctionner si vous avez un domaine particulier de chaînes, notamment:

Encodage de la longueur d’exécution et autres formes de compression.

Au prix d’un access aléatoire à une chaîne et du risque d’utiliser réellement plus de mémoire si les entrées s’avèrent ne pas être comme prévu. Le codage de Huffman a tendance à bien fonctionner sur le texte anglais et est assez simple à réaliser, il a l’avantage que le dictionnaire peut être partagé entre toutes les entités du jeu tant que la dissortingbution de fréquence des lettres est comparable. Le sorting deviendrait problématique à nouveau.

Chaînes de longueur fixe.

Si vous savez que les chaînes sont petites et qu’elles ont presque toutes la même taille (ou exactement la même taille), vous pouvez les stocker dans des valeurs de taille fixe (même des structures si vous le souhaitez si le nombre de caractères est inférieur ou égal à 16). la limite d’utilisation dépendra ici de votre utilisation précise et peut dépendre fortement de la volonté de vous d’accorder votre code pour jouer avec ce design)

Vous pourriez créer une nouvelle structure de données pour les stocker, même si je pense que c’est exagéré.

Mais, si vous avez un tableau de chaque mot ou phrase commune, vous stockez l’index sous forme de tableau pour chaque mot.

Vous payez alors 4 octets pour chaque mot, mais si chaque mot est en moyenne de 3,6 caractères, vous économisez 3,2 octets pour chaque mot, en moyenne, puisque vous payez une pénalité de 2 octets / lettre une fois / mot.

Mais, pour effectuer des recherches ou des sortings, vous allez avoir besoin de reconstruire la chaîne au moins pour une courte période.

Vous voudrez peut-être repenser la conception de votre programme, car de nombreux programmes utilisent de grandes quantités de données et peuvent fonctionner dans une mémoire relativement restreinte.

Eh bien, il y a la classe UTF8Encoding

 //Example from MSDN using System; using System.Text; public class Example { public static void Main() { Encoding enc = new UTF8Encoding(true, true); ssortingng value = "\u00C4 \uD802\u0033 \u00AE"; try { byte[] bytes= enc.GetBytes(value); foreach (var byt in bytes) Console.Write("{0:X2} ", byt); Console.WriteLine(); ssortingng value2 = enc.GetSsortingng(bytes); Console.WriteLine(value2); } catch (EncoderFallbackException e) { //Encoding error } } } 

Cependant, comme Jon le dit, chaque fois que vous voulez l’utiliser avec une méthode qui attend une chaîne (la plus grande partie de la bibliothèque .Net), vous devrez la convertir de toute façon en une chaîne Unicode normale si vous nous en avez donné plus. informations sur ce que vous essayez de faire, peut-être pourrions-nous vous aider à trouver une meilleure solution?

Ou, si vous avez vraiment besoin de chaînes de caractères terminées par des octets non internationalisables de type tableau à octets bas, vous feriez mieux de simplement écrire ceci en C ++.

Combien de doublons attendez-vous? S’il y a beaucoup de doublons dans votre tableau, vous pouvez envisager d’implémenter un cache de chaînes (encapsuleur autour d’un Dictionary ) qui met en cache des instances de chaînes particulières et renvoie une référence à chaque instance en double il.

Vous pouvez combiner cela avec la vérification des chaînes internes, de sorte que vous utilisez toujours la version interne, si vous avez beaucoup de chaînes partagées sur tout le programme.

Selon vos données, cela pourrait donner un résultat bien meilleur que d’essayer d’optimiser le stockage de chaque chaîne individuelle.

Je pense que la clé de ceci est que chaque enregistrement a de nombreux champs de chaînes

En stockant tous les champs de chaîne pour chaque enregistrement dans un seul tableau de caractères, puis en utilisant un champ int présentant le décalage, vous pouvez réduire considérablement le nombre d’objects. (Chaque object a une surcharge d’environ 2 mots avant même que vous y mettiez des données.)

Vos propriétés pourraient alors être converties en / depuis des chaînes standard. Le ramasse-miettes est très efficace pour sortinger beaucoup de déchets de courte durée , donc la création de beaucoup de chaînes “tmp” lorsque les propriétés sont accessibles ne devrait pas être un problème.

(Maintenant, si beaucoup de champs de chaînes ne changent jamais, les choses deviennent beaucoup plus faciles)

Vous pouvez enregistrer la surcharge par object en ayant un grand octet [] qui stocke les caractères, puis un int-offset dans ce tableau en tant que “chaîne”.

Peut-être qu’un bon tableau de caractères à la mode répondrait à vos besoins.

Toutes ces chaînes sont-elles distinctes?

Dans la plupart des ensembles de données du monde réel, le nombre réel de chaînes distinctes ne serait probablement pas si élevé, et si vous tenez compte de l’installation de chaînes, la quantité réelle de mémoire consommée pourrait être considérablement inférieure à ce que vous pourriez penser.