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

Ответ 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;
}

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

EDIT: Я только что понял, что "большой" случай может использовать "маленький" случай - разделить большое количество на два небольших и использовать полученные мемуары. Я дам это после обеда и напишу бенчмарк...

EDIT: Хорошо, готов к огромному количеству кода? Я понял, что для равномерно случайных чисел, по крайней мере, вы получите "большие" цифры гораздо чаще, чем маленькие, поэтому вам нужно оптимизировать для этого. Конечно, это может быть не для реальных данных, но в любом случае... это означает, что теперь я делаю свои тесты размера в обратном порядке, надеясь на большие числа в первую очередь.

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

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

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
}

Ответ 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;
} 

Ответ 3

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

// 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.

Ответ 4

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

Ответ 5

'Will' vs 'Does'? Я большой поклонник оптимизации кода после того, как он написал, профилировал, и это было определено как узкое место.

Ответ 6

Может быть, немного запущена петля?

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 thingy..;)

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

Я полностью развернул петли и сравнил с принятым memoized вариантом 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% быстрее.

Ответ 7

Просто для удовольствия, вот способ разделить все цифры, используя только один оператор С#. Он работает следующим образом: регулярное выражение использует строчную версию числа, разбивает его цифры на строковый массив и, наконец, внешний метод 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]

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

Ответ 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;
        }
    }

EDIT: более быстрая версия. На моем компьютере он тестировался быстрее, чем два алгоритма Jon Skeet, за исключением его memoized версии:

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

Ответ 9

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

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

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

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

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

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

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

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

    }

Ответ 10

Распределение нового 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;
    }

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

Ответ 11

Я не сравнивал это или что-то еще, но я думаю, что это был бы самый простой ответ. Исправьте меня, если я ошибаюсь.

    Dim num As Integer = 147483647
    Dim nDigits As Integer = 1 + Convert.ToInt32(Math.Floor(Math.Log10(num)))
    Dim result(nDigits - 1) As Integer

    For a As Integer = 1 To nDigits
        result(a - 1) = Int(num / (10 ^ (nDigits - a))) Mod 10
    Next

** РЕДАКТИРОВАТЬ **

Пересмотренная функция, потому что экспоненты выглядят очень дорого.

Private Function Calc(ByVal num As Integer) As Integer()
    Dim nDigits As Int64 = 1 + Convert.ToInt64(Math.Floor(Math.Log10(num)))
    Dim result(nDigits - 1) As Integer
    Dim place As Integer = 1

    For a As Integer = 1 To nDigits
        result(nDigits - a) = Int(num / place) Mod 10
        place = place * 10
    Next

    Return result
End Function

Этот показатель составляет около 775 к/сек (для цифр 9 или менее). Снимите максимальные цифры до 7 и скамейки со скоростью 885 к/с. 5 цифр при 1,1 м/с.