שלום,

אני בונה טבלת HASH שצריך לבצע עליה הרבה מניפולציות מתמטיות, וסטטיסטיות המפתח לטבלה אמור להיות מספר LONG לצרוך

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

יש לי 2 דרישות מהפונקציית מיפוי שלי:

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

2. המפתחות שומרים על יחס סדר חזק בין האיברים. כלומר אם אני מכניס 8 100,000 פעם נגיד ואחרי זה 9 אז

המפתח של 9 יהיה יותר גדול מכל אחד מהמפתחות ש 8 קיבל. (לצורך העניין היות ומדובר במשהו אפליקטיבי

נניח שיותר מ 100K פעם אני לא אכניס אותו איבר ל HASH)

אשמח בעזרה של יצירת פונקציית מיפוי כזאת ב C++... את האמת השפה כלל לא משנה אבל הגיונית אשמח לעצה

איך לבנות את המיפוי הנ"ל...

מה שאתה אומר, זה בעצם אתה מכניס איבר שהוא זוג {מספר, סדר}?

מה הטווח של המספרים, ועל כמה איברים אתה מדבר?

חוץ מזה, hash לא נועד להשוואת מפתחות לפי סדר. יעזור אם תפרט קצת יותר מה אתה מנסה לעשות.

אני מכניס ל HASH רק מספרים אני צריך שפונקציית המיפוי בין מספרים למפתחות שלהם תייצר מפתחות כפי שתיארתי למעלה.

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

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

בצד ושם למיין את הדברים...

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

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

אני מכניס ל HASH רק מספרים אני צריך שפונקציית המיפוי בין מספרים למפתחות שלהם תייצר מפתחות כפי שתיארתי למעלה.

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

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

בצד ושם למיין את הדברים...

אז מה שאתה מתאר זה ממש לא hash-map.

ב- hash אתה ממפה מרחב אחד לתוך מרחב אחר שהוא יותר קטן.

לכן, ב- hash-map המפתחות הם ממש לא ייחודיים, לא מוגדר עליהם סדר, וגם ברוב המקרים אין לך גישה אקראית.

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

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

נראה לי ש-multimap או hash_multimap יתאימו הרבה יותר טוב למטרה הזו (ואז לא צריך לחשוב על פונקציית hash)‏

http://www.sgi.com/tech/stl/hash_multimap.html

http://www.sgi.com/tech/stl/Multimap.html

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

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

אני מעדיף לא להחזיק כמה מבני נתונים בשביל לחסוך זכרון.... (גם אם אני מחזיק מבנים של מצביעים)[br]פורסם בתאריך: 21.04.2007 בשעה 10:37:47

---

נראה לי ש-multimap או hash_multimap יתאימו הרבה יותר טוב למטרה הזו (ואז לא צריך לחשוב על פונקציית hash)‏

http://www.sgi.com/tech/stl/hash_multimap.html

http://www.sgi.com/tech/stl/Multimap.html

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

ב-multimap (וב-hash_multimap) ניתן לקשר בין מפתח בודד למספר איברים. נראה לי שזה בדיוק מה שאתה מחפש.

ב-multimap (וב-hash_multimap) ניתן לקשר בין מפתח בודד למספר איברים. נראה לי שזה בדיוק מה שאתה מחפש.

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

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

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

וצרך לתמוך בכפילויות גם כן כלומר כל איבר יכול להופיע 10 פעמם למשל...

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

יש טיפוס נתונים מורכב לבעיות של שמירת סדר שמאפשר הכנסה והוצאה ב- O(1) amortized, והשוואת סדר ב- O(1) worst-case.

אני לא יודע אם זה רלוונטי לך (תצטרך לקרוא מאמר כדי לממש אותו כמו שצריך).

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

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

את המאיונים הסטטיסטיים של המספרים שהמבנה מחזיק.

הסידור של האיברים הוא על פי המפתחות. (מפתחות ומספרים זה הינו הך מבחינתי במידה ואני לא משתמש ב HASH...)

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

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

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

תודה! בסוף באמת מה שעשיתי זה לולאה עם כל הצער והיגון שבדבר נראה עד כמה זה יהיה מהיר או איטי עם הזמן

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