Méthode la plus rapide à inverser dans une chaîne en C # .net

Je pense qu’il serait peut-être plus rapide de faire la comparaison sur place. Si vous inversez la chaîne, vous devez:

1. Instancier un nouvel object ssortingng (ou un object SsortingngBuffer)
2. Copier les données (en sens inverse) de la première chaîne dans la nouvelle chaîne
3. Faites votre comparaison.

Si vous effectuez la comparaison sur place, vous ne réalisez que la dernière étape. Même dans ce cas, votre comparaison ne représente que la moitié de la chaîne (ou la moitié – 0,5 en cas de nombre impair de caractères). Quelque chose comme ce qui suit devrait fonctionner:

static bool IsPalindromic(ssortingng s){ int len = s.Length; int half = len-- >> 1; for(int i = 0; i < half; i++) if(s[i] != s[len - i]) return false; return true; } 

MODIFIER:

Bien que cela réponde à la question du PO, les solutions proposées par ggf31416 et son configurateur permettent de résoudre le besoin réel du PO environ 30% plus rapidement, d’après mes tests. La solution du configurateur est un peu plus rapide que celle de ggf31416, si vous la convertissez en une méthode statique et utilisez int s à la place de ulong s (mais beaucoup plus lentement, sinon).

Incidemment, en parcourant ces exemples pour résoudre le problème mentionné dans le PO (trouver le plus gros produit palindrome de deux nombres à trois chiffres), utilisez la boucle simple (peut-être naïve) ci-dessous:

 for(int i = 100; i < 1000; i++) for(int j = i; j < 1000; j++) // calculations where j < i would be redundant ... 

donne les résultats suivants sur ma machine:

 IsPalindromic (product.ToSsortingng ()) a pris 0.3064174 secondes.
 ggf31416Reverse (produit) == le produit a pris 0,1933994 seconde.
 configuratorReverse (produit) == le produit a pris 0,18872061 secondes.

Chacun produit le résultat correct de 913 * 993 = 906609 .

Inverser le nombre ne serait-il pas plus rapide?

 // unchecked code, don't kill me if it doesn't even comstack. ulong Reverse(ulong number) { ulong result = 0; while (number > 0) { ulong digit = number % 10; result = result * 10 + digit; number /= 10; } return result; } 

Si vous souhaitez comparer un nombre avec son inverse, il peut être plus rapide d’inverser le nombre en utilisant la division plutôt que de le convertir en chaîne. J’ai encore besoin d’en tester la vitesse.

  private static int Reverse(int num) { int res = 0; while (num > 0) { int rm ; num = Math.DivRem(num, 10, out rm); res = res * 10 + rm; } return res; } 

EDIT: DivRem était environ 1% plus rapide que la division et le module de mon ordinateur. Une optimisation de la vitesse est sortie si le dernier chiffre est 0:

  private static int Reverse(int num) { int res = 0; int rm; num = Math.DivRem(num, 10, out rm); //Some magic value or return false, see below. if (rm == 0) return -1 ; res = res * 10 + rm; while (num > 0) { num = Math.DivRem(num, 10, out rm); res = res * 10 + rm; } return res ; } 

Faire en sorte que la méthode retourne un booléen était légèrement plus lent que de comparer un booléen en boucle dans mon ordinateur, mais je ne comprends pas pourquoi. Veuillez tester sur votre ordinateur.

La multiplication et le transfert de bits devraient être plus rapides que la division mais ne sont probablement pas assez précis. EDIT: utiliser long semble être assez précis.

  private static int FastReverse(int num) { int res = 0; int q = (int)((214748365L * num) >> 31); int rm = num - 10 * q; num = q; if (rm == 0) return -1; res = res * 10 + rm; while (num > 0) { q = (int)((214748365L * num) >> 31); rm = num - 10 * q; num = q; res = res * 10 + rm; } return res; } 

(214748365L * num) >> 31 est égal à i / 10 jusqu’à 1 073 741 829, où 1/10 donne 107374182 et la multiplication + décalage binary donne 107374183.

Performance: algorithmes d’inversion de chaînes les plus rapides … (résultats finaux)

 ssortingng test = "ABC"; ssortingng reversed = new Ssortingng(test.ToCharArray().Reverse().ToArray()); 

 public static Ssortingng Reverse(ssortingng input) { var length = input.Length; var buffer = new char[length]; for ( var i= 0; i < input.Length; i++ ) { buffer[i] = input[(length-i)-1]; } return new String(buffer); } 

EDIT: Doh! Oublié de réduire de moitié la longueur pour perf 🙂

Le moyen le plus rapide que j’ai trouvé d’inverser une chaîne en C # est d’utiliser le code suivant. C’est une lecture plus rapide en 32 bits à la fois au lieu d’une longueur de caractère de 16 bits. En mode débogage, il est plus rapide jusqu’à environ 93 caractères. Plus longtemps que cela, Array.Reverse () est plus rapide. En utilisant une version release et en cours d’exécution en dehors de l’EDI, cette méthode va extraire Array.Reverse () de l’eau, quelle que soit la longueur de la chaîne.

 char[] MyCharArray = MySsortingng.ToCharArray(); UIntSsortingngReverse(ref MyCharArray); //Code to reverse is below. ssortingng ReversedSsortingng = new ssortingng(MyCharArray); private static unsafe void UIntSsortingngReverse(ref char[] arr) { uint Temp; uint Temp2; fixed (char* arrPtr = &arr[0]) { uint* p, q; p = (uint*)(arrPtr); q = (uint*)(arrPtr + arr.LongLength - 2); if (arr.LongLength == 2) { Temp = *p; *p = ((Temp & 0xFFFF0000) >> 16) | ((Temp & 0x0000FFFF) << 16); return; } while (p < q) { Temp = *p; Temp2 = *q; *p = ((Temp2 & 0xFFFF0000) >> 16) | ((Temp2 & 0x0000FFFF) << 16); *q = ((Temp & 0xFFFF0000) >> 16) | ((Temp & 0x0000FFFF) << 16); p++; q--; } } } 

essayez aussi: http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx

 ssortingng Reverse(ssortingng s) { return new ssortingng(s.ToCharArray().Reverse().ToArray()); } 

En utilisant la fonction FastReverse de ggf31416, voici la solution au problème n ° 4 de Project Euler, qui s’achève sur mon ordinateur en 47 ms.

 using System; using System.Diagnostics; namespace Euler_Problem_4 { class Program { static void Main(ssortingng[] args) { Stopwatch s = new Stopwatch(); s.Start(); int t = 0; for (int i = 999; i > 99; i--) { for (int j = i; j > 99; j--) { if (i*j == FastReverse(i*j)) { if (i * j > t) { t = i * j; } } } } Console.WriteLine(t); s.Stop(); Console.WriteLine("{0}mins {1}secs {2}ms", s.Elapsed.Minutes, s.Elapsed.Seconds, s.Elapsed.Milliseconds); Console.ReadKey(true); } private static int FastReverse(int num) { int res = 0; int q = (int)((214748365L * num) >> 31); int rm = num - 10 * q; num = q; if (rm == 0) return -1; res = res * 10 + rm; while (num > 0) { q = (int)((214748365L * num) >> 31); rm = num - 10 * q; num = q; res = res * 10 + rm; } return res; } } } 

La classe Chronomètre doit être réinitialisée après chaque exécution. le code ci-dessous a été corrigé

 var d = s.ToCharArray(); Array.Reverse(d); return s == new ssortingng(d); 

 using System; using System.Diagnostics; namespace longestssortingng_codegolf { class Program { static void Main(ssortingng[] args) { int t = 0, v = 0; var sw = new Stopwatch(); sw.Start(); for (int i = 999; i > 99; i--) for (int j = 999; j > 99; j--) if ((v = i * j) > t && IsPalindromicMine(v.ToSsortingng())) t = v; sw.Stop(); var elapsed = sw.Elapsed; var elapsedMilliseconds = sw.ElapsedMilliseconds; var elapsedTicks = sw.ElapsedTicks; Console.WriteLine("Ticks: " + elapsedTicks.ToSsortingng());//~189000 Console.WriteLine("Milliseconds: " + elapsedMilliseconds.ToSsortingng()); //~9 sw = Stopwatch.StartNew(); for (int i = 999; i > 99; i--) for (int j = 999; j > 99; j--) if ((v = i * j) > t && IsPalindromic(v.ToSsortingng())) t = v; sw.Stop(); var elapsed2 = sw.Elapsed; var elapsedMilliseconds2 = sw.ElapsedMilliseconds; var elapsedTicks2 = sw.ElapsedTicks; Console.WriteLine("Ticks: " + elapsedTicks2.ToSsortingng());//~388000 Console.WriteLine("Milliseconds: " + elapsedMilliseconds2.ToSsortingng());//~20 } static bool IsPalindromicMine(ssortingng s) { var d = s.ToCharArray(); Array.Reverse(d); return s == new ssortingng(d); } static bool IsPalindromic(ssortingng s) { int len = s.Length; int half = len-- >> 1; for (int i = 0; i < half; i++) if (s[i] != s[len - i]) return false; return true; } } }