בתשובה לאביב י., 29/05/04 11:06
 |
|
 |
||
|
||||
 |
איפה יש זכרון של יותר מ־10^12 רשומות? באופן כללי, כאשר אתה עובר את 10^6 אתה מתחיל להתקל במגבלות גודל הזכרון. ר' גם http://www.schneier.com/crypto-gram-0203.html#6 |
 |
 |
 |
|
|
|
||
|
||||
|
הזיכרון מוגבל ל 57M ? ומה הקשר לזיכרון ? מה עם אלגוריתם של חיפוש רשומה בבסיס נתונים ? בסיס נתונים של עיריית ירושליים או תל-אביב יכול בקלות לעבור עשרות ג'יגה. ואז השאלה היא אם ייקח עשר דקות, חמש שעות, יומיים או חצי שנה להוציא דו"ח של כל התושבים בין גיל 30 ל 50 שיש להם פחות מארבעה ילדים, הכנסה ממוצעת של יותר מ8000 נטו וסך חובות לעירייה בארנונה ודו"חות חנייה שעולה על 10000 ש"ח. במצב הנ"ל מעבר לאיכות חומרה מסויימת הפרשים בזמן גישה לדיסק יהיו חסרי משמעות אם אלגוריתם החיפוש יהיה מספיק לא יעיל. |
|
|
|
|
|
|
||
|
||||
|
הכל טוב ויפה, אבל 12 בחזקת 10 זה 57G (ויכול להיות שהכוונה היתה בכלל 10 בחזקת 12 והעסק התהפך לו?). מה אנחנו מודדים בדיוק (בייטים? רשומות? ביסקוויטים?) גם לא ממש הבנתי. אגב, מה בא מהדיסק אל הזיכרון מתי וכמה, זה גם עניין לניתוח ולאלגוריתמים. גם פה הקבועים לא תמיד משחקים את התפקיד החשוב ביותר (מערכת הפעלה עם ניהול זיכרון וירטואלי או Process Scheduler לא יעיל, תהפוך את הכונן הקשיח, בעל זמן הגישה הקבוע המהיר ביותר, למטחנת בייטים רעשנית ואיטית למדי). עוד משהו שלא הבנתי זה *איפה* קיימת הגבלת הזיכרון לשיטתו. על מחשב ספציפי? על מערכת הפעלה ספציפית? זו לא דרך מחשבה שקצת מקובעת על מודל המחשב השולחני הבודד לשם פיתרון בעיות? _______ וכן! הצלחתי לשעמם את עצמי כבר באמצע התגובה. לחצתי על אשר רק כדי שלא אסבול לבד :) |
|
|
|
|
|
|
||
|
||||
|
כן, החזקות התהפעו להן. (לפי כיוון הטקסט דווקא כתוב שם 10 בחזקת 12, לא ברור לי למה הסימן "^" מתנהג שם כאילו הוא עברית. אתה צריך זכרון של המחשב הקוונטי. בשביל שאלגוריתם כזה יהיה מעשי אתה צריך קודם־כל לטחון את הדיסק כדי להביא את הנתונים הרלוונטיים לתוך הזכרון הקוונטי. (ואגב: הדיסק "טוחן" כאשר הקריאה אינה סדרתית בעיקרה. קריאת קובץ גדול תגרום בד"כ קריאה סדרתית שקטה יחסית) אם הרשומות הן בגודל בייטים, מה טוב. אם הרשומות גדולות הרבה יותר: הקבוע גדל בהתאם. כשהגדלים קטנים מספיק אז חישובים אסימפטוטיים אינם מועילים: הכל הוא O(1) |
|
|
|
|
|
|
||
|
||||
|
אני חושב שאתה מגזים (בכוונה?). מליוני רשומות (או יותר) זה בהחלט גדול מספיק בשביל שלחישובים אסימפטוטיים תהיה חשיבות מכרעת גם כאשר מעורבים קבועים ענקיים כמו C=10000(למשל, כבר בסביבות n=2^18 אלגוריתם ריבועי יתחיל לפגר אחרי ידידו שהוא NLOGN למרות היותו מוכפל בקבוע הענקי שדיברת עליו קודם C=10000). מבנה נתונים עם n=2^18 זה פיצ'פקס. להגיד שחישובים אסימפטוטיים אינם מועילים, זה כמו להגיד שחישוב ממוצע וסטיית תקן של ציוני הכיתה זה דבר שאיננו מועיל (מורים ומרצים, קחו לתשומת הלב!). מדובר במדדים שמספקים מידע לא שלם, בכך אין כל ספק, אבל הם בהחלט מדדים שאומרים *משהו* (חשוב). אתה מוזמן להתייחס אל הכל כאל קבוע, אבל אני לא חושב שתגיע עם זה רחוק במיוחד (מה עושים? כל פעם שיש רעיון לפתרון בעיה, מנחשים אלגוריתם באופן רנדומלי ורצים אל המחשב לתכנת ולמדוד אמפירית מה קורה בזמן ריצה?). לגבי החסם העליון של זיכרון, לא הבנתי בדיוק למה אתה מתכוון (אל חסם עליון במחשב ספציפי? אל חסם עליון במערכת מבוזרת? אל תיקרת הזכוכית?) ומה אתה בדיוק מכנה זיכרון (RAM? זיכרון וירטואלי? מדיה? זיכרונו של דובי קננגיסר בעל היכולות המפורסמות?). ברור שאם כל גישה להבאת נתונים תקח זמן קבוע של 20 שנה (או דקה וחצי) אז חישוב אסימפטוטי לא יעזור לנו יותר מדי באופן מעשי (אך מחקר תאורתי של אלגוריתמים המנותק ממגבלות טכניות הוא גם חשוב). אני לא טענתי משהו אחר. אני רק מתנגד פה לרעיון ה-"O no" ושקבועים זה הכל בחיים. איזו בעיה מיוחדת (לא טכנית רגעית, אלא תאורתית עקרונית) אתה רואה בהבאת נתונים אל זכרונו של המחשב הקוונטי? |
|
|
|
|
|
|
||
|
||||
|
נחשוב שוב בצורה מעשית: כמה קיוביטים צריך במחשב כדי שהאלגוריתם הזה יהיה יותר יעיל מחיפוש לינארי פשוט? באלגוריתמים כמו פיקטור, מכונה עם בערך אלף קיוביטים תהיה כבר מועילה למדי. הניחוש שלי שבמקרה של חיפוש ברשימה, הקבוע הוא מספיק גדול כך שאפילו חיפוש ברשימה של 10000 ערכים יהיה עדיין יותר מהיר באלגוריתם לינארי רגיל. כלומר: תצטרך מכונה קוונטית "גדולה" למדי כדי לנצל את האלגוריתם. צריך להתחשב גם בסיבוכיות המקום, לא רק בסיבוכיות הזמן... |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |