מחפש מבנה נתונים
נתונה רשימה של ערכים (סדר גודל של מאות אלפים) הערכים הם מסוג double אבל זה לא מאוד משנה. כל ערך ממופה על ידי מפתח שמורכב מארבעה עצמים:
המטרה היא שבהינתן מפתח שמורכב מארבעה עצמים, אוכל לשלוף את הערך המתאים בצורה מהירה. הפתרון הוא כמובן טבלת גיבוב שממפה מהמפתח לערך.
לאחר מכן קיבלתי הוראה לאפשר חיפוש עם מפתחות שמכילים * כלומר בהינתן המפתח K<A1, B1, C1, *> z (התעלמו מה-z) אמצא את כל הערכים שהמפתחות שלהם מורכבים מהעצמים A1, B1, C1 ומכל D אפשרי.
זו הייתה בקשה מהPL שהחשיבה שלו היא SQL-ית במקור.
ידוע לי שיש מעט מאוד אפשרויות לערכי A ו-B שונים, יש המון אפשרויות לערכי C ואילו ב99 אחוז מהמקרים ה-* יהיה על D בלבד.
פיתרון שחשבתי עליו הוא מיפוי כפול: קודם כל על ידי C ולאחר מכן על ידי כל המפתח. כך בהינתן מפתח אני אצמצם את האפשרויות בכל שאגש רק למפה שנמצאת בתא של C וממנה אבחר את כל העצמים עם A וB נתונים.
השאלה שלי היא האם יש פיתרון יותר יעיל מבחינת סיבוך?
אשמח לעצות,
גיא
נתונה רשימה של ערכים (סדר גודל של מאות אלפים) הערכים הם מסוג double אבל זה לא מאוד משנה. כל ערך ממופה על ידי מפתח שמורכב מארבעה עצמים:
Key<A, B, C, D> -> Value<Double>המטרה היא שבהינתן מפתח שמורכב מארבעה עצמים, אוכל לשלוף את הערך המתאים בצורה מהירה. הפתרון הוא כמובן טבלת גיבוב שממפה מהמפתח לערך.
לאחר מכן קיבלתי הוראה לאפשר חיפוש עם מפתחות שמכילים * כלומר בהינתן המפתח K<A1, B1, C1, *> z (התעלמו מה-z) אמצא את כל הערכים שהמפתחות שלהם מורכבים מהעצמים A1, B1, C1 ומכל D אפשרי.
זו הייתה בקשה מהPL שהחשיבה שלו היא SQL-ית במקור.
ידוע לי שיש מעט מאוד אפשרויות לערכי A ו-B שונים, יש המון אפשרויות לערכי C ואילו ב99 אחוז מהמקרים ה-* יהיה על D בלבד.
פיתרון שחשבתי עליו הוא מיפוי כפול: קודם כל על ידי C ולאחר מכן על ידי כל המפתח. כך בהינתן מפתח אני אצמצם את האפשרויות בכל שאגש רק למפה שנמצאת בתא של C וממנה אבחר את כל העצמים עם A וB נתונים.
השאלה שלי היא האם יש פיתרון יותר יעיל מבחינת סיבוך?
אשמח לעצות,
גיא
