streamalism.org

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

במדריך זה נלמד כיצד להטמיע חיץ צלצולים ב- Java.

2. חיץ צלצולים

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

2.1. איך זה עובד

חיץ טבעות מיושם באמצעות מערך בגודל קבוע שעוטף את הגבולות.

מלבד המערך, הוא עוקב אחר שלושה דברים:

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

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

נשאל את הגישה מיישום Disruptor של חיץ הטבעת באמצעות רצפים.

הדבר הראשון שעלינו לדעת הוא הקיבולת - הגודל המרבי הקבוע של המאגר. הַבָּא, נשתמש בשני גידולים מונוטונייםרצפים:

• כתוב רצף: החל מ -1, רווחים ב -1 כאשר אנו מכניסים אלמנט
• קרא רצף: החל מ- 0, רווחים ב -1 כאשר אנו צורכים אלמנט

אנו יכולים למפות רצף לאינדקס במערך באמצעות פעולת mod:

arrayIndex = רצף% קיבולת 

ה פעולת mod עוטפת את הרצף סביב הגבולות כדי להפיק חריץ במאגר:

בואו נראה איך נכניס אלמנט:

חיץ [++ writeSequence% קיבולת] = אלמנט 

אנו מגדילים מראש את הרצף לפני הכנסת אלמנט.

כדי לצרוך אלמנט אנו מבצעים תוספת לאחר:

element = buffer [readSequence ++ קיבולת] 

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

2.2. מאגרים ריקים ומלאים

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

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

המאגר מלא אם גודל המאגר שווה ליכולתו, כאשר גודלו שווה למספר האלמנטים שלא נקראו:

size = (writeSequence - readSequence) + 1 isFull = (קיבולת גודל ==) 

אם רצף הכתיבה נמצא מאחורי רצף הקריאה, המאגר ריק:

isEmpty = writeSequence <readSequence 

המאגר מחזיר א ריק ערך אם הוא ריק.

2.2. יתרונות וחסרונות

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

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

3. יישום בג'אווה

כעת, לאחר שהבנו כיצד פועל חיץ טבעת, נמשיך ליישם אותו ב- Java.

3.1. אִתחוּל

ראשית, נגדיר קונסטרוקטור שמאתחל את המאגר עם יכולת מוגדרת מראש:

CircularBuffer ציבורי (int קיבולת) {this.capacity = קיבולת; this.data = (E []) אובייקט חדש [קיבולת]; this.readSequence = 0; this.writeSequence = -1; } 

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

3.3. הַצָעָה

לאחר מכן, ניישם את הַצָעָה פעולה שמכניסה אלמנט למאגר במשבצת הזמינה הבאה ומחזירה נָכוֹן על הצלחה. זה חוזר שֶׁקֶר אם המאגר אינו יכול למצוא חריץ ריק, כלומר איננו יכולים להחליף ערכים שלא נקראו.

בואו ליישם את הַצָעָה שיטה ב- Java:

הצעה בוליאנית ציבורית (אלמנט E) {בוליאני isFull = (writeSequence - readSequence) + 1 == קיבולת; אם (! isFull) {int nextWriteSeq = writeSequence + 1; data [nextWriteSeq% capacity] = אלמנט; writeSequence ++; לחזור אמיתי; } להחזיר שקר; } 

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

בואו ננסה את זה:

@ מבחן חלל ציבורי givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {חיץ CircularBuffer = CircularBuffer חדש (defaultCapacity); assertTrue (buffer.offer ("כיכר")); assertEquals (1, buffer.size ()); } 

3.4. מִשׁאָל

לבסוף, נבצע את ה- מִשׁאָל פעולה המאחזרת ומסירה של האלמנט שלא נקרא הבא. ה מִשׁאָל הפעולה אינה מסירה את האלמנט אלא מגדילה את רצף הקריאה.

בואו נבצע את זה:

סקר E ציבורי () {בוליאני isEmpty = writeSequence <readSequence; אם (! isEmpty) {E nextValue = data [קיבולת% readSequence]; readSequence ++; חזור nextValue; } להחזיר אפס; } 

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

בואו נבדוק את זה:

@Test הציבור בטל givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {חיץ CircularBuffer = CircularBuffer חדש (defaultCapacity); buffer.offer ("משולש"); צורת מחרוזת = buffer.poll (); assertEquals ("משולש", צורה); } 

4. בעיה יצרנית-צרכנית

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

בואו ניישם פתרון המבוסס על חיץ טבעת.

4.1. נָדִיף שדות רצף

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

המפיק כותב נתונים למאגר ומגדיל את ה- writeSequenceבעוד הצרכן קורא רק מהמאגר ומגדיל את ה- readSequence. לכן, מערך הגיבוי הוא ללא מחלוקת ואנחנו יכולים לברוח ללא כל סנכרון.

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

אנו יכולים להפוך את חיץ הטבעת במקביל ולנעול במקרה זה על ידי ביצוע שדות הרצף נָדִיף:

פרטי נדיף פרטי writeSequence = -1, readSequence = 0; 

בתוך ה הַצָעָה שיטה, לכתוב ל נָדִיף שדה writeSequence מבטיח שהכתיבה למאגר תתרחש לפני עדכון הרצף. במקביל, ה נָדִיף ערבות נראות מבטיחה כי הצרכן תמיד יראה את הערך העדכני ביותר של writeSequence.

4.2. יַצרָן

בואו נפעיל מפיק פשוט ניתן לרוץ שכותב למאגר הטבעת:

הפעלה בטלנית ציבורית () {for (int i = 0; i <items.length;) {if (buffer.offer (items [i]))) {System.out.println ("הופק:" + פריטים [i]) ; i ++; }}} 

חוט המפיק ימתין לחריץ ריק בלולאה (עסוק בהמתנה).

4.3. צרכן

אנו ניישם צרכן ניתן להתקשר שקורא מהמאגר:

ציבורי T [] שיחה () {T [] פריטים = (T []) אובייקט חדש [צפוי]; עבור (int i = 0; i <items.length;) {T item = buffer.poll (); if (item! = null) {items [i ++] = item; System.out.println ("נצרך:" + פריט); }} להחזיר פריטים; } 

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

בואו נכתוב את קוד הנהג שלנו:

executorService.submit (שרשור חדש (מפיק חדש (חיץ))); executorService.submit (שרשור חדש (צרכן חדש (חיץ))); 

ביצוע תוכנית המפיק-צרכנים שלנו מייצר תפוקה כמו להלן:

הופק: עיגול הופק: משולש נצרך: מעגל הופק: מלבן נצרך: משולש נצרך: מלבן הופק: ריבוע הופק: מעוין נצרך: ריבוע הופק: טרפז נצרך: מעוין נצרך: טרפז הופק: פנטגון הופק: פנטגרם הופק: משושה נצרך: פנטגון נצרך: פנטגרם הופק: משושה נצרך: משושה נצרך: הקסגרמה 

5. סיכום

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

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