עוד חידת תכנות

[עריסטו]

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

 

[בחשכת הלילה]

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

ידידי שואב המים הראה לי קישור לאלגוריתם הזה: https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm

 

[הפרבולה1]

שלב ראשון למיין את מערך המילים בסדר עולה או יורד ( סיבוכיות ריצה וזכרון ( n ) n*log ), ואז לקחת את האיבר האמצעי במערך הממוין.

 

[עריסטו]

שלב ראשון למיין את מערך המילים בסדר עולה או יורד ( סיבוכיות ריצה וזכרון ( n ) n*log ), ואז לקחת את האיבר האמצעי במערך הממוין.

יש דרך טובה יותר.

 

[הפרבולה1]

שאלה: האם שאר ה 1000000 מילים שונים זה מזה ?

 

[עריסטו]

שאלה: האם שאר ה 1000000 מילים שונים זה מזה ?

לא בהכרח.

 

[SupermanZW]

לטעון את המילים לטבלה בה שדה אחד הוא המילה (להשתמש בdistinct) והשדה הסמוך הוא מספר המופעים (פונקציית count), לבחור מהטבלה את המילה שמספר המופעים שלה 1000001.

 

[עריסטו]

לטעון את המילים לטבלה בה שדה אחד הוא המילה (להשתמש בdistinct) והשדה הסמוך הוא מספר המופעים (פונקציית count), לבחור מהטבלה את המילה שמספר המופעים שלה 1000001.

יש דרך טובה יותר.

 

[SupermanZW]

יש דרך טובה יותר.

Select top 1 word from counttab order by wordinstances desc

 

[עריסטו]

Select top 1 word from counttab order by wordinstances desc

זה לא תיאור של אלגוריתם. באותה מידה יכולת לכתוב "מצא את המלה בעלת מספר המופעים הגדול ביותר".

 

[Lucifer LightBringer]

להזכיר שזה פורום מתמטיקה ולא תכנות.

או שזה המובן מאליו....

 

[עריסטו]

להזכיר שזה פורום מתמטיקה ולא תכנות.

או שזה המובן מאליו....

זה גם לא פורום מטאל.

 

[ai27]

פשוט אספור את כמות הפעמים שאות הופיעה בכל מיקום
וכך אקבל מטריצה עם 22 אותיות כפול m אורך המילה.
בכל מיקום, האות עם הכי הרבה מופעים היא המילה המנצחת

מעבר אחד או 2 על כל אות בקובץ
זיכרון: אורך המילה המקסימלית m*מספר האותיות החוקיות(שהוא קבוע)

 

[עריסטו]

פשוט אספור את כמות הפעמים שאות הופיעה בכל מיקום
וכך אקבל מטריצה עם 22 אותיות כפול m אורך המילה.
בכל מיקום, האות עם הכי הרבה מופעים היא המילה המנצחת

מעבר אחד או 2 על כל אות בקובץ
זיכרון: אורך המילה המקסימלית m*מספר האותיות החוקיות(שהוא קבוע)

יש פתרון פשוט ומהיר יותר.

 

[ai27]

יש פתרון פשוט ומהיר יותר.

מהיר יותר מלעבור פעם אחת על הקובץ...
מעניין
אז איך אתמודד עם המצב הגרוע של 2 מילים שאחת מופיעה מליון פעמים והשנייה מליון ואחד?

 

[עריסטו]

מהיר יותר מלעבור פעם אחת על הקובץ...
מעניין
אז איך אתמודד עם המצב הגרוע של 2 מילים שאחת מופיעה מליון פעמים והשנייה מליון ואחד?

מה זה "מהיר יותר מלעבור פעם אחת על הקובץ"? יכולים להיות שני אלגוריתמים שעוברים פעם אחת על הקובץ, ואחד מהם יותר מהיר מהאחר.

 

[ai27]

מה זה "מהיר יותר מלעבור פעם אחת על הקובץ"? יכולים להיות שני אלגוריתמים שעוברים פעם אחת על הקובץ, ואחד מהם יותר מהיר מהאחר.

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

באלגוריתם שהצעתי
על כל אות יש העלאת מונה בודד במערך.
אם היית אומר ש22*m זה הרבה מקום עוד מילא

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