בתשובה לגדי אלכסנדרוביץ', 07/08/06 10:30
 |
|
 |
||
|
||||
 |
המשימה היא לבנות מערך P בגודל N, שיחזיק במקום ה-n את סכום המחלקים של n. בשלב ראשון, הצב את המספר 1 בכל המקומות. אחר-כך, הוסף 2 לכל המקומות מהצורה 2n (עד N, כמובן). ואז 3 לכל המקומות מהצורה 3n, ו- 4 לכל המקומות מהצורה 4n, וכן הלאה. בתוך N*logN פעולות, המערך מלא. את הזוגות של מספרים ידידים אפשר למצוא על-ידי בדיקה מתי P[P[n]]=n. |
 |
 |
 |
|
|
|
||
|
||||
|
טוב, אני הולך להתבייש בפינה... הייתי צריך לחשוב על זה. | |
|
|
|
|
|
||
|
||||
|
אתה מציע בניה של מערך של מאה מיליון אלמנטים? | |
|
|
|
|
|
||
|
||||
|
לדעתי אפשר להחליף את המערך ב-lazy evaluation שמסמלץ את הגישה למערך. אם אני לא טועה, אנחנו עדיין נשארים בגבולות הסיבוכיות הלא-אקספוננציאלית. | |
|
|
|
|
|
||
|
||||
|
איך זה יעבוד? בעניין הסיבוכיות, אין לי מושג, עוזי טען שתוכנית מחשב תוכל לבצע את הבדיקות ב5 דקות. |
|
|
|
|
|
|
||
|
||||
|
5 דקות זה כבר לא ייקח (במחשב שלי, שמועמס כבר כך, ובלי אופטימיזציות), אבל האלגוריתם בבירור יותר יעיל ברמה העקרונית. | |
|
|
|
|
|
||
|
||||
|
אז תן אומדן משלך- כמה זמן זה ייקח, וכמה זמן זה היה לוקח במחשב לא עמוס וקוד אופטימלי? | |
|
|
|
|
|
||
|
||||
|
אין לי שום מושג. בשביל לתת אומדן אני צריך להריץ את התוכנה על המחשב הנ''ל ועם האופטימיזציות הנ''ל על טווחים קטנים יחסית ולראות את קצב הגידול. | |
|
|
|
|
|
||
|
||||
|
סדר גודל? חצי שעה? יום? שבוע? | |
|
|
|
|
|
||
|
||||
|
שוב: אין לי מושג. המספר 100,000,000 הוא שרירותי למדי. דוגמה אחרת: בתוכנה שהייתי צריך להריץ ושזמן הריצה שלה הוא אקספוננציאלי "מאוד", הרצה עבור הפרמטר 15 לקחה כמה שניות, עבור 16 יום, עבור 17 חודש ועבור 18 המון זמן. אני לא יכול לתת הערכה לדבר כזה בלי לבדוק את קצב הריצה עבור פרמטרים יותר קטנים - אבל אחרי שעשיתי את זה, הצלחתי להעריך את זמן הריצה בדיוק לא רע. לפחות אני צריך בסיס כלשהו. |
|
|
|
|
|
|
||
|
||||
|
חשבתי שיש לך קוד רץ, לא? ב5 דקות, לאן הגעת? אולי שווה לחשב את היחס: זמן ריצה פר ראשוני. |
|
|
|
|
|
|
||
|
||||
|
הקוד שכתבתי פועל בשני שלבים: קודם מחשב את כל המערך, ורק אחר כך עובר עליו ומוצא את המספרים המתאימים. אני לא הדפסתי מונה רץ שאומר לאן כבר הגעתי כי זה מאט את הריצה (שהפסקתי בינתיים). | |
|
|
|
|
|
||
|
||||
|
בדיקה קצרה ב-pc די רגיל נתנה לי ב-102 שניות את כל הזוגות עד 100,000,000 (הזוג האחרון הוא 99,899,792 ו 93,837,808 סה"כ 467 זוגות אבל לא הורדתי כפילויות ולא הורדתי מספרים שהם הזוג של עצמם). | |
|
|
|
|
|
||
|
||||
|
איזו שפה ואיזה קומפיילר? | |
|
|
|
|
|
||
|
||||
|
שפת c++ (בעצם, לא ממש השתמשתתי ב++). הקומפיילר של מיקרוסופט. אגב, כשאני מסנן את הזוגות הכפולים ואת אלה שהם הזוג של עצמם, אני מקבל 231 זוגות, כשהאחרון הוא 97,041,735 ו-97,945,785. זה גם מוריד את הזמן ב-2 שניות. |
|
|
|
|
|
|
||
|
||||
|
6 28 496 8,128 33,550,336 |
|
|
|
|
|
|
||
|
||||
|
כל מספר הוא ידיד של עצמו ולכן צריך לסנן את התשובות האלה. | |
|
|
|
|
|
||
|
||||
|
מספרים מושלמים, כמו 6 (מספרים שסכום המחלקים שלהם שווה לעצמם). | |
|
|
|
|
|
||
|
||||
|
טוב, אני בספק אם הבעיה היא בקומפיילר (גם אני ב-++C). עד 10,000,000 הוא דווקא עושה את זה די מהר. כנראה שב-100,000,000 אני כבר מתחיל להרגיש את ההשפעה של הזכרון הוירטואלי. | |
|
|
|
|
|
||
|
||||
|
תוכל לפרט קצת איך היית עושה את זה מבלי לקבל בעצם את האלגוריתם ה"מקורי" (שגם הוא לא אקספוננציאלי, כמובן)? | |
|
|
|
|
|
||
|
||||
|
(אני מניח שהכוונה היא "אקספוננציאלי בגודל המספר N", לא "אקספוננציאלי בגודל הייצוג של N"). | |
|
|
|
|
|
||
|
||||
|
המ... מסתבר שאני בעצם מקבל את האלגוריתם ה"מקורי", לא? :) | |
|
|
|
|
|
||
|
||||
|
מה הבעיה כאן? במימוש סטנדרטי כל תא במערך ידרוש 4 בייטים - בהחלט בגבולות הזכרון הוירטואלי הסביר. המחשב קצת יקרטע, אבל לדעתי ישרוד (אני מנסה את זה כרגע). | |
|
|
|
|
|
||
|
||||
|
אם תצליח לבצע את זה בפחות מ5 דקות על PC תעדכן אותי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |