Erlang;形成庞大的重复整数

Question

在Erlang中，有没有办法形成一个没有列表的大规模重复整数？

我写道：

{I, _} = string:to_integer(lists:concat([9 || _ <- lists:seq(1,trunc(math:pow(10,2)))])), I. 

形成100路787-9的列表，然后将整数999 ....（100 787-9）。然而，如果我想要形成一个数量为十亿分之九的列表，则这会失败：

{I, _} = string:to_integer(lists:concat([9 || _ <- lists:seq(1,trunc(math:pow(10,9)))])), I. 

（永不完成）。清单明智地，10亿整数列表的内存占用量应该是大约4GB，所以不应该成为一个内存问题来保存单个大规模的int（尽管我不确定在Erlang中如何实现任意的精度整数） ）。

有没有一种方法可以做到这一点？

Answer 1

你不能真正创建这样一个长列表，然后尝试将其转换为整数。 Erlang中的列表是linked list，每个元素都包含值和下一个元素的地址。对于64位系统，这将意味着每元件16个字节：在64位系统地址

• 8字节
• 1个字/ 8个字节用于small integer

字长：

7> erlang:system_info(wordsize). 
8 

因此，构建一个列表与1.0e9元素需要1.6e10字节或15 GB：

13> 1.6e10/(1024*1024*1024). 
14.901161193847656 

这很可能超出了单个进程在大多数系统上可以分配的内容。

唯一的方法是应用某种数学公式来算法地创建这样一个数字。一个天真的执行将得到10简单乘法和加法次数多次：

-module(bigint). 

-export([make/2]). 

make(N, A) -> make(N, A, N). 

make(_N, 1, R) -> R; 
make(N, A, R) -> make(N, A-1, R*10+N). 

结果：

2> bigint:make(3, 5). 
33333 

但它成倍放缓与数字量，所以，只要超过几十万的数字是计算起来可能计算起来太昂贵了。

您也可以尝试，生成二进制的，而不是一个列表，因为二进制文件implemented on consecutive bytes在内存段，如：

-module(bigint). 

-export([make/2]). 

make(N, A) -> 
    Bin = integer_to_binary(N), 
    make(Bin, A, Bin). 

make(_B, 1, R) -> binary_to_integer(R); 
make(B, A, R) -> make(B, A-1, <<R/binary, B/binary>>). 

但是计算，这将是类似于以前的解决方案 - 一个大的二进制可构建得非常快，但后来将其转换为整数的计算成本很高。

您可以试着问一个关于算法的问题，用最小的步数或Mathematic SE在算法上创建一个大数字，然后在这里询问这种算法的具体实现。

Answer 2

使用中间列表是没有用的，bitstring不是直接转换成整数，所以我不认为它也有用，所以最好的解决方案是直接使用大数字。 让说你想要创建其在十进制表示由宽度宽的图案的N次重复来表示的整数：

与N = 3，Pattern = 52，Width = 4，预期的结果是5200520052

第一个简单的实现，通过移动并添加模式N次计算结果，但对于大N来说效率非常低。下面是一个实现（请注意，为了衡量性能，我避免打印结果，因为否则shell会将整数iolist）：

-module (pattern). 

-export ([simple/3,perf/4]). 

simple(N,Pattern,Width) when is_integer(N), N > 0 -> 
    simple(N,Pattern,shift(1,Width),0). 

simple(0,_,_,R) -> R; 
simple(X,P,Shift,R) -> simple(X-1,P,Shift,R*Shift+P). 


shift(X,0) -> X; 
shift(X,N) -> shift(10*X,N-1). 

perf(Type,N,P,S) -> 
    {T,_} = timer:tc(?MODULE,Type,[N,P,S]), 
    T. 

这样，你得到的结果：

1> pattern:simple(7,52,3). 
52052052052052052052 
2> pattern:simple(7,52,2). 
52525252525252 
3> pattern:perf(simple,1000,5,1).  
0 
4> pattern:perf(simple,10000,5,1). 
63000 
5> pattern:perf(simple,100000,5,1). 
1810000 
6> pattern:perf(simple,1000000,5,1). 
309522533 

的时间很长（5分钟1000000）和成倍增加。

减少这一点的想法是要成倍减少操作的次数。这个智能版本是使用图案至极在宽度在每次迭代增加一倍，并在需要时在当前结果级联（I有使用N的分解在2的幂）：

-module (pattern). 

-export ([simple/3,smarter/3,perf/4]). 

simple(N,Pattern,Width) when is_integer(N), N > 0 -> 
    simple(N,Pattern,shift(1,Width),0). 

simple(0,_,_,R) -> R; 
simple(X,P,Shift,R) -> simple(X-1,P,Shift,R*Shift+P). 


shift(X,0) -> X; 
shift(X,N) -> shift(10*X,N-1). 

perf(Type,N,P,S) -> 
    {T,_} = timer:tc(?MODULE,Type,[N,P,S]), 
    T. 

smarter(1,Pattern,_Width) -> Pattern; 
smarter(N,Pattern,Width) when is_integer(N), N > 0 -> 
    smarter(N,Pattern,shift(1,Width),0). 

smarter(1,Pattern,Shift,R) -> 
    R * Shift + Pattern; 
smarter(X,Pattern,Shift,R) when (X rem 2) == 0 -> 
    smarter(X div 2, Shift * Pattern + Pattern, Shift * Shift, R); 
smarter(X,Pattern,Shift,R) -> 
    smarter(X div 2, Shift * Pattern + Pattern, Shift * Shift, R * Shift + Pattern). 

的结果是多更好：5万秒1000000，仍然增加n * n，由于乘法。

1> pattern:smarter(7,52,4).   
52005200520052005200520052 
2> pattern:smarter(7,9,1). 
9999999 
3> pattern:perf(smarter,1000,5,1). 
0 
4> pattern:perf(smarter,10000,5,1). 
0 
5> pattern:perf(smarter,100000,5,1). 
125000 
6> pattern:perf(smarter,500000,5,1). 
1279007 
7> pattern:perf(smarter,1000000,5,1). 
5117000