חיפוש איבר במערך JS

[רחמים]

אם המערך ממויין אפשר לעשות חיפוש בינאר הנקרא אריה במדבר

פורסם במקור בפורום CODE613 ב07/03/2016 23:57 (+02:00)

[avraham]

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

פורסם במקור בפורום CODE613 ב08/03/2016 00:32 (+02:00)

[רחמים]

הוא משתמש בלולאה אבל לא עובר על כל המערך אלא על איברים מייצגים.

פורסם במקור בפורום CODE613 ב08/03/2016 07:27 (+02:00)

[avraham]

המערך הוא אוסף מחרוזות, ואני מחפש פוקציה כמו indexOf שיודעת לחפש תו במחרוזת בלי לולאה בכלל, כך שיחפש לי את המחרוזת הספציפית בלי לולאה. יש כזה דבר?

פורסם במקור בפורום CODE613 ב08/03/2016 08:24 (+02:00)

[ארכיטקט]

@avraham

האם אפשר לחפש במערך אם יש בו איבר מסוים, בלי לעבור בלולאה על המערך?

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

פורסם במקור בפורום CODE613 ב08/03/2016 08:33 (+02:00)

[avr416]

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

פורסם במקור בפורום CODE613 ב08/03/2016 11:12 (+02:00)

[dovid]

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

אבל אם כבר הוא שאל הוא אכן למד לדעת שindexOf לא עובד חכם באוסף מסודר (המשמעות מתחילה במערך ענק).

החיפוש הבינארי חותך כל פעם לשתיים. זה פעולה הפוכה מחזקת 2 שכל פעם מכפילה את גודלה.
במקרה הגרוע ביותר זה הנוסחה log(n) : זה נוסחה שמחזירה את המספר שדרוש ל"חזק" את שתיים עד שתגיע למס' של כל האיברים.
אם יש 10000 איברים אז זה 10 פעמים שכן 2 בחזקת 9.9 זה 1000 בקירוב (באקסל ע"י הנוסחה log עם פרמטר שני 2).
במקרה הנורמלי זה יהיה 5 פעמים.

הספריה underscore מממשת את זה בindexOf שלה.

_.indexOf(array, value, true) // הארגומנט השלישי מאשר שהמערך ממויין

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

פורסם במקור בפורום CODE613 ב08/03/2016 11:30 (+02:00)

[אהרן]

צריך אבל לזכור למיין כל הזמן
וגם זה עולה ביצועים

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

פורסם במקור בפורום CODE613 ב08/03/2016 11:47 (+02:00)

[dovid]

לא למיין אלא להכניס במקום הנכון (לא מצאתי לזה מימוש מוכן! נו). זה אכן עולה אבל ההנחה היא שיותר ניגשים מאשר מכניסים.

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

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

פורסם במקור בפורום CODE613 ב08/03/2016 12:58 (+02:00)

[dovid]

@דוד ל.ט.

לא למיין אלא להכניס במקום הנכון (לא מצאתי לזה מימוש מוכן! נו).

חצי כבר ממומש - למצוא מיקום, אז זה לא נורא:

var newItem = 3;
list.splice(_.sortedIndex(list, newItem), 0, newItem)

פורסם במקור בפורום CODE613 ב08/03/2016 13:38 (+02:00)