String.Substring () semble goulot d'étranglement ce code

Question

Introduction

J'ai ce favori de l'algorithme que j'ai fait il y a quelques temps je suis toujours écrit et ré-écrit dans de nouveaux langages de programmation, les plates-formes etc. comme une sorte de référence. Bien que mon principal langage de programmation C# je viens de littéralement copier-collé le code et changé la syntaxe légèrement, construit en Java et l'a trouvé pour exécuter 1000x plus rapide.

Le Code

Il y a un peu de code, mais je ne vais présenter cet extrait de ce qui semble être le principal problème:

for (int i = 0; i <= s1.Length; i++) 
{
    for (int j = i + 1; j <= s1.Length - i; j++)
    {
        string _s1 = s1.Substring(i, j);
        if (tree.hasLeaf(_s1))
         ...

Les Données

Il est important de souligner que la chaîne s1 dans ce test particulier est de longueur 1 million de caractères (1 MO).

Les mesures

J'ai profilé mon exécution de code dans Visual Studio parce que je pensais que la manière dont je construis mon arbre ou de la façon dont je le traverse n'est pas optimal. Après examen des résultats, il apparaît que la ligne string _s1 = s1.Substring(i, j); est accessible à plus de 90% du temps d'exécution!

Observations Supplémentaires

Une autre différence que j'ai remarqué, c'est que, bien que mon code est mono-thread Java gère pour l'exécuter à l'aide de tous les 8 cœurs (100% d'utilisation CPU) alors que même avec en Parallèle.For() et multi threading techniques de mon code C# parvient à utiliser de 35 à 40% au plus. Puisque l'algorithme évolue linéairement avec le nombre de cœurs (et la fréquence), j'ai compensé pour cela, et encore de l'extrait de code en Java exécute l'ordre de grandeur de 100 1000x plus rapide.

Le raisonnement

Je suppose que la raison pour laquelle ce qui se passe a à voir avec le fait que les chaînes de caractères en C# sont immuables sorte de Chaîne.Substring() a pour créer une copie et puisque c'est l'intérieur d'un ensemble de boucle avec un nombre d'itérations je présume que beaucoup de copie de ramassage des ordures et la collecte est en cours, cependant, je ne sais pas comment la sous-Chaîne est implémenté en Java.

Question

Quelles sont mes options à ce point? Il n'y a pas moyen de contourner le nombre et la longueur des chaînes (ce qui est déjà optimisé au maximum). Est-il une méthode que je ne connais pas (ou à la structure de données peut-être) qui pourrait résoudre ce problème pour moi?

Demande Minimale de mise en Œuvre (de commentaires)

J'ai laissé de côté la mise en œuvre du suffixe de l'arbre, qui est O(n) dans la construction et O(log(n)) dans la traversée de

public static double compute(string s1, string s2)
{
    double score = 0.00;
    suffixTree stree = new suffixTree(s2);
    for (int i = 0; i <= s1.Length; i++) 
    {
        int longest = 0;
        for (int j = i + 1; j <= s1.Length - i; j++)
        {
            string _s1 = s1.Substring(i, j);
            if (stree.has(_s1))
            {
                score += j - i;
                longest = j - i;
            }
            else break;
         };

        i += longest;
    };
    return score;
}

Capture d'écran extrait de le profiler

Remarque cela a été testé avec string s1, la taille de 300.000 caractères. Pour une raison de 1 million de caractères ne se termine jamais en C# alors qu'en Java il faut seulement 0,75 secondes.. La mémoire consommée et le nombre de collectes ne semblent pas indiquer un problème de mémoire. Le pic a été d'environ 400 MO, mais compte tenu de l'énorme suffixe de l'arbre ce qui semble être normal. Pas bizarre ordures collecte des motifs tachetés soit.

Answer 1

Question D'Origine

Après avoir une glorieuse bataille qui a duré deux jours et trois nuits (et incroyable d'idées et de réflexions dans les commentaires) j'ai enfin réussi à résoudre ce problème!

J'aimerais poster une réponse pour tout le monde courir dans des problèmes similaires où l' string.Substring(i, j) fonction n'est pas une solution acceptable pour obtenir la sous-chaîne d'une chaîne, car la chaîne est trop grande et vous ne pouvez pas se permettre la copie effectuée par string.Substring(i, j) (il doit en faire une copie, parce que C# les chaînes sont immuables, pas moyen de contourner cela) ou de l' string.Substring(i, j) est appelé à un grand nombre de fois sur la même chaîne (comme dans mes boucles for imbriquées) donnant le garbage collector est un moment difficile, ou, comme dans mon cas les deux!

Les tentatives de

J'ai essayé beaucoup ont suggéré des choses telles que le StringBuilder, Ruisseaux, non géré, l'allocation de la mémoire à l'aide de Intptr et le Maréchal au sein de l' unsafe{} bloc et même la création d'un IEnumerable et les taux de retour les personnages par référence dans les positions. Toutes ces tentatives ont échoué ultimatively parce que d'une certaine forme de joindre des données devait être fait, comme il n'était pas facile pour moi de parcourir mon arbre, caractère par caractère, sans compromettre les performances. Si seulement il y avait un moyen de s'étendre sur plusieurs adresses de mémoire dans un tableau à la fois, comme vous pourrez vous en C++ avec certains de l'arithmétique des pointeurs.. sauf qu'il n'y est.. (crédits de @Ivan Stoev du commentaire)

La Solution

La solution a l'aide d' System.ReadOnlySpan<T> (ne pouvait pas être System.Span<T> en raison de cordes immuable) qui, entre autres choses, nous permet de lire des sous-tableaux des adresses de la mémoire dans un tableau existant, sans création de copies.

Ce morceau de code affiché:

string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
    score += j - i;
    longest = j - i;
}

A été modifié comme suit:

if (stree.has(i, j))
{
    score += j - i;
    longest = j - i;
}

Où stree.has() maintenant prend deux entiers (position et la longueur de la chaîne) et n':

ReadOnlySpan<char> substr = s1.AsSpan(i, j);

Notez que l' substr variable est littéralement une référence à un sous-ensemble de caractères de la première s1 tableau et non pas une copie! (L' s1 variable a été rendue accessible à partir de cette fonction)

Notez qu'au moment de la rédaction de ce que je suis en utilisant C#et 7.2 .NET Framework 4.6.1 ce qui signifie que pour obtenir la Durée de fonction, j'ai dû aller à Projet > Gérer les Packages NuGet, cochez la case "Inclure préliminaire" case à cocher et parcourir pour le Système.De la mémoire et de l'installer.

De ré-exécuter le test initial (sur des chaînes de longueur 1 million de caractères, c'est à dire de 1 mo) l'augmentation de la vitesse de+ de 2 minutes (je me gave d'attendre au bout de 2 minutes) à ~86 milisecondes!!