Misra–Gries heavy hitters algorithm
મિશ્રા અને ગ્રીસે હેવી-હિટરની સમસ્યાને વ્યાખ્યાયિત કરી હતી (જોકે તેમણે હેવી-હિટર શબ્દ રજૂ કર્યો ન હતો) અને પેપર ફાઇન્ડિંગ રિપીટેડ એલિમેન્ટ્સમાં તેના માટે પ્રથમ અલ્ગોરિધમનું વર્ણન કર્યું હતું. તેમનું અલ્ગોરિધમ બોયર-મૂર બહુમતી શોધ અલ્ગોરિધમને નોંધપાત્ર રીતે વિસ્તરે છે. હેવી-હિટર સમસ્યાનું એક સ્વરૂપ નીચે મુજબ છેઃ તત્વોની થેલી અને પૂર્ણાંક આપવામાં આવે છે. એવા મૂલ્યો શોધો જે એક કરતા વધુ વખત આવે છે. મિશ્રા-ગ્રીઝ અલ્ગોરિધમમાં મૂલ્યો પર બે પાસ કરીને સમસ્યાનું સમાધાન કરે છે, જ્યારે અલ્ગોરિધમ દરમિયાન મોટાભાગના મૂલ્યો અને તેમની ઘટનાઓની સંખ્યાને સંગ્રહિત કરે છે. મિશ્રા-ગ્રીઝ એ પ્રારંભિક સ્ટ્રીમિંગ અલ્ગોરિધમ્સમાંનું એક છે, અને તે વિભાગ #Summaries માં તે શબ્દોમાં નીચે વર્ણવેલ છે. મિશ્રા-ગ્રીઝ અલ્ગોરિધમ બેગ એ એક સમૂહ જેવું છે જેમાં સમાન મૂલ્ય ઘણી વખત આવી શકે છે. ધારો કે બેગ તત્વોની શ્રેણી તરીકે ઉપલબ્ધ છે. અલ્ગોરિધમના અમૂર્ત વર્ણનમાં, આપણે અને તેના વિભાગોને પણ બેગ તરીકે ગણીએ છીએ. હવેથી, થેલીનો ભારે હિટર એ એક એવું મૂલ્ય છે જે તેમાં અમુક પૂર્ણાંક માટે એક કરતા વધુ વખત જોવા મળે છે. બેગ માટે એ-ઘટાડેલી થેલી જ્યાં સુધી શક્ય ન રહે ત્યાં સુધી નીચેની કામગીરીનું પુનરાવર્તન કરીને મેળવવામાં આવે છેઃ તેમાંથી અલગ ઘટકો કાઢી નાખો. તેની વ્યાખ્યા અનુસાર,-ઘટાડેલી થેલીમાં વિવિધ મૂલ્યો કરતાં ઓછા મૂલ્યો હોય છે. નીચેનો પ્રમેય સાબિત કરવા માટે સરળ છેઃ પ્રમેય 1. દરેક હેવી-હિટર માટે-ઘટાડેલી થેલીનું એક તત્વ છે. હેવી-હિટરની ગણતરીનો પ્રથમ પાસ-ઘટાડેલી થેલી બનાવે છે. બીજો પાસ એક તત્વને હેવી-હિટર જાહેર કરે છે જો તે એક કરતા વધુ વખત થાય છે. પ્રમેય 1 મુજબ, આ પ્રક્રિયા તમામ અને માત્ર હેવી-હિટર નક્કી કરે છે. બીજો પાસ પ્રોગ્રામ કરવા માટે સરળ છે, તેથી અમે ફક્ત પ્રથમ પાસનું વર્ણન કરીએ છીએ. રચના કરવા માટે, મૂલ્યોને મનસ્વી ક્રમમાં સ્કેન કરો, વિશિષ્ટતા માટે નીચેનું અલ્ગોરિધમ તેમને વધતા સૂચકાંકોના ક્રમમાં સ્કેન કરે છે. અલ્ગોરિધમનો ઇનવેરિયન્ટ એ છે કે તે સ્કેન કરેલા મૂલ્યો માટે-ઘટાડેલી બેગ છે અને તેમાં અલગ મૂલ્યોની સંખ્યા છે. શરૂઆતમાં, કોઈ મૂલ્ય સ્કેન કરવામાં આવ્યું નથી, ખાલી થેલી છે, અને શૂન્ય છે. જ્યારે પણ ઘટકને સ્કેન કરવામાં આવે ત્યારે, અપરિવર્તનને જાળવી રાખવા માટેઃ (1) જો તેમાં ન હોય તો, તેને ઉમેરો અને 1 વડે વધારો, (2) જો તેમાં હોય તો, તેને ઉમેરો પણ તેમાં ફેરફાર કરશો નહીં, અને (3) જો બરાબર થાય તો, તેમાંથી અલગ મૂલ્યો કાઢીને ઘટાડો અને યોગ્ય રીતે અપડેટ કરો. અલ્ગોરિધમ મિશ્રા-ગ્રીઝ એ 1 = t, d: = {}, 0 છે; i માટે 0 થી n-1 સુધી કરો જો b [i] t તો t, d: = t ≤ {b [i]}, d + 1 અન્યથા t, d: = t ≤ {b [i]} અંત જો d = k હોય તો પછી અપડેટમાંથી અલગ મૂલ્યોને કાઢી નાખો અંત માટે A નું સંભવિત અમલીકરણ ફોર્મની જોડીના સમૂહ તરીકે છે,) જ્યાં દરેક એક અલગ મૂલ્ય છે અને તે અંદરની ઘટનાઓની સંખ્યા છે. પછી આ સમૂહનું કદ છે. "માંથી અલગ મૂલ્યો કાઢી નાંખો" પગલું દરેકને 1 વડે ઘટાડવા અને પછી જો 0 બને તો સમૂહમાંથી કોઈપણ જોડી (,) ને દૂર કરવા સમાન છે. AVL વૃક્ષના અમલીકરણનો ઉપયોગ કરીને, અલ્ગોરિધમનો ચાલી રહેલો સમય હોય છે. જગ્યાની જરૂરિયાતનું મૂલ્યાંકન કરવા માટે, ધારો કે તેના ઘટકોમાં સંભવિત મૂલ્યો હોઈ શકે છે, તેથી મૂલ્યના સંગ્રહ માટે બિટ્સની જરૂર છે. દરેક કાઉન્ટરનું મૂલ્ય જેટલું ઊંચું હોઈ શકે છે, તેના સંગ્રહ માટે બિટ્સની જરૂર પડે છે. તેથી, મૂલ્ય-કાઉન્ટર જોડીઓ માટે, જગ્યાની જરૂરિયાત છે. સારાંશો સ્ટ્રીમિંગ અલ્ગોરિધમ્સના ક્ષેત્રમાં, પ્રથમ પાસમાં મિશ્રા-ગ્રીઝ અલ્ગોરિધમના આઉટપુટને સારાંશ કહી શકાય, અને આવા સારાંશોનો ઉપયોગ ડેટા સ્ટ્રીમ મોડેલમાં વારંવાર ઘટકોની સમસ્યાને ઉકેલવા માટે થાય છે. સ્ટ્રીમિંગ અલ્ગોરિધમ સ્ટ્રીમ તરીકે ઓળખાતી ડેટા વસ્તુઓની સૂચિ પર નાની, મર્યાદિત સંખ્યામાં પાસ બનાવે છે. તે જવાબ આપવા માટે સૂચિના કદમાં વધારાની જગ્યાના મહત્તમ લઘુગણક જથ્થાનો ઉપયોગ કરીને તત્વોની પ્રક્રિયા કરે છે. મિશ્રા-ગ્રીઝ સારાંશ શબ્દ ગ્રેહામ કોર્મોડ દ્વારા રચવામાં આવ્યો હોવાનું જણાય છે. સંદર્ભો સ્ટ્રીમિંગ અલ્ગોરિધમ્સ