Ssortingng.Subssortingng () semble geler ce code

introduction

J’ai cet algorithme favori que j’ai créé il y a un certain temps et que j’écris et ré-écris toujours dans de nouveaux langages de programmation, plates-formes, etc. Bien que mon langage de programmation principal soit C # Je viens de copier-coller le code et de modifier légèrement la syntaxe, de le construire en Java et de le rendre plus rapide.

Le code

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

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 de ce test est d’une longueur de 1 million de caractères (1 Mo).

Des mesures

J’ai profilé mon exécution de code dans Visual Studio car je pensais que la façon dont je construis mon arbre ou la façon dont je le parcourais n’est pas optimale. Après avoir examiné les résultats, il apparaît que la ssortingng _s1 = s1.Subssortingng(i, j); est accommodant pour plus de 90% du temps d’exécution!

Observations supplémentaires

Une autre différence que j’ai remarquée est que, bien que mon code soit à thread unique, Java parvient à l’exécuter en utilisant les 8 cœurs (100% d’utilisation du processeur), même avec Parallel.For () et les techniques multi-thread. 40% au maximum Puisque l’algorithme s’adapte de manière linéaire au nombre de cœurs (et de fréquence), je l’ai compensé et l’extrait de Java exécute toujours l’ordre de grandeur 100-1000x plus rapidement.

Raisonnement

Je suppose que la raison en est que les chaînes de caractères en C # sont immuables, alors Ssortingng.Subssortingng () doit créer une copie et, comme il se trouve dans une boucle nestede avec de nombreuses itérations, je suppose que beaucoup de copies sont nécessaires. la collecte des ordures est en cours, cependant, je ne sais pas comment Subssortingng est implémenté en Java.

Question

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

Mise en œuvre minimale requirejse (commentaires)

J’ai omis l’implémentation de l’arbre de suffixe qui est O (n) en construction et O (log (n)) en traversée

 public static double compute(ssortingng s1, ssortingng 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; }

Extrait de capture d’écran du profileur

Notez que ceci a été testé avec la chaîne s1 de la taille de 300 000 caractères. Pour une raison quelconque, 1 million de caractères ne se termine jamais en C # alors qu’en Java, cela ne prend que 0,75 seconde. La mémoire consommée et le nombre de garbage collections ne semblent pas indiquer de problème de mémoire. Le pic était d’environ 400 Mo, mais vu le grand suffixe, cela semble normal. Pas de modèles de collecte de déchets bizarres non plus.

Profileur CPU

Profileur de mémoire

Origine du problème

Après une bataille glorieuse qui a duré deux jours et trois nuits (et des idées et des pensées étonnantes à partir des commentaires), j’ai finalement réussi à résoudre ce problème!

Je voudrais poster une réponse pour quiconque rencontre des problèmes similaires où la fonction ssortingng.Subssortingng(i, j) 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 vous le permettre la copie faite par ssortingng.Subssortingng(i, j) (il doit faire une copie parce que les chaînes C # sont immuables, aucun moyen de les contourner) ou la ssortingng.Subssortingng(i, j) est appelé un grand nombre de fois sur même chaîne (comme dans mes boucles nestedes) donnant du temps à la garbage collector, ou comme dans mon cas les deux!

Tentatives

J’ai essayé beaucoup de choses suggérées, telles que SsortingngBuilder , Streams , l’allocation de mémoire non gérée utilisant Intptr et Marshal dans le bloc unsafe{} et même la création d’un IEnumerable et le rendement retournent les caractères par référence dans les positions données. En fin de compte, toutes ces tentatives ont échoué car une certaine forme de jonction des données devait être effectuée car il n’existait pas de moyen simple pour moi de parcourir mon caractère d’arbre par caractère sans compromettre les performances. Si seulement il y avait un moyen de parcourir plusieurs adresses mémoire dans un tableau à la fois, comme vous le feriez en C ++ avec une arithmétique de pointeur .. sauf qu’il existe .. (Crédits au commentaire de @Ivan Stoev)

La solution

La solution utilisait System.ReadOnlySpan (ne pouvait pas être System.Span car les chaînes étaient immuables), ce qui nous permet, entre autres, de lire des sous-tableaux d’adresses mémoire dans un tableau existant sans créer de copies.

Ce morceau de code posté:

 ssortingng _s1 = s1.Subssortingng(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() prend maintenant deux entiers (position et longueur de la sous-chaîne) et fait:

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

Notez que la variable substr est littéralement une référence à un sous-ensemble de caractères du tableau s1 initial et non une copie! (La variable s1 a été rendue accessible depuis cette fonction)

Notez qu’au moment d’écrire ceci, j’utilise C # 7.2 et .NET Framework 4.6.1, ce qui signifie que pour obtenir la fonctionnalité Span, je devais aller à Projet> Gérer les paquets NuGet, cocher la case “Inclure une version préliminaire” et rechercher System .Mémoire et installez-le.

En relançant le test initial (sur des chaînes de longueur de 1 million de caractères, soit 1 Mo), la vitesse est passée de 2 minutes (j’ai cessé d’attendre après 2 minutes) à environ 86 millisecondes!