אני מחפש מבנה נתונים ב-++C שיאפשר לי לאכסן אובייקטים המכילים ID ייחודי ועדיפות (priority).

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

מה הכוונה ב"מסודרים"? אתה רוצה להיות מסוגל לעבור על האיברים במבנה לפי סדר העדיפות, וגם להכניס, לחפש ולהוציא אובייקטים ב-(O(1?

הכוונה במסודרים היא FIFO.

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

אז אתה בעצם רוצה לשלב בין hash map ו-priority queue.

ה-hash map יאפשר לך לבדוק אם איבר נמצא בזמן קבוע, וה-priority queue יאפשר לך כל פעם להוציא את האיבר הבא מהתור, לפי העדיפות. כשאתה מכניס או מוציא איבר צריך להכניס או להוציא אותו משני המבנים.

בתקן האחרון של ++C יש גרסה של hash map שנקראת unordered_map, וגם priority_queue. תלמד קצת איך הם עובדים ואיך להשתמש בהם...

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

אתה אומר להשתמש בשני קונטיינרים במקביל?

אני לא רואה סיבה שלא. אחד יזהה איברים לפי ה-ID, השני לפי העדיפות.

לא חשבתי על להשתמש בשני קונטיינרים במקביל... תודה!

עריכה: השאלה איך אני מבדיל בין שני איברים בעלי אותה עדיפות

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

"אני מניח" לא מספיק... איך אני יכול לבדוק את זה?

שאלה נוספת: אם אני מוחק איבר מהמפה, איך אני מוחק אותו גם מהתור?

"אני מניח" לא מספיק... איך אני יכול לבדוק את זה?

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

שאלה נוספת: אם אני מוחק איבר מהמפה, איך אני מוחק אותו גם מהתור?

זו כרגע הבעיה היחידה - priority_queue לא מאפשר מחיקת איברים מאמצע הרשימה. לפי אחד התיעודים שמצאתי, יש לו שדה פנימי (protected) בשם C שמייצג את מבנה הנתונים הפנימי שמכיל את האיברים, ככה שאולי אפשר דרך השדה הזה למחוק את האיבר, עם קצת מאמץ.

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

השאלה היא, כאמור, כמה אתה מוכן להשקיע, וכמה חשובה הסיבוכיות.

אני אוותר על זה. חשבתי לממש pair ולהוסיף לכל איבל מעין time stamp ככה שיהיה לי עוד מקור להשוואה.

לפי התאור של הבעיה בעיקר עם המפתח הוא priority עדיף להשתמש ב hash table עם dynamic arrays . אפשר להשתמש בlink list אם לא אכפת לך מחיפוש סיבוכיות N ו cache thrashing .

זה מאוד תלוי מה אתה רוצה לעשות אם אתה רק מעוניין למצוא את הראשון link list יהיה קל למימוש . בrandom access הבאופציה של המערכים הדינאמים תצתרך להשתמש ב queue קלאסי כדי שתוכל להוריד את הראשון כל פעם ויהיה לך קל להכניס את הבא.

אם לא ניגשים למבנה הנתונים הרבה לא צריך לדאוג לthrashing כי גם ככהה המידע לא יהיה בcache.

אפשר לנצל טוב את הcache עם שומרים רק אינדקסים לבלוקים של המידע זה אותו דבר כמו לשמור pointers אבל כדי לשמור על cache performance רצוי שהם יהיו קרובים אחד לשני בזיכרון. context switch גם יכול לדפוק cache performance ואני מדבר מניסיון.

אני בדיוק עובד על משהו כדי לשפר ביצועים אבל אני עדיין לא במצב סופר אופטימאלי לאפליקציה אבל אני יודע איך לעשות את זה. בנתיים אני רץ בbest case קרוב לפי 4 יותר מהר .אפשר עדיין לשפר את זה עם כל מני טריקים של data structures .

סיבוכיות של n לא טובה לי.

אני אשתמש ב-set ו-map לצורך החזקת האיברים. אחד יסודר עפ"י ID ואחד על פי PRIORITY.

אני אשתמש ב-PAIR בשביל להחזיק את האיבר עצמו + TIME STAMP

הפתרון הכי יעיל שהצלחתי לחשוב עליו עד כה (מבחינת סיבוכיות):

class TheClass {
 int id;
 int priority;
};
map<int, list<TheClass*>> queue;
hash_map<int, pair<list<TheClass*>*, list<TheClass*>::iterator>> idToObjMap;

נניח ש-TheClass היא המחלקה שלך (ויש בה עוד שדות שלא רלוונטיים כאן).

queue ממפה כל priority לרשימה מקושרת של אובייקטים שיש להם את העדיפות הזו. כיוון שזה map, הוא ממויין לפי ה-priority.

idToObjMap ממפה כל id לזוג: הרשימה המקושרת (זו שב-queue) שבה נמצא האובייקט, וה-iterator המצביע לאובייקט הזה ברשימה.

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

בעת מחיקת אובייקט, מוצאים את הרשימה שבה הוא נמצא ואת האיטרטור באמצעות idToObjMap, ואז מוחקים אותו מהרשימה. אם לאחר מכן הרשימה ריקה, מוחקים אותה גם מ-queue.

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

סיבוכיות: (O(logk, כאשר k הוא מספר העדיפויות השונות (או ליתר דיוק - (O(1 כאשר מוסיפים או מורידים אובייקט שיש אובייקטים אחרים עם אותה עדיפות, ו-(O(logk אם אין). אני מניח שאפשר לייעל את זה אם מחליפים את ה-queue בערימה (heap), אבל אני לא חושב שיש מימוש של heap שיתאים לנו כאן.

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

עריכה: הבנתי מה אתה אומר. מה קורה בעת עדכון האובייקט (שינוי priority)?