最快的一个int数字分成.NET中的数组的方式？ [英] Fastest way to separate the digits of an int into an array in .NET?
本文介绍了最快的一个int数字分成.NET中的数组的方式？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我要分出一个整数数字，比如12345，成字节{1,2,3,4,5}的数组，但我最想要的性能有效的方法来做到这一点，因为我的程序做了数百万次。</ P>
有什么建议？谢谢你。
解决方案
怎么样：
公共静态INT [] ConvertToArrayOfDigits（int值）
{
INT大小= DetermineDigitCount（值）;
INT []位数=新INT [尺寸]
对于（INT指数=大小 - 1;索引＆gt; = 0; index--）
{
数字[指数] =值10％;
值=价值/ 10;
}
返回的数字;
}
私有静态诠释DetermineDigitCount（INT X）
{
//该位可以用二进制搜索优化
返回X＆LT; 10？ 1
：X＆LT; 100？ 2
：X＆LT; 1000？ 3
：X＆LT; 10000？ 4
：X＆LT; 100000？五
：X＆LT;百万？ 6
：X＆LT;千万？ 7
：X＆LT;亿？ 8
：X＆LT; 10亿？ 9
：10;
}
请注意，这将不能应付负数...你需要它？
编辑：这是其中memoizes的结果在10000，所建议的埃里克版本。如果可以的绝对保证的，你会不会改变返回数组的内容，你可以删除克隆通话。它还具有减少检查次数来决定的大号的长度的方便性 - 小号码将只通过该code一旦反正：）
私有静态只读INT [] [] memoizedResults =新INT [10000] [];
公共静态INT [] ConvertToArrayOfDigits（int值）
{
如果（值小于10000）
{
INT [] memoized = memoizedResults [值];
如果（memoized == NULL）{
memoized = ConvertSmall（值）;
memoizedResults [值] = memoized;
}
返程（INT []）memoized.Clone（）;
}
//我们知道，值GT = 10000
INT大小=值小于; 100000？五
：值小于;百万？ 6
：值小于;千万？ 7
：值小于;亿？ 8
：值小于; 10亿？ 9
：10;
返回ConvertWithSize（价值大小）;
}
私有静态诠释[] ConvertSmall（int值）
{
//我们知道，值小于; 10000
INT大小=值小于; 10？ 1
：值小于; 100？ 2
：值小于; 1000？ 3：4;
返回ConvertWithSize（价值大小）;
}
私有静态诠释[] ConvertWithSize（int值，诠释大小）
{
INT []位数=新INT [尺寸]
对于（INT指数=大小 - 1;索引＆gt; = 0; index--）
{
数字[指数] =值10％;
值=价值/ 10;
}
返回的数字;
}
请注意，这不尝试是线程安全的时刻。您可能需要添加内存屏障，以确保在写memoized结果是不可见的，直到单个结果中的写入是可见的。我已经放弃了努力来思考这些事情，除非我绝对必须的。我敢肯定，你可以把它锁定，自由搭配的努力，但你确实应该得到别人的很聪明的这样做，如果你真的需要。
编辑：我刚刚意识到大的情况下，可以使用小的情况下 - 分裂的大量成两个小的，并使用memoised结果。我给了一个去吃完饭，写一个基准...
编辑：好了，准备好了code一个巨大的量？我意识到，均匀随机的数量至少，你会得到大的数字更往往比小的 - 所以你需要优化的。当然，这可能不是真实数据的情况，但无论如何......这意味着我现在就做我的规模测试以相反的顺序，希望能为大数字第一位。
我已经有了一个标杆原来的code，简单的记忆化，然后极度-展开code。
结果（以毫秒为单位）：
简单：3168
SimpleMemo：3061
UnrolledMemo：1204
code：
使用系统;
使用System.Diagnostics程序;
类DigitSplitting
{
静态无效的主要（）
{
测试（简单）;
测试（SimpleMemo）;
测试（UnrolledMemo）;
}
const int的迭代次数=千万;
静态无效测试（Func键＆LT; INT，INT []→候选）
{
随机RNG =随机新（0）;
秒表SW = Stopwatch.StartNew（）;
的for（int i = 0; I＆LT;迭代;我++）
{
候选（rng.Next（））;
}
sw.Stop（）;
Console.WriteLine（{0}：{1}，
candidate.Method.Name，（int）的sw.ElapsedMilliseconds）;
}
＃区域简单
静态INT []简单（int值）
{
INT大小= DetermineDigitCount（值）;
INT []位数=新INT [尺寸]
对于（INT指数=大小 - 1;索引＆gt; = 0; index--）
{
数字[指数] =值10％;
值=价值/ 10;
}
返回的数字;
}
私有静态诠释DetermineDigitCount（INT X）
{
//该位可以用二进制搜索优化
返回X＆LT; 10？ 1
：X＆LT; 100？ 2
：X＆LT; 1000？ 3
：X＆LT; 10000？ 4
：X＆LT; 100000？五
：X＆LT;百万？ 6
：X＆LT;千万？ 7
：X＆LT;亿？ 8
：X＆LT; 10亿？ 9
：10;
}
#endregion简单
＃地区SimpleMemo
私人静态只读INT [] [] memoizedResults =新INT [10000] [];
公共静态INT [] SimpleMemo（int值）
{
如果（值小于10000）
{
INT [] memoized = memoizedResults [值];
如果（memoized == NULL）{
memoized = ConvertSmall（值）;
memoizedResults [值] = memoized;
}
返程（INT []）memoized.Clone（）;
}
//我们知道，值GT = 10000
INT大小=值＆GT; = 10亿？ 10
：值GT =亿？ 9
：值GT =千万？ 8
：值GT; = 1000000？ 7
：值GT = 100000？ 6
：5;
返回ConvertWithSize（价值大小）;
}
私有静态诠释[] ConvertSmall（int值）
{
//我们知道，值小于; 10000
返回值GT = 1000？新的[] {值/ 1000，（值/ 100）％10，
（值/ 10）％10，价值10％}
：值GT = 100？新的[] {值/ 100，（数值/ 10）％10，
值％10}
：值GT = 10？新的[] {值/ 10，价值10％}
新INT [] {值};
}
私有静态诠释[] ConvertWithSize（int值，诠释大小）
{
INT []位数=新INT [尺寸]
对于（INT指数=大小 - 1;索引＆gt; = 0; index--）
{
数字[指数] =值10％;
值=价值/ 10;
}
返回的数字;
}
#endregion
＃地区UnrolledMemo
私人静态只读INT [] [] memoizedResults2 =新INT [10000] [];
私人静态只读INT [] [] memoizedResults3 =新INT [10000] [];
静态INT [] UnrolledMemo（int值）
{
如果（值小于10000）
{
返回（INT []）UnclonedConvertSmall（值）.Clone（）;
}
如果（值GT = 10亿）
{
INT [] RET =新INT [10];
INT firstChunk =值/亿;
保留[0] = firstChunk / 10;
保留[1] = firstChunk％10;
值 - = firstChunk *亿;
INT [] secondChunk = ConvertSize4（价值/ 10000）;
INT [] thirdChunk = ConvertSize4（价值10000％）;
保留[2] = secondChunk [0];
保留[3] = secondChunk [1];
保留[4] = secondChunk [2];
保留[5] = secondChunk [3];
保留[6] = thirdChunk [0];
保留[7] = thirdChunk [1];
保留[8] = thirdChunk [2];
保留[9] = thirdChunk [3];
返回RET;
}
否则，如果（值GT =亿）
{
INT [] RET =新INT [9];
INT firstChunk =值/亿;
保留[0] = firstChunk;
值 - = firstChunk *亿;
INT [] secondChunk = ConvertSize4（价值/ 10000）;
INT [] thirdChunk = ConvertSize4（价值10000％）;
保留[1] = secondChunk [0];
保留[2] = secondChunk [1];
保留[3] = secondChunk [2];
保留[4] = secondChunk [3];
保留[5] = thirdChunk [0];
保留[6] = thirdChunk [1];
保留[7] = thirdChunk [2];
保留[8] = thirdChunk [3];
返回RET;
}
否则，如果（值GT = 10000000）
{
INT [] RET =新INT [8]。
INT [] firstChunk = ConvertSize4（价值/ 10000）;
INT [] secondChunk = ConvertSize4（价值10000％）;
保留[0] = firstChunk [0];
保留[1] = firstChunk [0];
保留[2] = firstChunk [0];
保留[3] = firstChunk [0];
保留[4] = secondChunk [0];
保留[5] = secondChunk [1];
保留[6] = secondChunk [2];
保留[7] = secondChunk [3];
返回RET;
}
否则，如果（值GT = 1000000）
{
INT [] RET =新INT [7];
INT [] firstChunk = ConvertSize4（价值/ 10000）;
INT [] secondChunk = ConvertSize4（价值10000％）;
保留[0] = firstChunk [1];
保留[1] = firstChunk [2];
保留[2] = firstChunk [3];
保留[3] = secondChunk [0];
保留[4] = secondChunk [1];
保留[5] = secondChunk [2];
保留[6] = secondChunk [3];
返回RET;
}
否则，如果（值GT = 100000）
{
INT [] RET =新INT [6];
INT [] firstChunk = ConvertSize4（价值/ 10000）;
INT [] secondChunk = ConvertSize4（价值10000％）;
保留[0] = firstChunk [2];
保留[1] = firstChunk [3];
保留[2] = secondChunk [0];
保留[3] = secondChunk [1];
保留[4] = secondChunk [2];
保留[5] = secondChunk [3];
返回RET;
}
其他
{
INT []保留=新INT [5];
INT []块= ConvertSize4（价值10000％）;
RET [0] =价值/ 10000;
保留[1] =块[0];
保留[2] =块[1];
保留[3] =块[2];
保留[4] =块[3];
返回RET;
}
}
私有静态诠释[] UnclonedConvertSmall（int值）
{
INT [] RET = memoizedResults2 [值];
如果（RET == NULL）
{
RET =值＆GT; = 1000？新的[] {值/ 1000，（值/ 100）％10，
（值/ 10）％10，价值10％}
：值GT = 100？新的[] {值/ 100，（数值/ 10）％10，
值％10}
：值GT = 10？新的[] {值/ 10，价值10％}
新INT [] {值};
memoizedResults2 [值] = RET;
}
返回RET;
}
私有静态诠释[] ConvertSize4（int值）
{
INT [] RET = memoizedResults3 [值];
如果（RET == NULL）
{
RET =新的[] {值/ 1000，（值/ 100）％10，
（值/ 10）％10，价值10％};
memoizedResults3 [值] = RET;
}
返回RET;
}
#endregion UnrolledMemo
}
I want to separate the digits of an integer, say 12345, into an array of bytes {1,2,3,4,5}, but I want the most performance effective way to do that, because my program does that millions of times.
Any suggestions? Thanks.
解决方案
How about:
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;
}
Note that this won't cope with negative numbers... do you need it to?
EDIT: Here's a version which memoizes the results for under 10000, as suggested by Eric. If you can absolutely guarantee that you won't change the contents of the returned array, you could remove the Clone call. It also has the handy property of reducing the number of checks to determine the length of "large" numbers - and small numbers will only go through that code once anyway :)
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;
}
Note that this doesn't try to be thread-safe at the moment. You may need to add a memory barrier to make sure that the write to the memoized results isn't visible until the writes within the individual result are visible. I've given up trying to reason about these things unless I absolutely have to. I'm sure you can make it lock-free with effort, but you should really get someone very smart to do so if you really need to.
EDIT: I've just realised that the "large" case can make use of the "small" case - split the large number into two small ones and use the memoised results. I'll give that a go after dinner and write a benchmark...
EDIT: Okay, ready for a giant amount of code? I realised that for uniformly random numbers at least, you'll get "big" numbers much more often than small ones - so you need to optimise for that. Of course, that might not be the case for real data, but anyway... it means I now do my size tests in the opposite order, hoping for big numbers first.
I've got a benchmark for the original code, the simple memoization, and then the extremely-unrolled code.
Results (in ms):
Simple: 3168
SimpleMemo: 3061
UnrolledMemo: 1204
Code:
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
}
这篇关于最快的一个int数字分成.NET中的数组的方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
