מבני נתונים ואלגוריתמים בג'אווה, חלק 1: סקירה כללית

מתכנתי Java משתמשים במבני נתונים כדי לאחסן ולארגן נתונים, ואנחנו משתמשים באלגוריתמים כדי לתפעל את הנתונים במבנים אלה. ככל שתבינו יותר על מבני נתונים ואלגוריתמים, וכיצד הם עובדים יחד, כך תוכניות ה- Java שלכם יהיו יעילות יותר.

הדרכה זו משיקה סדרה קצרה המציגה מבני נתונים ואלגוריתמים. בחלק 1 תלמד מהו מבנה נתונים וכיצד מסווגים מבני נתונים. תוכלו גם ללמוד מהו אלגוריתם, כיצד מיוצגים אלגוריתמים וכיצד להשתמש בפונקציות מורכבות זמן ומרחב כדי להשוות אלגוריתמים דומים. לאחר שתקבל את היסודות האלה, תהיה מוכן ללמוד על חיפוש ומיון באמצעות מערכים חד-ממדיים, בחלק 2.

מהו מבנה נתונים?

מבני נתונים מבוססים על סוגי נתונים מופשטים (ADT), אותם מגדירה ויקיפדיה כדלקמן:

[A] מודל מתמטי לסוגי נתונים כאשר סוג הנתונים מוגדר על ידי התנהגותו (סמנטיקה) מנקודת מבטו של משתמש הנתונים, במיוחד מבחינת ערכים אפשריים, פעולות אפשריות על נתונים מסוג זה והתנהגות של פעולות אלה.

ל- ADT לא אכפת מייצוג הזיכרון של ערכיו או מאופן יישום פעולותיו. זה כמו ממשק Java, שהוא סוג נתונים שמנותק מכל יישום. לעומת זאת, מבנה נתונים הוא יישום קונקרטי של ADT אחד או יותר, בדומה לאופן שבו מחלקות Java מיישמות ממשקים.

דוגמאות ל- ADT כוללות עובדים, רכב, מערך ורשימה. שקול את הרשימה ADT (המכונה גם Sequence ADT), המתאר אוסף מסודר של אלמנטים החולקים סוג משותף. לכל אלמנט באוסף זה מיקום משלו ומותר לאלמנטים כפולים. פעולות בסיסיות הנתמכות על ידי ADT רשימה כוללות:

  • יצירת רשימה חדשה וריקה
  • הוספת ערך לסוף הרשימה
  • הכנסת ערך לרשימה
  • מחיקת ערך מהרשימה
  • מתבשל מעל הרשימה
  • השמדת הרשימה

מבני נתונים שיכולים ליישם את ה- ADT של רשימה כוללים מערכים חד-ממדיים בגודל קבוע ובגודל דינמי ורשימות המקושרות יחידה. (תוצג בפניך מערכים בחלק 2, ורשימות מקושרות בחלק 3.)

סיווג מבני נתונים

ישנם סוגים רבים של מבני נתונים, הנעים בין משתנים בודדים למערכים או רשימות מקושרות של אובייקטים המכילים מספר שדות. ניתן לסווג את כל מבני הנתונים כפרימיטיבים או אגרגטים, וחלקם מסווגים כמכולות.

פרימיטיבים לעומת אגרגטים

סוג מבנה הנתונים הפשוט ביותר מאחסן פריטי נתונים בודדים; למשל, משתנה המאחסן ערך בוליאני או משתנה המאחסן מספר שלם. אני מתייחס למבני נתונים כאלה כפרימיטיבים .

מבני נתונים רבים מסוגלים לאחסן פריטי נתונים מרובים. לדוגמא, מערך יכול לאחסן פריטי נתונים מרובים בחריצים השונים שלו, ואובייקט יכול לאחסן מספר פריטי נתונים דרך השדות שלו. אני מתייחס למבני הנתונים הללו כאל אגרגטים .

כל מבני הנתונים שנבחן בסדרה זו הם אגרגטים.

מיכלים

כל דבר שממנו מאוחסנים ומאוחזרים פריטי נתונים יכול להיחשב כמבנה נתונים. דוגמאות כוללות את מבני הנתונים שמקורם ב- ADTs לעובדים, רכב, מערכים ורשימות שהוזכרו בעבר.

מבני נתונים רבים נועדו לתאר ישויות שונות. מופעים של Employeeכיתה הם מבני נתונים שקיימים לתיאור עובדים שונים, למשל. לעומת זאת, ישנם מבני נתונים הקיימים ככלי אחסון כללי למבני נתונים אחרים. לדוגמא, מערך יכול לאחסן ערכים פרימיטיביים או הפניות לאובייקטים. אני מתייחס לקטגוריה האחרונה של מבני נתונים כאל מכולות .

מלבד היותם אגרגטים, כל מבני הנתונים שנבחן בסדרה זו הם מכולות.

מבני נתונים ואלגוריתמים באוספי Java

מסגרת אוספי הג'אווה תומכת בסוגים רבים של מבני נתונים מכוונים למכולה ואלגוריתמים קשורים. סדרה זו תעזור לך להבין טוב יותר את המסגרת הזו.

דפוסי עיצוב ומבני נתונים

זה נהיה די מקובל להשתמש בדפוסי עיצוב כדי להציג לסטודנטים אוניברסיטאות מבני נתונים. מאמר של אוניברסיטת בראון סוקר כמה דפוסי עיצוב שימושיים לתכנון מבני נתונים באיכות גבוהה. בין היתר, העיתון מדגים כי תבנית המתאם שימושית לעיצוב ערימות ותורים. קוד ההדגמה מוצג ברשימה 1.

רישום 1. שימוש בתבנית המתאם לערימות ותורים (DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

רישום 1 מביא את DequeStackכיתת העיתון של אוניברסיטת בראון , המדגימה את דפוס המתאם. שים לב Stackו Dequeהם ממשקים המתארות סטאק Deque ADTs. MyDequeהוא מחלקה המיישמת Deque.

עקיפת שיטות ממשק

הקוד המקורי כי 1 הרישום מבוסס על לא להציג את קוד המקור כדי Stack, Deque, ו MyDeque. לשם הבהרה, הצגתי @Overrideהערות כדי להראות שכל DequeStackהשיטות שאינן קונסטרוקטור עוקפות את Stackהשיטות.

DequeStackמסתגל MyDequeכך שיוכל ליישם Stack. כל DequeStackהשיטות הן שיחות בשורה אחת Dequeלשיטות הממשק. עם זאת, יש קמט קטן בו Dequeיוצאים Stackמן הכלל יוצאים מן הכלל לחריגים.

מהו אלגוריתם?

היסטורי המשמש ככלי לחישוב מתמטי, אלגוריתמים קשורים עמוק עם מדעי המחשב, ועם מבני נתונים בפרט. אלגוריתם הוא רצף של הוראות כי משיג משימה בתוך תקופה מוגבלת של זמן. תכונות האלגוריתם הן כדלקמן:

  • מקבל אפס תשומות או יותר
  • מייצר תפוקה אחת לפחות
  • מורכב מהוראות ברורות וחד משמעיות
  • מסתיים לאחר מספר סופי של צעדים
  • הוא בסיסי מספיק כדי שאדם יוכל לבצע אותו באמצעות עיפרון ונייר

שים לב שבעוד שתוכניות עשויות להיות באלגוריתם, תוכניות רבות אינן מסתיימות ללא התערבות חיצונית.

רצפי קוד רבים מתאימים כאלגוריתמים. דוגמא אחת היא רצף קוד המדפיס דוח. מפורסם יותר, האלגוריתם של אוקלידס משמש לחישוב המחלק המשותף הגדול ביותר המתמטי. ניתן אפילו לגרום לכך שפעולות בסיסיות של מבנה נתונים (כגון ערך חנות בחריץ המערך ) הן אלגוריתמים. בסדרה זו, לרוב, אתמקד באלגוריתמים ברמה גבוהה יותר המשמשים לעיבוד מבני נתונים, כגון אלגוריתמי חיפוש בינארי ומכפיל מטריקס.

תרשימי זרימה ופסאודוקוד

איך אתה מייצג אלגוריתם? כתיבת קוד לפני הבנה מלאה של האלגוריתם הבסיסי שלו עלולה להוביל לבאגים, אז מה אלטרנטיבה טובה יותר? שתי אפשרויות הן תרשימי זרימה ופסאוד-קוד.

שימוש בתרשימי זרימה לייצוג אלגוריתמים

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • פונקציה מרחב-מורכבות המודדת של אלגוריתם מורכב בחלל --meaning את כמות הזיכרון הנדרשת תקורה ידי האלגוריתם לביצוע המשימה שלה.

שתי פונקציות המורכבות מבוססות על גודל הקלט ( n ), שמשקף איכשהו את כמות נתוני הקלט. שקול את הפסאוד-קוד הבא להדפסת מערך:

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

מורכבות זמן ופונקציות מורכבות זמן

באפשרותך לבטא את מורכבות הזמן של אלגוריתם זה על ידי ציון פונקציית מורכבות הזמן , כאשר (מכפיל קבוע) מייצג את משך הזמן להשלמת איטרציה של לולאה אחת, ומייצג את זמן הגדרת האלגוריתם. בדוגמה זו, מורכבות הזמן היא לינארית.t(n) = an+bab