רוטר - צריך טריק יותר אופטימלי מאשר Hash Map למיפוי כתובות

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"צריך טריק יותר אופטימלי מאשר Hash Map למיפוי כתובות"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10107	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10107

ldan192
חבר מתאריך 14.9.08
95119 הודעות

22:48 15.10.10

צריך טריק יותר אופטימלי מאשר Hash Map למיפוי כתובות

אני צריך שבהנתן פויינטר - להחזיר פויינטר אחר בצורה הכי מהירה שניתן (בתקווה שב-(O(1).
בהתחלה ניסיתי לצאת מהנחה כלשהי שההקצאות פחות או יותר רציפות בזכרון ו-7 הביטים הראשונים תמיד מתחילים מ-0 עקב צורת מימוש הקלאסים,
כלומר ביצעתי SR של 7 ביטים ואז את המספר הזה מודלו 5000 (או לאחר מכן 4999 לערבול יותר טוב) ואת זה הכנסתי לווקטור,
אבל עדיין עם טסט אינטנסיבי גיליתי שאחרי כמה זמן (סביב ה-200 כתובות) המערכת קפצה להקצות טווח כתובות שונה לגמרי שגרר להתנגשויות.
חשבתי להשתמש ב-Dense Google Hash Map שנחשב יותר ביצועיסטי במהירות ופחות בזכרון, אבל לשימושים שלי כרגע נראה שהוא פחות מתאים כי הוא יותר מדיי אבסטרקטי והפונקציונליות רק מכבידה עליו.

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

כל רעיון יתקבל בברכה

בברכה,
עידן

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אממ	ג'וני הקטן	16.10.10 10:25	1
למרות שזה רעיון באמת נחמד להשתמש במבנה נתונים	ldan192	16.10.10 10:52	2

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות, דרג אמינות חבר זה

10:25 16.10.10

1. אממ
בתגובה להודעה מספר 0

תעשה בערך כמו שהזכרון במחשב עובד...
אני בטוח שאתה יודע
תיצור קאש באמת בגודל שאתה מחליט... (תעשה את זה 1 WAY או 2 WAY או N WAY... מה שאתה מחליט לפי מה שאתה רואה שיותר מתאים לך) בגודל מסויים
שהמקום בו זה לפי הX ספרות האחרונות בכתובת... כל רשומה תיהיה מן הסתם STRUCT (שכמו שאמרתי המערך יהיה לפי הX ספרות האחרונות בכתובת) שיכיל את הספרות הראשונות בכתובת את הDATA...
לגשת לשם יעלה לך O(1) אז לבדוק אם זה מתאים עדיין O(1) ואם כן אז איזה יופי אם לא אז תחפש אחרי זה בHASH..

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

10:52 16.10.10

2. למרות שזה רעיון באמת נחמד להשתמש במבנה נתונים
בתגובה להודעה מספר 1

של קאש של מעבד - עדיין מדובר בגישות שהן לא ב-(O(1 (כי יש קונפליקטים).
ובנוסף, אני חושב שצריך לתחזק מבנה נתונים דיי עצבני, וברגע שיש בעיית Capacitance/Conflict אז צריך למחוק חלק מהכתובות שברשימה שבשבילי זה דבר שלא יסולח מבחינת ביצועים (לצורך העניין הבאת 100M כתובות בהאש טייבל רגיל הוא 2.5 שניות, כאשר 100M דרך גישה למבנה נתונים רציף מיוחד שטוען מהדיסק - 8.5 שניות).
מאותה סיבה גם מה שקורה במערכות הפעלה לא הכי מתאים לי (כששם פשוט הדפדוף נעשה לדיסק מלת ברירה כפתרון טרוויאלי, אבל אני יוצא מהנחה שהזכרון שלי אינסופי).
מה שאני מחפש זה איכשהו למפות מספר חסום של כתובות במערך (וקטור).
השאלה היא אם תתכן איזושהי פונקציית ערבול שבאמת יכולה להבטיח לי דבר כזה?

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד