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

[רחמים]

@דוד ל.ט.

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

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

@דוד ל.ט.

בכל אופן זו בדיוק הדרך שבה עובדת הפונקציה 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)