ડો LLOYD: તેથી CS50 માં, અમે આવરી કર્યું વિવિધ માહિતી માળખાં ઘણો, અધિકાર? અમે એરે જોવા મળે છે, અને સાથે લિંક કરી છે યાદીઓ, અને હેશ કોષ્ટકો, અને પ્રયત્નોમાં, રન ટાઇમ સ્ટેકનું અને ક્યુને. અમે પણ થોડી જાણવા મળશે વૃક્ષો અને ઢગલા વિશે પરંતુ ખરેખર આ બધા માત્ર અંત ઉપર એક થીમ પર ભિન્નતા છે. ત્યાં ખરેખર છે આ ચાર મૂળભૂત વિચારો કાઇન્ડ બીજું કે બધું કરવા માટે નીચે રાંધવું કરી શકો છો. એરે, સંલગ્ન યાદીઓ, હેશ કોષ્ટકો, અને પ્રયત્ન કરે છે. અને જેમ હું ત્યાં જણાવ્યું હતું કે, તેમના પર ભિન્નતા હોય છે, પરંતુ આ ખૂબ છે ખૂબ સારાંશ રહ્યું બધું અમે વાત કરવા જઈ રહ્યાં સી દ્રષ્ટિએ આ વર્ગ વિશે પરંતુ કેવી રીતે આ અધિકાર, બધા માપ ઉપર છે? અમે સારી અને ખરાબ વિપક્ષ વિશે વાત કરી છે તેમના પર અલગ વિડિઓઝ દરેક, પરંતુ નંબરો ઘણો છે આસપાસ ફેંકવામાં રહ્યું. સામાન્ય ઘણો છે વિચારો આસપાસ ફેંકવામાં રહ્યું. માતાનો પ્રયાસ કરો અને ભેગા દો તે માત્ર એક સ્થળ માં. સામે પક્ષ તોલવું દો વિપક્ષ, અને ધ્યાનમાં જે માહિતી માળખું અધિકાર માહિતી હોઈ શકે છે તમારા ચોક્કસ પરિસ્થિતિ માટે માળખું, માહિતી ગમે પ્રકારની તમે સ્ટોર કરી રહ્યાં. તમે જરૂરી હંમેશા જરૂર નથી સુપર ઝડપી નિવેશ, કાઢી નાંખવાનું ઉપયોગ એક trie અને લુકઅપ જો તમે ખરેખર દાખલ અને કાઢવા વિશે કાળજી નથી ઘણુ બધુ. તમે માત્ર ગમેતે જરૂર હોય તો ઍક્સેસ, કદાચ એક એરે સારી છે. તેથી આપણે તે distill દો. માતાનો ચાર દરેક વિશે વાત કરો માહિતી માળખાં મુખ્ય પ્રકારના અમે વિશે વાત કરી, અને કર્યું છે તેઓ સારી પણ હોઈ શકે છે જ્યારે માત્ર જુઓ, અને જ્યારે તેઓ જેથી સારા ન હોઈ શકે છે. તેથી આપણે એરે સાથે શરૂ કરીએ. નિવેશ તેથી, તે પ્રકારના ખરાબ છે. 

એક એરે ઓવરને અંતે નિવેશ, ઠીક છે અમે જાઓ તરીકે અમે એક એરે મકાન કરી રહ્યાં છો. પરંતુ અમે દાખલ કરવાની જરૂર છે, તો મધ્યમ માં તત્વો, નિવેશ પર પાછા લાગે સૉર્ટ કરો, ઘણો છે ત્યાં એક તત્વ ફિટ સ્થળાંતર. અને અમે દાખલ કરવા માટે જઈ રહ્યાં છો, તેથી જો ગમે છે પરંતુ એક એરે ઓવરને, તે કદાચ એટલા મહાન નથી. 

એ જ રીતે, કાઢી નાંખવાનું, જ્યાં સુધી અમે છો એક એરે ઓવરને થી કાઢવા, કદાચ પણ જો એટલા મહાન નથી અમે ખાલી જગ્યાઓ છોડવા માંગો છો નથી, જે સામાન્ય રીતે આપણે નથી. અમે એક તત્વ દૂર કરવા માંગો છો, અને પછી પ્રકારની તે ફરીથી snug બનાવે છે. અને તેથી ઘટકો કાઢવા ઝાકઝમાળ, પણ એટલા મહાન નથી. 

લુકઅપ માટે, જોકે, મહાન છે. અમે રેન્ડમ વપરાશ હોય છે, સતત સમય લુકઅપ. અમે ફક્ત સાત કહે છે, અને અમે જાઓ એરે સ્થળાંતર સાત. અમે જાઓ સાથે, 20 કહે છે એરે સ્થળાંતર 20. અમે સમગ્ર ફરી વળવું નથી. તે ખૂબ સારી છે. 

એરે પણ પ્રકારની પ્રમાણમાં સરળ હોય છે. અમે સૉર્ટ વિશે વાત કરી દર વખતે આવા પસંદગી સૉર્ટ તરીકે અલ્ગોરિધમનો, નિવેશ સૉર્ટ કરો, બબલ સૉર્ટ મર્જ, સૉર્ટ, અમે હંમેશા તે કરવા એરે ઉપયોગ થાય છે, એરે માટે ખૂબ સરળ છે, કારણ કે આ માહિતી માળખાં સંબંધિત સૉર્ટ કરો, અમે અત્યાર સુધી જોઇ છે. 

તેઓ પણ પ્રમાણમાં નાના છો. વધારાની જગ્યા ઘણો નથી. તમે માત્ર બરાબર તેટલી કોરે સુયોજિત તમે તમારા ડેટાને પકડી જરૂર છે, અને તે ખૂબ ખૂબ છે. તેથી તેઓ ખૂબ નાના છો અને તે રીતે કાર્યક્ષમ. પરંતુ અન્ય નુકસાન, જોકે, તેઓ કદ નિયત કરવામાં આવે છે. અમે કેવી રીતે બરાબર જાહેર હોય છે મોટા અમે અમારા એરે પ્રયત્ન કરવા માંગો છો અને અમે ફક્ત તે એક શોટ વિચાર. અમે વૃદ્ધિ અને તે સંકોચો કરી શકો છો. 

અમે તેને વધવા અથવા સંકોચો જરૂર હોય તો, અમે એક સંપૂર્ણપણે નવી એરે જાહેર કરવાની જરૂર છે, ના બધા તત્વો નકલ બીજા એરે માં પ્રથમ એરે. અને અમે આગળ જતા ખોટુ તો સમય, અમે તેને ફરીથી કરવા માટે જરૂર છે. એટલા મહાન નથી. તેથી એરે અમને રાહત આપી નથી તત્વો ચલ નંબરો હોય છે. 

એક કડી થયેલ યાદી સાથે, નિવેશ ખૂબ સરળ છે. અમે હમણાં જ આગળના પર ખીલી. કાઢી નાંખવામાં પણ ખૂબ સરળ છે. અમે તત્વો શોધવા હોય છે. તે કેટલાક શોધ સમાવેશ થાય છે. 

પરંતુ તમે તત્વ મળ્યાં છે એકવાર તમે શું કરવાની જરૂર છે, બધા માટે જોઈ રહ્યાં છો, એક નિર્દેશક ફેરફાર છે, કદાચ બે જો તમારી પાસે એક સમયમાં બમણું યાદી કડી કડી થયેલ યાદી, બદલે અને પછી તમે ફક્ત નોડ મુક્ત કરી શકો છો. તમે પાળી કરવાની જરૂર નથી આસપાસ બધું. તમે ફક્ત બે પોઇન્ટર બદલવા તેથી તે ખૂબ ઝડપી છે. 

લુકઅપ અધિકાર છે, તેમ છતાં ખરાબ છે? અમને એક શોધવા માટે ક્રમમાં એક કડી થયેલ યાદીમાં તત્વ, કે શું એકલા અથવા સમયમાં બમણું કડી અમે તેને રેખીય શોધ હોય છે. અમે શરૂઆતમાં શરૂ હોય છે અને એ ઓવરને ખસેડવા, અથવા ઓવરને ખસેડવા ખાતે શરૂ શરૂઆતમાં. અમે હવે રેન્ડમ એક્સેસ નથી. અમે કરી રહ્યા છીએ તેથી જો શોધ ઘણો છે, કદાચ એક કડી થયેલ યાદી નથી અમારા માટે તદ્દન જેથી સારી છે. 

તેઓ ખરેખર પણ છો સૉર્ટ મુશ્કેલ છે, અધિકાર? આ માત્ર રસ્તો તમે કરી શકો છો ખરેખર એક કડી થયેલ યાદી સૉર્ટ તમે તેને રચવા, કે સૉર્ટ કરવા માટે છે. પરંતુ તમે, કે સૉર્ટ તો તે રચવું, તમે લાંબા સમય સુધી છો હવે ઝડપી દાખલ બનાવે છે. તમે માત્ર આબંધન નથી કરી રહ્યાં છો આગળના પર વસ્તુઓ. તમે શોધવા માટે હોય છે જમણી સ્થળ તેને મૂકવા માટે, અને પછી તમારા નિવેશ માત્ર વિશે તરીકે ખરાબ બને ઝાકઝમાળ માં દાખલ થાય છે. તેથી કડી થયેલ યાદીઓ નથી માહિતી સૉર્ટ માટે ખૂબ મહાન છે. 

તેઓ પણ ખૂબ નાની છે, કદ મુજબના છો. સમયમાં બમણું સહેજ યાદી કડી એકલા કડી થયેલ યાદીઓ મોટા, જે થોડી મોટી હોય છે એરે કરતાં, પરંતુ તે નથી વેડફાઇ જતી જગ્યા એક વિશાળ જથ્થો. તેથી જો જગ્યા પ્રીમિયમ પર છે, પરંતુ નથી ખરેખર તીવ્ર પ્રીમિયમ, આ પર જાઓ કરવા માટે યોગ્ય રીતે હોઈ શકે છે. 

હેશ કોષ્ટકો. હેશ ટેબલ માં નિવેશ એકદમ સરળ છે. તે બે પગલું પ્રક્રિયા છે. પ્રથમ અમે દ્વારા અમારી માહિતી ચલાવવા માટે જરૂર છે હેશ વિધેય હેશ કોડ વિચાર કરવા માટે, અને પછી અમે માં તત્વ સામેલ કે હેશ કોડ સ્થાન પર હેશ કોષ્ટક. 

યાદીની લિંક જેવી જ કાઢી નાંખવામાં, તમે તત્વ શોધવા વાર સરળ છે. તમે પ્રથમ તે શોધવા માટે હોય છે પરંતુ તે પછી તમે તેને કાઢી ત્યારે, તમે માત્ર બદલી કરવાની જરૂર છે પોઇન્ટર એક દંપતિ, જો તમે અલગ chaining ઉપયોગ કરી રહ્યાં છો. તમે ચકાસણી ઉપયોગ કરી રહ્યાં છો, અથવા તમે ન હો તો મદદથી બધા chaining તમારા હેશ કોષ્ટકમાં, કાઢી નાંખવાનું ખરેખર ખરેખર સરળ છે. તમે શું કરવાની જરૂર છે હેશ છે માહિતી, અને પછી તે સ્થાન પર જાઓ. અને એમ ધારી રહ્યા છીએ તમે નથી , કોઈપણ અથડામણમાં હોય છે તમે ખૂબ જ ઝડપથી કાઢી નાખવા માટે સક્ષમ હશો. 

હવે, લુકઅપ જ્યાં વસ્તુઓ છે થોડી વધુ જટિલ વિચાર. તે વધુ સારું સરેરાશ છે કડી થયેલ યાદીઓ કરતાં. તમે સાંકળ ઉપયોગ કરી રહ્યાં છો, જો તમે હજુ પણ એક કડી થયેલ યાદી હોય છે, જે તમે હજુ પણ હોય છે શોધ એક કડી થયેલ યાદી તોટો. તમે લઈ રહ્યા છો કારણ કે, પરંતુ તમારી સાથે લિંક યાદી અને 100 અથવા 1,000 તે વિભાજન અથવા n તમારા હેશ કોષ્ટકમાં તત્વો, તમે છો કડી થયેલ યાદીઓ માપ nth બધા એક છે. તેઓ બધા નોંધપાત્ર નાના છો. તમે એન બદલે યાદીઓ કડી થયેલ છે માપ n એક કડી થયેલ યાદી. 

અને તેથી આ વાસ્તવિક દુનિયાની સતત સામાન્ય રીતે આપણે જે પરિબળ સમય જટિલતા વિશે વાત નથી, તે ખરેખર અહીં એક ફરક નથી. તેથી લુકઅપ હજુ રેખીય છે તમે સાંકળ ઉપયોગ કરી રહ્યાં છો, તો શોધ, પરંતુ યાદી લંબાઈ તમે મારફતે શોધ કરી રહ્યાં છે સરખામણી દ્વારા ખૂબ, ખૂબ ટૂંકી છે. ફરીથી, સોર્ટિંગ તમારા છે જો અહીં ધ્યેય, હેશ ટેબલ કદાચ યોગ્ય રીતે ન જાય. સૉર્ટ તો માત્ર એક એરે ઉપયોગ તમે ખરેખર મહત્વનું છે. 

અને તેઓ કદ ના સંગીતનું સંપૂર્ણ સપ્તક ચલાવી શકો છો. તે કહે છે કે શું મુશ્કેલ છે હેશ ટેબલ, નાના અથવા મોટા છે તે ખરેખર પર આધાર રાખે છે મોટા કેવી રીતે તમારા હેશ ટેબલ છે. તમે માત્ર સ્ટોર કરી રહ્યા છીએ તો તમારા હેશ કોષ્ટકમાં પાંચ તત્વો, અને તમે હેશ કોષ્ટક હોય છે તે 10,000 તત્વો સાથે, તમે કદાચ જગ્યા ઘણો બગાડ કરી રહ્યાં છો. વિરોધાભાસ પણ તમે કરી શકો છો હોવા , ખૂબ જ નાજુક હેશ કોષ્ટકો છે પરંતુ નાના તમારા હેશ ટેબલ, નહીં તે કડી થયેલ યાદીઓ દરેક લાંબા સમય સુધી નહીં. અને તેથી ખરેખર વ્યાખ્યાયિત કરવા માટે કોઈ રીત હોય છે બરાબર એક હેશ ટેબલ કદ, પરંતુ તે કદાચ સલામત છે તે સામાન્ય રીતે કહે છે એક કડી થયેલ કરતાં મોટી હોઈ ચાલે આ જ માહિતી સ્ટોર યાદી એક trie કરતાં પરંતુ નાના. 

અને પ્રયત્નોમાં ચોથા છે આ માળખાં કે અમે વિશે વાત કરવામાં આવી છે. એક trie માં દાખલ જટિલ છે. ગતિશીલ ઘણો છે મેમરી ફાળવણી, ખાસ કરીને શરૂઆતમાં, તમે બિલ્ડ કરવા શરૂ કરી રહ્યાં છો છે. પરંતુ તે સતત સમય છે. તે માત્ર ત્યારે જ માનવ તત્વ છે અહીં તે મુશ્કેલ બનાવે છે. નલ નિર્દેશક અનુભવી રહી છે, malloc જગ્યા, કદાચ malloc જગ્યા જાઓ ત્યાંથી ફરી. ના ધમકી પરિબળ સૉર્ટ ગતિશીલ મેમરી ફાળવણી પોઇન્ટર સાફ કરવા માટે અવરોધ છે. પરંતુ તમે તેને સાફ કરી લો, નિવેશ ખરેખર, ખૂબ સરળ આવે છે અને તે ચોક્કસપણે સતત સમય છે. 

કાઢી નાંખવામાં સરળ છે. તમે શું કરવાની જરૂર છે નીચે શોધખોળ છે પોઇન્ટર અને મફત છે નોડ દંપતિ તેથી તે ખૂબ સારી છે. લુકઅપ પણ ખૂબ ઝડપી છે. તે માત્ર ત્યારે જ પર આધારિત છે તમારી માહિતી લંબાઈ. તમારી માહિતીના છે તો પાંચ પાત્ર શબ્દમાળાઓ, ઉદાહરણ તરીકે, તમે પાંચ સ્ટોર કરી રહ્યાં તમારા trie પાત્ર શબ્દમાળાઓ, તે માત્ર પાંચ પગલાંઓ લે તમે શોધી રહ્યાં છો તે શોધવા. પાંચ તેથી, માત્ર એક સતત પરિબળ છે ફરીથી, નિવેશ, ઘટાડા અને લુકઅપ અહીં અસરકારક રીતે, બધા સતત સમય છે. 

અન્ય વસ્તુ તમારા trie છે ખરેખર પ્રકારની પહેલેથી જ અધિકાર છટણી? અમે છો કેવી રીતે સદ્ગુણ દ્વારા દાખલ તત્વો, ના પત્ર દ્વારા પત્ર જઈને કી US સ્થાન દ્વારા કી, અથવા અંક, ખાસ કરીને, તમારા trie હોવા અંત થાય છે તમે તેને બિલ્ડ તરીકે પ્રકારની સોર્ટ થાય છે. તે ખરેખર બનાવે નથી અર્થમાં સૉર્ટ વિશે વિચારો એ જ રીતે અમે વિશે વિચારો તે એરે, અથવા કડી થયેલ યાદીઓ સાથે, અથવા હેશ કોષ્ટકો. પરંતુ અમુક અર્થમાં, તમારા તરીકે તમે જાઓ trie છટણી કરવામાં આવે છે. 

આ નુકસાન, અલબત્ત, છે એક trie ઝડપથી વિશાળ બની જાય છે. દરેક જંકશન બિંદુ પ્રતિ, તમે કદાચ તમારી કી અંકો નો સમાવેશ થાય છે, તો અહી, તમે અન્ય 10 સ્થાનો તમે જઇ શકો છો કે જે દરેક નોડ કે જે થાય છે જાણકારી સમાવે છે આ માહિતી વિશે તમે સંગ્રહ કરવા માંગો છો કે નોડ, વત્તા 10 પોઇન્ટર છે. જે CS50 IDE પર 80 બાઇટ્સ છે. તેથી તે માટે ઓછામાં ઓછા 80 બાઇટ્સ છે તમે બનાવો કે દરેક નોડ, અને તે પણ માહિતી ગણાય નથી. અને તમારા ગાંઠો હોય તો તેના બદલે અંકો અક્ષરો, હવે તમે 26 પોઇન્ટર છે દરેક સ્થાન છે. અને 26 ગુણ્યા 8 કદાચ 200 બાઇટ્સ, અથવા તે કંઈક. અને તમે મૂડી અને તમે કરી શકો છો lowercase-- હું આ સાથે જાઉં છું જ્યાં, અધિકાર છે? તમારા નોડોના ખરેખર વિચાર કરી શકો છો મોટા, અને તેથી આ trie પોતે એકંદરે, કરી શકો છો પણ, ખરેખર મોટી મળે છે. જગ્યા ઊંચી સપાટીએ છે તેથી જો તમારી સિસ્ટમ પર પ્રીમિયમ, એક trie કરવા માટે યોગ્ય રીતે ન પણ હોઈ શકે પણ તેના અન્ય ફાયદાઓ છતાં, જાઓ નાટક માં આવે છે. હું ડો લોયડ છું. આ CS50 છે.