将非常大的数字转换为基数10字符串
一个整数测量4个字节。 在我的例子中,我的数字为1 MB。 如何快速将它们转换为人类可读的十进制数?
该数字出现在包含Size
项的uint[]
数组中。
我不知道这是否更快,但这里是delphi中的一个例子,我很久以前写过把大字符串作为字符串处理(非常快速和脏) – 这是128bit uint但你可以无限延长
Function HexToBinShort(hex:integer):string; begin case hex of 0: result:='0000'; //convert each hex digit to binary string 1: result:='0001'; //could do this with high-nybble and low nybble 2: result:='0010'; //of each sequential byte in the array (mask and bit shift) 3: result:='0011'; //ie: binstring:=binstring + HexToBinShort(nybble[i]) 4: result:='0100'; //but must count DOWN for i (start with MSB!) 5: result:='0101'; 6: result:='0110'; 7: result:='0111'; 8: result:='1000'; 9: result:='1001'; 10: result:='1010'; 11: result:='1011'; 12: result:='1100'; 13: result:='1101'; 14: result:='1110'; 15: result:='1111'; end; end;
然后取出连接的二进制字符串,每次看到’1’时加上2的幂
Function BinToIntString(binstring:string):string; var i, j : integer; var calcHold, calc2 :string; begin calc2:=binstring[Length(binstring)]; // first bit is easy 0 or 1 for i := (Length(binstring) - 1) downto 1 do begin if binstring[i] = '1' then begin calcHold:=generateCard(Length(binstring)-i); calc2 := AddDecimalStrings(calcHold, calc2); end; end; result:=calc2; end;
generateCard用于创建2 ^ i的十进制字符串表示(对于i> 0)
Function generateCard(i:integer):string; var j : integer; var outVal : string; begin outVal := '2'; if i > 1 then begin for j := 2 to i do begin outVal:= MulByTwo(outVal); end; end; result := outVal; end;
和MulByTwo将十进制字符串乘以2
Function MulByTwo(val:string):string; var i : integer; var carry, hold : integer; var outHold : string; var outString :string; var outString2 : string; begin outString:= StringOfChar('0', Length(val) + 1); outString2:= StringOfChar('0', Length(val)); carry :=0; for i := Length(val) downto 1 do begin hold := StrToInt(val[i]) * 2 + carry; if hold >= 10 then begin carry := 1; hold := hold - 10; end else begin carry := 0; end; outHold := IntToStr(hold); outString[i+1] := outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end;
最后 – AddDecimalStrings ……好吧,它添加了两个十进制字符串:
Function AddDecimalStrings(val1, val2:string):string; var i,j :integer; var carry, hold, largest: integer; var outString, outString2, bigVal, smVal, outHold:string; begin if Length(val1) > Length(val2) then begin largest:= Length(val1); bigVal := val1; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val2) +1) to largest do begin smVal[i] := val2[j]; j:=j+1; end; end else begin if length(val2) > Length(val1) then begin largest:=Length(val2); bigVal:=val2; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val1) +1) to largest do begin smVal[i] := val1[j]; j:=j+1; end; end else begin largest:=length(val1); bigVal:=val1; smVal:=val2; end; end; carry:=0; outString:=StringOfChar('0', largest +1); outString2:=StringOfChar('0', largest); for i := largest downto 1 do begin hold := StrToInt(bigVal[i]) + StrToInt(smVal[i]) + carry; if hold >=10 then begin carry:=1; hold := hold - 10; end else begin carry:=0; end; outHold:= IntToStr(hold); outString[i+1]:=outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end;
这些函数允许您对几乎任意大的整数执行基本算术作为字符串。 当然,当数字位数太大而无法索引数组时,你会碰到另一面墙。
这是一个除以二,顺便说一句(对于另一种方式很有用……)。 我这里不处理奇数。
Function DivByTwo(val:string):string; var i : integer; var hold : integer; var outHold : string; var outString, outString2 :string; begin outString:=StringOfChar('0',Length(val)); for i := Length(val) downto 1 do begin if StrToInt(val[i]) mod 2 = 0 then begin hold:= Math.Floor(StrToInt(val[i]) / 2); outHold:= IntToStr(hold); outString[i]:=outHold[1]; end else begin hold:= Math.Floor((StrToInt(val[i]) - 1) / 2); outHold:=IntToStr(hold); outString[i]:= outHold[1]; if i <> Length(val) then begin hold:= StrToInt(outString[i+1]) + 5; outHold:= IntToStr(hold); outString[i+1] := outHold[1]; end; end; end; outString2:=StringOfChar('0',Length(val)-1); if (outString[1] = '0') and (length(outString) > 1) then begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result:=outString2; end else begin result:=outString; end; end;
编辑:我刚用一个900万位长的二进制字符串尝试了这个,它非常慢! 真的,这并不奇怪。 这是一个完全未经优化的代码,它有很多低成本可供选择,以加快速度。 尽管如此,我还是忍不住觉得这是你可能想要在完全优化的assembly中编写的问题的种类(或规模)。 个别操作很小但是必须多次完成 – 这些咒语要求组装。 multithreading当然也可以在这里使用。
我一直在考虑你的问题。 我没有编写解决方案,但这是一种方法:
首先,让我们假设你有一个2 n位的集合而不失一般性。 (如果你的位数少于2 n ,则用前导零填充位数组,直到你这样做。显然这样做的时间绝对不会超过数组的大小。)在你的情况下,你说你有一百万的uint,所以这是2 25位。
我们还假设每个2 k + 1位的集合可以均匀地分成两个位集合,左右集合,每个集合有2 k位。
因此,每个比特集合或子集合具有“大小”,其是2的精确幂。 最小的集合包含一个位,无法进一步细分。
其次,我们假设您同样具有十进制forms的数字的不可变表示,并且再次,在不失一般性的情况下,字符串中有2个d十进制数字。 如果少于2 d ,则再次使用前导零填充。 同样,每个大于1的小数集合可以分成两个集合,每个集合大小只有一半。
现在我们勾勒出一个递归算法:
DigitCollection Convert(BitCollection bits) { if (bits.Size == 1) return bits[0] ? DigitCollection.SingleOne : DigitCollection.SingleZero; DigitCollection left = Convert(bits.Left); DigitCollection right = Convert(bits.Right); DigitCollection power = MakePowerOfTwo(bits.Right.Size); return Add(Multiply(left, power), right); }
我们现在需要方法Add,Multiply和MakePowerOfTwo。 正如我们稍后将看到的,我们还需要Subtract和两个Shift运算符,以便快速乘以10的幂。
加法和减法很容易。 显然,如果较长的集合包含n个数字,则可以实现加法和减法方法以花费O(n)时间。
FullShift和HalfShift运算符从旧的数字集合中创建新的数字集合,以便于以10的幂进行快速乘法。 如果大小为2 d + 1的数字集合由每个大小为2 d的子集合(X1,X2)组成,那么“半移”集合包含2 d + 2项并且由((2 d前导零,X1)组成),(X2,2 d尾随零))。 全class集合包括((X1,X2),(2 d + 1尾随零))。
这些显然非常便宜。
乘法是我们遇到大问题的地方 。 假设在不失一般性的情况下,我们将两个DigitCollections相乘,每个DigitCollections正好有2个数字。 我们可以使用Karatsuba的算法:
DigitCollection Multiply(DigitCollection x, DigitCollection y) { // Assume x and y are the same digit size. if (x and y are both single digits) return the trivial solution; // Assume that z2, z1 and z0 are all the same digit size as x and y. DigitCollection z2 = Multiply(x.Left, y.Left); DigitCollection z0 = Multiply(x.Right, y.Right); DigitCollection z1 = Subtract( Multiply(Add(x.Left, x.Right), Add(y.Left, y.Right)), Add(z2, z0)); return Add(Add(FullShift(z2), HalfShift(z1)), z0); }
这个算法的顺序是什么? 假设有n = 2个d位数。 什么是O(乘(n))? 我们递归三次,每次都有一半的数字问题。 其余的加,减和移位操作都不超过O(n)。 所以我们有一个复发:
T(n) = 3 T(n/2) + O(n)
通过主定理有一个简单的解决方案:这个算法是O(n 1 / lg 3 ),大约是O(n 1.58 )。
MakePowerOfTwo怎么样? 鉴于我们已经拥有的东西,这很容易。 我们使用身份:
2 2n + 1 = 2 n x 2 n + 2 n x 2 n
并编写算法:
DigitCollection MakePowerOfTwo(int p) { if (p == 0) return DigitCollection.SingleOne; DigitCollection power = MakePowerOfTwo(p / 2); power = Multiply(power, power); if (p % 2 != 0) power = Add(power, power); return power; }
它由乘法的计算决定,O(n 1.58 )也是如此。
现在我们可以看到转换的原始调用也由乘法控制。
因此,如果您有2 d二进制数字进行转换,使用此算法,您可以预期这将需要大约O(2 1.58 d )步骤。 在你的情况下你有2 25位转换,所以这应该需要大约7,770亿计算。
这里的关键事实是该算法完全由乘法的成本支配 。 如果你可以将乘法的成本降低到小于O(n 1.58 ),那么你将获得巨大的胜利。 如果我是你,我将研究对Karatsuba的十进制乘法算法的改进。
您可以通过一次执行多个数字来节省一些时间。 如果你这样做,比如说,每次100,000,那么它一次可能至少比10快一点。
请注意,它仍然可能非常缓慢,但它会为您节省一些时间。
可以想象你可以使它递归,并加快它的速度 – 获得数字的粗略平方根,向下舍入到最接近的10. div和mod的指数,并将结果发送回相同的function。 请注意,我不确定你如何有效地运行那个大小的div或mod,但是如果你能弄明白(并且不会耗尽内存),它仍然必然会更加节省时间而不是一次将其分成一个数字。
替代版本:放弃小数 – 因为数字太大而无法理解任何真正的人类读者 – 并以hex呈现。 技术上仍然是人类可读的,但你可以一次渲染一个字节,为自己省去了很多心痛。
谢谢大家,我想出了一种主要基于J …的想法,他建议将数字转换为10个基数,每次加1时加2的幂。 但是我使用基于1000000000000000000(10 ^ 18)的系统而不是基于10的(人类十进制系统)。 所以每个数字不仅有10个可能性(0 … 9),实际上10 ^ 18! 这适用于我们随后转换的64位数字.ToString()
这是最有效的方式。
上述就是C#学习教程:将非常大的数字转换为基数10字符串分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/960750.html