我希望将一个整数的各个数字分离出来，例如 12345，变成一个字节数组 {1,2,3,4,5}，但是我需要最高效的方式来实现这一点，因为我的程序需要执行数百万次。
有什么建议吗？谢谢。
在.NET中，将int的数字分离成数组的最快方法是什么？
17
- Moayad Mardini
10
6如果这真的很关键，那么尽量获取所有的方式，并使用可以模拟您实际环境的周期来进行基准测试。 - Russell Steen
1好的，我不知道所有可能的方法，你能建议一些吗？ - Moayad Mardini
3你是真的想要将十进制数字分开，还是指逐字节分开？ - plinth
3你了解输入的相关信息吗？例如，你知道这个整数始终为正数吗？你知道它始终小于一百万吗？通过缩小问题的范围，你可以得到更好的优化。请注意不改变原意，并使翻译通俗易懂。 - Eric Lippert
1这真的很有趣。我很好奇。你为什么要这样做？ - Chris
显示剩余5条评论
11个回答
22
如何：
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的结果，就像Eric建议的那样。如果你能绝对保证你不会改变返回的数组内容，你可以去掉
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;
}
注意，目前这个程序并不尝试保证线程安全。您可能需要添加内存屏障(memory barrier)，以确保对缓存结果的写入不会在单个结果中的写入可见之前就已经可见了。除非我绝对必须这样做，否则我已经放弃了理解这些事情的尝试。我相信您可以通过努力使它无锁化，但如果您真的需要，您应该请一个非常聪明的人来做。
编辑：我刚意识到“大数”情况可以利用“小数”情况——将大数分成两个小数，并使用缓存的结果。我晚饭后会试一下并编写基准测试...
编辑：好吧，你准备好写一堆代码了吗？我意识到，至少对于均匀随机数，你会更频繁地得到“大”数字而不是小数字——所以你需要针对这一点进行优化。当然，对于真实数据可能不是这样，但无论如何...这意味着我现在按照相反的顺序进行大小测试，希望首先得到大数。
我已经为原始代码、简单的记忆化代码和极度展开的代码编写了一个基准测试。
结果(毫秒)：
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
}
- Jon Skeet
28
3@Thorarin：好主意，但有更好的 :) - Jon Skeet
1其实，我不确定哪个更好。理论上来说，应该是后者更快，但 JIT 编译器会对
for (int i = 0; i < size; i++) 进行优化，使其比 for (int i = size - 1; i >= 0; i--) 更快。有点傻，我知道 :( 我主要是为了可读性。 - Thorarin3通过记忆化结果，你有可能使平均速度更快。 - Eric Lippert
1我曾考虑将数字分成两半并实现它，而且它确实比你目前的解决方案更快。 - Joren
1第一种解决方案的性能“难以超越”（去掉函数调用可以改善它）。第二种解决方案……太多错别字，而Clone()会消耗大部分性能增益。 - DK.
显示剩余23条评论
9
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;
}
- Johan Kullbom
8
将整数转换为字符串，然后使用String.Chars[]。
- DmitryK
3
我不相信这是最快的方式。 - Moayad Mardini
34每当有人使用字符串进行简单的算术运算时，就会有一只小猫咪死去。 - Joren
8硬件便宜，程序员昂贵。 - Nick
7
百万次并不算多。
请注意，如果您将字节更改为有符号字节并测试
// 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();
请注意，如果您将字节更改为有符号字节并测试
num != 0，则可以更改以处理负数。- H H
2
3这里有几个耗费昂贵的操作：分配一个列表，插入到列表中，转换为数组。这可以加速至少一百倍。 - cdiggins
最好的方法是先倒序填充一个包含10个元素的数组，然后再将数字复制到新数组中。 - Joren
5
'Will' 和 'Does'？我非常喜欢在编写代码、分析和确定瓶颈之后优化代码。
- Obi
4
6为什么会有人踩这篇帖子？+！过早的优化是万恶之源。 - Daniel Elliott
3你的回答并没有回答问题。你怎么知道他没有编写和分析代码，并且确认这是瓶颈所在？ - cdiggins
@cdiggins：是的，谢谢，这是我程序逻辑的瓶颈。 - Moayad Mardini
1他说我的代码将会，而不是已经。他推断了未来时态，就像之前所说的一样。过早地优化是万恶之源。 - Obi
3
也许可以进行一些小循环展开？
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%。
- user159335
5
1这对于小数字来说会做很多冗余工作... 即使您跳过它们，它仍将计算值。 - Jon Skeet
确实，Jon，平均而言，这并不比你的解决方案更快。 - Joren
1冗余的工作主要是数学计算，虽然可以节省循环条件和一组赋值操作，但编译器最终可能会生成相同的代码。@Joren 这是来自基准测试还是仅仅估计的？ - user159335
我对前一亿个整数进行了基准测试，结果显示Jon的代码速度比你的快5:3。如果你不对不存在的数字进行任何算术运算，我认为你的代码有很大的可能性更快。不经过测试很难确定。 - Joren
完全展开后，我可以省去数组重新调整大小的操作，性能得到了很大提升。我对此进行了基准测试，比Jon Skeet的两个可接受答案快了20%。 - user159335
3
仅供娱乐，这里有一种使用单个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]
就效率而言，相比于其他快速答案，我不确定。需要有人进行测试。
- John K
1
正则表达式的好处在于，如果您只想提取数字并将其拆分，可以修改模式以排除特殊的数字相关符号，如. $ E等。 - John K
2
如果您可以接受前导零，那么这将更容易实现。
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;
}
}
编辑：这里有一个更快的版本。在我的电脑上，它的测试速度比Jon Skeet的两个算法都要快，除了他的记忆化版本：
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;
}
- cdiggins
2
当然，通过在返回之前将相关数字复制到新数组中，轻松摆脱零。好的，它再次迭代数组，但对于长度为10个条目的数组，我真的看不出有什么问题。 - Joren
额外的迭代是完全正确的。我们可能会遇到的唯一问题是数百万个数组分配。更快的方法是预先分配10个静态数组，然后选择正确的数组。 - cdiggins
1
除法和取模运算往往是较慢的操作。我想找出是否使用乘法和减法的解决方案会更快，而且似乎确实如此（在我的电脑上）：
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倍的时间来生成给定数字的所有数组。我还尝试使用浮点数，速度只慢了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;
}
}
- Dolphin
1
根据我的测试，每次分配新的int[]都会占用大量时间。如果您知道这些值将在下一次调用之前被使用一次并且被丢弃，那么您可以重复使用静态数组以显著提高速度：
为了让代码更简洁，我会在数字较小的情况下返回尾随的零，但这很容易通过使用9个不同的静态数组（或者一个数组的数组）来改变。
另外，也可以提供两个单独的ConvertToArrayOfDigits方法，一个带有预先创建的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个不同的静态数组（或者一个数组的数组）来改变。
另外，也可以提供两个单独的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;
}
这样，如果使用情况允许，调用者可以自行创建静态可重用缓冲区。
- Luke Hutteman
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接