הפוסט הקודם בסדרה – רקורסיה חלק ה' – חיפוש קובץ במערכת קבצים
אני מאמינה שרובכן ראיתן את סרטון המאסטר שף של מייקרוסופט ששטף את הרשתות החברתיות בשבוע שעבר.
להמשיך לקרוא "רקורסיה חלק ו' – הטעות של יונתן"הפוסט הקודם בסדרה – רקורסיה חלק ה' – חיפוש קובץ במערכת קבצים
אני מאמינה שרובכן ראיתן את סרטון המאסטר שף של מייקרוסופט ששטף את הרשתות החברתיות בשבוע שעבר.
להמשיך לקרוא "רקורסיה חלק ו' – הטעות של יונתן"היי לכולן!
בפוסטים הקודמים כתבתי על שיטות שונות לפיתוח רקורסיות. לפני שנמשיך לתרגילים ועוד דברים מעניינים בנושאי רקורסיות, אני רוצה להקדיש פוסט לאחד מהיישומים השימושיים של רקורסיות – חיפוש במערכות קבצים היררכיות.
בפוסט זה אני רוצה ליישם חיפוש פשוט של קובץ בתיקייה נתונה ובכל תתי התיקיות שלה.
לפני שאנחנו מתחילות ליישם, בואו נחשוב איך חיפוש כזה צריך להתבצע, והאם בכלל אפשר ליישם אותו בקוד שאיננו רקורסיבי?
מערכת קבצים במחשב היא מערכת היררכית. כל תיקייה יכולה להכיל תחתיה גם קבצים וגם תיקיות אחרות שבתורן יכילו קבצים ותיקיות וכן הלאה. דרך נוחה להסתכל על כל הקבצים, התיקיות ותת התיקיות יכולה להיות בעץ.
לדוגמא, הנה כמה המבנה של כמה מהתיקיות והקבצים בתיקיית Documents במחשב שלי –
כעת, נניח והייתי רוצה להריץ חיפוש מתוך תיקיית Documents ולמצוא קובץ בשם response.txt .
ישירות מתחת לתיקייה נמצאים רק שני קבצים – cookies.jpg ו-Penguins.png. אף אחד מהם הוא לא הקובץ שאני מחפשת. אבל האם הגיע הזמן להיכנע? עדיין לא! בתיקייה שלי יש שלוש תתי-תיקיות, והקובץ המבוקש יכול להיות בכל אחת מהן.
אני אכנס לכל אחת מהתיקיות ואבדוק האם אחד מהקבצים בהן הוא הקובץ שאני מחפשת. הקבצים בתתי התיקיות שלי הם הקבצים README.md, anagrams.py, empty spaces, portal. שוב לא מצאתי את מה שחיפשתי. אבל גם הפעם יש לי עוד תתי תיקיות לחפש בהן.
אני ממשיכה את החיפוש, ובסוף תחת התיקיה code_jam אני מוצאת את הקובץ שחיפשתי – response.txt.
כעת, בואו נחשוב – האם הייתי יכולה לבצע חיפוש שכזה בעזרת לולאה?
אחת מהטענות שנשמעות לעתים קרובות כנגד רקורסייה היא שכל משימה שנפתרת באמצעות רקורסיה אפשר לכתוב בצורה פשוטה יותר בעזרת לולאה. האם זה המקרה כאן?
התשובה היא כן ולא – ניתן לפתור בעזרת לולאה, אבל לא באופן פשוט יותר.
השיטה למימוש חיפוש שכזה בעזרת לולאה היא בעזרת מחסנית ולולאת while. זה מימוש ממש מגניב, ואני אשמח לכתוב אותו בפירוט בפוסט עתידי. כרגע אני רק רוצה שנשים לב לנקודה אחת – במימוש בעזרת מחסנית ולולאה אנחנו בעצם מחקות את אותה עבודה שרקורסיה עושה. אנחנו מכניסות את כל התיקיות ותתי התיקיות למחסנית, מוציאות אותן אחת ואחת ומריצות עליהן את אלגוריתם החיפוש שלנו. במקרה של חיפוש במערכות היררכיות מימוש בעזרת לולאה מנסה להעתיק את מה שהרקורסיה עושה – ולא להיפך.
אז מה הדרך לממש חיפוש כזה בעזרת רקורסיה?
נתחיל מההתחלה – אם היה נתון לי מערך של קבצים והייתי צריכה רק לבדוק האם אחד מהם הוא הקובץ שאני מחפשת, איך הייתי עושה זאת? בקלות, הייתי מחפשת את שם הקובץ במערך ואם קיים כזה מחזירה אותו.
def find_file(files_list, name):
for f in files_list:
if f.name == name:
return f
return None
שימו לב שאני נותנת לעצמי פה שתי הקלות:
עכשיו, לחלק הבא – נניח וברשימת הקבצים שלי הייתה גם תיקיות. במקרה כזה הייתי צריכה לבדוק האם הקובץ נמצא בתוכן. איך הייתי עושה זאת?
הייתי מוסיפה חלק מיוחד לקוד שמטפל בתיקיות – במקום לבדוק אם שם התיקייה זהה לשם הקובץ שאני מחפשת, הייתי מוציאה את רשימת כל הקבצים בתיקייה ובודקת אותם.
כשאתן קוראות את הקוד שימו לב לכמה דברים.
def find_file(files_list, name):
for f in files_list:
if is_folder(f):
folder_files = get_files(f)
for f in folder_files:
if f.name == name:
return f
elif f.name == name:
return f
return None
בזאת כתבנו אלגוריתם שיודע לחפש קובץ בשתי רמות היררכיה – בתיקייה הראשית ובתתי התיקיות המיידיות שלה.
מה היה קורה אם היינו רוצות להוסיף רמה נוספת של חיפוש בתוך תתי התיקיות של אותן תיקיות?
ואם היינו רוצות לחפש בתתי התיקיות שלהן?
כמובן שלא נוסיף עוד לולאות מקוננות לעד, פה נכנסת הרקורסיה לעניין.
החלק בתוך הלולאה הפנימית של האלגוריתם שלנו (שורות 5-7) עושה פחות או יותר את אותו הדבר שהלולאה החיצונית עושה. הוא משווה כל קובץ ברשימת הקבצים לשם שאנחנו מחפשים. במקום לכתוב את אותו הקוד מחדש, יכולנו לקרוא לפונקציה find_file שתעשה את החיפוש בשבילנו.
בואו נכניס את הקריאה הזו לאלגוריתם –
def find_file(files_list, name):
for f in files_list:
if is_folder(f):
folder_files = get_files(f)
return find_file(folder_files, name)
elif f.name == name:
return f
return None
זה כבר נראה קצת יותר טוב, אבל עכשיו הכנסנו באג לקוד.
הפונקציה find_file תמיד מחזירה תוצאה, בין אם היא מחזירה קובץ ובין אם היא מחזירה None. המשמעות כאן היא שאנחנו עלולות לצאת מהרקורסיה לפני שהספקנו לעבור על כל הקבצים.
אני אמחיש את הבאג בעזרת הדוגמא של התיקיות במחשב שלי איתה התחלנו.
נניח ואני מחפשת את הקובץ penguins.png, ורשימת הקבצים שאיתה אני מתחילה היא הרשימה שמכילה את התיקייה Documents בלבד.
הריצה של הפונקציה תיראה כך –
find_file([Documents], “Penguins.png”): f = Documents is_folder(Documents) → True folder_files = [coockies.png, maya_solves, Blog, Beatsaber, Penguins.png] find_file([coockies.png, maya_solves, Blog, Beatsaber, Penguins.png], “Penguins.png”) find_file([cookies.png, maya_solves, Blog, Beatsaber, Penguins.png], “Penguins.png”): f = cookies.png is_folder(cookies.png) → False “cookies.png” == “Penguins.png” → False f = maya_solves is_folder(maya_solves) → True folder_files = [README.md, anagrams.py, code_jam] find_file([README.md, anagrams.py, code_jam], “Penguins.png”) . . .find_file([README.md, anagrams.py, code_jam], “Penguins.png”)→ None return None find_file([Documents], “Penguins.png”):find_file([coockies.png, maya_solves, Blog, Beatsaber, Penguins.png], “Penguins.png”)→ None return None
הפונקציה שלנו החזירה None1 למרות שהקובץ penguins.png קיים בתיקייה Documents. זה קרה בגלל שהחזרנו את תוצאת הקריאה שלנו לרקורסיה מיד כשהיא חזרה בלי לבדוק את שאר הקבצים בתיקייה.
מה שחסר לנו באלגוריתם זה קוד שבודק האם הקובץ נמצא בתיקייה או באחת מתתי התיקיות שלה ואם לא ממשיך הלאה בחיפוש.
נתקן את האלגוריתם בהתאם –
def find_file(files_list, name):
for f in files_list:
if is_folder(f):
folder_files = get_files(f)
result = find_file(folder_files, name)
if result:
return result
elif f.name == name:
return f
return None
זהו, יש לנו אלגוריתם פועל.
נריץ על דוגמא כדי לבדוק אותו (דוגמא ארוכה, כדאי להצטייד בכוס תה).
find_file([Documents], “recursion_e”): f = Documents is_folder(Documents) → True folder_files = [coockies.png, maya_solves, Blog, Beatsaber, Penguins.png] result = find_file([coockies.png, maya_solves, Blog, Beatsaber, Penguins.png], “recursion_e”) find_file([cookies.png, maya_solves, Blog, Beatsaber, Penguins.png], “recursion_e”): f = cookies.png is_folder(cookies.png) → False “cookies.png” == “recursion_e” → False f = maya_solves is_folder(maya_solves) → True folder_files = [README.md, anagrams.py, code_jam] result = find_file([README.md, anagrams.py, code_jam], “recursion_e”) find_file([README.md, anagrams.py, code_jam], “recursion_e”): f = README.md is_folder(README.md) → False “README.md” == “recursion_e” → False f = anagrams.py is_folder(anagrams.py) → False “Anagrams.py” == “recursion_e” → False f = code_jam is_folder(code_jam) → True folder_files = [response.txt] result = find_file([response.txt], “recursion_e”) find_file([response.txt], “recursion_e”): f = response.txt is_folder(response.txt) → False “response.txt” == “recursion_e” → False return None find_file([README.md, anagrams.py, code_jam], “recursion_e”): result =find_file([response.txt], “recursion_e”)None return None find_file([cookies.png, maya_solves, Blog, Beatsaber, Penguins.png], “recursion_e”): result =find_file([README.md, anagrams.py, code_jam],“recursion_e”)None f = Blog is_folder(Blog) → True folder_files = [Drafts, Published] result = find_file([Drafts, Published], “recursion_e”) find_file([Drafts, Published], “recursion_e”): f = Drafts is_folder(Drafts) → True folder_files = [recursion_e] result = find_file([recursion_e], “recursion_e”) find_file([recursion_e], “recursion_e”): f = recursion_e is_folder(recursion_e) → False “recursion_e” == “recursion_e” → True return recursion_e find_file([Drafts, Published], “recursion_e”): result =find_file([recursion_e], “recursion_e”)recursion_e return recursion_e find_file([cookies.png, maya_solves, Blog, Beatsaber, Penguins.png], “recursion_e”): result =find_file([Drafts, Published], “recursion_e”)recursion_e return recursion_e find_file([Documents], “recursion_e”): result =find_file([coockies.png, maya_solves, Blog, Beatsaber,Penguins.png], “recursion_e”)recursion_e return recursion_e
יאי, שרדנו את הדוגמא הארוכה, ואפילו קיבלנו תוצאה נכונה!
נסתכל שוב על האלגוריתם שלנו.
def find_file(files_list, name):
for f in files_list:
if is_folder(f):
folder_files = get_files(f)
result = find_file(folder_files, name)
if result:
return result
elif f.name == name:
return f
return None
שני דברים בולטים באלגוריתם הזה.
אני אנסה לפתור את שתי הבעיות הללו יחד.
נתחיל מנושא תנאי העצירה. מהו תנאי העצירה של האלגוריתם שלנו?
תנאי העצירה מתקיים כשאנחנו מגיעות לקובץ שאיננו תיקייה ואיננו הקובץ שאנחנו מחפשות. במקרה זה אנחנו יכולות להחזיר תשובה. אין יותר קריאות רקורסיביות.
כדי להבהיר את המקום של תנאי העצירה אני אפצל את האלגוריתם לשני חלקים.
I. אלגוריתם אחד נקי וקצר שרק בודק את תנאי העצירה וקורא קריאה רקורסיבית על כל תיקיה.
II. אלגוריתם שני שעובר על הקבצים בתוך התיקיות, וקורא לאלגוריתם הראשון על כל תיקייה הראשית.
האלגוריתם החדש שלי מתחיל מתיקייה ראשית אחת, שזה מימוש יותר הגיוני ואינטואיטיבי לחיפוש במערכת קבצים, ומכיל פחות קוד מקונן.
def find_file(f, name):
if !is_folder(f):
return f.name == name
else:
return find_file_in_folder(f, name)
def find_file_in_folder(folder, name):
folder_files = get_files(f)
for f in folder_files:
result = find_file(f, name)
if result:
return result
return None
def find_files_recur(root, file_name):
return find_file(root, file_name)
אין ספק שיש פה עניין של טעם. התייחסתי לזה בפוסט שלי על חלוקה לפונקציות.
לא תמיד, ולא בעיני כולן חלוקה כזו תשפר את המצב הקיים. לדעתי מה שטוב באלגוריתם הסופי שלי הוא שהוא מסודר וברור יותר. קל לראות מתי הוא אמור לעצור, ולכן גם קל יותר לדבג ולבדוק אותו.
החיסרון של האלגוריתם הזה הוא שבמקום קריאה רקורסיבית אחת מפורשת, יש לנו רקורסיה מעגלית – find_file קורא ל-find_file_in_folder ולהיפך.
כדי להקל על הקוראת להבין הייתי מקפידה להשתמש במילה רקורסיה בשם הפונקציה הראשית. כמו כן, כיוון שמדובר בפונקציות עזר ולא בפונקציה הראשית, אפשר להגדיר אותן כתתי פונקציות.
אני מקווה שנהניתן מהפוסט ושהוא עזר לכן להבין את השימושיות של רקורסיה. סגנון דומה של אלגוריתם יכול להיות שימושי גם במקרה שאתן מחפשות במבנה נתונים או טקסט מקונן. למשל, ב-json.
בפוסטים הבאים נחזור לדוגמאות בסיסיות יותר, ונפתור תרגילי רקורסיה קלאסיים.
הערות:
פוסט זה נכתב על ידי Captain Fwiffo. במקור כשרשור בטוויטר, ולאחר מכן עובד לפוסט ונתרם לבלוג.
להמשיך לקרוא "[פוסט אורח] איך להתראיין בלי להתייאש (יותר מדי)"הפוסט הקודם בסדרה – רקורסיה – חלק ב' – כתיבת אלגוריתם רקורסיבי מהסוף להתחלה
היי לכולן!
אז כמו שאמרתי בתחילת הסדרה, יש הרבה שיטות להסביר רקורסיות, ואף שיטה לא מתאימה לכולן. אם קראתן את הפוסט הקודם שלי בסדרה, ועדיין לא נפל לכן האסימון, אולי השיטה שאני מציגה בפוסט הזה תהיה השיטה שתתאים לכן.
להמשיך לקרוא "רקורסיה חלק ג' – קופסא שחורה"בשנים האחרונות נהיה יותר ויותר מקובל שמתכנתות יצרפו פרופיל גיטהאב לקורות החיים שלהן. השימוש בגיטהאב בתור "תיק עבודות" הוא משמעותי במיוחד לג'וניורית (כפי שמסבירה פונקצייה אנונימית) אבל גם הרבה סיניוריות מטפחות פרופיל גיטהאב פעיל עם תרומה לפרוייקטי קוד פתוח, כתיבת פרוייקטים אישיים ועוד…
להמשיך לקרוא "איך להפוך פרופיל גיטהאב לכרטיס ביקור"הפוסט הזה נכתב בשיתוף עם תמר דליות המדהימה, ראש צוות גיוס הנדסה של פייסבוק, שהיא המגייסת הכי אכפתית כלפי מועמדות ומועמדים שאי פעם יצא לי לדבר איתה. חלק מהמידע בפוסט הם לקחים שלמדתי על בשרי, חלק הוא תובנות שחברות שיתפו איתי, אבל הרוב הוא מידע יקר ערך שתמר ביקשה ממני להעביר הלאה, כדי לעזור לכן בתהליכי חיפוש עבודה וראיונות אחרי פיטורים.
להמשיך לקרוא "איך להתראיין אחרי פיטורים"הפוסט הקודם בסדרה – רקורסיה – חלק א' – הבנת אלגוריתמים רקורסיביים
אחרי שהצלחנו להבין אלגוריתם רקורסיבי שנתון לנו, הקפיצה המחשבתית הגדולה באמת היא לכתוב אלגוריתם כזה בעצמנו. כפי שאמרתי בפוסט הפותח של הסדרה, אני רוצה להציג מספר הסברים ושיטות לפיתוח אלגוריתם רקרוסיבי. לשם כך אני אשתמש בתרגיל יחיד, וכל פעם אפתור אותו בשיטה אחרת.
להמשיך לקרוא "רקורסיה – חלק ב' – כתיבת אלגוריתם רקורסיבי מהסוף להתחלה"הפוסט הקודם בסדרה – רקורסיה – הקדמה
אז נתחיל מההגדרה הפשוטה ביותר – רקורסיה היא פונקציה שקוראת לעצמה.
אחת הדוגמאות המפורסמות ביותר לרקורסיה היא סדרת פיבונאצ'י. למקרה שאתן לא מכירות – סדרת פיבונאצ'י היא סדרה של מספרים, בה כל מספר הוא הסכום של שני קודמיו בסדרה.
זה לא סוד שאני אוהבת רקורסיות. כתבתי על זה בבלוג, וזו דעה שאני לא מתביישת להביע בפומבי, רקורסיות הן אחת התופעות היפות והאלגנטיות ביותר במדעי המחשב, לטעמי.
לצערי הרב, לרקורסיות יש מוניטין קצת רע, הן נחשבות מאוד מסובכות להבנה ולא כל כך שימושיות – מה שגורם לכך שהמון מתכנתות מתייאשות מהר מהניסיון להבין אותן ומדלגות הלאה.
להמשיך לקרוא "רקורסיה – הקדמה"לפני שבועיים התחלתי להרגיש שאני מתגעגעת לפתירת "שאלות ראיונות". מאז שהתחלתי את העבודה החדשה שלי יצא לי להתעסק בהמון נושאים מרתקים וכיפיים, אבל לא בפתירת חידות אלגוריתמיות פשוטות.
להמשיך לקרוא "המספר הגדול הבא"