6 דרגות של ויקיפדיה - דיון פתוח

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

תעשה בדיקות עבור מספרי n קטנים נגיד 2 או 3
מה שיעבוד על n יעבוד גם על n-x

עבור N=2 זה דיי מיידי כי זה סהכ האם לראשון יש לינק ישירות לשני
עבור N=3 יוצא לי סביבות ה-50 שניות חישוב נראה לי
עבור N=4 הרצתי מוקדם יותר שעה שלמה ולא סיים לחשב :frowning:

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

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

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

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

ומה הכוונה

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

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

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

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

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


מה שאומר שבטוח משהו מתפספס

זה שאפשר מהיר מאוד אני יודע… אני פשוט לא יודע אם זה בגבול היכולות שלנו כרגע :slight_smile: - או בגבול היכולות שלי (מדבר בשם עצמי כמובן)
אישית הכי מהר שהגעתי לערכים במדרגות 3 זה כמה דקות.

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

ניראה כמו עץ חיפוש בינארי
יעילות = O (nlogn) או משהו בסגנון…
אם לוקח לך הרבה זמן ביחס לאחרים יכול להיות שאחרים פתרו את זה בשפות תכנות מהירות יותר

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

לייק 1

זה פרוייקט קוד פתוח, אתה יכול להיכנס ולראות אותו בגיט (בשלב הזה אני מאמין להבין כל קוד).
אני מאמין שמה שקורה שם הוא יותר מחיפוש בינארי - היעילות בזמן מתבססת גם על זה שהם חוקרים את ה-dumps שויקיפדיה משחררים כל הזמן (~150GB של דאטה) + מתבססים על האינטרנט לערכים חדשים שלא בקבצים האלו ועושים להם חקירה לאחור עד למצב שמחברים אותם וקטורית לעץ ה-Offline שיש להם.

זה לא מה שמצופה ממך במקרה הזה (נראה לי :stuck_out_tongue_winking_eye:)

לייק 1

ובקיצור נישאר עם הזמנים הארוכים לבינתיים חחח
:rofl::rofl::rofl:

לייק 1

חחח לגמרי, תודה על התשובה המפורטת :+1: :fire:
התרגילי השלמה נותנים הרבה ערך מוסף

צוואר הבקבוק כרגע הוא שליחת בקשות באופן טורי לעמודי ויקיפדיה.
יש טכניקות שלא למדנו לעיבוד של כמה קישורים במקביל, והתוצאות שיושגו אכן יהיו טובות יותר. אין צורך להשתמש בהן.
לא צריך באמת שהתוכנה תעבוד בזמן סביר עבור N=6, אבל בואו נגיד שהיא כן אמורה להחזיר דברים בזמן סביר (עד 5 דק’ בערך; תלוי במהירות אינטרנט ושלל פרמטרים אחרים) עבור N=3

לייק 1

אפשר הסבר בבקשה
מה זה אומר חיבור וקטורית לעץ?

זו הכוונה: