שאלה כללית סיבוכיות מקום+זמן מול קוד יפה (שפת C)

[noodle]

שלום לכולם,

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

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

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

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

תודה למגיבים

[Jaman]

לא בדיוק הבנתי את המצב הספציפי שלך, אבל בעקרון, premature optimization is the root of all evil.

אם הפתרון ה"מיועל" שלך לא מספק יתרון אמיתי בסיבוכיות (לצורך העניין מ- O(n^2)l ל- O(n Log n)l), והוא גורם לקוד להיות פחות אלגנטי - אל תשתמש בו.

[שניצל]

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

[B.D.B]

אתה חייב C? זה דוגמא קלאסית לתכנות ג'נרי (קיים ב-C++)

[noodle]

הקורס הוא ב-C

לא למדנו מצביעים לפונקציות בקורס הזה.

כמו שאמרתי ההבדל בסיבוכיות הזמן הוא מזערי, אני עדיין אשאר ב-O(n) פשוט אני אצטרך לעשות עוד O(n) לפני שאני מחפש בעץ.

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

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

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

אז אתם ממליצים לממש את המערך ולהתעלם מזמן הריצה הנוסף?

[matteo]

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

אבל תדע שתמיד תמיד יש פתרון

[djdodo]

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

יש מספיק גישות לעשות אלגוריתמים גינריים גם בשפת C.

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

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

לא אמורה להיות בעיה.

[B.D.B]

לא ממש, אלא אם אתה משתמש בפוינטרים לפונקציות, וגם אז זה כמו מימוש OOP.

[noodle]

אוקיי פתרתי את הבעיה בצורה הבאה תאמרו את דעתכם:

מימשתי פונקציות שממירות int לסטרינג וההפך.

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

ונשארה לי רק פונקצית חיפוש אחת שמטפלת בסטרינג.

מה דעתכם?

[jackofalltrades]

פונקציה להמרה מאסקי לאינטג'ר כבר קיימת - atoi. יש גם מקבילה בכוון ההפוך...

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

[noodle]

פונקציה להמרה מאסקי לאינטג'ר כבר קיימת - atoi. יש גם מקבילה בכוון ההפוך...

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

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

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

[B.D.B]

אם הבנתי נכון אתה מחפש בעץ בינארי כאשר הערך של ה-Node הוא לפעמים מטיפוס int ולפעמים סטרינג.

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

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

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

http://publications.gbdirect.co.uk/c_book/chapter5/function_pointers.html

[noodle]

לא הבנת נכון, כאשר אני בונה את העץ, למשל אני מעוניין להכניס עכשיו את הנוד ה-100 אז אני יודע שאבא שלו יהיה עם אינדקס 50, והוא הבן השמאלי, אם זה הנוד ה-101 אז אבא שלו גם יהיה נוד עם אינדקס 50 והוא יהיה הבן הימני, ופה אני משתמש בחיפוש לפי אינדקס - בבניה.

אני קולט מחרוזות ובונה עץ, המידע בתוך ה-NODE זה תמיד סטרינג.

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

האם הפתרון שהצעתי לא טוב?

[B.D.B]

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

[Gil28]

אכן לא ברור מה הכוונה. תפרט בדיוק מה כל נוד מכיל (חוץ מ-left, right) ואילו חיפושים אתה רוצה לבצע.