הדרך המהירה ביותר לאתחל מערך מדיסק

[dovid]

מה ממש לא נכון לדעתי, ההמרה של הבתים לאובייקטים, עוד לפני שווידאת שהם הם הרלוונטיים לך.

מה מיותר זה כבר מסובך, כי באמת אני חולק על הגישה האלגוריתמית לעניין.
אני חוזר בי מגישת מסד הנתונים, כי זה באמת לא הנקודה כאן.

לדעתי צריך להיות:
[u:2hxx37a7]א. מילון[/u:2hxx37a7]
קובץ אחד שהוא מילון של כל המילים, והוא אמור להיות כולו בזיכרון מתחילת חיי היישום עד סופו. זה הכי פחות חשוב האופן בו הוא נכתב לדיסק ונטען ממנו.
כל מילה מופיעה פעם אחת, ומיקומה ביחס לתחילת המילון (לדוגמא המילה ה27) היא הזיהוי שלה.
[u:2hxx37a7]ב. אינדקס דחוס (+ כל ערך באורך קבוע)[/u:2hxx37a7]
האינדקס בעצם זה עותק של קובץ המקור אבל במקום לכתוב "פעם היה איש" לדוגמה, לכתוב (ע"פ המילון) שלושה קודי Integer שכל אחד לוקח ארבעה בתים תמיד.
אז יש לנו קובץ בינארי שאנו יודעים שהוא מורכב מ4 בתים * מספר המילים בקובץ.
[u:2hxx37a7]ג. חיפוש תוך כדי הקריאה[/u:2hxx37a7]
כשמחפשים לדוגמה את המילים: שלום {30} ברה {11} הצלה {22} שמח,
אז דבר ראשון נשיג מהמילון את קודי הזיהוי שלהם. לא בצורת מספר, אלא מספר מומר למערך בתים בגודל 4 (עדיף כבר במילון בזיכרון, אבל אם לא עכשיו).
דבר שני נעבור בלולאה של Stream על קובץ האינדקס שמורכב כאמור מסטים של ארבע ארבע בתים.
אז במהלך הלולאה שעוברת על בתי הקובץ (של האינדקס), לבדוק התאמה בין הקטע הנקרא כעת לבין אחד מאבעת הקודים אותם אנו מחפשים.
**[size=85:2hxx37a7]אפשר לעשות את זה תוך כדי (שהקריאה לא תחכה לבדיקה, והבדיקה לא תחכה לקריאה) אבל זה כבר מורכב יותר. אם תאחז בזה אשמח להראות לך איך.[/size:2hxx37a7]**אם נמצאה התאמה פותחים מונה שיבדוק את המרחק בין ההתאמה הזו לזו שאחריה, במידה וזה התאמה לא ראושנה נבדוק את המרחק ונחליט אם יש בהתאמה הוקדמת רלוונטיות לאור המרחק.

כדי להבהיר את כוונתי אראה כאן קוד דוגמה:

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

פורסם במקור בפורום CODE613 ב04/07/2013 11:57 (+03:00)

[רחמים]

א. לגבי המילון אני מבין שצריך לעשות מילון נפרד עבור כל קובץ כלומר כל קובץ יקבל מילון וגם קובץ אינדקס.

ב. לגבי האינדקס יוצא שאתה עושה את הספירה כמה פעמים כל מילה מופיעה תוך כדי חיפוש וזה לוקח זמן, אולי עדיף שכל מילה תופיע באינדקס כמספר כמו שאמרת, אבל רק פעם אחת ולצידה יופיעו מספרים שמציינים את מיקומי המילה בקובץ למשל תופיע מילה 'שלום' אבל לא כשלום אלא כמספר נאמר 20 כיון שזה המזהה של המילה 'שלום' במילון ואחר המספר 20 יופיע רצף של מספרים למשל 40 500 780 שזה אומר שהמילה 'שלום' מופיעה בקובץ המקורי כמילה ה 40 מתחילת הקובץ וכמילה ה500 מתחילת הקובץ וכו'.

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

ובמחשבה שניה למה לא לאחד בין המילון לאינדקס? אחר כל מילה במילון יופיעו כל המופעים של אותה מילה בקובץ המקור.

וכדי לגשת ולעבור מהר בין מילה למילה במילון אפשר לעשות קובץ של 'תוכן עינינים' של המילון בצורה כזו:
התוכן עינינים יכיל מספרים, כל מספר יציין את המיקום שממנו מתחילה מילה במילון.
למשל המילה הראשונה מתחילה ב 0 כמובן, כי זה תחילת הקובץ אחר המילה מופיעים כל המיקומים שלה, המיקומים לוקחים למשל 200 ביטים מתחילת הקובץ, ואז מגיעה המילה השניה ואחריה כל המיקומים שלה וכן הלאה, אז בקובץ תוכן העינינים יהיה כתוב 0 200 350 וכדומה. וכשנרצה לגשת מילה אחר מילה נעביר את המצביע של קורא הקובץ למיקום הרצוי אחד אחר השני. נעביר ל 0 נקרא מילה אחת אם אין התאמה נעבור ל 200 נקרא מילה אחת אם יש התאמה נמשיך לקורא את כל מיקומי המילה ואז נעבור ל350 ונקרא עוד מילה ונבדוק התאמה, וכן הלאה.

פורסם במקור בפורום CODE613 ב04/07/2013 12:38 (+03:00)

[dovid]

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

אני לא הדבקתי את הקוד קודם, אדביק אותו כאן

Sub SerachInIndex(WordsCodes() As Byte, fileIndex As String)
        Using Stream As New IO.FileStream(fileIndex, IO.FileMode.Open, IO.FileAccess.Read)
            Dim bytes(4095) As Byte
            Dim numBytesToRead As Integer = Stream.Length
            Dim numBytesRead As Integer = 0

            While numBytesRead < numBytesToRead
                numBytesRead = Stream.Read(bytes, 0, 4096)
                For i As Integer = 0 To 1023
                    For Each WordCheck In WordsCodes
                        If bytes.Skip(i).Take(4).SequenceEqual(WordsCodes) Then
                            'החזרת המיקום והמילה שנמצאה
                        End If
                    Next
                Next
            End While
        End Using
    End Sub

פורסם במקור בפורום CODE613 ב04/07/2013 14:18 (+03:00)

[רחמים]

@דוד ל.ט.

זה חבל מאוד לכתוב מיקומים אחרי ערך כי אז אתה מסתבך אם הקריאה המהירה.

בשביל לקרוא מהר יש את התוכן עינינים שהסברתי לעיל, אני מקווה שהסברתי מספיק ברור. ע''י התוכן עינינים אתה עובר ממילה למילה אף שהם לא רצופות במהירות, ורק כאשר יש התאמה אתה מיד קורא גם את הביטים שאחר המילה ומקבל את כל המיקומים שלה ולא צריך להמשיך ולקרוא עד סוף הקובץ כדי למצוא את כל המיקומים של אותה מילה.

@דוד ל.ט.

מלבד זאת מיקום לוקח מקום בדיוק כמו הערך, אז מה הטעם לכתוב גם מילה וגם מיקומה במקום פשוט לכתוב לפי הסדר?

מה שאני מרויח הוא כנ''ל שלא צריך לקרוא עד סוף הקובץ, נציג את התהליך כך:
נאמר שאני מחפש את המילה 'שלום' תחילה אני אקרא את כל התוכן עינינים ואז מיד אני אדע איפה מתחילה כל מילה אתחיל לקרוא מילה אחר מילה אם המילה שקראתי היא 'שלום' מיד אני לוקח את כל המיקומים ויוצא מהקריאה.

אפשר לעשות את זה עוד יותר מהר אם אשמור מידע על סדר הא''ב של תוכן העינינים, למשל אני יכול לציין לעצמי ש10 המספרים הראשונים בתוכן העינינים שייכים לאות א' ו20 הבאים הן מילים שמתחילות בב' וכו' וכך כאשר אני מחפש 'שלום' אני מיד אגש למספרים הרלוונטים בתוכן עינינים ועם המספרים האלו בלבד אלך ואקרא מהאינדקס את המילים שמתחילות בש'.

לדעתי זה יהיה ממש מהיר לא ?

פורסם במקור בפורום CODE613 ב04/07/2013 14:44 (+03:00)

[dovid]

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

פורסם במקור בפורום CODE613 ב04/07/2013 14:53 (+03:00)

[dovid]

@רחמים

אפשר לעשות את זה עוד יותר מהר אם אשמור מידע על סדר הא''ב של תוכן העינינים, למשל אני יכול לציין לעצמי ש10 המספרים הראשונים בתוכן העינינים שייכים לאות א' ו20 הבאים הן מילים שמתחילות בב' וכו' וכך כאשר אני מחפש 'שלום' אני מיד אגש למספרים הרלוונטים בתוכן עינינים ועם המספרים האלו בלבד אלך ואקרא מהאינדקס את המילים שמתחילות בש'.

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

פורסם במקור בפורום CODE613 ב04/07/2013 17:30 (+03:00)

[רחמים]

@דוד ל.ט.

יש לי על היישום כמה הערות

אשמח לשמוע ולהחכים.

@דוד ל.ט.

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

שים לב שאין אני רוצה לאתחל מערך עם כל המילים אלא לעבור על כל המילים ישירות על הדיסק כעצתך לעיל וממילא אני מוכרח לכתוב בעצמי פונקציה לחיפוש בינארי זה. יש עוד שיטה לחיפוש בינארי כאן:
http://vlib.eitan.ac.il/ds1/block_find.htm

פורסם במקור בפורום CODE613 ב04/07/2013 20:37 (+03:00)

[רחמים]

@דוד ל.ט.

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

באמת בדקתי וקריאה רצופה מהירה פי מאה מקריאה עם העברת מצביע כל פעם!

Dim MAX As Integer = 2000000
    Dim SW As New Stopwatch

    Dim ARR(MAX) As Integer

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        'בניית הקובץ
        SW.Reset()
        SW.Start()

        Dim BW As New BinaryWriter(File.Open("C:\SS.TXT", FileMode.Create), Encoding.UTF8)
        For I = 2 To MAX + 2
            BW.Write(CInt(I))
        Next
        BW.Close()

        SW.Stop()

    End Sub

    Private Sub Button2_Click(sender As System.Object, e As System.EventArgs) Handles Button2.Click

        SW.Reset()
        SW.Start()

        Dim BR As New BinaryReader(File.OpenRead("C:\SS.TXT"), Encoding.UTF8)
        Dim num As Integer = MAX
        'קריאה רצופה
        For I = 0 To MAX

            'קריאה עם דילוג כל פעם
            'For I = MAX * 4 To 0 Step -4
            '    BR.BaseStream.Position = I

            ARR(num) = BR.ReadInt32
            num -= 1
        Next

        BR.Close()

        SW.Stop()

    End Sub

פורסם במקור בפורום CODE613 ב04/07/2013 21:46 (+03:00)

[רחמים]

@דוד ל.ט.

[u:11abktml]ג. חיפוש תוך כדי הקריאה[/u:11abktml]
כשמחפשים לדוגמה את המילים: שלום {30} ברה {11} הצלה {22} שמח,
אז דבר ראשון נשיג מהמילון את קודי הזיהוי שלהם. לא בצורת מספר, אלא מספר מומר למערך בתים בגודל 4 (עדיף כבר במילון בזיכרון, אבל אם לא עכשיו).
דבר שני נעבור בלולאה של Stream על קובץ האינדקס שמורכב כאמור מסטים של ארבע ארבע בתים.
אז במהלך הלולאה שעוברת על בתי הקובץ (של האינדקס), לבדוק התאמה בין הקטע הנקרא כעת לבין אחד מאבעת הקודים אותם אנו מחפשים.
**[size=85:11abktml]אפשר לעשות את זה תוך כדי (שהקריאה לא תחכה לבדיקה, והבדיקה לא תחכה לקריאה) אבל זה כבר מורכב יותר. אם תאחז בזה אשמח להראות לך איך.[/size:11abktml]**אם נמצאה התאמה פותחים מונה שיבדוק את המרחק בין ההתאמה הזו לזו שאחריה, במידה וזה התאמה לא ראושנה נבדוק את המרחק ונחליט אם יש בהתאמה הוקדמת רלוונטיות לאור המרחק.

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

טוב, בניתי את המילון והאינדקס כמו שאמרת כעת הגעתי לשלב הקריאה אז איך עושים שהקריאה לא תחכה לבדיקה, והבדיקה לא תחכה לקריאה ?
עוד דבר למעשה השאילתא קצת יותר מורכבת היא יכולה להראות כך:
+שלום/שפע# {30} ברה {11} הצלה/רווח {22} שמח/מאושר/עליז/רוקד

כאשר סימן הפלוס מיצג קידומות דיקדוקיות סימן הסולמית מיצג סיומות דיקדוקיות והקוים הנטויים כוונתו או מילה הזאת או הזאת וכו'.
בשיטה שלי הכל עובד מצויין איך עושים את זה בשיטה שלך?

פורסם במקור בפורום CODE613 ב05/07/2013 16:39 (+03:00)

[dovid]

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

לשאלת החיפוש המשוכלל:
לפי דרכי, המילון על הזיכרון, והשליפה ממנו ע"י חיפוש בינארי.
בחיפוש משוכלל, פשוט מאפשרים כמה מילים למילה אחת כלומר מי שמחפש "איש אחד* היה" נחפש במילון את הקוודים של כל המילות שמתחילות באותיות אחד עם המשך כל שהוא, וכל האפשרויות יהיו תקינות בתור המילה השנייה של מחרוזת החיפוש.
אותו דבר דקדוקי וכו'.

פורסם במקור בפורום CODE613 ב07/07/2013 11:40 (+03:00)

[רחמים]

מצאתי דבר מאוד מעניין כאשר אני משווה בין השיטה שלך לשלי:
בשיטה שלך מחפשים על קובץ האינדקס בעצמו ללא אתחול מערך זה ממש ממהר את החיפוש כאשר מחפשים 2-3 מילים ואז יוצא שצריך לעבור על כל הקובץ 2-3 פעמים וזה כמובן יותר מהר ב30% מלאתחל מערך מהקובץ.
אולם כאשר מחפשים הרבה מילים כמו בחיפוש עם כוכביות וכדומה שכל מילה שהמשתמש מקליד בשאילתא הופכת לכמה עשרות או מאות מילים, הרי שהחיפוש בשיטה שלך איטי פי 7 ! כי צריך לעבור על הקובץ מאות או עשרות פעמים וכמובן שלאתחל מערך זה יותר מהר.
אבל בשיטה של איתחול מערך אומנם בתחילה זה לוקח קצת זמן כדי לאתחלו אבל אחר שיש מערך וצריך רק לגשת לאיברים לכמה עשרות או מאות איברים ולקבל את כל המיקומים מוכנים אז כמעט אין הפרש בזמן בין חיפוש עם כוכביות או בלי , עם כוכביות זמן החיפוש עולה ב 10% בלבד.

אני מקווה שההסבר שלי מספיק מובן אבל בכל מקרה אלו עובדות שמתגלות כאשר אני משווה בין שתי התוכנות עם אותן השאילתות ועל אותם המאגרים ממש.

פורסם במקור בפורום CODE613 ב07/07/2013 11:52 (+03:00)

[dovid]

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

פורסם במקור בפורום CODE613 ב07/07/2013 12:49 (+03:00)

[רחמים]

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

פורסם במקור בפורום CODE613 ב07/07/2013 12:55 (+03:00)

[dovid]

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

פורסם במקור בפורום CODE613 ב07/07/2013 13:07 (+03:00)

[רחמים]

כן, תודה רבה.

פורסם במקור בפורום CODE613 ב07/07/2013 13:11 (+03:00)

[dovid]

@דוד ל.ט.

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

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

זו הצורה הבסיסית:

Class MyComparer
    Implements System.Collections.IComparer
    Public Function Compare(x As Object, y As Object) As Integer Implements IComparer.Compare
        Dim xStr As String = x
        Dim yStr As String = y
        If (xStr < yStr) Then
            Return 1
        End If
        If (xStr > yStr) Then
            Return -1
        Else
            Return 0
        End If
    End Function
End Class

ואח"כ משתמשים ככה:

Array.BinarySearch(coll, 0, coll.Length, "אחד", New MyComparer)

פורסם במקור בפורום CODE613 ב07/07/2013 13:35 (+03:00)

[רחמים]

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

פורסם במקור בפורום CODE613 ב07/07/2013 18:21 (+03:00)