Самый быстрый способ разделить цифры интервала в массив в.NET?
Это зависит, если алгоритм не берет функтор, то всегда используют версию алгоритма станд. И более просто для Вас записать и более ясный.
Для алгоритмов, которые берут функторы, обычно не, пока C++ 0x лямбды не может использоваться. Если функтор является маленьким, и алгоритм сложен (большинство не), тогда, может быть лучше все еще использовать алгоритм станд.
11 ответов
Как насчет:
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
}
Just for fun, here's a way to separate all the digits using just one C# statement. It works this way: the regular expression uses the string version of the number, splits apart its digits into a string array, and finally the outer ConvertAll method creates an int array from the string array.
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]
Efficiency-wise?... I'm unsure compared to some of the other fast answers I see here. Somebody would have to test it.
Если вы можете обойтись с ведущими нулями, это намного проще .
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;
}
«Будет» или «Сделает»? Я большой поклонник оптимизации кода после того, как он был написан, профилирован и был определен как узкое место.
Миллионы раз не так уж и много.
// 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 .
Возможно, небольшая петля разворачивается?
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 ..;)
Были некоторые разговоры о тестировании производительности ...
Я полностью развернул циклы и сравнил их с принятым мемоизированным вариантом Джонса, и я получил последовательно более быстрое время с этим: -
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% быстрее.
преобразовать целое число в строку, а затем использовать String.Chars []
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;
}
Согласно моим тестам, выделение нового 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
Этот тест показывает около 775 тыс. / Сек (для чисел с 9 цифрами или меньше). Снизьте максимальное количество цифр до 7, и он достигнет 885k / s. 5 цифр при скорости 1,1 м / с.
В изначальные времена твердого старого J2EE появился Spring Framework, который позволил внедрить зарегистрированные JNDI сервисы в EJB. Ну и дела,
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 раз для генерации всех массивов до заданного числа. Я также пробовал использовать числа с плавающей запятой, и это было только примерно на 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;
}
}