使用静态 int 数组进行缓存的阶乘

Question

static int count = 0;
static long[] cache = new long[3000];

static {
    cache[0] = 1;
}
public static void main(String args[]) {
    for (int i = 0; i < 100; i++){
        factorial_with_cache(2999);
    }
    System.out.println(count);        
}

public static long factorial_with_cache (int n){
    if (cache[n] != 0){
        return cache[n];
    }
    cache[n] = n * factorial_with_cache(n - 1);
    count++;
    return cache[n];
}

我构建了一个使用缓存计算阶乘的函数（忽略溢出）。

但与非缓存功能相比，它的运行时间也好不到哪里去，我发现缓存无法正常工作。

因为我预计变量 'count' 在循环后为 2999，但我发现它是 293465，比这多得多。（没有循环，它打印 2999）

这个函数有什么问题？

Answer 1

所以，让我为您分解一下！

2999的阶乘值为13831198678126180285189556976955373903170397316439366392298225525658528550411773166953335884059334473358394878461205706165250290371348635931517800720356113203873679301399725840687554463393227601721573232498656280819242922032367667908703698446747042372944385912938442812976579204340368770976791467161792908482026536763476497016597962706920837208377639001547222987372530067858391829660217859289638428364594156664891566396944031170356121274762354507422848113071258383496196034678939603033097637499047300169646331468238450491051510529147169986724755958362486789324705690789582425714662973561230539501202732819906031261484507986168459203695503720787715306962036185816958171315101812071237299383615730698142124734425009998777928314671591890471560274735833304904959453223240212984890196653392856493421129589037623689334983609133572374939825462133789731181451373437595533811597516653047843373551034468875167743673579450500731701049557870779579798365517154053116338596649981357437001475641612713380485162624246015285341187194401439315317685276897783748963573748717156161769574677089322363037849660911158458585633121725465474927244487503626338581145799640164089032772344644035725447994450814858680158855133471471566493328118184865933128900946476171137729637721898436949504508364668715924682335777135513931476001478897301228489756952423900549337170685817482869322924594934553551003036605213030431370211238540513634600045019557208087444634144722209572173742863424856277834965975623123264292792298280478857955478985025157988294085407394460004866920398953072534411602822485072110137246001443714741975414563519594304969324628586261528579942898463434127945755294142551435479172585965738348357120600576683876141492098075828585209276254499589065093789637861306274833094913863894376778010733315584027638295254781954610771181735025318637354022424432317128707664886202509105961484149955116054723079614963020498616978124480963271628142440605710424177963844835527047941127068625126602868360296587251294298750977877916818183056200089076530408509618194827562218441437670451251604136520412562026002566902646513949635716489125951469176102624329367970981707309954931234483752478815193819919046940901995441721784302194857041195090070644484327035189466269961364993448728359341757679578928014056475745993488101416681676935545677586672113973814268569600810283522630702882325818379846373279545389063433426048793378977494110923865060198731023168079278694206856962403099309932476468192292446106625814895181431600107247018896474570181676290139870638357579666677214004824737774431290539343185204668200955800140961796618216776009476171707432009598580600540607745366106990480349004177689104965384412262911661517983201465683450782588737131971506423474040743808999564029154506993562074784937792064798377314289371162177187409391071658827235127282051775532062510098826200386957421213481307419200642164870305628383671047981858132767730852384720717147489707456839716365953949812050321036644546531520598864465617319535112877058774715688947419064131580843908826519916664427749093269298823584351338064696733536570891584395455175134404252585951310232510018865069402485833157299381484590749402629481111706181867189617902727630965072766713218125649095472925555254271796579113386470181227145145782044748230689023360927474548519150294185556719080917603439047213543803560461443641342427106320294937680221742056517608545727954154981431896286464615575574564733158523773515339421141910343038451177576269394257673865595696145764470705694837193543322565755533887878425653323007167374034984753189092864395172089482366791478206807334511797067912797698473565007162069130217730303607114778083832632094745399523891591282708699147685012083622118240243657099361565732179240926631053400186908352669170802498149387797404799372830916093992885059492849249732904712828347430127984696856947346045759045222567855013693926840231677378744507230913510338446973920611359605911891548916357205533551076812967546595355169668436624145148563105200443314135704098338484590507017314148504265121657071624074064576429719944333914132659197510167106279294498294744074169106272133146311875939034291810862931519619247593463572388793752634599383049481842295290543310338170244405184924421525345305394766236107745856279305711691002008912764098229027010250648673458812712892369111259770860752452145178192387601343493641928636582411137977634690746620001816089765370131213375846513299799140007308422976207521653093045456515661082438164698099164737736238987887604321282063792704869736900344337373311421647222149710103632831178455467277094227704168859462141968845732336969092143110178250432445572309805015956983080592707178326499816577452815043403343240119997858835910187898983513330297084001603373363523211048122726398082654521129700828750257789083133267241150542349616716479447911942146684493824985807109624549493196517947945459425200477792599605375618154135498044805373036317551108920542553407043626403888641459832178279343412021431660661847004770522200579839513142002891066188195561545147576726674097535863255730732789176509455052905173962566105999668617707172897012592225627884763749139942033144845223843137607945870705185228736818194603451718134984572823575454406177591828833937000873777076143286975370719857688674644025825580933636487558107379601763547689237092321337911968750350350207856080439217177676925119658378188382474722467172490240279700623329997759788303630895974913235271384285181321984740867973019755275212448225468786508612988993837327986628867894584347339330109395315189804183506355434284956511125894328200010602697940710012700738129019153727101417320638801990152011727707236050552882452185513510976137249542985694285597433351175282125687093530484011848796644042625302116542612658623784196206071084087859012798734245795108302784560165996695233840827767813175065781551114331550855078698914278183507913244634124753936290599761240761788764479746965254304384814035524536401827280713121964622571847614159091700055578119247697879649481521588125728024624793157002622383690149851552542093855379183576921256026866677281432077992602744437119929192378994337605857208557227762427170645778895263145703032582860407622708941374105757560394991735954484369165110569420051053146751215121841484529317344915071143082972214834934785117427325907327323956351628058965466260901594022042307157516206082619875478093063424834484331589789332405761721821863933157263022628562426191490028096574592744921026913639837655412782142613217955005774888616730714697231543457088527065900258227520678399439594304530337999272434545057921568904794664270097074820282773506327749449618377008513240527728310551223577424390998477250258491878249375773652218477283959862326057497240566955256032969442610279413479245991485114175229570966285171060322337499286484763536542456863553323594724246140240535192263020188389231521830040129388591953979743641454327796516619093291507799363499952822494950133169703132944736808231037872625326203934365369591454254996804885055848502537888575304997792038113414587636763461378629510437530377514949741965335728283723130064661811549805161260779434177122925330001814574110967154189394698666276840840528442866611330112198472977565560054421966452744887749026774673476597119141918499516457632064030550264890665707146610860517981945041882670296628962352294237074209578011924139474934410391009112814073534671869747359856497734981269800821854176767776274721767346002013762814794961396376464661990588556737167203780040389785178621661600980521079426482525438347561911423287705520933644054859388470137299692798736919535048363842176140811215743626823029475470841708861576378019731723918097050874000743252328975986374873654787685684044366405474086145883963064543443283741094316935375400191188518071061185279429772712931980320767930925743448141144113853867852863500774825091500876956610471375132123918137870632423052883572240769361145098526133695745342449000372928715411061813143685686161256824935345001518961673534243407418799210246313328341659385060893305664721381846776636604396835551452718885897176356302728734712814697152118430414021633905812143491151730458640971651094329383936246692244495665898440957150263861482901326801912557851925957864645963859049318674446902818797438056706130851744872706591971891128651973088423541354578092586738615503678456019321106904965647554452856791768609892202741402821821519518889296407542539996754653930879152617217513639585536181286553740648082906808320000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000find it yourself

我知道滚动很多:P

好的，现在在您的迭代过程中，20 的阶乘 将是 2,432,902,008,176,640,000，而 21 的阶乘 将是 51,090,942,171,709,440,000 和 java 中 long 的最大值是 9,223,372,036,854,775,807 所以，这里你的 cache[19] 将是 -4,249,290,049,419,214,848 而 cache[65] 将是 0。这使得缓存 [2999] 之前的所有值变为 0。因此，每次调用方法 factorial_with_cache 时，它都不是从缓存中提供服务，而是每次都计算（因为您正在检查 if(cache[n] != 0) 然后 return 从缓存中计算）导致计数值293465 而不是 2999.

为了您的理解，我对代码做了一些修改。

public class Test2 {
    static int count = 0;
    static long[] cache = new long[3000];

    static {
        cache[0] = 1;
    }
    public static void main(String args[]) {
            factorial_with_cache(2999);
    }

    public static long factorial_with_cache (int n){
        if (cache[n] != 0){
            return cache[n];
        }
        cache[n] = n * factorial_with_cache(n - 1);
        System.out.println("Factorial(" + n + ") is " + cache[n]);
        count++;
        return cache[n];
    }
}

这将打印您计算出的事实值。

public class Test2 {
    static int count = 0;
    static long[] cache = new long[3000];

    static {
        cache[0] = 1;
    }
    public static void main(String args[]) {
        for (int i = 0; i < 100; i++){
            factorial_with_cache(2999);
            System.out.println("i[" + i + "] count[" + count +"]");
        }
    }

    public static long factorial_with_cache (int n){
        if (cache[n] != 0){
            return cache[n];
        }
        cache[n] = n * factorial_with_cache(n - 1);
        count++;
        return cache[n];
    }
}

这将打印每次迭代的计数值。

Answer 2

因为long数据类型的范围：

long 8 bytes (-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807)

在您搜索 25 的阶乘之前，您的阶乘会给出正值。后面的 25 ，计算出的阶乘值为负（这意味着你溢出了很长时间）并且你的计数将按预期工作直到计算出 65 阶乘（直到负值）然后阶乘 66 的值达到 0 ..

只需在下面打印阶乘即可：

for (int i = 0; i < 100; i++) {
          long fact=factorial_with_cache(66);
          System.out.println(fact);
        }
        System.out.println(count);

并且计数将打印为

(forLoopCount*(number-65))+65 , In your case (100*(2999-65))+65 is 293465

因为它在缓存中追溯的阶乘值不为零，因此是第 65 个元素（在 64 索引处）。

使用静态 int 数组进行缓存的阶乘

Factorial with caching with static int array

java

caching

runtime

factorial