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

[אפר]

איך החיפוש ידלג למחרוזת הגדולה יותר?

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

זה נראה לי קטן מבדיקת הכלה אבל בכל מקרה ניתן לשמור אינדקס של זה

 

[שלמה וייס]

3. מפרקים כל מחרוזת ומכניסים את האינדקס של כל תתי המחרוזות מהארוכה לקצרה, בלי כפילויות.
נקבל - י' = [ירושלים], ר' = [רושלים] ו' = [ושלים] ש' = [שלים] ל' = [לים] י' = [ים]

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

 

[אפר]

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

וכן במקביל חיסור בתחילה ובסוף

 

[nigun]

@Rרחמים
מה אורך המחרוזות?
מעניין אותי לבדוק האם זה באמת לוקח עשרות שעות?

 

[שלמה וייס]

נכון.

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

בפייתון למשל, זה יראה כך:

def no_duplicate(arr):                   
    arr.sort(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

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

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 תמחוק את כל הכפילויות הזהות ממש.

 

[Rרחמים]

@Rרחמים
מה אורך המחרוזות?
מעניין אותי לבדוק האם זה באמת לוקח עשרות שעות?

קח 10 מליון מחרוזות, שהקטנה באורך תו אחד, והגדולה באורך 100 אלף תוים. ותריץ את זה עם 8 ליבות ו16 נימים במקביל, וזה יקח כמה ימים.

 

[nigun]

@Rרחמים
מה יעזור לך ריבוי ליבות
לתוכנית יכול להיות רק ט'רד בודד.

 

[אלעזר 1]

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

[0] = 'א',
[1] = 'ב',
[2] = 'י'

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

 

[Rרחמים]

@Rרחמים
מה יעזור לך ריבוי ליבות
לתוכנית יכול להיות רק ט'רד בודד.

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

 

[nigun]

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

 

[Rרחמים]

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

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

 

[חגי פאהן]

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

 

[שימיגם]

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

 

[Rרחמים]

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

קודם צריך אלגוריתם טוב...

 

[ירושל]

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

עבור כל אות במילון שומרים מערך של אינדקסים או מצביעים בלבד.

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

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

 

[Rרחמים]

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

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

 

[שימיגם]

לקחת מחרוזת בודדת הגדולה ביותר ולחלק אותה לאורכים של 1 2 3 וכ"ו
להשוות מחרוזות של אותו אורך לחלקים מהמחרוזת הגדולה
ואח"כ למחרוזת הגדולה הבאה וכ"ו

ירושלים
י ר ו ש ל י ם > להשוות מול כל המחרוזות של תו אחד
יר רו וש של לי ים > להשוות מול כל המחרוזות של 2 תווים
ירו רוש ושל שלי לים > מול 3
ירוש רושל ושלי שלים > מול 4 וכ"ו

 

[nigun]

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

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

 

[nigun]

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

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

 

[גזעי]

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

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