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