Kinetic data structure
કાઇનેટિક ડેટા સ્ટ્રક્ચર એ એક ડેટા સ્ટ્રક્ચર છે જેનો ઉપયોગ ભૌમિતિક પ્રણાલીના લક્ષણને ટ્રેક કરવા માટે થાય છે જે સતત આગળ વધી રહ્યું છે. ઉદાહરણ તરીકે, ગતિશીલ બહિર્મુખ પતવાર માહિતી માળખું ગતિશીલ બિંદુઓના જૂથના બહિર્મુખ પતવારને જાળવે છે. કાઇનેટિક ડેટા સ્ટ્રક્ચર્સનો વિકાસ સતત ગતિમાં ભૌતિક પદાર્થોને સંડોવતા કોમ્પ્યુટેશનલ ભૂમિતિ સમસ્યાઓ દ્વારા પ્રેરિત હતો, જેમ કે રોબોટિક્સ, એનિમેશન અથવા કમ્પ્યુટર ગ્રાફિક્સમાં અથડામણ અથવા દૃશ્યતા શોધ. ઝાંખી કાઇનેટિક ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ સિસ્ટમો પર થાય છે જ્યાં મૂલ્યોનો સમૂહ હોય છે જે જાણીતા ફેશનમાં સમયના કાર્ય તરીકે બદલાઈ રહ્યો હોય છે. તેથી સિસ્ટમમાં કેટલાક મૂલ્યો હોય છે, અને દરેક મૂલ્ય માટે, તે જાણીતું છે. કાઇનેટિક ડેટા સ્ટ્રક્ચર્સ વર્તમાન વર્ચ્યુઅલ સમયે સિસ્ટમ પર ક્વેરીઝને મંજૂરી આપે છે, અને બે વધારાની કામગીરીઓઃઃ સિસ્ટમને સમયાંતરે આગળ વધે છે. : વર્તમાન સમય પ્રમાણે મૂલ્યના માર્ગને બદલે છે. વધારાની કામગીરીઓને ટેકો આપવામાં આવી શકે છે. ઉદાહરણ તરીકે, ગતિશીલ માહિતી માળખાઓનો ઉપયોગ ઘણીવાર બિંદુઓના સમૂહ સાથે થાય છે. આ કિસ્સામાં, માળખું સામાન્ય રીતે બિંદુઓને દાખલ કરવા અને કાઢી નાખવાની મંજૂરી આપે છે. પરંપરાગત ડેટા સ્ટ્રક્ચર્સ સાથે વિરોધાભાસ ગતિશીલ ડેટા સ્ટ્રક્ચર તેમાં સંગ્રહિત મૂલ્યોને સમય સાથે સતત બદલવાની મંજૂરી આપે છે. સૈદ્ધાંતિક રીતે, નિશ્ચિત સમયાંતરે બિંદુઓની સ્થિતિનું નમૂના લઈને અને દરેક બિંદુને "સ્થિર" (પરંપરાગત) ડેટા માળખામાં કાઢીને અને ફરીથી દાખલ કરીને આનો અંદાજ લગાવી શકાય છે. જો કે, કયા સમય અંતરાલનો ઉપયોગ કરવામાં આવે છે તેના આધારે, આ પ્રકારનો અભિગમ ઓવરસેમ્પલિંગ અથવા અન્ડરસેમ્પલિંગ માટે સંવેદનશીલ છે, અને તે કોમ્પ્યુટેશનલ સંસાધનોનો બગાડ પણ કરી શકે છે. પ્રમાણપત્રોનો અભિગમ ગતિશીલ ડેટા માળખાઓ બનાવવા માટે નીચેના સામાન્ય અભિગમનો ઉપયોગ કરી શકાય છેઃ વર્તમાન સમયે સિસ્ટમ પર ડેટા માળખું સંગ્રહિત કરો. આ માહિતી માળખું વર્તમાન વર્ચ્યુઅલ સમયે સિસ્ટમ પર પ્રશ્નોની મંજૂરી આપે છે. પ્રમાણપત્રો સાથે માહિતી માળખું વધારવું. પ્રમાણપત્રો એવી શરતો છે કે જેના હેઠળ માહિતીનું માળખું સચોટ હોય છે. પ્રમાણપત્રો હવે બધા સાચા છે, અને માહિતી માળખું માત્ર ત્યારે જ સચોટ રહેવાનું બંધ કરશે જ્યારે પ્રમાણપત્રોમાંથી એક હવે સાચું રહેશે નહીં. દરેક પ્રમાણપત્રના નિષ્ફળતાના સમયની ગણતરી કરો, તે સમય જ્યારે તે સાચું રહેશે નહીં. પ્રમાણપત્રોને અગ્રતાની કતારમાં સંગ્રહિત કરો, જેમાં તેમના નિષ્ફળતાના સમયનો સમાવેશ થાય છે. સમયની સાથે આગળ વધવા માટે, અગ્રતાની કતારમાંથી સૌથી ઓછા નિષ્ફળતાના સમય સાથે પ્રમાણપત્રને જુઓ. જો પ્રમાણપત્ર સમય પહેલાં નિષ્ફળ જાય, તો તેને કતારમાંથી બહાર કાઢો અને ડેટા માળખાને ઠીક કરો જેથી તે નિષ્ફળતાના સમયે સચોટ હોય અને પ્રમાણપત્રોને અપડેટ કરે. જ્યાં સુધી પ્રાથમિકતા કતારમાં સૌથી ઓછો નિષ્ફળતા સમય ધરાવતું પ્રમાણપત્ર સમય પછી નિષ્ફળ ન થાય ત્યાં સુધી આનું પુનરાવર્તન કરો. જો અગ્રતા કતારમાં સૌથી ઓછો નિષ્ફળતા સમય ધરાવતું પ્રમાણપત્ર સમય પછી નિષ્ફળ જાય, તો પછી તમામ પ્રમાણપત્રો સમયે સાચા હોય છે જેથી ડેટા માળખું સમયે પ્રશ્નોના યોગ્ય જવાબ આપી શકે. ઘટનાઓના પ્રકાર પ્રમાણપત્ર નિષ્ફળતાઓને "ઘટનાઓ" તરીકે ઓળખવામાં આવે છે. જો કાઇનેટિક ડેટા સ્ટ્રક્ચર દ્વારા જાળવવામાં આવતી મિલકત જ્યારે ઘટના બને ત્યારે બદલાતી નથી તો ઇવેન્ટને આંતરિક ગણવામાં આવે છે. ઇવેન્ટ થાય ત્યારે ડેટા સ્ટ્રક્ચર દ્વારા જાળવવામાં આવતી મિલકત બદલાય તો ઇવેન્ટને બાહ્ય ગણવામાં આવે છે. પ્રદર્શન પ્રમાણપત્ર અભિગમનો ઉપયોગ કરતી વખતે, પ્રદર્શનના ચાર માપ હોય છે. આપણે કહીએ છીએ કે જથ્થો નાનો હોય છે જો તે બહુપત્નીકીય કાર્ય હોય, અથવા મનસ્વી રીતે નાનો હોય, તો વસ્તુઓની સંખ્યા ક્યાં છેઃ પ્રતિભાવ પ્રતિભાવ એ માહિતી માળખાને ઠીક કરવા અને પ્રમાણપત્ર નિષ્ફળ જાય ત્યારે પ્રમાણપત્રોને વધારવા માટે જરૂરી સમયની સૌથી ખરાબ સ્થિતિ છે. કાઇનેટિક ડેટા સ્ટ્રક્ચર પ્રતિભાવશીલ હોય છે જો અપડેટ માટે જરૂરી સમયની સૌથી ખરાબ સ્થિતિ ઓછી હોય. સ્થાન પ્રમાણપત્રોની મહત્તમ સંખ્યા કોઈપણ એક મૂલ્યમાં સામેલ છે. ફરતા બિંદુઓને સંડોવતા માળખાઓ માટે, આ તે પ્રમાણપત્રોની મહત્તમ સંખ્યા છે જેમાં કોઈપણ એક બિંદુ સામેલ છે. કાઇનેટિક ડેટા સ્ટ્રક્ચર સ્થાનિક હોય છે જો કોઈપણ એક મૂલ્ય સાથે સંકળાયેલા પ્રમાણપત્રોની મહત્તમ સંખ્યા ઓછી હોય. કોમ્પેક્ટનેસ કોઈપણ સમયે ડેટા સ્ટ્રક્ચરને વધારવા માટે ઉપયોગમાં લેવાતા પ્રમાણપત્રોની મહત્તમ સંખ્યા છે. કાઇનેટિક ડેટા સ્ટ્રક્ચર કોમ્પેક્ટ હોય છે જો તે ઉપયોગમાં લેવાતા પ્રમાણપત્રોની સંખ્યા અથવા મનસ્વી રીતે ઓછી હોય. (રેખીય જગ્યા કરતાં એક નાનું પરિબળ) કાર્યક્ષમતા એ ઘટનાઓની સૌથી ખરાબ કેસ સંખ્યાનો ગુણોત્તર છે જે ત્યારે થઈ શકે છે જ્યારે માળખું ડેટા માળખામાં "જરૂરી ફેરફારો" ની સૌથી ખરાબ કેસ સંખ્યા સુધી આગળ વધે છે. "જરૂરી ફેરફારો" ની વ્યાખ્યા સમસ્યા આધારિત છે. ઉદાહરણ તરીકે, ગતિશીલ ડેટા સ્ટ્રક્ચરના કિસ્સામાં ગતિશીલ બિંદુઓના સમૂહના ગતિશીલ હલને જાળવી રાખવામાં આવે છે, જરૂરી ફેરફારોની સંખ્યા એ હશે કે સમય જતાં ગતિશીલ હલ કેટલી વાર બદલાય છે. જો આ ગુણોત્તર ઓછો હોય તો ગતિશીલ માહિતી માળખું કાર્યક્ષમ હોવાનું કહેવાય છે. માર્ગના પ્રકાર ચોક્કસ પ્રકારના માર્ગ માટે ચોક્કસ ગતિશીલ માહિતી માળખાની કામગીરીનું વિશ્લેષણ કરી શકાય છે. લાક્ષણિક રીતે, નીચેના પ્રકારનાં માર્ગને ધ્યાનમાં લેવામાં આવે છેઃ એફાઇનઃ (રેખીય કાર્યો) બાઉન્ડેડ-ડિગ્રી બીજગણિતઃ (બાઉન્ડેડ ડિગ્રીના બહુપદી કાર્યો) કેટલાક નિશ્ચિત માટે. સ્યુડો-બીજગણિતઃ કોઈ પણ વ્યાજનું પ્રમાણપત્ર સાચા અને ખોટા સમયની વચ્ચે પલટી જાય છે. ઉદાહરણો કાઇનેટિક ટુર્નામેન્ટ કાઇનેટિક સૉર્ટ લિસ્ટ કાઇનેટિક હીપ કાઇનેટિક કન્વેક્સ હલ કાઇનેટિક સૌથી નજીકની જોડી કાઇનેટિક મિનિમમ સ્પૅનિંગ ટ્રી કાઇનેટિક યુક્લિડિયન મિનિમમ સ્પૅનિંગ ટ્રી સંદર્ભો કાઇનેટિક ડેટા સ્ટ્રક્ચર્સ