לוגו אתר Fresh          
 
 
  אפשרות תפריט  ראשי         אפשרות תפריט  מבזקים     אפשרות תפריט  צור קשר     חץ שמאלה ‎print ‎"Hello World!"; if‎ ‎not rules.‎know ‎then rules.‎read(); חץ ימינה  

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



  #1  
ישן 17-02-2014, 08:43
  ramboli ramboli אינו מחובר  
 
חבר מתאריך: 11.07.05
הודעות: 1,003
בחירת פריטים מרשימה באופן אקראי

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

דוגמה (C#):

קוד PHP:
 //המערך שאליו יכנסו הפריטים שנבחרו באקראי
= new int[wrdcnt];
 

            
int randomum;
//העתק של הרשימה על מנת לא לפגוע ברשימה המקורית
        
List<intl2 = new List<int> (l1);

            for (
int i 0a.Lengthi++)
            {

                
randomum r1.Next(il2.Count);


                
a[i] = int.Parse(l2[randomum].ToString());
                
l2.RemoveAt(randomum);

            } 
_____________________________________
Ramboli


נערך לאחרונה ע"י ramboli בתאריך 17-02-2014 בשעה 08:45.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #4  
ישן 17-02-2014, 11:40
צלמית המשתמש של DeepSpace
  DeepSpace DeepSpace אינו מחובר  
 
חבר מתאריך: 23.09.03
הודעות: 11,958
בתגובה להודעה מספר 3 שנכתבה על ידי ramboli שמתחילה ב "תודה על התגובה, הידע שלי..."

60 שניות על סיבוכיות:

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

האומדן נעשה כמספר הפעולות שהאלגוריתם מבצע כתלות בגודל הקלט. אני לא אכנס כרגע להגדרות מתמטיות של חסמים עליונים ותחתונים, אבל בדר"כ משתמשים בסימון [tex]\Theta[/tex] שמסמן "חסם הדוק" (גם חסם תחתון וגם חסם עליון).


לדוגמא, כאשר [tex]n[/tex] הוא גודל הקלט:

סריקת מערך, איבר-איבר: [tex]\Theta (n)[/tex]

מיון מערך בעזרת bubble-sort: [tex]\Theta (n^2)[/tex] (בלי להתייחס למקרה הטוב ביותר, בו המערך כבר ממויין, ואז מדובר ב [tex]O(n)[/tex])


בנוגע לשאלה שלך:

בגלל שרשימה מקושרת לא בהכרח יושבת באופן רציף בזיכרון, גם אם אתה יודע את האינדקס שאתה רוצה למחוק, המחשב עדיין צריך לרוץ על כל האיברים בה, מהראשון עד לאינדקס הרצוי, לכן גם מדובר ב- [tex]\Theta (n)[/tex]
_____________________________________
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rick Cook


נערך לאחרונה ע"י DeepSpace בתאריך 17-02-2014 בשעה 11:51.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #7  
ישן 18-02-2014, 00:19
  משתמש זכר dorM dorM אינו מחובר  
מנהל
 
חבר מתאריך: 26.07.08
הודעות: 6,473
איזה סיבוכיות זה האלגוריתמים האלה?
בתגובה להודעה מספר 2 שנכתבה על ידי Idjo שמתחילה ב "נניח כי בוחרים [tex]k[/tex]..."

זהירות - ספויילר!

שני:
זהירות - ספויילר!


עריכה:

שלישי:
זהירות - ספויילר!

את השלישי ממש אהבתי! D=

נערך לאחרונה ע"י dorM בתאריך 18-02-2014 בשעה 00:27.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #8  
ישן 18-02-2014, 00:44
צלמית המשתמש של Idjo
  Idjo Idjo אינו מחובר  
 
חבר מתאריך: 05.05.02
הודעות: 6,840
בתגובה להודעה מספר 7 שנכתבה על ידי dorM שמתחילה ב "איזה סיבוכיות זה האלגוריתמים האלה?"

הפתרון הראשון מצריך ניתוח של בעיה הנקראת בעית איסוף הקופונים. מספר הפעמים שצריך לחזור על סעיף 1 הוא בממוצע [tex]n\cdot\left(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\cdots+\frac{1}{n-k+1}\right)[/tex]. זה סדר גודל של [tex]n\cdot\log k[/tex]. צריך להסביר איך אתה בודק אם האיבר נמצא כבר ברשימה כדי לנתח את זמן הריצה.

הפתרון השני, כמו שציינת, אינו מתאים להגדרת הבעיה בה אנחנו מעוניינים בסיכוי שווה לכל בחירה. בכל מקרה, זמן הריצה שלו הינו [tex]\Theta(k)[/tex] (שזה הכי טוב שאפשר לצפות).

הפתרון השלישי זה אחד מהפתרונות שרמזתי אליו. כל הכבוד. הוא לוקח [tex]\Theta(n)[/tex] כי צריך להעתיק את המערך ע"מ לא לשנות אותו. עכשיו כשאני חושב על זה אפשר לשפר אותו ל-[tex]\Theta(k)[/tex], רעיונות?

נערך לאחרונה ע"י Idjo בתאריך 18-02-2014 בשעה 00:46.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #23  
ישן 19-02-2014, 22:13
צלמית המשתמש של פסטן
  פסטן פסטן אינו מחובר  
 
חבר מתאריך: 14.12.09
הודעות: 9,648
בתגובה להודעה מספר 22 שנכתבה על ידי Idjo שמתחילה ב "אני לא רואה בקישור ששניכם..."

ציטוט:
במקור נכתב על ידי Idjo
אני לא רואה בקישור ששניכם הבאתם פתרון יעיל כמו שהוצע כאן לבחירת k איברים מתוך n.
שאלת המשך מעניינת: כמה טוב אפשר להשיג אם אסור לשנות את המערך המקורי אפילו באופן זמני? (יש לי רעיון לזמן של [tex]\Theta(k)[/tex] במקרה הממוצע)
אני רואה שם את ההצעה השלישית של dorM:
בוחרים מספר אקראי בין 1 לטווח העליון. בוחרים מספר בין 1 לטווח העליון-1. בוחרים מספר בין 1 לטווח העליון-2. בוחרים מספר בין 1 לטווח העליון-3... ממשיכים כך עד שמסיימים לבחור את k האיברים שרצינו.

בהתחלה המספר הוא האינדקס (כשסופרים מ-1) במערך.

בבחירה השנייה זה האינדקס שממופה למערך כך שאם הוא גדול מ-[TEX]i_1[/TEX] זה האינדקס במערך, ואם הוא גדול או שווה ל-[TEX]i_1[/TEX] אז בוחרים את האלמנט ה-[TEX]i_1+1[/TEX] במערך.

בבחירה השנייה זה האינדקס שממופה למערך כך:
  • אם [TEX]i_3<min(i_1,i_2)[/TEX] זה האינדקס במערך.
  • אם [TEX]min(i_1,i_2) < i_3 < max(i_1,i_2)[/TEX] אז בוחרים את האלמנט ה-[TEX]i_3+1[/TEX] במערך
  • אם [TEX]i_3>max(i_1,i_2)[/TEX] אז בוחרים את האלמנט ה-[TEX]i_3+2[/TEX] במערך.
וכך הלאה. כדי להקל את המיפוי הזה, כל פעם מחליפים בין האלמנט שבחרנו לאלמנט העליון במערך,ועוברים לעבוד בתת-מערך [קצה_תחתון : קצה_עליון-1].

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

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #27  
ישן 19-02-2014, 22:41
צלמית המשתמש של פסטן
  פסטן פסטן אינו מחובר  
 
חבר מתאריך: 14.12.09
הודעות: 9,648
בתגובה להודעה מספר 26 שנכתבה על ידי Idjo שמתחילה ב "לא הבנתי. הסכמתי איתך..."

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

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

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
תגובה

כלי אשכול חפש באשכול זה
חפש באשכול זה:

חיפוש מתקדם
מצבי תצוגה דרג אשכול זה
דרג אשכול זה:

מזער את תיבת המידע אפשרויות משלוח הודעות
אתה לא יכול לפתוח אשכולות חדשים
אתה לא יכול להגיב לאשכולות
אתה לא יכול לצרף קבצים
אתה לא יכול לערוך את ההודעות שלך

קוד vB פעיל
קוד [IMG] פעיל
קוד HTML כבוי
מעבר לפורום



כל הזמנים המוצגים בדף זה הם לפי איזור זמן GMT +3. השעה כעת היא 06:01

הדף נוצר ב 0.38 שניות עם 12 שאילתות

הפורום מבוסס על vBulletin, גירסא 3.0.6
כל הזכויות לתוכנת הפורומים שמורות © 2019 - 2000 לחברת Jelsoft Enterprises.
כל הזכויות שמורות ל Fresh.co.il ©

צור קשר | תקנון האתר