מה זה מערך (Array)?

אפליקציית מזג אוויר שמציגה את הטמפרטורות של השבוע צריכה שבעה מספרים. היא יכולה להשתמש בשבעה משתנים נפרדים, monday, tuesday וכן הלאה, אבל אז שום לולאה לא תוכל לעבור עליהם, והוספת יום שמיני תדרוש לכתוב קוד חדש. מערך שם את שבעת המספרים תחת שם אחד, temperatures, בתאים ממוספרים מ-0 עד 6.

איך מערך עובד

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

address of element i = start address + i × element size

נניח שמערך של מספרים שלמים של 32 ביט (4 בייטים כל אחד) מתחיל בכתובת זיכרון 1000. איבר 0 נמצא ב-1000, איבר 1 ב-1004, איבר 2 ב-1008 ואיבר 3 ב-1012. ההגעה לאיבר 3 או לאיבר 3,000,000 לוקחת אותו צעד יחיד, ולכן קריאה ממערך לפי אינדקס נקראת זמן קבוע, ונכתבת O(1).

המודול array של Python שומר מספרים גולמיים בדיוק כך, אז אפשר לבדוק את החשבון:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

הנוסחה הזו מסבירה גם למה רוב השפות סופרות מ-0. האינדקס הוא היסט (offset): כמה איברים לדלג מההתחלה. האיבר הראשון נמצא במרחק 0 איברים מההתחלה, ולכן האינדקס שלו הוא 0, והאיבר האחרון במערך באורך n נמצא באינדקס n − 1. כמה שפות, כמו Lua, MATLAB, R ו-Fortran, מתחילות דווקא ב-1.

שימוש במערך ב-Python

רוב הקוד ב-Python משתמש ב-list המובנית בתור מערך. יוצרים אותה עם סוגריים מרובעים, קוראים ומשנים איברים לפי אינדקס, ומקבלים את האורך שלה עם len():

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

אינדקס שלילי סופר מהסוף, כך ש-temperatures[-1] הוא האיבר האחרון. הקיצור הזה שייך ל-Python; ב-C וב-Java אין אינדקסים שליליים.

כמה עולות פעולות על מערך

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

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

מעבר על מערך בלולאה

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

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

מערכים בשפות אחרות

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

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

גם למערכים ב-Java יש אורך קבוע, ואיברים חדשים מתחילים בערך ברירת מחדל, למשל 0 למספרים. כשצריך ב-Java מערך שגדל, משתמשים ב-ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

מערכים ב-JavaScript גדלים וקטנים בחופשיות ויכולים לערבב טיפוסים, כמו ב-[1, "two", true].

מערכים שגדלים, כמו list של Python, ArrayList של Java ו-std::vector של C++, נקראים מערכים דינמיים. הם שומרים מקום נוסף בסוף. כשהמקום הזה נגמר, הם מקצים בלוק גדול יותר, מעתיקים אליו את כל האיברים וממשיכים. ההעתקות נדירות מספיק כדי שהוספה בסוף תישאר מהירה בממוצע.

מערך יכול גם להכיל מערכים אחרים. grid[row][col] קורא תא אחד של מערך דו ממדי, הסידור שמשמש ללוחות משחק, גיליונות אלקטרוניים ותמונות. המדריך ל-C על מערכים רב ממדיים מראה איך הם יושבים בזיכרון.

טעויות נפוצות

טעות של אחד (off by one). למערך של 3 איברים יש אינדקסים 0, 1 ו-2, כך שאינדקס 3 כבר מעבר לסוף. Python עוצרת עם שגיאה:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java זורקת ArrayIndexOutOfBoundsException, ו-JavaScript מחזירה בשקט undefined. ב-C אין שום בדיקה: קריאה מעבר לסוף היא התנהגות לא מוגדרת, שיכולה להחזיר זבל או להקריס את התוכנית עם segmentation fault.

העתקה בהשמה. ב-Python, ב-Java וב-JavaScript, b = a לא מעתיק מערך; שני השמות מפנים לאותו מערך, כך ששינוי של b משנה גם את a. להעתקה אמיתית השתמשו ב-a.copy() ב-Python או ב-[...a] ב-JavaScript. העמוד על משתנים מסביר למה.

לאן ממשיכים מכאן

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