אתגר - אלגוריתם סופר מהיר להסרת מחרוזות כפולות

[ירושל]

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

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

 

[Rרחמים]

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

 

[חגי פאהן]

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

ר' רחמים, קשה לי להאמין שת"ח כמוך ישאל שאלה שאינה למעשה.

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

 

[פרוגיוזרית]

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

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

כשבאים להשוות אלגוריתמים מדברים בסדרי גודל.

סדרי גודל יכולים להיות
N
N^y
Nlogy
וכולי.

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

אלו הכללים, לא אנחנו המצאנו אותם

 

[Rרחמים]

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

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

 

[חגי פאהן]

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

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

 

[nigun]

@Rרחמים
חשבתי גם על הכיוון של @חגי פאהן אבל עם שיפורים שיתאימו לכל מקרה.
להמיר את כל הסטרינגים לBase64, ואז לבנות מערך באורך 64*64
ולאנדקס את כל הקשרים כך ש AA == 0 AB ==1 וכן הלאה.

בתוכם צריך לשמור את המיקומים של כל הקשרים, אולי משהו כזה:
בכל מערך לשמור מערך באורך N , ובתוכם לשמור מערכים באורך של הסטרינג הכי הארוך -1, שכולם מכילים NULL.

אם הסטרינג הראשון הוא AABB אני שומר ב0>0>0 מצביע ל0, דהיינו שהקשר הבא הוא AB, וב1>0>1 אני שומר מצביע ל2 שזה אומר שהקשר הבא הוא BB.
בחיפוש של AAB אני עובר על הקשר הראשון ומוצא שהקשר הבא זהה
וכנ"ל בחיפוש של ABB וכן הלאה.

כנראה שיש דרך לשפר את זה, אבל זה הכיוון.

 

[ctrl c]

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

סיבוכיות זמן ריצה:
הכנסת איבר לtrie בO(s) כאשר s אורך המחרוזת. לכן סה"כ זמן הריצה O(m) כאשר m הוא סכום אורכי המחרוזות

סיבוכיות זיכרון:
O(m) כאשר m הוא סכום אורכי המחרוזות

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

 

[Rרחמים]

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

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

 

[xl3391]

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

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