פורסם 2007 באפריל 2018 שנים שלום,אני בונה טבלת HASH שצריך לבצע עליה הרבה מניפולציות מתמטיות, וסטטיסטיות המפתח לטבלה אמור להיות מספר LONG לצרוךהעניין (כל טיפוס נומרי אחר גם יתקבל כסביר אני מניח..)יש לי 2 דרישות מהפונקציית מיפוי שלי:1. הפונקצייה תלויה בזמן כלומר אם אני מכניס את המספר 8 ואח"כ עוד פעם את 8 אז הם יקבלו מפתחות שונים.2. המפתחות שומרים על יחס סדר חזק בין האיברים. כלומר אם אני מכניס 8 100,000 פעם נגיד ואחרי זה 9 אז המפתח של 9 יהיה יותר גדול מכל אחד מהמפתחות ש 8 קיבל. (לצורך העניין היות ומדובר במשהו אפליקטיבינניח שיותר מ 100K פעם אני לא אכניס אותו איבר ל HASH)אשמח בעזרה של יצירת פונקציית מיפוי כזאת ב C++... את האמת השפה כלל לא משנה אבל הגיונית אשמח לעצהאיך לבנות את המיפוי הנ"ל...
פורסם 2007 באפריל 2018 שנים מה שאתה אומר, זה בעצם אתה מכניס איבר שהוא זוג {מספר, סדר}?מה הטווח של המספרים, ועל כמה איברים אתה מדבר?חוץ מזה, hash לא נועד להשוואת מפתחות לפי סדר. יעזור אם תפרט קצת יותר מה אתה מנסה לעשות.
פורסם 2007 באפריל 2018 שנים מחבר אני מכניס ל HASH רק מספרים אני צריך שפונקציית המיפוי בין מספרים למפתחות שלהם תייצר מפתחות כפי שתיארתי למעלה.אני צריך משהו שיחזיק מידע שניתן לגשת אליו בצורה אקראית וגם לערוך עליו חישובים סטטיסטיים - למשל למצוע חציון וכו'... לצורךחישוב ייעל של חציון אני מחזיק את הדברים ב HASH_MAP ככה שהמפתחות יהיו ממויינים וזה מונע צורך להחזיק עוד וקטור נגידבצד ושם למיין את הדברים...
פורסם 2007 באפריל 2018 שנים אז למה שלא תייצר כמה מבנים שינהלו את אותו מידע, וכל אחד יהיה אחראי לענות בצורה טובה יותר על חלק מהדרישות (למשל גישה רנדומלית וסידור בין האוביקטים וכו') ?למצוא חציון, אפשר גם לנסול אולי לתחזק איזה מבנה שימצא את החציון בין כל האיברים שנמצאים כעת במערכת ואז בכל הוספה / הורדה לנסות לתחזק משהו פשוט יותר.
פורסם 2007 באפריל 2018 שנים אני מכניס ל HASH רק מספרים אני צריך שפונקציית המיפוי בין מספרים למפתחות שלהם תייצר מפתחות כפי שתיארתי למעלה.אני צריך משהו שיחזיק מידע שניתן לגשת אליו בצורה אקראית וגם לערוך עליו חישובים סטטיסטיים - למשל למצוע חציון וכו'... לצורךחישוב ייעל של חציון אני מחזיק את הדברים ב HASH_MAP ככה שהמפתחות יהיו ממויינים וזה מונע צורך להחזיק עוד וקטור נגידבצד ושם למיין את הדברים...אז מה שאתה מתאר זה ממש לא hash-map.ב- hash אתה ממפה מרחב אחד לתוך מרחב אחר שהוא יותר קטן.לכן, ב- hash-map המפתחות הם ממש לא ייחודיים, לא מוגדר עליהם סדר, וגם ברוב המקרים אין לך גישה אקראית.למה שלא תחזיק מבנה נתונים מסודר לפי הערכים, ובכל איבר תחזיק את הערך ומספר הפעמים שהוא חזר?יש לך צורך לבצע פעולות שקשורות בסדר ההכנסה? אם כן - מה למשל?
פורסם 2007 באפריל 2018 שנים נראה לי ש-multimap או hash_multimap יתאימו הרבה יותר טוב למטרה הזו (ואז לא צריך לחשוב על פונקציית hash)http://www.sgi.com/tech/stl/hash_multimap.htmlhttp://www.sgi.com/tech/stl/Multimap.html
פורסם 2007 באפריל 2118 שנים מחבר אז למה שלא תייצר כמה מבנים שינהלו את אותו מידע, וכל אחד יהיה אחראי לענות בצורה טובה יותר על חלק מהדרישות (למשל גישה רנדומלית וסידור בין האוביקטים וכו') ?למצוא חציון, אפשר גם לנסול אולי לתחזק איזה מבנה שימצא את החציון בין כל האיברים שנמצאים כעת במערכת ואז בכל הוספה / הורדה לנסות לתחזק משהו פשוט יותר.אני מעדיף לא להחזיק כמה מבני נתונים בשביל לחסוך זכרון.... (גם אם אני מחזיק מבנים של מצביעים)[br]פורסם בתאריך: 21.04.2007 בשעה 10:37:47נראה לי ש-multimap או hash_multimap יתאימו הרבה יותר טוב למטרה הזו (ואז לא צריך לחשוב על פונקציית hash)http://www.sgi.com/tech/stl/hash_multimap.htmlhttp://www.sgi.com/tech/stl/Multimap.htmlלא הבנתי איך הן עוזרות לי? אצלן פשוט יש קשר בין מפתח לאיבר.... עדיין צריך לייצר את המפתח איכשהו לא?
פורסם 2007 באפריל 2118 שנים ב-multimap (וב-hash_multimap) ניתן לקשר בין מפתח בודד למספר איברים. נראה לי שזה בדיוק מה שאתה מחפש.
פורסם 2007 באפריל 2118 שנים מחבר ב-multimap (וב-hash_multimap) ניתן לקשר בין מפתח בודד למספר איברים. נראה לי שזה בדיוק מה שאתה מחפש.זהו הבעיה היא שאני מחפש בדיוק את ההפך לקשר בין אותו איבר למפתחות שונים - אחרי שחשבתי על זה קצת זה נשמע די טיפשי סה"כ...לכן אני גם אסתפק במבנה נתונים כלשהו שמחזיק את המידע בפנים ממויין ונותן הכנסה בזמן קבוע לא תלוי בגודלו... יש הצעות למשהו כזה?אני אוכל לוותר על גישה אקראית בתנאי שההכנסה היא בזמן קבוע ואפשר לעבור על המבנה בצורה סדורה.. (יהיה נחמד אם יש הוצעה בזמן קבוע אבל גם אם לא..)וצרך לתמוך בכפילויות גם כן כלומר כל איבר יכול להופיע 10 פעמם למשל...
פורסם 2007 באפריל 2118 שנים לא הסברת בדיוק ממוין על מה לעבור סדור על מה. אתה מכניס כל הזמן דברים ומוציא בזמן פעולת התוכנית ?
פורסם 2007 באפריל 2118 שנים יש טיפוס נתונים מורכב לבעיות של שמירת סדר שמאפשר הכנסה והוצאה ב- O(1) amortized, והשוואת סדר ב- O(1) worst-case.אני לא יודע אם זה רלוונטי לך (תצטרך לקרוא מאמר כדי לממש אותו כמו שצריך).
פורסם 2007 באפריל 2118 שנים מחבר לא הסברת בדיוק ממוין על מה לעבור סדור על מה. אתה מכניס כל הזמן דברים ומוציא בזמן פעולת התוכנית ?במהלך התוכנית אני מוציא ומכניס דברים למבנה נתונים לא מובטח לי שההכנה היא לאו דווקא לסוף או להתחלה וכל הזמן אני צריך לדעתאת המאיונים הסטטיסטיים של המספרים שהמבנה מחזיק. הסידור של האיברים הוא על פי המפתחות. (מפתחות ומספרים זה הינו הך מבחינתי במידה ואני לא משתמש ב HASH...)ראיתי שיש טיפוס נתונים מתוחכם שדי עושה דברים כאךה HASH_MULTIMAP אבל הוא לא מאפשר גישה סבירה לנתונים...כלומר אני יכול לעבור על האיברים שם לפי הסדר אבל לא יכול לגשת לאיבר ה 8 לפי הסדר ישר.. אלא צריך בלולאה...
פורסם 2007 באפריל 2118 שנים לא נראה לי שתהיה לך דרך אחרת ממימוש לולאה בסוף (מכיוון שאתה מכניס / מוציא דברים, אלא אם מראש תגדיר איזה חסם על כל דלי, ואז אולי אפשר לנסות לעשות מימוש של מערך סטטי ולגשת לאיבר ספציפי בו).
פורסם 2007 באפריל 2218 שנים מחבר תודה! בסוף באמת מה שעשיתי זה לולאה עם כל הצער והיגון שבדבר נראה עד כמה זה יהיה מהיר או איטי עם הזמןמקסימום נוסיף אופטימיזציות שונות בהמשך בהנתן שבצורה יעילה זה לא פתיר כנראה...
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.