בתשובה לערן בילינסקי, 17/10/04 13:16
 |
|
 |
||
|
||||
 |
אם כבר גיקים אז עד הסוף: איך האתר עושה את זה? הוא מייצר אקראית כתובת אוטומטית בכל פעם שמכניסים לו כתובת (בלי חשיבות למה הכתובת, אלא רק לזמן שבו הכניסו אותה), או שהוא מפעיל פונקציה כלשהי (גיבוב?) על הכתובת שהכניסו לו כדי שתהפוך את הכתובת הארוכה לקצרה? אם זו האפשרות השנייה, זה מעניין מאוד. |  |
 |
 |
|
|
|
||
|
||||
|
לא יודע. <אזהרת גיקים> אני יכול לראות יתרון לפונקציית ערבול (זמן שליפה). עם זאת, אם מאחסנים את מחרוזת המפתח ב-Trie אפשר להגיע לזמן חיפוש קבוע לכל צורך מעשי, לדעתי. </אזהרת גיקים> |
|
|
|
|
|
|
||
|
||||
|
<למה סגרת את אזהרת הגיקים?> (ולפני שכותבים <אזהרת גיקים>, לא צריך <אזהרת גיקים>?) למה Trie כשאפשר hash? אתה לא צריך להדפיס רשימה אלפביתית שלהם, אני מניח. |
|
|
|
|
|
|
||
|
||||
|
העדפתי Trie כי לא היה לי רעיון לפונקציית ערבול עבור URL, אז אני יכול ליצר מפתח (פשוט את הבא בתור ב-Trie) ולהשתמש בו. זה פחות טוב מבחינת ביצועים? | |
|
|
|
|
|
||
|
||||
|
על קצה המזלג, מה זה Trie? | |
|
|
|
|
|
||
|
||||
|
(תנאי מוקדם כדי להבין הסבר זה יש להכיר את המושגים "מצביע" ו"מערך" בתכנות) Trie הוא מבנה נתונים שבנוי כך: הצומת הראשון מצביע אל מערך שמכיל את כל אותיות האלפבית של המפתח של המידע. כל איבר במערך, בנוסף לכך שהוא מכיל אות כלשהי (נסמנה a), מכיל גם מצביע למערך נוסף בעל אותו מבנה (שמאותחל ל-null - "כלום"), ומצביע לערך (Value), שמאותחל גם הוא ל-null. המצביע למערך הנוסף אכן מצביע למערך שכזה רק אם הוכנס ערך שהמפתח שלו, במקום המתאים, כולל את האות המתאימה (a). כלומר, עבור הכנסת המפתחות abc, abd ו-abdd נקבל את המבנה הבא: מצביע לתחילת המבנה - המערך (נסמנו 1). מערך (1) שמכיל את כל אותיות האלפבית. בתא של האות a המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 2), כל שאר המצביעים במערך זה הם null. מערך (2) שמכיל את כל אותיות האלפבית. בתא של האות b המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 3), כל שאר המצביעים במערך זה הם null. מערך (3) שמכיל את כל אותיות האלפבית. בתא של האות c המצביע אל *ערך* אינו ריק אלא מצביע אל הערך המתאים למפתח abc. בתא של האות d המצביע אל ערך גם אינו ריק אלא מצביע אל הערך המתאים למפתח abd. כמו כן, בתא זה גם המצביע למערך נוסף אינו null אלא מצביע למערך (נסמנו 4), כל שאר המצביעים במערך זה הם null. מערך (4) שמכיל את כל אותיות האלפבית. בתא של האות d המצביע אל הערך אינו ריק אלא מצביע אל הערך המתאים למפתח abdd. כל שאר המצביעים במערך זה הם null. כדי לבדוק אם מפתח נמצא במבנה אתה מטייל לפי אותיות המפתח לעומק (ממערך (1) והלאה), ואם הגעת למצב שאינך יכול להתקדם (כי המצביע למערך הבא הוא null), או שהגעת ליעדך ואין שם מצביע לערך, אזי אין ערך שמתאים למפתח הנ"ל במבנה. מאד נוח להחזיק בצורה כזו מילון של ערכים, כי כפי שציין ירדן, קל מאד להדפיס אותם לפי סדר אלפביתי - ערוך טיול DFS על המבנה והדפס כל צומת שנכנסת אליו לראשונה ושהמצביע לערך שלו אינו null. |
|
|
|
|
|
|
||
|
||||
|
מה רע בפונקציית הערבול הסטנדרטית למחרוזות (למשל זו של ג'אווה)? hash אמור להיות קצת יותר מהיר מ-trie, ובמחשבה חפוזה נראה לי שצורך פחות תקורה של זכרון. פרקטית, שיקול חביב הוא שהרבה שפות או סביבות של תכנות נותנות לך hash מן המוכן, ואילו trie קצת יותר נדיר. אבל רגע, אם אני זוכר נכון לקח מאיזשהו קורס, מה שנכון למבני נתונים בזכרון גישה אקראית, לא בהכרח נכון לנתונים בדיסק - שם יש שיקולים של גישות סמוכות וכאלו, מה שעשוי להיות רלוונטי לאתר מבוקש כמו tinyurl. |
|
|
|
|
|
|
||
|
||||
|
נזכרתי למה Trie. כי המפתח שאני רוצה לייצר צריך להיות גם קריא לדפדפנים (שכן זו הרי הבעיה שרצינו לפתור - קישורים ש"נשברים"). Trie, עם האלפבית המוגבל שלו, מתאים למשימה - אני מגדיר מהו האלפבית, ואני אגדיר כזה שמכיל רק אותיות מתאימות. עם זאת, ברור שאפשר בקלות להגדיר פונקציה חד-חד ערכית פשוטה גם על התוצאה של פונקציית הערבול הסטנדרטית שהטווח שלה הוא מילים מהאלפבית המוגבל הנ"ל. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |