ידידי שואב המים הראה לי קישור לאלגוריתם הזה: https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithmנתון קובץ טקסט ובו 2000001 מלים. יש מלה אחת שמופיעה 1000001 פעמים בקובץ. עליכם למצוא את המלה הזו בדרך מהירה וחסכונית בזכרון.
יש דרך טובה יותר.שלב ראשון למיין את מערך המילים בסדר עולה או יורד ( סיבוכיות ריצה וזכרון ( n ) n*log ), ואז לקחת את האיבר האמצעי במערך הממוין.
לא בהכרח.שאלה: האם שאר ה 1000000 מילים שונים זה מזה ?
יש דרך טובה יותר.לטעון את המילים לטבלה בה שדה אחד הוא המילה (להשתמש בdistinct) והשדה הסמוך הוא מספר המופעים (פונקציית count), לבחור מהטבלה את המילה שמספר המופעים שלה 1000001.
Select top 1 word from counttab order by wordinstances descיש דרך טובה יותר.
זה לא תיאור של אלגוריתם. באותה מידה יכולת לכתוב "מצא את המלה בעלת מספר המופעים הגדול ביותר".Select top 1 word from counttab order by wordinstances desc
זה גם לא פורום מטאל.להזכיר שזה פורום מתמטיקה ולא תכנות.
או שזה המובן מאליו....
יש פתרון פשוט ומהיר יותר.פשוט אספור את כמות הפעמים שאות הופיעה בכל מיקום
וכך אקבל מטריצה עם 22 אותיות כפול m אורך המילה.
בכל מיקום, האות עם הכי הרבה מופעים היא המילה המנצחת
מעבר אחד או 2 על כל אות בקובץ
זיכרון: אורך המילה המקסימלית m*מספר האותיות החוקיות(שהוא קבוע)
מהיר יותר מלעבור פעם אחת על הקובץ...יש פתרון פשוט ומהיר יותר.
מה זה "מהיר יותר מלעבור פעם אחת על הקובץ"? יכולים להיות שני אלגוריתמים שעוברים פעם אחת על הקובץ, ואחד מהם יותר מהיר מהאחר.מהיר יותר מלעבור פעם אחת על הקובץ...
מעניין
אז איך אתמודד עם המצב הגרוע של 2 מילים שאחת מופיעה מליון פעמים והשנייה מליון ואחד?
שניהם בדיוק אותה סיבוכיות.מה זה "מהיר יותר מלעבור פעם אחת על הקובץ"? יכולים להיות שני אלגוריתמים שעוברים פעם אחת על הקובץ, ואחד מהם יותר מהיר מהאחר.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.