Самый быстрый способ разделить цифры int на массив в .NET?
https://stackoverflow.com/questions/1613317
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу разделить цифры целого числа, скажем 12345, на массив байтов {1,2,3,4,5}, но мне нужен наиболее эффективный способ сделать это, потому что моя программа делает это миллионы раз.
Есть какие-нибудь предложения?Спасибо.
Решение
Как насчет:
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
}
Другие советы
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;
}
преобразовать целое число в строку, а затем использовать String.Chars []
Миллионы раз не так уж много.
// 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 .
«Будет» против «делает»? Я большой поклонник оптимизации кода после того, как он написан, профилирован и определен как узкое место.
Просто для забавы, вот способ разделить все цифры, используя всего один оператор 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]
Эффективность? ... Я не уверен по сравнению с некоторыми другими быстрыми ответами, которые я вижу здесь. Кто-то должен был бы проверить это.
Возможно, разворачивается небольшая петля?
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% быстрее.
Если вы можете обойтись с ведущими нулями, это намного проще.
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;
}
split и 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;
}
}
Я передаю массив вместо того, чтобы выделять его каждый раз, чтобы вывести из уравнения распределитель памяти и длину. Эта версия будет производить начальные нули, если массив длиннее, чем число. По сравнению с аналогично преобразованной версией примера Джона:
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;
}
}
Распределение нового 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;
}
Таким образом, вызывающий может создать статический многократно используемый буфер, если это позволяет его сценарий использования.
Я не проверял это или что-то еще, но я думаю, что это будет самый простой ответ. Поправь меня, если я ошибаюсь.
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
Это тесты со скоростью около 775k / сек (для чисел 9 цифр или меньше). Сбросьте максимальные цифры до 7, и он будет на скорости 885k / s. 5 цифр при скорости 1,1 м / с.
