הפוסט הקודם בסדרה – רקורסיה חלק ה' – חיפוש קובץ במערכת קבצים

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

היי לכולן!

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

חיפוש במערכת קבצים היררכית

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

מערכת קבצים במחשב היא מערכת היררכית. כל תיקייה יכולה להכיל תחתיה גם קבצים וגם תיקיות אחרות שבתורן יכילו קבצים ותיקיות וכן הלאה. דרך נוחה להסתכל על כל הקבצים, התיקיות ותת התיקיות יכולה להיות בעץ.
לדוגמא, הנה כמה המבנה של כמה מהתיקיות והקבצים בתיקיית 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

שימו לב שאני נותנת לעצמי פה שתי הקלות:

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

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

כשאתן קוראות את הקוד שימו לב לכמה דברים.

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

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

הפונקציה שלנו החזירה None¹ למרות שהקובץ 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

שני דברים בולטים באלגוריתם הזה.

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

אני אנסה לפתור את שתי הבעיות הללו יחד.

נתחיל מנושא תנאי העצירה. מהו תנאי העצירה של האלגוריתם שלנו?
תנאי העצירה מתקיים כשאנחנו מגיעות לקובץ שאיננו תיקייה ואיננו הקובץ שאנחנו מחפשות. במקרה זה אנחנו יכולות להחזיר תשובה. אין יותר קריאות רקורסיביות.

כדי להבהיר את המקום של תנאי העצירה אני אפצל את האלגוריתם לשני חלקים.
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.

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

פוסטים נוספים בסדרת הרקורסיות

הערות:

הפוסט הקודם בסדרה – רקורסיה – חלק ב' – כתיבת אלגוריתם רקורסיבי מהסוף להתחלה

היי לכולן!

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

הפוסט הקודם בסדרה – רקורסיה – חלק א' – הבנת אלגוריתמים רקורסיביים

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