אלגוריתם למיון רשומות על פי "חשיבות": עזרה?

[Guy Yafe]

אלגוריתם למיון רשומות על פי "חשיבות": עזרה?

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

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

בכל שימוש הוסף 1 לרשומה
באופן מחזורי (למשל פעם ביום), כפול את כל הערכים של כל הרשומות במקדם התיישנות (למשל 0.9).
הערה: המספרים "1", "0.9" ו"פעם ביום" הם כמובן אמפיריים.

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

 

[BravoMan]

משהו כאן ממש לא מובן לי:

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

 

[Guy Yafe]

אסביר יותר בפירוט

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

 

[bismark1]

יש לך הגדרה ל"שימושים אחרונים" או שזה משתנה רציף?

 

[Guy Yafe]

פתוח להצעות

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

 

[bismark1]

תראה, הדבר הראשון שקפץ לי לראש

זה נוסחאות דעיכה של איזוטופים רדיואקטיביים לפי זמן מחצית חיים או קבוע דעיכה.
עדיין תצטרך לקבוע את קבוע הדעיכה בצורה אמפירית בכדי לקבל תוצאות הגיוניות אבל זה כבר נגזר מאופי השימוש במערכת ומה הגדלים האופייניים של שימוש רב ברשומה ספציפית (10, 1000, 1M?. )

 

[Guy Yafe]

מכאן שאוב הרעיון שלי

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

 

[bismark1]

אתה צריך להזהר

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

בסוף זה תרגיל היוריסטי - יש לך מספיק סטטיסטיקה של שימוש אמיתי במערכת בשביל להריץ סימולציות כדי לוודא שאתה מגיע לתוצאות סבירות?

 

[Guy Yafe]

אני לא דואג מבעיות נומריות

אם משקל של רשומות דועך לאפס, זה אומר שהחשיבות שלו כל כך נמוכה שלא אכפת לי אם היא תהיה לפני או אחרי רשומה אחרת עם משקל אפס.
אפשר כמובן להוסיף עוד משתנה שמתאר את הסכום של השימושים, אבל זה נראה לי מיותר.
&nbsp
אין לי סטטיסטיקה על השימוש בכל רשומה לכן קשה לי להניח מראש מה הפרמטרים המדוייקים, אבל אני כן יודע שיש שימוש בעשרים רשומות ביום, למשך שלושה ימים בשבוע למשך 10 שנים: סה"כ 31,200 שימושים. זה לא מספר שעלול להגיע ל - overflow.

 

[הפרבולה]

המספר המכסימלי שתגיע אליו הוא

הוא
M = X/(1-K)
M מדד החשיבות לרשומה שלפיו ממיינים את הרשומות.
X מספר השימושים ליום לרשומה.
K מקדם הדעיכה ( נגיד 0.9)

דוגמה: אם X=20 קבוע ( כל יום יש 20 שימושים לרשימה מסוימת ) ו K=0.9 אז נקבל במצב מתמיד ש M=200

צריך ש M יהיה משתנה מסוג float .

אגב :
אם K גדול שווה מ1 אז M לא יהיה חסום ( ישאף ל +אין סוף ) ,
אם K בין 0 ל 1- אז M יהיה עדין חסום אבל ההתכנסות תהיה תנודתית
אם K קטן מ 1- אז M לא יהיה חסום וישאף ל +- איןסוף

 

[Guy Yafe]

נשמע סביר

יוצא שבשימוש קבוע, המשקל נשאר קבוע.
בעיני זה הגיוני

 

[bismark1]

אם אתה מוותר על "הזכרון"

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

 

[Guy Yafe]

נכון

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

 

[BravoMan]

אתה מחפש אלגוריתם אופטימיזציה עבור 20 שליפות רשומה ביום????

מה זה מבחינתך "שליפת רשומה"? כמה זה עולה, ומה חשיבות מקומה ב-DB שצריך להריץ כל יום task של מיון מחדש של כל ה-DB?
&nbsp
אם המספרים שנתת בשורה האחרונה אמתיים, ואפילו אם הם יגדלו ב-3 סדרי גודל, עדיין נראה לי שאתה שובר את הראש על משהו מיותר שמסבך את הקוד שלך בצורה לא נחוצה.
&nbsp
תוסיף לזה את העובדה שאתה הולך נגד רצון הלקוח מאחורי גבו, ולמרות שאין זה כלל מקומי לדבר על כך, ולא את זה שאלת, אני חש צורך להזהיר אותך שאתה מתקדם לכיוון ממש לא טוב מבחינתך...
&nbsp
אני לא יודע כמה עוד מידע אתה יכול לשתף פה, אבל אישית, לפי מה שכתבת עד עכשיו, נראה לי נכון במקום לחפש אלגוריתם למיון, לבדוק איפה צור הבקבוק האמתי שלך, האם אפשר לייעל את האחסון עצמו והגישה אליו, לצמצם כמות רשומות, לממש cache וכו'.
&nbsp
אבל בשביל לדעת היכן ניתן "לחתוך", צריך להבין יותר מה הן דרישות מהמערכת.
מה גורם לרשומה להתעדכן, מה גורם לשימוש בה ליפול או לעלות, וכו'.

 

[Guy Yafe]

זו לא אופטימיזציה

המטרה שלי היא לא לשפר ביצועים אלא לשפר UX.
המערכת מיועדת לרופא שבין השאר ממלא בה דו"ח סיכום ביקור של מטופל.
אחד השדות בדו"ח נקרא "דיון והמלצות".
הרופא משתמש באחת מתוך 60 תבניות מוכנות מראש: לחיצה על אחת התבניות מעתיקה אותה לאותו שדה, כדי שלא יצטרך להקליד בצורה ידנית.
דוגמה לתבניות "יש לקחת אקמול פעם ביום", "יש למרוח משחה שלוש פעמים ביום".
&nbsp
השאלה היא איך לסדר את התבניות כך שהשימושיות ביותר תהיינה ראשונות. אפשר אולי לקרוא לזה "אופטימיזציה של שימושים בגלגלת העכבר".
&nbsp
אם נניח שהרופא רואה עשרות בודדות של מטופלים ביום, כל ביקור נמשך כרבע שעה עד חצי שעה, ובסופו של דבר ישנה עבודה עם פחות משישים רשומות בבסיס הנתונים, הרי שכל העיבוד המתמטי הוא בחינם: חישוב משקלים, מיון רשומות, שליפות מבסיס הנתונים וכו', ואני יכול לסבך אותו כרצוני.
&nbsp
אז הפתרון שלי הוא להגדיר משקל לכל רשומה ולמיין לפי המשקלים האלה, ואני מנסה לחשוב מה הדרך הכי מוצלחת לחשב את המשקל הזה.
&nbsp
אגב, אני כמובן לא הולך נגד רצון הלקוח. הצעתי לו את זה והוא ביקש יותר הבהרות לפני שהוא מחליט.

 

[BravoMan]

אה, אם כך לא הבנתי נכון את הבעיה המקורית.

חשבתי שיש כאן ניסיון לשפר גישות ל-DB ושליפת מידע.
&nbsp
אם מדובר ב-UX, ועוד ספציפית UX של רופא, יש כנראה כל מיני דברים אחרים ומעניינים שהיו יכולים להשפיע על "סידור חכם" של רשומות.
&nbsp
באופן אישי, אם הייתי צריך לחשוב על דבר כזה הייתי עושה 2 דברים כדי ליצור UX טוב:
1. מסך או תפריט "מועדפים" נוח ונגיש בו המשתמש יוכל בעצמו למקם את הדברים שהם בשימוש הכי תדיר שלו.
2. שדה חיפוש "חי" כזה שמצמצם אפשרויות בזמן הקלדה, כך שמספיק 2 - 3 אותיות כדי שהרשומה הרצויה כבר תהיה בתוך 3-5 אופציות ראשונות (או אפילו יחידות).
&nbsp
יצא לך לראות איך עובד מסך היישומים בממשק Unity של Ubuntu או שורת הכתובת החכמה ב-Chrome \ FF?
&nbsp
משהו כזה.
משם כבר לא ממש צריך מתמטיקה עבור 60 רשומות.
&nbsp
אני כמובן לא רופא, אבל ייתכן שתדירות השימוש במה שתיארת כאן משתנה לפי עונות השנה.
למשל, בחורף מגיעים יותר חולים עם שפעת שצריכים אקמול, ובקיץ מגיעים אלרגיות שצריכות משהו אחר.
&nbsp
ייתכן גם, שיתר השדות מכילים מידע שמאפשר לצמצם את רשימת ההצעות, אבל אלה כבר שיקולים מורכבים וייתכן שעלות הפיתוח לא כדאית...

 

[Guy Yafe]

אני לא כל כך יכול לשחק עם השדות

כל השדות הם שדות נדרשים (מילוי בטופס), ולכן אין כאן כל כך עניין של מועדפים.
המועדפים היחידים הם התבניות אותן יש לתעדף בהתאם לשימוש. לרופא חשוב מאוד שסדר הרשימה הזו יהיה גם אוטומטי (כך שהרופא לא יצטרך להחליט בעצמו על תיעדופים) וגם דינמי (בהתאם לכמות השימושים). הרעיון שלו לספירת שימושים הוא יוריסטיקה סבירה אבל אני מחפש אחת יותר טובה כדי להציע לו.
על פי היוריסטיקה של הרופא, אנחנו באמת ניתקל בבעיה כמו בדוגמה שלך: מכיוון שרשומה מסויימת צברה תיעדוף משך עונה שלמה, יקח לרשומה אחרת שיותר מתאימה לעונה הבאה, משך זמן כל העונה עדי להגיע לראש הרשימה אבל אז היא כבר לא תהיה רלוונטית. למעשה הדוגמה שלך היא בדיוק הדוגמה שנתתי לו.
&nbsp
&nbsp
הרעיון שלך לשדה חיפוש "חי" הוא רעיון טוב ואני אכן משתמש בו. למזלי HTML List נותן את זה בחינם.

 

[אוהב להתווכח]

נראה לי שפילטרינג סוגר את הפינה

השיפור בסדר מותאם אישית ישפר קצת מאוד את החוויה.
אם אתה מתעקש אתה יכול לספור כמות שימושים עם משקל לפי זמן. כלומר לחודש האחרון יש משקל של 12, לחודש אחד קודם יש 11 וכן הלאה.
איך לעשות את זה?
נניח שיש לך טבלה של שימושים בתוויות מסוימות עם תאריך שימוש.
zz moths(now-date) zz מסל את ההפרש בין התאריך הנוכחי לתאריך של השימוש. בכל מסד נתונים עושים את זה אחרת אז השארתי את זה לך.

select label
from(
    select label,12-months(now-date) w
    from table
    where date > now-1 year
)a
group by label
order by sum(w) desc

 

[Javali]

זה הפתרון הסטנדרטי

חפש דעיכה אקספוננציאלית (exponential decay) לפרטים נוספים.
&nbsp
בגדול, כמו שכבר נאמר כאן, אם השימוש קבוע, אתה תקבל מספר קבוע. אבל זמן ההתכנסות למספר הזה והרגישות לשינויים בקצב תלויים בגודל המקדם שאתה בוחר. בבחירה של 0.9 ביום אתה מקבל שינויים מאוד מהירים - זמן מחצית החיים של מידע הוא כשבעה ימים, מה שאומר שאם יש שינוי בשימוש, תוך שבועיים שלושה אתה תהיה מכוייל עליו. מצד שני, אם קצב השימוש קבוע בממוצע אבל נתון לשינויים במהלך השבוע אתה תגיב יותר מדי לרעשים.
&nbsp
בשביל לחסוך את הצורך בעבודה עם floats, אתה יכול לעבוד עם נקודה קבועה - פשוט תוסיף למונה 1000 (או 100 או 1000000 תלוי במה אתה צריך) בכל שימוש. אתה רק צריך לדאוג שלא תעבור את גודל המשתנה. אם ידוע חסם למספר השימושים היומי אפשר לחשב בקלות את המקסימום שהמונה יכול להגיע אליו.