רוטר - הוצאת נתונים ממערך בדרך היעילה ביותר,

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

"הוצאת נתונים ממערך בדרך היעילה ביותר,"

גירסת הדפסה

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

אשכול מספר 10544

dvir8
חבר מתאריך 13.5.02
5929 הודעות

23:46 10.12.11

הוצאת נתונים ממערך בדרך היעילה ביותר,

ערכתי לאחרונה בתאריך 10.12.11 בשעה 23:57 בברכה, dvir8

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

public void removeAllLine (int line)
{
while(isLineExist(line))
{
//If the line exist so the loop is overall the bounds to find the line number.
for(int i=0;i<_noOfBuses;i++)
{
//This is the part when i find the bound that contain the line number.
if(_buses.getLineNum() == line)
{
//Override the bound by copying the next bounds one back bound every time.
for(int j=i;j<_noOfBuses-1;j++)
_buses = _buses;
}
}
//Null the last bound everytime, and decrease.
_buses = null;
_noOfBuses--;
}
}

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

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
כמה שאלות	Yariv-H	11.12.11 09:31	1
תודה על התגובה המפורטת,	dvir8	11.12.11 12:54	2
מכתב	Yariv-H	11.12.11 23:39	3
זה בדיוק מה שעשיתי :] תראה בקוד מעל	dvir8	12.12.11 08:35	4
אהה אוקי =]	Yariv-H	12.12.11 16:48	5
תודה!	dvir8	13.12.11 15:48	6
לדעתי אם אתה יודע את גודל המערך יש יותר יעיל	no_angel	14.12.11 23:46	7
גם אני חשבתי על זה ,	Yariv-H	16.12.11 09:45	10
מערך זה פתרון רע לבעייה.	Deuce	15.12.11 21:43	8
הכוונה שלך לרשימה מקושרת?	Yariv-H	16.12.11 09:42	9
כן, רשימה מקושרת רגילה.	Deuce	16.12.11 14:12	11
אוקי	Yariv-H	17.12.11 09:47	12
למדת אסמבלר?	Net_Boy	17.12.11 11:48	13
אמ...	Yariv-H	17.12.11 12:24	14
מכתב	Deuce	17.12.11 14:57	15
תודה לכולם, לגבי מה שרשמתם,	dvir8	20.12.11 17:38	16

Yariv-H

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

09:31 11.12.11

1. כמה שאלות
בתגובה להודעה מספר 0

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

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

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

dvir8
חבר מתאריך 13.5.02
5929 הודעות

12:54 11.12.11

2. תודה על התגובה המפורטת,
בתגובה להודעה מספר 1

אני כותב ב JAVA
לא למדנו יעילות עדיין
הכוונה שלא יהיה חורים ברצף של המערך
בכל מקרה, אני חושב שהצלחתי ליעל את הקוד מ 4 לולאות ללולאה אחת:
הקוד שלי הוא כזה:

public void removeAllLine (int line)
{
for(int i=0;i<_noOfBuses;i++)
{
if(_buses.getLineNum() == line)
{
_buses = null;
_noOfBuses--;
}
if(_buses.getLineNum() == line)
{
_buses = _buses;
_buses = null;
_noOfBuses--;
i--;
}

}
}

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

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

Yariv-H

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

23:39 11.12.11

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

מה שעוד אתה יכול לעשות , במידה ואתה יודע את אורך המערך מראש , ליעל את זה ללולאה אחת.
תחזיק משתנה עם גודל המערך.
ברגע שהוצאת נתון מסויים , אתה מכניס לו NULL ומחליף את התא שלך עם התא האחרון. ומוריד את הקאונטר של גודל המערך.
ככה בסריקה אחת אתה שולף את הנתון שלך וגם מעביר אותו לסוף המערך.
עדין ב מקרה הכי גרוע אתה תסרוק את המערוך שלך ב O(n) אבל אני מאמין שלא לזה מתכוונים אצלכם נכון לעכשיו.

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

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

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

dvir8
חבר מתאריך 13.5.02
5929 הודעות

08:35 12.12.11

4. זה בדיוק מה שעשיתי :] תראה בקוד מעל
בתגובה להודעה מספר 3

אני שמח שהגעתי לזה לבד!

לגבי וקטורים עוד לא למדנו, תודה רבה לך!

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

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

Yariv-H

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

16:48 12.12.11

5. אהה אוקי =]
בתגובה להודעה מספר 4

היה לי יום ארוך אתמול ראיתי את זה כאילו רשמת שם עוד לולאה =]
בהצלחה.

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

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

dvir8
חבר מתאריך 13.5.02
5929 הודעות

15:48 13.12.11

6. תודה!
בתגובה להודעה מספר 5

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

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

no_angel
חבר מתאריך 20.3.02
4989 הודעות

23:46 14.12.11

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

אני מקווה שאני הבנתי נכון מה שאתה רוצה.
אם יש לך מערך בגודל 10 זה אומר שיש 10 קווים.
זה אומר שיש קו 1 וקו 2 וכו' עד 10.
אם מבקשים להכניס קו חדש זה לוקח בעצם O(1) מבחינת סיבוכיות כי אתה
מכניס לArr[i[ שלך . לכל קו יש תא בפני עצמו באינדקס שלו.
ואז בעצם כל הכנסה ושליפה שלך היא בעצם O(1) .

העבודה ה"גדולה" בעצם זה באתחול המערכך בהתחלה שאתה בונה אותו.

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

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

Yariv-H

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

09:45 16.12.11

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

אבל הבעייה היא אם הקווים שלך לא מספר רץ עד 10?
רציתי להגיד לו שהוא יכול להשתמש בטבלת HASH אבל הם לא למדו מבני נתונים .

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

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

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

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

21:43 15.12.11

8. מערך זה פתרון רע לבעייה.
בתגובה להודעה מספר 0

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

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

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

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

Yariv-H

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

09:42 16.12.11

9. הכוונה שלך לרשימה מקושרת?
בתגובה להודעה מספר 8

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

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

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

14:12 16.12.11

11. כן, רשימה מקושרת רגילה.
בתגובה להודעה מספר 9

מה ההגיון לתחזק את האיברים במערך אם אתה מוצא איבר ב-O(n(?
וכמו שאמרתי, באופן כללי אתה לא מקצה מערך בגודל N אם אתה יודע שבמסגרת הריצה שלו הוא יצטמצם בסדר גודל.
זה נחמד שהפגנתם במהלך האשכול את הידע שלכם במבני נתונים (אפילו שהוא ביקש בלי מבני נתונים מיוחדים), אלא שחלק מהדברים שכתבתם הם לא מדוייקים, לא כ"כ יעילים ובטח שלא פרקטים (אני אשמח לראות איך אתה ממפה n מספרים אקראיים ל-(1..n) בעזרת מודולו P ראשוני גדול).

הדרך הפרקטית בשפת C# או JAVA היא כנראה להשתמש פשוט ב-Dictionary או ב-HashTable, ששתיהן מתחזקות ערכים בצורה של key,value ושתיהן מחזיקות טבלת Hash מאחורי הקלעים (ודואגת לטפל בהתנגשויות, כל אחת בדרכה - דבר שלא לקחתם בחשבון בכלל כאן).

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

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

Yariv-H

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

09:47 17.12.11

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

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

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

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

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

Net_Boy

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

11:48 17.12.11

13. למדת אסמבלר?
בתגובה להודעה מספר 12

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

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

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

Yariv-H

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

12:24 17.12.11

14. אמ...
בתגובה להודעה מספר 13

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

בסופו של דבר שניהם ינפיקו פה O(n)

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

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

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

14:57 17.12.11

15. מכתב
בתגובה להודעה מספר 14

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

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

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

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

dvir8
חבר מתאריך 13.5.02
5929 הודעות

17:38 20.12.11

16. תודה לכולם, לגבי מה שרשמתם,
בתגובה להודעה מספר 0

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

תודה לכולם על העזרה :]

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

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