רוטר - שאלה שמפריע לי בזמני ריצה של מעבד...

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה שמפריע לי בזמני ריצה של מעבד..."

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10417	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10417

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

07:59 02.07.11

שאלה שמפריע לי בזמני ריצה של מעבד...

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

O(n)
הוא אמר לו שהוא ירוץ על הרשימה , יספור כמה איברים יש , ואז ירוץ שוב את מספר האיברים פחות 4.
המתכנת שם אמר לו שאולי באקדמיה מלמדים אותנו ש

O(2n)~o(n)

אבל בתעשייה זה לא ככה , כי בתאכלס המעבד רץ 2N פעמים.

ואחרי זה הוא אמר לו שהפתרון זה לשים פויינטר 1 , לקדם אותו ב 4.
ואחרי זה לשים פויינטר נוסף , וכול פעם לקדם את שניהם.
כאשר הראשון מגיע לסוף , אז להדפיס את השני.
בקיצר , לדעתי זה מריץ גם 2n-4 איטרציות... ועדין הוא רץ סדר גודל של

O(2n)
מה אתם אומרים? הבחור טעה? או שיש הסבר?

תודה!

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
לא בטוח שהבנתי את נכונות הפתרון השני	ldan192	02.07.11 10:23	1
ברשימה מקושרת יש רק מצביע לאיבר הבא	Webmonster	02.07.11 11:05	3
אה, משום מה חשבתי שדיבר על מערך. וצודק אז	ldan192	02.07.11 23:47	10
תוכל להסביר למה זה יותר מהיר?	Yariv-H	03.07.11 08:03	11
בעיקר בגלל לוקאליות של קאש, אבל לא מהסיבה שהוא ציין.	ldan192	03.07.11 11:31	12
אההה, אוקי נכון ..	Yariv-H	03.07.11 21:22	13
מכתב	VeNom	02.07.11 10:33	2
קידום פוינטר זה	Webmonster	02.07.11 11:08	4
מסכים עם כולכם.	Yariv-H	02.07.11 18:23	5
כשמחשבים O זה עבור n-ים ממש גדולים	Webmonster	02.07.11 18:43	6
ממש לא מסכים אותך .	Yariv-H	02.07.11 22:13	8
הוא סתם מזיין את השכל	Net_Boy	02.07.11 20:32	7
נכון אבל ,	Yariv-H	02.07.11 22:15	9
המראיין אידיוט.	Deuce	08.07.11 00:22	14

ldan192
חבר מתאריך 14.9.08
95119 הודעות

10:23 02.07.11

1. לא בטוח שהבנתי את נכונות הפתרון השני
בתגובה להודעה מספר 0

אבל למה לא להתקדם עד הסוף n צעדים ובסוף לקחת 4 צעדים אחורה? למה להתחיל מההתחלה?
איך הפויינטר השני בדיוק עזר בפתרון?

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Webmonster
חבר מתאריך 21.4.02
2499 הודעות

11:05 02.07.11

3. ברשימה מקושרת יש רק מצביע לאיבר הבא
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

23:47 02.07.11

10. אה, משום מה חשבתי שדיבר על מערך. וצודק אז
בתגובה להודעה מספר 3

שומרים על מצביע נוסף "שמאחר" 4 צעדים אחורה וסגרנו ת'סיפור.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

08:03 03.07.11

11. תוכל להסביר למה זה יותר מהיר?
בתגובה להודעה מספר 10

מאשר לרוץ עד הסוף , לספור כמה איברים יש , ואז לרוץ שוב מספר איברים פחות 4?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

11:31 03.07.11

12. בעיקר בגלל לוקאליות של קאש, אבל לא מהסיבה שהוא ציין.
בתגובה להודעה מספר 11

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

21:22 03.07.11

13. אההה, אוקי נכון ..
בתגובה להודעה מספר 12

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

אחלה תודה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק

10:33 02.07.11

2. מכתב
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 02.07.11 בשעה 10:49 בברכה, VeNom

תחזיק 4 פוינטרים וקאונטר..וכל פעם שאתה מתקדם ברשימה תקדם אותם ואת הקאונטר.
תוודא שהקאונטר מתאפס שהוא מגיע ל 4(קאונטר מודולו 4) ואז באמצעות If\Else תחזיר את הפוינטר הרלוונטי מבין הארבעה..בטוח יש דרכים שצורכות אפילו פחות משתנים..אז אין סיבה שזה לא יעבוד..ואתה עובר פעם אחת על הרשימה עם פוינטר ראשי כזה..כל השאר זה משחק של שמירת כתובות ופוינטרים.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Webmonster
חבר מתאריך 21.4.02
2499 הודעות

11:08 02.07.11

4. קידום פוינטר זה
בתגובה להודעה מספר 0

O של 1
קידום של 2 זה גם כולה שינוי ערך בתא בזיכרון
O של 1
כל איטרציה שלך עד סוף הרשימה המקושרת היא N (לופ שעובר על כל איברי המערך)
וכל פעולה בלופ היא O של 1
כלומר בקירוב יש לך

O(n)+O(1)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

18:23 02.07.11

5. מסכים עם כולכם.
בתגובה להודעה מספר 4

אבל לא משנה איך נסובב את זה אם בקידום פויינטרים או בכול קידום קאוטר או לא משנה מה , מספר הפעולות יהיה 2n-4

ואני גם אומר ש O(1) זה בדיוק On
אבל זה לא מה שהבחור אמר שם...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Webmonster
חבר מתאריך 21.4.02
2499 הודעות

18:43 02.07.11

6. כשמחשבים O זה עבור n-ים ממש גדולים
בתגובה להודעה מספר 5

זה לא בדיוק משנה אם זה 100 או 1000000 העיקר זה סדר גודל של זמן ריצה

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

22:13 02.07.11

8. ממש לא מסכים אותך .
בתגובה להודעה מספר 6

ערכתי לאחרונה בתאריך 02.07.11 בשעה 22:17 בברכה, Yariv-H

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

ולפעמים גם שזמן הריצה הוא O(n)
הקבוע מפיל לך את האלגוריתמים , ואולי אפילו אלגוריתם אחר שמטפל בקלט שלך בעבוד מוקדם ,קיימים ואריאציות שלפעמים גם זמן ריצה של o(n^2) יהיה יותר משתלם.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

20:32 02.07.11

7. הוא סתם מזיין את השכל
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 02.07.11 בשעה 21:09 בברכה, Net_Boy

הקטע של הזמני ריצה תמיד נמדד לפי המחלקה (גם מיליון N זה O(N) ) גם באקדמיה וגם בתעשייה.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

22:15 02.07.11

9. נכון אבל ,
בתגובה להודעה מספר 7

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

וכן, אני מכיר את החידה עם הרשימה המעגלית.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

00:22 08.07.11

14. המראיין אידיוט.
בתגובה להודעה מספר 0

ראשית נוטציית O מוגדרת בצורה אבסולוטית במתמטיקה ובמדעי המחשב. O(n) = O(cn) באשר c קבוע וזה אבסולוטי. נכון להגיד שלא תמיד מה שמעניין אותנו הוא סדר הגודל או מחלקת הסיבוכיות, לדוגמה כמו שאמרת ב-Real Time, באופטימיזציות למיניהן או אפילו לדוגמה QuickSort שב-WC למשל פחות טוב מ-MergeSort ועדיין נותן ביצועים טובים יותר בפרקטיקה.
מבחינת יחידות עיבוד של המעבד בשני הפתרונות יש 2n-4 צעדים, בפתרון שלו יכול להיות שימוש ב-Cache, אך עדיין - מבחינת ספירת צעדים, הוא שקול.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד