Самый быстрый способ разделить цифры int в массив в .NET?

Question

Я хочу разделить цифры целого числа, скажем 12345, на массив байтов {1,2,3,4,5}, но я хочу наиболее эффективный способ сделать это, потому что моя программа это делает миллионы раз.

Есть предложения? Спасибо.

Answer 1

Как насчет:

public static int[] ConvertToArrayOfDigits(int value)
{
    int size = DetermineDigitCount(value);
    int[] digits = new int[size];
    for (int index = size - 1; index >= 0; index--)
    {
        digits[index] = value % 10;
        value = value / 10;
    }
    return digits;
}

private static int DetermineDigitCount(int x)
{
    // This bit could be optimised with a binary search
    return x < 10 ? 1
         : x < 100 ? 2
         : x < 1000 ? 3
         : x < 10000 ? 4
         : x < 100000 ? 5
         : x < 1000000 ? 6
         : x < 10000000 ? 7
         : x < 100000000 ? 8
         : x < 1000000000 ? 9
         : 10;
}

Обратите внимание, что это не справится с отрицательными числами ... вам это нужно?

РЕДАКТИРОВАТЬ: Вот версия, которая запоминает результаты для менее чем 10000, как предложено Эриком. Если вы можете абсолютно гарантировать , что не будете изменять содержимое возвращаемого массива, вы можете удалить вызов Clone. У него также есть удобное свойство уменьшения количества проверок для определения длины «больших» чисел - и маленькие числа в любом случае будут проходить этот код только один раз:)

private static readonly int[][] memoizedResults = new int[10000][];

public static int[] ConvertToArrayOfDigits(int value)
{
    if (value < 10000)
    {
        int[] memoized = memoizedResults[value];
        if (memoized == null) {
            memoized = ConvertSmall(value);
            memoizedResults[value] = memoized;
        }
        return (int[]) memoized.Clone();
    }
    // We know that value >= 10000
    int size = value < 100000 ? 5
         : value < 1000000 ? 6
         : value < 10000000 ? 7
         : value < 100000000 ? 8
         : value < 1000000000 ? 9
         : 10;

    return ConvertWithSize(value, size);
}

private static int[] ConvertSmall(int value)
{
    // We know that value < 10000
    int size = value < 10 ? 1
             : value < 100 ? 2
             : value < 1000 ? 3 : 4;
    return ConvertWithSize(value, size);
}

private static int[] ConvertWithSize(int value, int size)
{
    int[] digits = new int[size];
    for (int index = size - 1; index >= 0; index--)
    {
        digits[index] = value % 10;
        value = value / 10;
    }
    return digits;
}

Обратите внимание, что в данный момент этот процесс не является поточно-ориентированным. Возможно, вам придется добавить барьер памяти, чтобы убедиться, что запись в запомненные результаты не видна, пока записи в отдельном результате не видны. Я прекратил пытаться рассуждать об этих вещах, если я абсолютно не обязан. Я уверен, что вы можете сделать это без блокировки с усилием, но вам действительно нужно, чтобы кто-то очень умный сделал это, если вам действительно нужно.

РЕДАКТИРОВАТЬ: Я только что понял, что «большой» случай может использовать «маленький» случай - разбить большое число на два маленьких и использовать запомненные результаты. Я попробую после обеда и напишу тест ...

РЕДАКТИРОВАТЬ: Хорошо, готовы к огромному количеству кода? Я понял, что, по крайней мере, для равномерно случайных чисел вы будете получать "большие" цифры гораздо чаще, чем маленькие - поэтому вам нужно оптимизировать это. Конечно, это может быть не так для реальных данных, но в любом случае ... это означает, что я сейчас делаю свои тесты размера в обратном порядке, надеясь сначала на большие числа.

У меня есть эталон для исходного кода, простого напоминания, а затем чрезвычайно развернутого кода.

Результаты (в мс):

Simple: 3168
SimpleMemo: 3061
UnrolledMemo: 1204

Код:

using System;
using System.Diagnostics;

class DigitSplitting
{
    static void Main()        
    {
        Test(Simple);
        Test(SimpleMemo);
        Test(UnrolledMemo);
    }

    const int Iterations = 10000000;

    static void Test(Func<int, int[]> candidate)
    {
        Random rng = new Random(0);
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            candidate(rng.Next());
        }
        sw.Stop();
        Console.WriteLine("{0}: {1}",
            candidate.Method.Name, (int) sw.ElapsedMilliseconds);            
    }

    #region Simple
    static int[] Simple(int value)
    {
        int size = DetermineDigitCount(value);
        int[] digits = new int[size];
        for (int index = size - 1; index >= 0; index--)
        {
            digits[index] = value % 10;
            value = value / 10;
        }
        return digits;
    }

    private static int DetermineDigitCount(int x)
    {
        // This bit could be optimised with a binary search
        return x < 10 ? 1
             : x < 100 ? 2
             : x < 1000 ? 3
             : x < 10000 ? 4
             : x < 100000 ? 5
             : x < 1000000 ? 6
             : x < 10000000 ? 7
             : x < 100000000 ? 8
             : x < 1000000000 ? 9
             : 10;
    }
    #endregion Simple    

    #region SimpleMemo
    private static readonly int[][] memoizedResults = new int[10000][];

    public static int[] SimpleMemo(int value)
    {
        if (value < 10000)
        {
            int[] memoized = memoizedResults[value];
            if (memoized == null) {
                memoized = ConvertSmall(value);
                memoizedResults[value] = memoized;
            }
            return (int[]) memoized.Clone();
        }
        // We know that value >= 10000
        int size = value >= 1000000000 ? 10
                 : value >= 100000000 ? 9
                 : value >= 10000000 ? 8
                 : value >= 1000000 ? 7
                 : value >= 100000 ? 6
                 : 5;

        return ConvertWithSize(value, size);
    }

    private static int[] ConvertSmall(int value)
    {
        // We know that value < 10000
        return value >= 1000 ? new[] { value / 1000, (value / 100) % 10,
                                           (value / 10) % 10, value % 10 }
              : value >= 100 ? new[] { value / 100, (value / 10) % 10, 
                                         value % 10 }
              : value >= 10 ? new[] { value / 10, value % 10 }
              : new int[] { value };
    }

    private static int[] ConvertWithSize(int value, int size)
    {
        int[] digits = new int[size];
        for (int index = size - 1; index >= 0; index--)
        {
            digits[index] = value % 10;
            value = value / 10;
        }
        return digits;
    }
    #endregion

    #region UnrolledMemo
    private static readonly int[][] memoizedResults2 = new int[10000][];
    private static readonly int[][] memoizedResults3 = new int[10000][];
    static int[] UnrolledMemo(int value)
    {
        if (value < 10000)
        {
            return (int[]) UnclonedConvertSmall(value).Clone();
        }
        if (value >= 1000000000)
        {
            int[] ret = new int[10];
            int firstChunk = value / 100000000;
            ret[0] = firstChunk / 10;
            ret[1] = firstChunk % 10;
            value -= firstChunk * 100000000;
            int[] secondChunk = ConvertSize4(value / 10000);
            int[] thirdChunk = ConvertSize4(value % 10000);
            ret[2] = secondChunk[0];
            ret[3] = secondChunk[1];
            ret[4] = secondChunk[2];
            ret[5] = secondChunk[3];
            ret[6] = thirdChunk[0];
            ret[7] = thirdChunk[1];
            ret[8] = thirdChunk[2];
            ret[9] = thirdChunk[3];
            return ret;
        } 
        else if (value >= 100000000)
        {
            int[] ret = new int[9];
            int firstChunk = value / 100000000;
            ret[0] = firstChunk;
            value -= firstChunk * 100000000;
            int[] secondChunk = ConvertSize4(value / 10000);
            int[] thirdChunk = ConvertSize4(value % 10000);
            ret[1] = secondChunk[0];
            ret[2] = secondChunk[1];
            ret[3] = secondChunk[2];
            ret[4] = secondChunk[3];
            ret[5] = thirdChunk[0];
            ret[6] = thirdChunk[1];
            ret[7] = thirdChunk[2];
            ret[8] = thirdChunk[3];
            return ret;
        }
        else if (value >= 10000000)
        {
            int[] ret = new int[8];
            int[] firstChunk = ConvertSize4(value / 10000);
            int[] secondChunk = ConvertSize4(value % 10000);
            ret[0] = firstChunk[0];
            ret[1] = firstChunk[0];
            ret[2] = firstChunk[0];
            ret[3] = firstChunk[0];
            ret[4] = secondChunk[0];
            ret[5] = secondChunk[1];
            ret[6] = secondChunk[2];
            ret[7] = secondChunk[3];
            return ret;
        }
        else if (value >= 1000000)
        {
            int[] ret = new int[7];
            int[] firstChunk = ConvertSize4(value / 10000);
            int[] secondChunk = ConvertSize4(value % 10000);
            ret[0] = firstChunk[1];
            ret[1] = firstChunk[2];
            ret[2] = firstChunk[3];
            ret[3] = secondChunk[0];
            ret[4] = secondChunk[1];
            ret[5] = secondChunk[2];
            ret[6] = secondChunk[3];
            return ret;
        }
        else if (value >= 100000)
        {
            int[] ret = new int[6];
            int[] firstChunk = ConvertSize4(value / 10000);
            int[] secondChunk = ConvertSize4(value % 10000);
            ret[0] = firstChunk[2];
            ret[1] = firstChunk[3];
            ret[2] = secondChunk[0];
            ret[3] = secondChunk[1];
            ret[4] = secondChunk[2];
            ret[5] = secondChunk[3];
            return ret;
        }
        else
        {
            int[] ret = new int[5];
            int[] chunk = ConvertSize4(value % 10000);
            ret[0] = value / 10000;
            ret[1] = chunk[0];
            ret[2] = chunk[1];
            ret[3] = chunk[2];
            ret[4] = chunk[3];
            return ret;
        }
    }

    private static int[] UnclonedConvertSmall(int value)
    {
        int[] ret = memoizedResults2[value];
        if (ret == null)
        {
            ret = value >= 1000 ? new[] { value / 1000, (value / 100) % 10,
                                           (value / 10) % 10, value % 10 }
              : value >= 100 ? new[] { value / 100, (value / 10) % 10, 
                                         value % 10 }
              : value >= 10 ? new[] { value / 10, value % 10 }
              : new int[] { value };
            memoizedResults2[value] = ret;
        }
        return ret;
    }

    private static int[] ConvertSize4(int value)
    {
        int[] ret = memoizedResults3[value];
        if (ret == null)
        {
            ret = new[] { value / 1000, (value / 100) % 10,
                         (value / 10) % 10, value % 10 };
            memoizedResults3[value] = ret;
        }
        return ret;
    }
    #endregion UnrolledMemo
}

Answer 2

1 + Math.Log10 (num) даст количество цифр без поиска / зацикливания:

public static byte[] Digits(int num)
{
    int nDigits = 1 + Convert.ToInt32(Math.Floor(Math.Log10(num)));
    byte[] digits = new byte[nDigits];
    int index = nDigits - 1;
    while (num > 0) {
        byte digit = (byte) (num % 10);
        digits[index] = digit;
        num = num / 10;
        index = index - 1;
    }
    return digits;
}

Редактировать: Возможно, красивее:

public static byte[] Digits(int num)
{
    int nDigits = 1 + Convert.ToInt32(Math.Floor(Math.Log10(num)));
    byte[] digits = new byte[nDigits];

    for(int i = nDigits - 1; i != 0; i--)
    {
        digits[i] = (byte)(num % 10);
        num = num / 10;
    }
    return digits;
} 

Answer 3

преобразовать целое число в строку и затем использовать String.Chars []

Answer 4

Миллионы раз не так уж много.

// input: int num >= 0
List<byte> digits = new List<byte>();
while (num > 0)
{
   byte digit = (byte) (num % 10);
   digits.Insert(0, digit);  // Insert to preserve order
   num = num / 10;
}

// if you really want it as an array
byte[] bytedata = digits.ToArray();

Обратите внимание, что это можно изменить, чтобы справиться с отрицательными числами, если вы измените байт на sbyte и протестируете на num != 0.

Answer 5

«Будет» против «делает»? Я большой поклонник оптимизации кода после того, как он написан, профилирован и определен как узкое место.

Answer 6

Просто для удовольствия, вот способ разделить все цифры, используя только один оператор C #. Это работает следующим образом: регулярное выражение использует строковую версию числа, разбивает его цифры на строковый массив и, наконец, внешний метод ConvertAll создает массив int из строкового массива.

    int num = 1234567890;

    int [] arrDigits = Array.ConvertAll<string, int>(
        System.Text.RegularExpressions.Regex.Split(num.ToString(), @"(?!^)(?!$)"),
        str => int.Parse(str)
        );

    // resulting array is [1,2,3,4,5,6,7,8,9,0]

В отношении эффективности? ... Я не уверен по сравнению с некоторыми другими быстрыми ответами, которые я вижу здесь. Кто-то должен был бы проверить это.

Answer 7

Возможно, разворачивается маленькая петля?

int num = 147483647;
int nDigits = 1 + Convert.ToInt32(Math.Floor(Math.Log10(num)));
byte[] array = new byte[10] {
            (byte)(num / 1000000000 % 10),
            (byte)(num / 100000000 % 10),
            (byte)(num / 10000000 % 10),
            (byte)(num / 1000000 % 10),
            (byte)(num / 100000 % 10),
            (byte)(num / 10000 % 10),
            (byte)(num / 1000 % 10),
            (byte)(num / 100 % 10),
            (byte)(num / 10 % 10),
            (byte)(num % 10)};
byte[] digits;// = new byte[nDigits];
digits = array.Skip(array.Length-nDigits).ToArray();

Спасибо выше за Log10 штуковину ..;)

Ходили разговоры о бенчмаркинге ...

Я полностью развернул циклы и сравнил с принятым запомненным вариантом Jons, и у меня все быстрее получается: -

    static int[] ConvertToArrayOfDigits_unrolled(int num)
    {
        if (num < 10)
        {
            return new int[1] 
            {
                (num % 10) 
            };
        }
        else if (num < 100)
        {
            return new int[2] 
            {
                (num / 10 % 10),
                (num % 10)
            };
        }
        else if (num < 1000)
        {
            return new int[3] {
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 10000)
        {
            return new int[4] {
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 100000)
        {
            return new int[5] {
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 1000000)
        {
            return new int[6] {
            (num / 100000 % 10),
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 10000000)
        {
            return new int[7] {
            (num / 1000000 % 10),
            (num / 100000 % 10),
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 100000000)
        {
            return new int[8] {
            (num / 10000000 % 10),
            (num / 1000000 % 10),
            (num / 100000 % 10),
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else if (num < 1000000000)
        {
            return new int[9] {
            (num / 100000000 % 10),
            (num / 10000000 % 10),
            (num / 1000000 % 10),
            (num / 100000 % 10),
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
        else
        {
            return new int[10] {
            (num / 1000000000 % 10),
            (num / 100000000 % 10),
            (num / 10000000 % 10),
            (num / 1000000 % 10),
            (num / 100000 % 10),
            (num / 10000 % 10),
            (num / 1000 % 10),
            (num / 100 % 10),
            (num / 10 % 10),
            (num % 10)};
        }
    }

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

Answer 8

Если вы можете обойтись с ведущими нулями, это намного проще.

    void Test()
    { 
        // Note: 10 is the maximum number of digits.
        int[] xs = new int[10];
        System.Random r = new System.Random();
        for (int i=0; i < 10000000; ++i)
            Convert(xs, r.Next(int.MaxValue));
    }

    // Notice, I don't allocate and return an array each time.
    public void Convert(int[] digits, int val)
    {
        for (int i = 0; i < 10; ++i)
        {
            digits[10 - i - 1] = val % 10;
            val /= 10;
        }
    }

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

static void Convert(int[] digits, int val)
{
  digits[9] = val % 10; val /= 10;
  digits[8] = val % 10; val /= 10;
  digits[7] = val % 10; val /= 10;
  digits[6] = val % 10; val /= 10;
  digits[5] = val % 10; val /= 10;
  digits[4] = val % 10; val /= 10;
  digits[3] = val % 10; val /= 10;
  digits[2] = val % 10; val /= 10;
  digits[1] = val % 10; val /= 10;
  digits[0] = val % 10; val /= 10;     
} 

Answer 9

Выделение нового int [] каждый раз занимает значительное количество времени в соответствии с моим тестированием. Если вы знаете, что эти значения будут использоваться один раз и выбрасываться перед следующим вызовом, вы можете вместо этого повторно использовать статический массив для значительного улучшения скорости:

    private static readonly int[] _buffer = new int[10];
    public static int[] ConvertToArrayOfDigits(int value)
    {
        for (int index = 9; index >= 0; index--)
        {
            _buffer[index] = value % 10;
            value = value / 10;
        }
        return _buffer;
    }

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

В качестве альтернативы могут быть предоставлены 2 отдельных метода ConvertToArrayOfDigits, один из которых принимает предварительно созданный массив int в качестве дополнительного параметра, а другой - без него, который создает результирующий буфер перед вызовом первого метода.

    public static void ConvertToArrayOfDigits(int value, int[] digits) { ... }
    public static int[] ConvertToArrayOfDigits(int value)
    {
        int size = DetermineDigitCount(value);
        int[] digits = new int[size];
        ConvertToArrayOfDigits(value, digits);
        return digits;
    }

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

Answer 10

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

    public static void ConvertToArrayOfDigits2(int value, int[] digits)
    {
        double v = value;
        double vby10 = v * .1;

        for (int index = digits.Length - 1; index >= 0; index--)
        {
            int ivby10 = (int)vby10;
            digits[index] = (int)(v)- ivby10* 10;
            v = ivby10;
            vby10 = ivby10 * .1;
        }       
    }

Я передаю массив вместо того, чтобы выделять его каждый раз, чтобы вывести из формулы распределение памяти и длину. Эта версия будет производить начальные нули, если массив длиннее, чем число. По сравнению с аналогично преобразованной версией примера Джона:

    public static void ConvertToArrayOfDigits(int value, int[] digits){

        for (int index = digits.Length - 1; index >= 0; index--)    { 
            digits[index] = value % 10;    
            value = value / 10;  
        }   
    }

версия без разделения / мода заняла еще около 50 раз, чтобы сгенерировать все массивы до заданного числа. Я также пытался использовать float, и он был всего на 5-10% медленнее (двойная версия была быстрее, чем float).

Только потому, что это беспокоило меня, вот развернутая версия, которая снова немного быстрее:

        public static void ConvertToArrayOfDigits3(int value, int[] digits)
    {
        double v = value;
        double vby10 = v * .1;
        int ivby10;

        switch(digits.Length -1){
            default:
                throw new ArgumentOutOfRangeException();
            case 10:
                ivby10 = (int)vby10;
                digits[10] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 9;
            case 9:
                ivby10 = (int)vby10;
                digits[9] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 8;
            case 8:
                ivby10 = (int)vby10;
                digits[8] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 7;
            case 7:
                ivby10 = (int)vby10;
                digits[7] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 6;
            case 6:
                ivby10 = (int)vby10;
                digits[6] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 5;
            case 5:
                ivby10 = (int)vby10;
                digits[5] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 4;
            case 4:
                ivby10 = (int)vby10;
                digits[4] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 3;
            case 3:
                ivby10 = (int)vby10;
                digits[3] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 2;
            case 2:
                ivby10 = (int)vby10;
                digits[2] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 1;
            case 1:
                ivby10 = (int)vby10;
                digits[1] = (int)(v) - ivby10 * 10;
                v = ivby10;
                vby10 = ivby10 * .1;
                goto case 0;
            case 0:
                ivby10 = (int)vby10;
                digits[0] = (int)(v) - ivby10 * 10;
                break;
        }

    }