עזרה בהבנת קוד פייתון (NCLS)

[yossiz]

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

בכל זאת ולמורת רוחי הפלט ש-@davidnead הביא סגר לי את הפינה האחרונה שעוד לא הבנתי

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

הבנאי NCLS מקבל רשימה של התחלות של טווחים, רשימה מקבילה של סיומי טווחים, ורשימה מקבילה של מזהים

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

מחיפוש מהיר ב-npm לא מצאתי ספרייה שמממשת את המבנה הזה (nested containment lists) אבל יש מבנים אחרים מוכרים (לדוגמה interval tree) אומנם פחות יעילים שמאפשרים את זה.

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

[davidnead]

@yossiz כתב בעזרה בהבנת קוד פייתון (NCLS):

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

בכל זאת ולמורת רוחי הפלט ש-@davidnead הביא סגר לי את הפינה האחרונה שעוד לא הבנתי

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

הבנאי NCLS מקבל רשימה של התחלות של טווחים, רשימה מקבילה של סיומי טווחים, ורשימה מקבילה של מזהים

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

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

[davidnead]

@yossiz כתב בעזרה בהבנת קוד פייתון (NCLS):

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

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

[yossiz]

@davidnead זה הרבה יותר פשוט ממה שאתה חושש

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

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

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

זה מבנה הנתונים NCLS

עד כאן מובן?

עכשיו ל-API של הספרייה,

הבנאי מקבל שלוש רשימות, 1) התחלות של טווחים 2) סופי טווחים 3) מזהים של טווחים (id כלשהו שמזהה את השורה)
שלושת הרשימות באורך זהה
הטווח הראשון בנוי מהאבר הראשון של 1 שזה מייצג את התחלת הטווח, והאבר הראשון של 2 שזה מייצג את סוף הטווח והאבר הראשון של 3 שזה ה-id של הטווח, וכן הלאה וכן הלאה

הבנאי מחזיר מבנה נתונים מסוג ncls

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

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

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

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

[davidnead]

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

    starts = np.array(([8, 5, 3]))
    ends = np.array(([9, 7, 6]))
    indexes = np.array(([21, 11, 10]))
    ncls = NCLS(starts, ends, indexes.astype("int64"))
    starts2 = np.array([1, 6])
    ends2 = np.array([10, 7])
    indexes2 = np.array([40, 41])
    ncls.all_overlaps_both(starts2, ends2, indexes2.astype("int64"))

הפלט של הדוגמה הזו הוא:

(array([40, 40, 40, 41]), array([10, 11, 21, 11]))

כעת אני מנסה להבין. הטווחים של הרשימה הראשונה הם 8-9,5-7,3-6.
הטווחים של הרשימה השניה הם 1-10,6-7.
כל הטווחים של הרשימה הראשונה נכנסים לתוך הטווח של 1-10 (שהאינדקס שלו 40) של הרשימה השניה.
לעומת זאת רק הטווח האחרון של הרשימה השניה (6-7) נכנס בתוך 2 הטווחים הראשונים של הרשימה הראשונה (שהאינדקסים שלהם 10 ו11).
אז אם היית שואל אותי (שכנראה אין לי לא בינה מלאכותית וגם לא שאינה ) הייתי מציע פלט כזה:
40,40,40
21,11
חשבתי גם על אפשרויות נוספות לעשות את זה, אבל אף אחד מהם לא מתאימה לתוצאה הרצויה.
מה פיספסתי?

[yossiz]

@davidnead כתב בעזרה בהבנת קוד פייתון (NCLS):

כלומר היא משוה כל אחד מהטווחים ברשימה אחת לכל אחד מהטווחים ברשימה אחרת

כן (ברעיון, אולי בפועל יש דרך יותר יעילה)

הטווח האחרון של הרשימה השניה (6-7) נכנס בתוך 2 הטווחים הראשונים של הרשימה הראשונה

כנראה שפה טעית, המספר השני של טווח כנראה הוא עד ולא עד בכלל, לכן ל-6-7 יש חפיפה עם 5-7 אבל לא עם 3-6

הייתי מציע פלט כזה:
40,40,40
21,11

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

[davidnead]

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

כעת ברור יותר. יש סך הכל 4 חפיפות. 3 הטווחים של הרשימה הראשונה (ID 21,11,10) חופפים לטווח הראשון של הרשימה השניה (ID 40. כלומר 40,40,40). בנוסף, הטווח האמצעי של הרשימה הראשונה (ID 11) חופף את הטווח האחרון של הראשוימה השניה (ID41). וההשערה שלך לגבי עד ולא עד בכלל - בטלה.

הדבר האחרון שלא מובן זה הסדר של התוצאה. הייתי מצפה לסדר כזה:
40,40,40,41
21,11,10,11

במקום זה קיבלנו:
40,40,40,41
10,11,21,11
כך שהסדר בו מתבצעות הבדיקות (וממילא הבנה של התוצאות) אינו ברור דיו.

[yossiz]

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

[davidnead]

@yossiz כתב בעזרה בהבנת קוד פייתון (NCLS):

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

תודה! אין כמוך.

[davidnead]

@yossiz כתב בעזרה בהבנת קוד פייתון (NCLS):

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

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