Самый быстрый метод для обращения к строкам в С#.net

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

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

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

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

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

Ответы

Ответ 1

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

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

Если вы выполняете сравнение на месте, вы делаете только последний шаг. Даже тогда ваше сравнение составляет только половину строки (или половину - 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:

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

Кстати, пробегая эти примеры для решения проблемы, OP упоминает (обнаруживая наибольшее палиндромное произведение любых двух трехзначных чисел) с простым (возможно, наивным) циклом ниже:

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.

Ответ 2

Не изменилось бы число раз быстрее?

// 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;
}

Ответ 3

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

 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 в цикле на моем компьютере, но я не понимаю, почему. Проверьте на своем компьютере.

Умножение и бит-shifing должны быть быстрее, чем деление, но, вероятно, недостаточно точны. EDIT: использование long кажется достаточно точным.

  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.

Ответ 5

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

Ответ 6

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! Забыли половину длины для perf:)

Ответ 7

Самый быстрый способ, которым я нашел обратное преобразование строки в С#, - со следующим кодом. Это более быстрое чтение в 32 бит за раз, а не char длиной 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--;
        }
    }
}

Ответ 9

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

Ответ 10

Использование функции ggf31416 FastReverse, вот решение проблемы Project Euler №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;
        }
    }
}

Ответ 11

Класс Stopwatch требует reset после каждого запуска. приведенный ниже код был исправлен

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;
        }

    }
}