סקירה כללית של ביצועי ביטויים רגולריים בג'אווה

1. סקירה כללית

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

להקדמה לשימוש ב- ביטויים קבועיםאנא עיין במאמר זה כאן.

2. המנוע התואם תבניות

ה java.util.regex החבילה משתמשת בסוג של מנוע תואם תבניות שנקרא אוטומטית סופית לא קבועה (NFA). זה נחשב לא קבוע מכיוון שבזמן ניסיון להתאים ביטוי רגולרי במחרוזת נתונה, כל תו בקלט עשוי להיבדק מספר פעמים מול חלקים שונים של הביטוי הרגולרי.

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

"tra (vel | ce | de) m"

עם הקלט חוּטלִנְסוֹעַ", המנוע תחפש תחילה"tra”ולמצוא אותו מיד.

אחרי זה, זה ינסה להתאים "vel”החל מהדמות הרביעית. זה יתאים, אז זה ילך קדימה וינסה להתאים "M“.

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

עם הכישלון האחרון, האלגוריתם יחזיר כישלון.

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

3. דרכים לייעל ביטויים רגילים

3.1. הימנע מהידור מחדש

ביטויים רגולריים בג'אווה נערכים למבנה נתונים פנימי. אוסף זה הוא התהליך הגוזל זמן.

בכל פעם שאנחנו קוראים את String.matches (מחרוזת regex) שיטה, הביטוי הרגולרי שצוין מקומפייל מחדש:

אם (input.matches (regexPattern)) {// לעשות משהו}

כפי שאנו רואים, בכל פעם שמעריכים את התנאי, מצטבר הביטוי regex.

כדי לייעל, ניתן לחבר את התבנית תחילה ואז ליצור a שידוך למצוא את המקריות בערך:

תבנית תבנית = תבנית.קומפילציה (regexPattern); עבור (ערך מחרוזת: ערכים) {Matcher matcher = pattern.matcher (value); אם (matcher.matches ()) {// עשה משהו}}

חלופה לאופטימיזציה שלעיל היא להשתמש באותה שידוך מופע עם שלו אִתחוּל() שיטה:

תבנית תבנית = תבנית.קומפילציה (regexPattern); התאמת התאמה = דפוס. התאמה (""); עבור (ערך מחרוזת: ערכים) {matcher.reset (value); אם (matcher.matches ()) {// עשה משהו}}

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

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

3.2. עבודה עם אלטרנטיבה

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

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

(נסיעות | סחר | עקבות)

מאשר:

tra (vel | de | ce)

האחרון מהיר יותר מכיוון ש- NFA ינסה להתאים "tra"ולא תנסה את אחת החלופות אם היא לא תמצא אותה.

3.3. לכידת קבוצות

בכל פעם שאנחנו תופסים קבוצות, אנו נקלעים לעונש קטן.

אם איננו צריכים ללכוד את הטקסט בתוך קבוצה, עלינו לשקול את השימוש בקבוצות שאינן לוכדות. במקום להשתמש “(M)", בבקשה תשתמש "(?:M)“.

4. מסקנה

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

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

כרגיל, ניתן למצוא את קוד המקור המלא ב- GitHub.


$config[zx-auto] not found$config[zx-overlay] not found