Самый быстрый способ обратить вспять в строке в C # .net

Question

В настоящее время я пишу быстрое решение для проблемы Эйлера # 4, где нужно найти наибольшее число палиндромов из произведения двух трехзначных чисел.

Чтобы определить, является ли число палиндромным, вы, очевидно, сравнили бы обратное число с оригиналом.

Поскольку в C # нет встроенного метода String.Reverse (), какой самый быстрый способ перевернуть строку?

Я буду тестировать все предложенные решения в цикле с 100 000 000 итераций. Правильный ответ будет дан человеку, который предоставил самое быстрое решение.

Я буду тестировать решение в консольном приложении C # .Net 3.5

Answer 1

Разве не поменять номер быстрее?

// unchecked code, don't kill me if it doesn't even compile.
ulong Reverse(ulong number) {
    ulong result = 0;

    while (number > 0) {
        ulong digit = number % 10;
        result = result * 10 + digit;
        number /= 10;
    }

    return result;
}

Answer 2

Если вы хотите сравнить число с обратным, может быть быстрее изменить число, используя деление, чем преобразовывать его в строку. Мне все еще нужно проверить скорость.

 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 был примерно на 1% быстрее, чем деление и модуль в моем компьютере. Оптимизация скорости - выход, если последняя цифра 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 ;
  }

Заставить метод возвращать bool было немного медленнее, чем сравнивать bool в цикле на моем компьютере, но я не понимаю почему. Пожалуйста, проверьте на вашем компьютере.

Умножение и сдвиг битов должны выполняться быстрее деления, но, вероятно, они недостаточно точны. РЕДАКТИРОВАТЬ: использование долго кажется достаточно точным.

  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 равно i / 10 до 1 073 741 829, где 1/10 дает 107374182, а умножение + двоичное смещение дает 107374183.

Answer 3

Я думаю, что это может быть быстрее сделать сравнение на месте. Если вы перевернете строку, вы должны:

1. Создание нового строкового объекта (или объекта StringBuffer)
2. Скопировать данные (в обратном порядке) из первой строки в новую строку
3. Сделай свое сравнение.

Если вы выполняете сравнение на месте, вы делаете только последний шаг. Даже в этом случае ваше сравнение составляет только половину строки (или половину - 0,5, в случае нечетного числа символов). Должно работать что-то вроде следующего:

static bool IsPalindromic(string 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;
}

EDIT:

Хотя это отвечает на вопрос ОП, решения, предлагаемые ggf31416 и конфигуратором , по моим тестам, на 30% быстрее удовлетворяют реальную потребность ОП на 30%. Решение конфигуратора будет немного быстрее, чем у ggf31416, если вы преобразуете его в статический метод и используете int с вместо ulong с (но намного медленнее, в противном случае).

---

Между прочим, пробежавшись по этим примерам, чтобы решить проблему, о которой упоминает ФП (найти наибольшее палиндромное произведение из любых двух трехзначных чисел), с помощью простого (возможно, наивного) цикла ниже:

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

дает следующие результаты на моей машине:

IsPalindromic(product.ToString()) took 0.3064174 seconds.
ggf31416Reverse(product) == product took 0.1933994 seconds.
configuratorReverse(product) == product took 0.1872061 seconds.

Каждый из них дает правильный результат 913 * 993 = 906609.

Answer 4

Производительность: самые быстрые алгоритмы обращения строк ... (окончательные результаты)

Answer 5

string test = "ABC";
string reversed = new String(test.ToCharArray().Reverse().ToArray());

Answer 6

Самый быстрый способ, который я нашел для обращения строки в C #, это следующий код. Это быстрее чтение в 32 бита за раз вместо длины символа в 16 бит. В режиме отладки это быстрее, пока вы не получите около 93 символов. Все, что длиннее этого Array.Reverse (), быстрее. Используя сборку релиза и работающую вне IDE, этот метод выдувает Array.Reverse () из воды на любую длину строки.

char[] MyCharArray = MyString.ToCharArray();
UIntStringReverse(ref MyCharArray);     //Code to reverse is below.
string ReversedString = new string(MyCharArray);


private static unsafe void UIntStringReverse(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--;
        }
    }
}

Answer 7

public static String Reverse(string 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);
}

РЕДАКТИРОВАТЬ: Doh! Забыл вдвое сократить длину для перфорации:)

Answer 8

Класс секундомера необходимо сбрасывать после каждого запуска. код ниже был исправлен

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

---

using System;
using System.Diagnostics;

namespace longeststring_codegolf
{
    class Program
    {
        static void Main(string[] 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.ToString()))
                        t = v;
            sw.Stop();

            var elapsed = sw.Elapsed;
            var elapsedMilliseconds = sw.ElapsedMilliseconds;
            var elapsedTicks = sw.ElapsedTicks; 
            Console.WriteLine("Ticks: " + elapsedTicks.ToString());//~189000
            Console.WriteLine("Milliseconds: " + elapsedMilliseconds.ToString()); //~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.ToString()))
                        t = v;
            sw.Stop();
            var elapsed2 = sw.Elapsed;
            var elapsedMilliseconds2 = sw.ElapsedMilliseconds;
            var elapsedTicks2 = sw.ElapsedTicks; 
            Console.WriteLine("Ticks: " + elapsedTicks2.ToString());//~388000
            Console.WriteLine("Milliseconds: " + elapsedMilliseconds2.ToString());//~20

        }

        static bool IsPalindromicMine(string s)
        {
            var d = s.ToCharArray();
            Array.Reverse(d);
            return s == new string(d);
        }

        static bool IsPalindromic(string 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;
        }

    }
}

Answer 9

Используя функцию FastReverse ggf31416, вот решение проблемы № 4 проекта Эйлера, которая завершается на моем компьютере за 47 мс.

using System;
using System.Diagnostics;

namespace Euler_Problem_4
{
    class Program
    {
        static void Main(string[] 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;
        }
    }
}

Answer 10

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