Theory
એ જ ચિઠ્ઠીઓ, ત્રણ ખાનાં
Canteen દિવસની દરેક order ની ચિઠ્ઠી રાખે છે. એમને સંઘરવાની ત્રણ રીત:
- ખાનામાં છૂટી ફેંકેલી.
- ખીલી પર ભરાવેલી, સૌથી નવી ઉપર.
- થાળીમાં ક્લિપ કરેલી, સૌથી જૂની આગળ.
એ જ 500 ચિઠ્ઠીઓ. પણ "હમણાં જ શું આવ્યું?" કે "હવે કોનો વારો?" નો જવાબ આપવા જાઓ અને દરેક ખાનું સાવ જુદી રીતે વર્તે છે.
તમે data ને કેવી રીતે ગોઠવો છો એ નક્કી કરે છે કે તમે એને કેટલી ઝડપથી વાપરી શકો. એ એક વાક્ય એ આ વિષયનો આખો બીજો અડધો ભાગ છે.
Theory
રસોડું પહેલેથી ગોઠવાયેલું છે
Canteen માં ચારે બાજુ જુઓ: થાળીઓ થપ્પીમાં (ઉપરથી લો), ગ્રાહકો હરોળમાં (પહેલાને પીરસો), menu નું પાટિયું ક્રમવ્યવસ્થા તરીકે (વિભાગ, પછી વાનગીઓ), પહોંચાડવાનો નકશો રસ્તાઓના જાળા તરીકે.
કોઈ થાળીઓને હરોળમાં કે ગ્રાહકોને ઢગલામાં સંઘરતું નથી. દરેક ગોઠવણ એટલા માટે પસંદ થઈ કારણ કે એ એક કામ સાવ સહેલું બનાવે છે. Data structures એ જ ગોઠવણો છે, code માં લખાયેલી.
Theory
Data structure, ઔપચારિક રીતે
Data structure એ memory માં data ગોઠવવાની અને સંઘરવાની એવી ચોક્કસ રીત છે જેથી એને કાર્યક્ષમ રીતે પહોંચી અને બદલી શકાય.
પરીક્ષાઓ જે વર્ગીકરણ દોરાવે છે:
Data structures
├── Primitive: int, char, float, double
└── Non-primitive
├── Linear: array, stack, queue, linked list
└── Non-linear: tree, graph
Linear રચનાઓ ઘટકોને એક પછી એક ક્રમમાં રાખે છે. Non-linear રચનાઓ ફંટાય છે (trees) કે એકબીજા સાથે જોડાય છે (graphs).
At a glance
કોણ ક્યાં વપરાય છે (ઉપયોગનાં ક્ષેત્રોનું કોષ્ટક)
| રચના | આકાર | વાસ્તવિક ઉપયોગ |
|---|---|---|
| Array | ક્રમાંકિત હરોળ | Marksheets, lookup ના કોષ્ટકો, matrices |
| Stack | થપ્પી, ફક્ત ઉપરથી | Function ના calls, undo, infix થી postfix |
| Queue | હરોળ, બંને છેડા | Token ની વ્યવસ્થા, printer નાં કામ, CPU નું scheduling |
| Linked list | Nodes ની સાંકળ | Playlists, ગતિશીલ memory ની ફાળવણી |
| Tree | ક્રમવ્યવસ્થા | File systems, database ના indexes, HTML DOM |
| Graph | જાળું | Google Maps ના રસ્તા, સામાજિક જાળાં |
Quiz
Canteen tokens છાપે છે અને ગ્રાહકોને ચુસ્તપણે આવવાના ક્રમમાં પીરસે છે. અંદરનું printer પણ કામોને એ જ રીતે હરોળમાં મૂકે છે. કઈ રચના **બંને** ને દર્શાવે છે, અને શા માટે?
- Queue: પહેલો અંદર, પહેલો બહાર એ આવવાના ક્રમની સેવા સાથે મળે છે
- Stack: છેલ્લે છપાયેલા token ને પહેલો પીરસાય છે
- Tree: ગ્રાહકો veg અને non-veg માં ફંટાય છે
- Array: tokens ને આંકડા હોય છે, એટલે array જરૂરી છે
Show the answer
Queue: પહેલો અંદર, પહેલો બહાર એ આવવાના ક્રમની સેવા સાથે મળે છે
આવવાના ક્રમની સેવા એ FIFO છે, જે queue ની વ્યાખ્યા છે, અને printer નું spooling એ પાઠ્યપુસ્તકનો queue નો ઉપયોગ છે. Stack સૌથી નવા ગ્રાહકને પહેલો પીરસત (હરોળમાં થતો હંગામો કલ્પો). ક્રમાંકિત tokens array ને ફરજિયાત બનાવતાં નથી: ક્રમાંક એ queue જે આપે છે એ છે, memory કેવી રીતે ગોઠવવી પડે એ નહીં. વર્તનને રચના સાથે મેળવવું, ઉપરછલ્લી વિગતો સાથે નહીં, એ પરીક્ષાની આવડત છે.
Think first
ખાનું પસંદ કરો
ત્રણ જરૂરિયાત: (1) browser નું Back બટન, (2) college નું folder ની અંદર folder વાળું file explorer, (3) campus ના બે દરવાજા વચ્ચેનો સૌથી ટૂંકો રસ્તો શોધવો. Tap કરતાં પહેલાં, દરેકને કોષ્ટકમાંથી એક રચના સોંપો.
Show the answer
(1) Stack: Back સૌથી તાજેતરના પાના પર પાછું જાય છે, LIFO.
(2) Tree: folder ની અંદર folder એ એક મૂળવાળી ક્રમવ્યવસ્થા છે.
(3) Graph: દરવાજા અને રસ્તા જાળું બનાવે છે, અને સૌથી ટૂંકા રસ્તાના પ્રશ્નો એ graph ના પ્રશ્નો છે.
જો ત્રણેય સાચાં પડ્યાં, તો તમે પહેલેથી data structures માં વિચારો છો; હવે પછીના પાઠો ફક્ત પ્રયુક્તિ ઉમેરે છે.
Watch out
વર્ગીકરણની લપસણ
Students linear રચનાઓ તરીકે "array, stack, queue, tree" લખે છે: tree એ non-linear છે, એ ફંટાય છે. ભરોસાપાત્ર કસોટી: શું તમે આખી રચના પર કોઈ ડાળી પસંદ કર્યા વગર એક સીધા ફેરામાં ચાલી શકો? Arrays, stacks, queues, linked lists: હા, linear. Trees અને graphs: ના, non-linear.
અને primitive સામે non-primitive ને linear સામે non-linear થી અલગ રાખો: બીજો ભાગ ફક્ત non-primitive ની અંદર જ લાગુ પડે છે.
Theory
કંપનીઓ interviews માં આની કસોટી કેમ કરે છે
Wirth ના જાણીતા પુસ્તકનું નામ બધું કહી દે છે: Algorithms + Data Structures = Programs. તમે વાપરેલી દરેક ધીમી app સામાન્ય રીતે ખોટી રચના પર સાચો algorithm જ હતી. આ વિષયમાંથી બે રચનાઓ તમારી પાસે પહેલેથી છે (થાળીની થપ્પીવાળો stack અને token ની હરોળવાળો queue); બાકીના પાઠો તમારી પાસે એમનો અમલ કરાવે છે અને વપરાવે છે.
Summary
Key takeaways
- Data structure એ કાર્યક્ષમ પહોંચ અને ફેરફાર માટે memory માં data ની પસંદ કરેલી ગોઠવણ છે.
- Primitive (int, char, float) સામે non-primitive; non-primitive એ linear અને non-linear માં વહેંચાય છે.
- Linear: array, stack, queue, linked list. Non-linear: tree, graph.
- ઉપયોગ: calls/undo માટે stack, scheduling માટે queue, ક્રમવ્યવસ્થા માટે tree, જાળાં માટે graph.
- એક-સીધા-ફેરાની કસોટી linear ને non-linear થી અલગ પાડે છે.
- Memory hook: એ જ ચિઠ્ઠીઓ, ત્રણ ખાનાં.