C# האם אפשר לייעל את הפונקציה הנ"ל ?

[Mike-]

שלום לכולם, לא מזמן התחלתי ללמוד קצת C# (לימוד עצמי)

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

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

אחר כך אני מתכוון לשכתב אותה כך שתחזיר את הערכים לתוך מערך או רשימה או משהו.

    static void Find(string substr, string str)
    {
      Find(substr, str, 0);
    }
    static void Find(string substr, string str, int loc)
    {
      int nextloc;
      if (loc == 0)
        nextloc = 0;
      if ((nextloc = str.IndexOf(substr,loc)) > loc)
      {
        Console.WriteLine("Found match for \"{0}\", at location: {1}", substr, nextloc);
        Find(substr, str, nextloc + substr.Length);
      }
    }

[Ghosthunter]

למה אתה צריך את השורות הבאות?

      if (loc == 0)
        nextloc = 0;

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

תחפש aa במחרוזת aaa.

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

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

[Mike-]

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

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

אם אשנה את השורה האחרונה כך הבעיה תתוקן.

Find(substr, str, nextloc + 1);

האם יש דרך יותר אלגנטית לעשות זאת ?

[M86]

אין לך תנאי עצירה, מה קורה אם אין את התת מחרוזת הזאת?

בכלליות בפונקציות רקורסביות צריכות תנאי עצירה.

[user57202]

אתה צריך להבין למה בכלל פונקציות רקורסיביות טובות

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

טובה.

לכל פונקציה רקורסיבית יש תנאי עצירה.

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

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

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

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

הקיימים (אלגוריתם KMP \ Boyer-moore)

[captaincaveman]

כל מה שכתבת אכן נכון. אבל.... הוא רוצה ללמוד C#, לא אלגוריתמים

שתי הערות שיש לי לגבי הקוד:

1. If block בלי סוגריים... רע! למרות שהקוד עובד מן הסתם, זה פשוט פתח לבעיות. תקפיד תמיד לעטוף בסוגריים. (ולא אכפת לי מה יגידו פה אחרים, כל פעם שאתה כותב בלי סוגריים, אלוהים הורג גור חתולים/כלבים/כלב ים או כל דבר חמוד אחר)

2. אפשר גם לכתוב מחרוזות בצורה כזו:

console.writeline("blablalba " + nameofvariable + "blablabla2" + nameofvariable2);

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

[Mike-]

מה ז"א if block ללא סוגריים ? יש סוגריים בתנאי.

תודה user57202 על ההסבר המפורט.

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

סתם כדי לגוון קצת את סגנון הכתיבה.

[captaincaveman]

if (condition)
{
  your code here
}

^^^^^

good!

if (condition)
  your code here

^^^^^

BAD BAD BAD

[user57202]

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

סתם כדי לגוון קצת את סגנון הכתיבה.

לממש פונקציה כזו ללא רקורסיה אתה יודע ?

[M86]

שתי הערות:

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

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

[Mike-]

תודה לכולם על התגובות.

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

אני אשכתב את הפונקציה הזאת לצורה של לולאה כדי שתזלול קצת פחות זכרון.

[isildur]

2. אפשר גם לכתוב מחרוזות בצורה כזו:

console.writeline("blablalba " + nameofvariable + "blablabla2" + nameofvariable2);

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

החיסרון בכתיבה כזו הוא שגורמים ליצירה של 6 מחרוזות שונות (כל מחרוזת עם "" ועוד מחרוזת על כל +). עדיף להשתמש ב format string כמו שהוא עשה או להשתמש ב StringBuilder.Append אם לא רוצים ללכת לסוף השורה כל פעם.

[שניצל]

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