Approximate counting algorithm
અંદાજિત ગણતરી અલ્ગોરિધમ નાની માત્રામાં મેમરીનો ઉપયોગ કરીને મોટી સંખ્યામાં ઘટનાઓની ગણતરી કરવાની મંજૂરી આપે છે. બેલ લેબ્સના રોબર્ટ મોરિસ દ્વારા 1977માં શોધાયેલ, તે કાઉન્ટરને વધારવા માટે સંભવિત તકનીકોનો ઉપયોગ કરે છે. 1980ના દાયકાની શરૂઆતમાં INRIA રોક્વેનકોર્ટના ફિલિપ ફ્લેજોલેટ દ્વારા તેનું સંપૂર્ણ વિશ્લેષણ કરવામાં આવ્યું હતું, જેમણે અંદાજિત ગણતરી નામ બનાવ્યું હતું અને સંશોધન સમુદાયમાં તેની માન્યતામાં મજબૂત યોગદાન આપ્યું હતું. જ્યારે અંદાજની ઉચ્ચ ગુણવત્તા અને નિષ્ફળતાની ઓછી સંભાવના પર ધ્યાન કેન્દ્રિત કરવામાં આવ્યું, ત્યારે નેલ્સન અને યુએ દર્શાવ્યું કે મોરિસ કાઉન્ટરમાં ખૂબ જ થોડો ફેરફાર સમસ્યા માટેના તમામ અલ્ગોરિધમ્સમાં એસિમ્પ્ટોટિક રીતે શ્રેષ્ઠ છે. અલ્ગોરિધમને સ્ટ્રીમિંગ અલ્ગોરિધમ્સના અગ્રદૂતમાંથી એક માનવામાં આવે છે, અને ડેટા સ્ટ્રીમની આવર્તન ક્ષણો નક્કી કરવાની વધુ સામાન્ય સમસ્યા ક્ષેત્ર માટે કેન્દ્રિય રહી છે. મોરિસના અલ્ગોરિધમનો ઉપયોગ કરીને, કાઉન્ટર વાસ્તવિક ગણતરીના "તીવ્રતાના અંદાજનો ક્રમ" રજૂ કરે છે. અંદાજ ગાણિતિક રીતે નિષ્પક્ષ છે. કાઉન્ટરને વધારવા માટે, સ્યુડો-રેન્ડમ ઇવેન્ટનો ઉપયોગ કરવામાં આવે છે, જેમ કે વૃદ્ધિ એ સંભવિત ઘટના છે. જગ્યા બચાવવા માટે, માત્ર ઘાતાંક રાખવામાં આવે છે. ઉદાહરણ તરીકે, આધાર 2 માં, કાઉન્ટર ગણતરીને 1,2,4,8,16,32 અને બેની તમામ શક્તિઓ હોવાનો અંદાજ લગાવી શકે છે. મેમરીની જરૂરિયાત ફક્ત ઘાતાંકને પકડી રાખવાની છે. ઉદાહરણ તરીકે, 4 થી 8 સુધી વધારવા માટે, એક સ્યુડો-રેન્ડમ નંબર એવી રીતે જનરેટ કરવામાં આવશે કે કાઉન્ટર વધવાની સંભાવના 0.25 છે. નહિંતર, કાઉન્ટર 4 પર રહે છે. નીચેનું કોષ્ટક કાઉન્ટરના કેટલાક સંભવિત મૂલ્યોને સમજાવે છેઃ જો કાઉન્ટર 101 નું મૂલ્ય ધરાવે છે, જે 5 ના ઘાતાંક (101 ની દશાંશ સમકક્ષ) સમાન છે, તો પછી અંદાજિત ગણતરી છે, અથવા 32. ત્યાં એકદમ ઓછી સંભાવના છે કે વૃદ્ધિ ઘટનાઓની વાસ્તવિક ગણતરી 5 () હતી. વૃદ્ધિની ઘટનાઓની વાસ્તવિક સંખ્યા "લગભગ 32" હોવાની શક્યતા છે, પરંતુ તે મનસ્વી રીતે વધારે હોઈ શકે છે (39થી ઉપરની વાસ્તવિક ગણતરીઓની ઘટતી સંભાવનાઓ સાથે). કાઉન્ટર મૂલ્યોની પસંદગી જ્યારે કાઉન્ટર મૂલ્યો તરીકે 2 ની શક્તિનો ઉપયોગ કરવો એ મેમરી કાર્યક્ષમ છે, મનસ્વી મૂલ્યો ગતિશીલ ભૂલ શ્રેણી બનાવવાનું વલણ ધરાવે છે, અને નાના મૂલ્યોમાં મોટા મૂલ્યો કરતાં વધુ ભૂલ ગુણોત્તર હશે. કાઉન્ટર મૂલ્યો પસંદ કરવાની અન્ય પદ્ધતિઓ મૂલ્યોના શ્રેષ્ઠ સમૂહને પ્રદાન કરવા માટે મેમરી ઉપલબ્ધતા, ઇચ્છિત ભૂલ ગુણોત્તર અથવા ગણતરી શ્રેણી જેવા પરિમાણોને ધ્યાનમાં લે છે. જો કે, જ્યારે ઘણા કાઉન્ટર્સ સમાન મૂલ્યો શેર કરે છે, ત્યારે મૂલ્યો સૌથી મોટી ગણતરી શ્રેણી સાથે કાઉન્ટર અનુસાર ઑપ્ટિમાઇઝ થાય છે, અને નાના કાઉન્ટર્સ માટે પેટા-શ્રેષ્ઠ ચોકસાઈ ઉત્પન્ન કરે છે. સ્વતંત્ર કાઉન્ટર એસ્ટિમેશન બકેટ જાળવીને શમન પ્રાપ્ત થાય છે, જે બકેટમાં અન્ય કાઉન્ટર પર મોટા કાઉન્ટરની અસરને પ્રતિબંધિત કરે છે. અલ્ગોરિધમ અલ્ગોરિધમનો હાથ દ્વારા અમલ કરી શકાય છે. કાઉન્ટરને વધારતી વખતે, કાઉન્ટરના વર્તમાન મૂલ્યને અનુરૂપ સિક્કાને ઘણી વખત ફેરવો. જો તે દરેક વખતે ઉપર આવે, તો પછી કાઉન્ટરમાં વધારો કરો. નહિંતર, તેને વધારશો નહીં. આ કમ્પ્યુટર પર સરળતાથી પ્રાપ્ત કરી શકાય છે. ધારો કે કાઉન્ટરનું વર્તમાન મૂલ્ય છે. સ્યુડો-રેન્ડમ બિટ્સ જનરેટ કરીને અને તે તમામ બિટ્સના લોજિકલ AND નો ઉપયોગ કરીને અને પરિણામને કાઉન્ટર પર ઉમેરો. જો તેમાંથી કોઈપણ સ્યુડો-રેન્ડમ બિટ્સ શૂન્ય હોય તો પરિણામ શૂન્ય હતું, જે વૃદ્ધિ સંભાવના પ્રાપ્ત કરે છે. જ્યારે પણ કાઉન્ટરને વધારવા માટે વિનંતી કરવામાં આવે ત્યારે આ પ્રક્રિયા ચલાવવામાં આવે છે. એપ્લિકેશન્સ અલ્ગોરિધમ પેટર્ન માટે મોટા ડેટા સ્ટ્રીમ્સની તપાસ કરવામાં ઉપયોગી છે. આ ખાસ કરીને માહિતી સંકોચન, દૃષ્ટિ અને ધ્વનિ ઓળખ અને અન્ય કૃત્રિમ બુદ્ધિના ઉપયોગોમાં ઉપયોગી છે. હાઇપરલોગલોગ સંદર્ભો સ્ત્રોતો મોરિસ, આર. નાના રજિસ્ટરમાં મોટી સંખ્યામાં ઘટનાઓની ગણતરી પણ જુઓ. કોમ્યુનિકેશન્સ ઓફ ધ ACM 21,10 (1978), 840-842 ફ્લેજોલેટ, પી. અંદાજિત ગણતરીઃ એક વિગતવાર વિશ્લેષણ. BIT 25, (1985), 113-134 ફૌચસ, એમ., લી, સી. કે., પ્રોડિંગર, એચ., પોઈસન-લેપલેસ-મેલિન પદ્ધતિ દ્વારા અંદાજિત ગણતરી રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સ