埃尔朗;形成大量重复整数

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

• 地址为8字节
• 1字/8字节 small integer

64位系统上的字大小:

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 然后在这里询问这种算法的具体实现。

使用中间列表是没有用的,位串不能直接转换为整数,所以我认为它也没有用,所以最好的解决方案是直接使用大num。 假设您想创建一个整数,该整数用十进制表示法表示,重复N次宽度为width的Pattern:

具有 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

时间非常长(1000000分钟为5分钟),并且呈指数增长。

减少这种情况的想法是以指数方式减少要执行的操作数。这个更聪明的版本使用的模式在每次迭代时宽度加倍,并在需要时连接到当前结果(我使用了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).

结果要好得多:1000000只需5秒,由于乘法运算,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