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

[Rרחמים]

אם אתה משתמש בקוד שהובא כאן לעיל, איך תפעיל אותו על כל הליבות?

בשורה הזו [שהוזכרה כאן לעיל], עוברים על כל המערך מהתחלה ועד הסוף אחד אחרי השני

for i, word in enumerate(arr):

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

 

[Rרחמים]

אני ראיתי שעוד לא הציעו כאן, אם זאת בעיה אמיתית שכל הדרכים קבילות, אפשר להשתמש בhashset שממפה את כל המחרוזות לפי HASH, מה שאומר שהכפילויות ימחקו, בהנחה ואין לשפה HASHSET, אז אפשר גם עם DICTIONARY או כל דבר דומה, הנה פסאודו קוד (באמת זה פיתון)

d = {}
for i in words:
    d[i] = i;
return list(d)

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

 

[שלמה וייס]

אני ראיתי שעוד לא הציעו כאן, אם זאת בעיה אמיתית שכל הדרכים קבילות, אפשר להשתמש בhashset שממפה את כל המחרוזות לפי HASH, מה שאומר שהכפילויות ימחקו, בהנחה ואין לשפה HASHSET, אז אפשר גם עם DICTIONARY או כל דבר דומה, הנה פסאודו קוד (באמת זה פיתון)

d = {}
for i in words:
    d[i] = i;
return list(d)

ואפשר להשמיט את כל המחרוזות הזהות ממש, כבר בהתחלה. לדוגמא:

def no_duplicate(arr):          
    arr = sorted(set(arr), key=len)            
    result = arr.copy()          
    for i, word in enumerate(arr):
        for rest in arr[i+1:]:  
            if word in rest:    
                result.remove(word)
                break            
    return result

ההמרה לset תמחוק את כל הכפילויות הזהות ממש.

 

[ירושל]

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

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

ירושלים, חלום, שלום, מספר, ספר, ים, לו.

נתחיל עם המחרוזת הארוכה ביותר, ונלך למקום של התו הראשון של המחרוזת במילון – נניח, עבור המחרוזת 'ירושלים' – נלך לאות י'. באותה אות, נראה אם נמצאו מחרוזות באורך זהה או גדול לאורך המחרוזת הנוכחית. לא נמצא? מצוין, המחרוזת אינה קיימת. נוסיף אותה למערך התוצאה ונפרק אותה – י': 7: ירושלים, ר': 6: רושלים, ו':5: ושלים וכן הלאה.

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

בכל פעם שמורידים אות, הולכים למקום המתאים במילון – ובודקים רק מול המילים באותו אורך.

את חיפוש ההתאמה של המחרוזת או תת המחרוזת אפשר למקבל (נניח, באות א' באורך 5 יש 30 מילים – אפשר להשוות לכולן במקביל)
וכמו כן - אפשר לחפש התאמה במקביל לכל המילים באותו האורך שמתחילות בתווים שונים.

 

[ynigun]

@ירושל
איך הוא ימצא את המחרוזת "ירו"?
איך זה חוסך בכמות הפעולות בסך הכל?

 

[ynigun]

@Rרחמים
אתה רוצה להסיר גם את "ירו" מ"ירושלים"
או רק מילים נפרדות כמו "עולם" מ"שלום עולם" או "וברכה לכל" מ"שלום וברכה לכל העולם"?

 

[gp]

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

 

[Tzzpora]

for i in words:

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

 

[Rרחמים]

@Rרחמים
אתה רוצה להסיר גם את "ירו" מ"ירושלים"
או רק מילים נפרדות כמו "עולם" מ"שלום עולם" או "וברכה לכל" מ"שלום וברכה לכל העולם"?

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

 

[ynigun]

@Rרחמים
אם זה רק מילים שלמות אפשר לשמור כל מילה באינדקס
לדוגמה (העקתי מאתר כל שהוא) :

documents = {
    1: "a donut on a glass plate",
    2: "only the donut",
    3: "listen to the drum machine",
}

index = {
    "a": [1],
    "donut": [1, 2],
    "on": [1],
    "glass": [1],
    "plate": [1],
    "only": [2],
    "the": [2, 3],
    "listen": [3],
    "to": [3],
    "drum": [3],
    "machine": [3],
}

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

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

 

[ירושל]

@ירושל
איך הוא ימצא את המחרוזת "ירו"?
איך זה חוסך בכמות הפעולות בסך הכל?

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

 

[s976]

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

עץ סיפות – ויקיפדיה

he.wikipedia.org

GitHub - kasraavand/SuffixTree: Optimized implementation of suffix tree in python using Ukkonen's algorithm.

Optimized implementation of suffix tree in python using Ukkonen's algorithm. - kasraavand/SuffixTree

github.com

Substring index - Wikipedia

en.wikipedia.org

ודרך אגב, אני מנחש שיותר טוב יהיה לחבר את כל המחרוזות לאחת ארוכה, ולעבוד אתה (כלומר, לעשות עץ ממנה, ולא מהרבה מחרוזות מקוריות).

 

[s976]

___

 

[ynigun]

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

 

[חגי פאהן]

למה?
מה ההבדל בין אסמבלר לכל שפה אחרת בלי GC?

למעשה המחשב עצמו לא יודע עברית, וגם לא c# ולא java. הוא יודע שפה אחת שמורכבת משתי אותיות: 0 ו-1. יש זרם ואין זרם. לימדו אותי בקורס שאסמבלר מתורגם לבינארי, וכל שאר השפות מתורגמות לאסמבלר ומשם לבינארי. כך שאסמבלר היתה ותהיה השפה הכי מהירה.
(ציפור קטנה לחשה לי שהתוכנות של מטוסי הקרב מתוכנתות אך ורק באסמבלר)

 

[שלמה וייס]

@Rרחמים
תעלה קובץ טקסט ונריץ בדיקות יעילות.

 

[ynigun]

למעשה המחשב עצמו לא יודע עברית, וגם לא c# ולא java. הוא יודע שפה אחת שמורכבת משתי אותיות: 0 ו-1. יש זרם ואין זרם. לימדו אותי בקורס שאסמבלר מתורגם לבינארי, וכל שאר השפות מתורגמות לאסמבלר ומשם לבינארי. כך שאסמבלר היתה ותהיה השפה הכי מהירה.

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

 

[חגי פאהן]

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

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

 

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

הצעה:

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

זמן ריצה: nlogn.

 

[Rרחמים]

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

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