שאלה על מיון מערך

[DadleFish]

3 לא מדוייק

זה לא נכון ל-BUCKET SORT, למשל.

 

[vinney]

בגלל זה תיקנתי אותו ל"ג'נריים" ../images/Emo6.gif

 

[DadleFish]

אני לא מכיר הגדרה של

"אלגוריתם מיון ג'נרי". אלגוריתם מיון מבוסס השוואות לא ניתן לבצע בזמן טוב יותר מNlogN; אבל יש אלגוריתמים אחרים, שאינם מבוססי השוואות.

 

[vinney]

ג'נרי <=> לא תלוי בקלט

Bucket Sort תלוי בקיום הנחות על הקלט (טווח פיזור ידוע)

 

[DadleFish]

מה הבעיה?

אם אתה עובר על כל הקלט פעם אחת (N), אתה יודע מה טווח הפיזור שלו. הבעיה היא אחרת - BUCKET SORT הוא לא מאוד פרקטי במרבית המקרים כיוון שהוא פשוט בזבזני מבחינת זכרון; אבל לכל דיון תיאורטי, BUCKET SORT הוא אלגוריתם מצוין למיון שעובד בסדר גודל ליניארי לגודל הקלט.

 

[demultiplexer]

בקיצור . . . .

יש לי מערך עם ערכים צפויים בין 1 ל 100. אני צריך למיין אותו בצ"ל זה בעיקרון טבלה מבסיס נתונים. איזה אלגו' הכי טוב למקרה כזה ?

 

[vinney]

אם פיזור הערכים קטן יחסית

אז לך על bucket. אם פיזור הערכים לא ידוע מראש (ואלדד מטעה פה לגבי חישוב בזמן N - כדי שBUCKET יהיה יעיל, לפיזור הזה צריך להיות חסם עליון אחד לכל קלט, לא לכל אחד מהקלטים בנפרד), אז לך על quicksort. הבדל הוא שbucket יתן לך O של N, במחיר עצום של זכרון (במקרה של פיזור גדול מדי), ואילו quicksort (כשמו כן הוא מהיר) יתן לך בד"כ משהו קרוב לO של N. במקרה הגרוע אבל הוא יתר N^2.

 

[demultiplexer]

מה זה אומר פיזור ערכים ?

הערכים מתחילים בכל המערך ב0 ואז לאט לאט אני מעדכן אותם ואני רוצה לעדכן את הטבלה לאחר כל עידכון. הם תמיד יהיו עוקבים ותמיד בין 1 ל100 מקסימום

 

[vinney]

BUCKET ללא ספק

תקרא את האלגוריתם, אתה תבין למה. זה מקרה קלאסי למיון הזה.

 

[demultiplexer]

אני מכיר את האלגוריתם מה שאני לא מב

אני מכיר את האלגוריתם אבל אני לא מבין איך אתם מחליטים איזה אלגו' מתאים לאיזה מקרה ?

 

[vinney]

אני אגיד לך את דעתי

מדובר בטבלה במסד נתונים => יש לך כמות גדולה של זכרון אל מול מעט זמן שמותר לך לעבוד => אלגוריתם צריך להיות יעיל בזמן, ולא איכפת לך מזכרון - וBUCKET זה אלגוריתם מאוד בזבזני מבחינת זכרון , אבל הוא ממיין בO של N, פחות מזה באמת אי אפשר

 

[demultiplexer]

אז תמיד בוחרים ככה ?

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

 

[vinney]

תמיד זה מילה קשה ../images/Emo13.gif

תפעיל את השיקול

לפעמים הN שלך הוא בגדלים שאתה לא יכול להרשות לעצמך לבזבז N^2 זכרון, גם אם אתה עובד על PC, למשל - אם אתה ממיין מליון רשומות, במקרה הכי גרוע של מיון דלי, יהיה לך דלי אחד עם כל הרשומות בו, אבל אתה לא יודע איזה, לכן אתה מקצה N זכרון לכל אחד מהדליים (שיכול להיות לכל היותר N כאלה).

 

[demultiplexer]

הבנתי, אבל זה מקרים קיצוניים

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

 

[DadleFish]

עניתי כבר על רוב השאלות ששאלת פה,

ולגבי "כמה תופס כל תא בזיכרון", זה כבר תלוי במימוש. במינימום זה יהיה BYTE אחד, אבל זה לא ריאלי - יותר ריאלי שכל BUCKET יהיה 4 בתים לפחות.

 

[DadleFish]

בוא ואתן לך דוגמה נגדית.

נגיד שיש לך מערך המכיל מספרים שהם unsigned int, כלומר בין 0 לבין 4GB. במקרה כזה תצטרך מערך שגודלו 4GB כפול 4 בתים. מעבר לזה ש-WIN XP בגרסתה הרגילה (לא 64BIT) לא תיתן לך לעשות דבר כזה, גם אם יכולת לעשות את זה זה היה מאוד בזבזני - לא רק מבחינת זכרון אלא גם מבחינת זמן ריצה. תיאוריה זה יפה, וזה נכון ש-BUCKET ממיין ב-(O(N, אבל יכול להיות ש-QUICKSORT יהיה יותר מהיר מ-BUCKET. שאלת איך בוחרים - בד"כ יש לך שתי אפשרויות. הראשונה היא ללכת על האלגוריתם מבוסס-ההשוואות המהיר ביותר, כשזו בד"כ איזושהי גרסה של quicksort. האפשרות השניה נובעת מהיכרות קרובה עם המערך - למשל, אם תגיד לי שיש לך מערך של 1000 משתנים בדיוק, ושהפיזור הוא 40% בין 900 לבין 1000, ועוד כל מיני נתונים כאלו, ייתכן שאוכל להכין אלגוריתם יותר מהיר מ-quicksort, או לשפר את qsort בעצמו; אבל אם אין לך כזה מידע, בד"כ תלך על האופציה הראשונה (וכמעט תמיד זה יהיה תוך שימוש באלגוריתם שאחרים כבר כתבו עבורך).

 

[DadleFish]

מי מטעה?

בהינתן מערך בן N איברים שתוכנו אינו ידוע, תסכים איתי שאפשר למצוא את המינימום ואת המקסימום בסריקה שמשכה הוא N? יופי. עכשיו יש לך את פיזור הערכים, ואתה יכול, תיאורטית, להכין N "סלים". בסריקה נוספת שמשכה N, אתה יכול לפזר את האיברים אל הסלים, ובסריקה נוספת שמשכה N, אתה יכול לבנות את המערך הממוין. אגב - ב-quicksort, אם משתמשים בניחוש, זה הופך אותו לנון-דטרמיניסטי אבל גם נותן אומגה של NlogN (וגם תטה מן הסתם), בסבירות גדולה מ-1 פחות N^2. ועוד - אם עושים "סיבוב" אחד של insertion sort ואז quicksort מלא, מסתבר שזה המימוש הפרקטי המהיר ביותר שקיים כיום למיון מבוסס השוואות ג'נרי, כשלא ידוע שום דבר על המערך.

 

[DadleFish]

אגב, יש לי טעות, אבל היא לא...

...מה שאמרת. הבעיה עם BUCKET SORT זה שה-N שלו הוא לא אורך המערך, או לפחות לא רק אורך המערך, אלא גם התוכן שלו. נניח שיש לנו אלגוריתם BUCKET שהתשלום בו הוא "1" על כל פעולה (כלומר (O(N יהיה בדיוק N פעולות) - אם יש לנו מערך בן 10 איברים שהפיזור שלו הוא בין 1 לבין 1000, מספר הפעולות שיבצע האלגוריתם יהיה 1000, ולא 10. QUICKSORT בסיטואציה כזו יבצע 30 פעולות בערך... הבדל גדול. ה-N ב-BUCKET SORT נקבע אם כן על ידי אורך המערך וגם על ידי תוכנו, ולכן זה מבלבל - (O(N של BUCKET SORT אינו ניתן להשוואה ל-(O(Nlogn של QUICK SORT (או כל מיון מבוסס השוואות אחר).

 

[vinney]

עכשיו אתה צודק לחלוטין

אבל אני חייב להדגיש שוב - quicksort עובד מצוין במקרה הסביר, אבל במקרה הגרוע הוא נותן N^2, ולפעמים זה משהו שחשוב להתחשב בו. יחד עם זאת זה באמת המיון הטוב ביותר עבור המקרה הסביר, לא בכדי הוכנס לANSI C

 

[demultiplexer]

עוד שאלות

1. מה אתם מגדירים כמקרה סביר ? 2. אני מבין שבממוצע QSORT הוא המיון מבוסס השוואות המהיר ביותר ? 3. מה לגביי מיון מערכים דו מימדיים ?