השוואת קבצים,

[yair24]

השוואת קבצים,

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

 

[dannykalfon]

רק brute FORce

 

[zontar]

שאלה אחת ורעיון אחד :../images/Emo26.gif

השאלה היא האם אתה צריך להשוות שורות שלמות או תת מחרוזת

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

, במידה ואתה משווה שורות שלמות אז העניין פשוט יותר,דרך אחת היא כפי שאמרת והרעיון הנוסף שיש לי הוא בכדי להקטין את הסיבוכיות תוכל אולי בכל איטרציה של הלולאה לבדוק במקבלי את 2 הקבצים,כלומר לבצע בדיקה על שורה מס´ 1 בקובץ 1 מול כל השורות בקובץ 2 ובאותה לולאה לבצע בדיקה על שורה מס´ 1 בקובץ 2 מול כל השורות בקובץ 1,דבר זה אמור להוריד את הסיבוכיות בצורה משמעותית והבדיקה הראשונית (לבדוק אם אותה שורה באותם הקבצים לא שוות ערך) היא זניחה ולא נכנסת לחישוב הסיבוכיות. תקן אותי אם אני טועה

.

 

[yair24]

סתם שאלה: ../images/Emo13.gif

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

 

[zontar]

-->

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

בנוגע לרעיון שלי,אני לא בטוח אם אכן הוא יוריד את הסיבוכיות אבל מה שהתכוונתי הוא : את הבדיקה של השוואת השורות אתה מבצע ע"י לולאה שמספר האיטרציות שלה הוא כמספר השורות בקובץ הגדול יותר,עד פה נכון? יפה, במקום לבדוק בכל פעם שורה אחת בקובץ מסויים אל מול כל השורות בקובץ השני נסה לבדוק בכל איטרציה את השורה הנוכחית בקובץ 1 מול כל שאר השורות בקובץ 2 וגם את השורה הנוכחית בקובץ 2 אל מול כל השורות בקובץ 1. (כמובן שהדבר מתבצע ב 2 לולאות מקוננות) בכל איטרציה של הלולאה החיצונית למעשה תבדוק 2 שורות במקביל (למשל שורה מס´ 1 בקובץ 1 אל מול כל השורות בקובץ 2 ושורה מס´N-1 בקובץ 2 אל מול כל השורות בקובץ 1 ) וכמובן כפי שאמרת למחוק את כל השורות הזהות. כך אתה מבצע חיפוש כפול למעשה באותה איטרציה ובמצב האידאלי ששתי הקבצים זהים לחלוטין במקום לבצע N איטרציות אתה תבצע רק N/2 איטרציות (כי בדקת במקביל את 2 הקבצים). (יכול להיות שאני מדבר שטויות אבל לפחות ניסיתי

)

 

[yair24]

אוקיי בוא נראה:

open two files for i=1 to size of bigger file. { for j=1 to size of smaller file. { compare line j with line i if equal then delete both } }​

למה זה לא מסתדר לי עם שתי איטרציות? יאיר

 

[zontar]

----> זאת כוונתי :

open two files n=size of smaller file for i=1 to size of bigger file. { for j=1 to size of smaller file. { compare (line i in bigger file)(with line j in smaller file) if equal then delete both compare (line i in smaller file)(with line n-j in bigger file) if equal then delete both } }​

 

[Zack DA]

לא !

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

 

[yair24]

אתה נותן פה רק מקרה אחד.

אם אני אתייחס רק למקרה הזה אז אני יכול להגיד דבר כזה: בוא נעתיק את שני הקבצים ומיד בסיבוכיות של N+M נקבל את כל השורות השונות (שזה כל השורות) אבל זה לא בסדר, כי אני לא יכול להניח שאין אף שורה זהה בין שני הקבצים, כמו שאני לא יכול להניח שכל השורות הן זהות... תמיד יהיה איזשהו מקרה קצה שדופק את האלגוריתם. במקרה שאני נותן הסיבוכיות תרד בצורה הסתברותית כלומר אם יש שורות זהות אז היא תרד אבל אם אין אז היא לא תרד, (שזה לא נורא לא קרה כלום) אתה כנראה מדבר על אלגוריתמים בסגנון רבין קרפ (RABIN KRAP) שנותנים פתרון למציאת תתי מחרוזות ארוכות מאוד מחרוזות שהם פאלינדרומים (מחרוזות שניתן לקרוא אותם מימין לשמאל ומשמאל לימין כמו למשל: מימ) גנטיים(חיפוש תת מחרוזת באורך 1000 תוים בתוך מחרוזת באורך מעל מיליון תוים וגם אלגוריתמים אלו עובדים בצורה הסתברותית וקיים המקרה שלא רק שהם לא עוזרים אלא להיפך מאריכים את זמן החיפוש!!) אבל זה לא מה שאני צריך כי דוקא המחרוזות אצלי הן לא ממש ארוכות. אם יש לך רעיון שיכול לשפר את הרעיון שלי (אפילו מבחינה הסתברותית כלומר שלא תמיד הוא פועל) אני אשמח לשמוע אותו ואני אתן עוד הבהרה: מאחר ואני מכיר את הקבצים האלו אני יכול לומר שרוב הפעמים יש די הרבה שורות שהן זהות ואף פעם (!!) אין מקרה שבו אין אף שורה זהה בין שניהם יאיר

 

[Zack DA]

מקרה אחד?

1. סיבוכיות אלגוריתם נקבעת לפי המקרה הגרוע ביותר ולא באופן ממוצע. 2. כוונתי הייתה לאלגוריתמים אחרים, והוכח מתמטית כי הם מורידים את זמן הריצה באופן אסימפטוטי, רק שנכונות התוצאה שהן מחזירים אינה נכונה באחוז קטן מהמקרים. 3. דווקא בגלל שיש ירידה בזמן הריצה האסימפטוטי חשוב שהמחרוזות יהיו ארוכות. 4. גם אם נתון שיש שורה זהה אחת לפחות עדיין זמן הריצה האסימפטוטי הוא NM. צחי

 

[selalerer]

הסדר בו מופיעות השורות ...

האם הסדר בו מופיעות השורות הקיימות בשני הקבצים הוא אותו סדר, כלומר האם אחרי שכבר מצאת את השורה הראשונה של הקובץ הראשון בקובץ השני ,נאמר, בשורה שש, אז לא יכול להיות ששורה 2 של הקובץ הראשון נמצאת בחמש שורות הראשונות של הקובץ השני?? אם זה באמת כך, אז יש לי דרך להוריד את הסיבוכיות ע"י בדיקה רק מהמקום שאתה מצביע עליו והלאה ובלי לבדוק את כל הקובץ השני אל מול כל שורה של הראשון(אלא רק את השארית שלו מאיפה שכבר סרקנו אותו).

 

[yair24]

אמממ אני צריך לבדוק את זה

תודה. יאיר

 

[aradori]

לא הבנתי משהו:

זה שיש פתרון טריוויאלי בסיבוכיות O של N+M (כש-N ו-M זה נניח מספר התווים בקובץ הראשון והשני בהתאמה) - זה ברור... מה שאני לא מבין זה איך יכול להיות פתרון בסיבוכיות טובה יותר? הכי לכל הפחות אתה צריל לעבור תו-תו - או כדי לבדוק אם הוא זהה בשני הקבצים, או (אם כבר הגעת למסקנה שהשורה שאתה בודק, לא מופיעה בקובץ השני) כדי להדפיס אותו. ככה שלא כל-כך הבנתי מה אתה מחפש - את הפתרון הטריוויאלי או פתרון בסיבוכיות טובה מ N+M?

 

[yair24]

אין פתרון טריוויאלי...

אין פתרון טריוויאלי שהסיבוכיות שלו היא N+M יש פתרון טריוויאלי שהסיבוכיות שלו היא M*N ובגלל שהקבצים הם גדולים מאוד אני לא יכול להסתפק בסיבוכיות של M*N. יאיר

 

[yair24]

הנה פתרון מעולה שמישהו נתן לי.

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

 

[shed]

הנה רעיון.

אני אזרוק לך רק קצה של חוט שיש לי כדי לייעל את האלגוריתם: תשתשמש בערימה (heap). האיבר הראשון בערימה הוא האיבר הכי גדול בה. תיקח את שני הקבצים, אחרי שנתת לכל שורה ערך מספרי חד חד ערכי (crc כזה או אחר), תכניס כל קובץ לערימה. זמן ההכנסה הוא (n*log(n . עכשיו תשווה את האיבר בראש כל ערימה עם חברו מהערימה השניה. אם הם שווים יופי, אם לא, אזי האיבר הגדול יותר לא נמצא בקובץ השני, תוציא אותו מהערימה (ותסמן לך שהוא שונה), תריץ על הערימה את הפונ´ heapify אשר "מסדרת" את הערימה (לוג n), ותחזור שוב. זמן ההשוואה: הוא שוב (n*log(n .

 

[selalerer]

ניתן בנוסף לCHECKSUM לעשות ...

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