לפני כמה פוסטים שאלתי את השאלה הבאה:
נתון מערך בגודל NxN של פיקסלים כאשר כל הפיקסלים שחורים חוץ מאחוז מסויים מהם שאינו שחור ומפוזר באופן אקראי,
בהינתן קואורדינטה (x,y) מסויימת בתמונה, מצא במהירות את כל הנקודות שנמצאות בתוך חלון בגודל K על K (כאשר K קבוע בבעיה) שמרכזו (x,y), משהו כזה:
פעולת המציאה עצמה צריכה להיות מהירה מאוד, אבל מותר לעבד מראש את התמונה פעם אחת (בזמן סביר).
אז הנה הפתרון שלי:
נחלק את התמונה למשבצות בגודל KxK, ונשמור רשימה של כל הנקודות בכל משבצת.
כאשר מבקשים מאיתנו לתת את רשימת הנקודות בחלון מסויים, נסתכל בארבעת החלונות שהחלון הזה חותך ונסנן את כל הנקודות בארבעת החלונות שלא נמצאות בתוך החלון המבוקש.
זה הכל בעצם.
הביצועים של הפתרון הזה מעולים, כדי להכין את הגריד (Grid) נעבור על כל הפיקסלים בתמונה, ולכל נקודה נמצא בזמן קבוע את המשבצת שאליה היא שייכת.
כשממש מחפשים את הנקודות בחלון מסויים, נבדוק במקרה הגרוע 2K*2K פיקסלים (אם כל הנקודות לבנות) אבל במקרה הרגיל נבדוק הרבה פחות (ואם החלון לא מכיל נקודות כלל נדע את זה מהר מאוד).
זה הקוד של העיבוד המקדים:
{
int grid[][][] = new int[width / gridSize][height / gridSize][];
// count the number of points in each grid cell
int numpoints[][] = new int[width / gridSize][height / gridSize];
for(int x=0;x<width;x++)
{
for(int y=0;y<height;y++)
{
if (image[x][y] > Byte.MIN_VALUE)
{
numpoints[x/gridSize][y/gridSize]++;
}
}
}
for(int x=0;x<width;x++)
{
for(int y=0;y<height;y++)
{
int c = image[x][y];
if (c > Byte.MIN_VALUE)
{
int gy = y/gridSize;
int gx = x/gridSize;
int list[] = grid[gx][gy];
if (list == null)
{
int np = numpoints[gx][gy];
list = new int[np * 2];
grid[gx][gy] = list;
numpoints[gx][gy] = 0;
}
list[numpoints[gx][gy]++] = x;
list[numpoints[gx][gy]++] = y;
}
}
}
return grid;
}
הקוד הבא סופר את המספר הנקודות בתוך החלון שמרכזו (x,y)’ שימו לב שהלולאות עוברות על ארבעה ריבועים בגריד בלבד:
int rx1 = x – grid_size/2;
int ry1 = y – grid_size/2;
int rx2 = rx1 + grid_size;
int ry2 = ry1 + grid_size;
// top left grid cell (out of 2×2 group to be checked)
int gx = rx1 / grid_size;
int gy = ry1 / grid_size;
for(int grid_x=gx;grid_x<gx+2 && grid_x >= 0 && grid_x < gwidth;grid_x++)
{
for(int grid_y=gy;grid_y<gy+2 && grid_y >= 0 && grid_y < gheight;grid_y++)
{
int list[] = grid[grid_x][grid_y];
if (list == null) continue;
for(int i=0;i<list.length/2;i++)
{
int jj = i*2;
int dx = list[jj];
int dy = list[jj+1];
if (dx >= rx1 && dx < rx2 && dy >= ry1 && dy < ry2)
{
c++;
}
}
}
}
יתכן שאפשר לשפר את הביצועים אם נחלק את הגריד לריבועים יותר קטנים ונכלול ריבועים שלמים שנופלים בתוך החלון בלי לבדוק כל נקודה באופן פרטני, אבל לא ניסיתי.
הביצועים של הפתרון הזה די מטורפים. על Q6600 במהירות 2.4GHZ, עם תמונה בגודל 500X500 פיקסלים וחלון של 20X20, בדיקה של כמה זמן לוקח לספור את הפיקסלים בכל 250,000 החלונות האפשריים לקחה כ160 מילישניות, מה שנותן מהירות בדיקה של מעל 1500 חלונות במילישניה (או יותר ממליון וחצי חלונות בשניה), בלי תלות בגודל התמונה שנבדקת (על תמונה של 1000X1000 המהירות היתה דומה).
האפלט הבאה מדגימה את האלגוריתם. אפשר להוריד אותה מפה. הקוד כלול בתוך הJAR (אפשר לפתוח את הJAR עם תוכנה לפתיחת קבצי ZIP).
בנוסף, האפלט יכולה לרוץ כתוכנית רגילה : java -jar fast_window.jar
אפשר ללחוץ בתוך האפלט כדי לסמן את הנקודות בחלון.
רסיסים (RSS)
מריץ FireStats
February 20th, 2010 ב13:23
למה לעשות ככה:
נתונה לך נקודה x,y שהיא מרכז המשבצת
k גודל המשבצת
לרוץ מ(x-k/2) עד (x+k/2) ואותו דבר על הy
ולבדוק עבור כל נקודה אם היא לבנה
February 20th, 2010 ב23:29
אתה מוזמן לשנות את הקוד באפלט ולבדוק מה הביצועים שזה נותן.
להערכתי פי 10 יותר לאט.
February 21st, 2010 ב00:28
הפיתרון שאנון הציע הוא הפתרון המובן מאליו, שזמן הריצה שלו הוא או של N (תקן אותי אם אני טועה).
זה קפץ לי מייד לראש, אני מניח שלהרבה אנשים. את הפיתרון שלך לא קראתי ואני מעדיף לא לקרוא כדי שתהיה לי הזדמנות לחשוב לבד (כמו שאני מכיר את עצמי ההזדמנות תישאר (-: ).
אבל אולי כדאי לך לרשום מהו זמן הריצה של הפיתרון שלך *ללא* הסריקה הראשונית (שינתנת “חינם”)?
שים לב, אני מציע את זה בלי שקראתי את הפתרון אז אם זה מסובך לחשב אז אין צורך.
February 21st, 2010 ב01:09
תיקון: ואני מעדיף לא לקרוא –> ואני מעדיף לא לקרוא עכשיו.
February 21st, 2010 ב13:22
זמן הריצה של הפתרון של אנין הוא ריבוע גודל החלון (K^2).
זמן הריצה של הפתרון שלי הוא לינארי למספר הנקודות בארבע חלונות. אם נסתכל על זמני ריצה, הפתרונות דומים (ארבע זה קבוע, ובבעיה יש כעשרה אחוז של נקודות, שזה עוד קבוע).
אבל בפועל אנון עובר תמיד על K^2 פיקסלים, ואני עובר בממוצע על
2k*2k*0.1=4k^2*0.1 = 0.4k^2
מבחינה תאורטית אין הבדל כי K קבוע בשאלה, אבל מבחינה מעשית יש הבדל משמעותי בביצועים.
שווה לנסות את הפתרון הטריוויאלי שאנון הציע רק בשביל לבדוק מה הביצועים שלו בפועל.
עוד נקודה חשובה:
הגדרתי את השאלה כך שיש 10% נקודות שמפוזרות באופן אקראי. זה לא מדוייק ובבעיות “אמיתיות” הפיזור הוא לא אקראי. במקרה כזה יש יתרון משמעותי לפתרון שלי כי הוא מסוגל לומר כמעט מיד שאין שום נקודות בחלון מסויים (בלי לעבור על K^2 פיקסלים).
February 22nd, 2010 ב01:05
רק עכשיו קראתי והפנמתי את הפתרון שלך, נראה מעניין מאוד.
יש לי מחשבה. לא חשבתי על זה עד הסוף אז רק אזרוק את זה:
נניח שאתה שומר את כל הנקודות הלבנות בסדר ממויין. במקרה כזה עבור ריבוע נתון לא תוכל למצוא מייד את הנקודות בלי לבצע חיפוש?
אילו היית צריך למיין את הנקודות בסריקה הראשונית אז זמן הביצוע היה מיון של (NxN) נקודות. אני חושב שזה N^2 פעולות, שזה הרבה. אבל הנקודות הלבנות והלא לבנות כבר ממויינות, כך שאם אתה מעתיק את הנקודות הלבנות לרשימה היא כבר תהייה ממויינת, ולכן העלות היא רק NxN. במקרה כזה אם אתה מקבל ריבוע אתה רק צריך להגיע לקטע בין הנקודות שהריבוע מייצג, וזהו, יש לך את כל הנקודות הלבנות.
שוב, רק מחשבה.
February 22nd, 2010 ב01:06
תיקון: אני חושב שזה N^2 פעולות –> אני חושב שזה N^4 פעולות
February 22nd, 2010 ב17:03
יונתן,
למרבה הצער לא ניתן ליצור רשימה חד מימדית ממוינת בגודל N^2 איברים כך שהיא תכיל רצפים שמכילים ריבועים שלמים.
תנסה לחשוב על זה עד הסוף ותווכח בעצמך.
February 23rd, 2010 ב00:32
צודק לחלוטין, אני מבין למה.
[שוב, רק מחשבה, אני אין לי זמן/כוח להעמיק ואני לא בטוח בזה]
אבל אם כך אפשר לעשות ורסיה שונה: לשמור את הנקודות הלבנות במטריצה לפי הסדר ברשימה דו מימדית של N רשימות חד ממדיות (חלקן עשויות להיות ריקות). כל שורה קטנה או שווה ל- N. השינוי העיקרי יהיה שיהיה צורך לעשות K חיפושים בינאריים במקום אחד כמו שחשבתי בהתחלה כדי למצוא את הנקודה הלבנה הראשונה בכל שורה עבור כל שורה בריבוע שעבורו מחפשים. אני גם לא בטוח שאפשר למצוא את זה בחיפוש בינארי, וזה עניין עקרוני.
February 23rd, 2010 ב09:54
לא ברור לי איך המטריצה שאתה שומר בנויה.
April 16th, 2010 ב23:15
אווףף שכחתי לגמרי מזה.,
עמרי אני כבר לא זוכר במדויק מה היה הפיתרון שלי אבל אני זוכר שהוא היה פחות יעיל משלך (כאשר חשבתי עליו שוב).
בקיצור עבודה יפה
June 25th, 2010 ב02:46
סליחה שאני מצטרף לחגיגה באיחור, רק עכשיו גיליתי את החידה הזו!
הפתרון שלך נראה מרשים ויעיל. לא “עליתי” עליו בעצמי. כשניסיתי לחשוב איך אני הייתי פותר את זה, יצא לי משהו שדומה אולי למה שיונתן אורלב אמר:
1. אני יוצר Y רשימות מקושרות (דו-כיווניות) של ערכי X של הפיקסלים הלבנים (כל שורה בנפרד).
2. כשאני מקבל X ו-Y עבור הריבוע, אני מחשב את ה-Y ההתחלתי והסופי לבדיקה ע”י Y +/- חצי K ועובר רק על הרשימות הרלוונטיות:
2.1. בכל רשימה, מבצע חיפוש בינארי כדי לאתר פיקסל שנמצא בטווחי X של הריבוע.
2.1.1 אם יש כזה, הולך קדימה ואחורה ברשימה ומסמן את הפיקסלים עד שאני יוצא מגבולות X של הריבוע או מגיע לקצה הרשימה.
אני רק לא מצליח לראות, אינטואיטיבית, מה גוזל יותר זמן – החיפוש הבינארי הזה או הבדיקות שלך.
רעיון גוזל זכרון ומשפר מהירות יהיה להוסיף לכל צומת בכל רשימה מצביעים לפיקסל הלבן הקרוב ביותר לפני ואחרי בשורה שמעל… מסבך את הקוד אבל חוסך את החיפושים הבינאריים, פרט לראשון.
June 25th, 2010 ב11:34
היי עידו וברוך הבא
.
אתה בטח מתכוון לומר שתיצור מערכים כי קשה לחפש בינארית ברשימות (כי אין גישה אקראית אלא רק סדרתית).
הפתרון שהצעת נשמע לי פחות יעיל:
בתור התחלה הוא רגיש לגודל החלון, מה שאומר שהביצועים שלו ירדו עבור חלונות גדולים (לוגריתמית), בפתרון שלי הביצועים הם פונקציה של גודל החלון ולא גודל התמונה.
חוץ מזה הוא מעניין ושווה בדיקה, אתה מוזמן לממש ולראות איך הוא מתמודד מול הפתרון שלי
June 25th, 2010 ב12:44
אכן מערכים ולא רשימות, ואני מאשים בזה את השעה בה כתבתי
אני אכתוב משהו ואראה מה יוצא. אם זה יהיה פייט מעניין, יש לך התנגדות שאכתוב על כך בטור שלי בנענע10 תוך אזכור הפוסט שלך?
June 25th, 2010 ב15:42
הנה רעיון חדש בלי בעיית הביצועים של החיפוש הבינארי.
שוב, ניצור מערך (A) של מיקומי הפיקסלים הלבנים עבור כל שורה.
כעת, ניצור מערך נוסף (B) של “קווים אנכיים” במרווחים של K פיקסלים, שכל אחד מהם בעצמו הוא מערך של מיקומי Y, שכל אחד מהם מכיל הפניה לפיקסל הלבן הקרוב ביותר מימין ומשמאל ב-(A) עבור אותו Y. זה דורש יותר זמן וחישובים בעיבוד הראשוני, אבל להערכתי לא משהו מוגזם.
כשמקבלים קואורדינטות של ריבוע, מוצאים את הקו האנכי שחותך אותו (בהגדרה יהיה בדיוק אחד כזה), עוברים על ערכי Y המתאימים באותו קו, ומההפניות שבהם רצים קדימה ואחורה כדי לספור את הפיקסלים הלבנים עד שחורגים מגבולות X של הריבוע.
לא נשמע ממש ברור, אני יודע, מצד שני זה נראה מאד מבטיח. אנסה לתכנת את זה בקרוב ולהביא תוצאות.
June 26th, 2010 ב15:45
רעיון מעניין עם ביצועים דומים אינטואיטיבית לפתרון שלי.
.
תממש ונראה מה עדיף
וכמובן שאין לי שום התנגדות שתכתוב על זה בטור שלך, אני אשמח.