הבא בתור – איך ולמה מימשתי FIFO בעצמי ב JavaScript – חלק 1
תור בהודו
יש הרבה שפות תכנות, ולכל שפה יש איזשהו בסיס, שמכונה standard library, שיש בו מבני נתונים מוכרים, כמו מערך, רשימה, hashmap ועוד.
ב JavaScript, מסתבר, יש כמה מבני נתונים בסיסיים, אבל תור – אין.
אני חושב שכולנו יודעים מה זה תור, או Queue: מבנה נתונים שמממש fifo, כלומר first-in-first-out. נו, תור, כמו בקופה של הסופר.
תור שימושי להרבה דברים. במקרה שלי, היינו צריכים להשתמש בתור כדי לאגור לוגים ואח"כ, בצורה הדרגתית, לשלוח אותם לפי הסדר שבו הם נכנסו.
יקפצו המתחכמים ויגידו: אבל רון, מה תור? יש לך מערך, יש לו מתודה push ומתודה pop, והנה לך תור! מה הסיפור?!
אז.. כן, זה תור. אבל אם נסתכל רגע על פרטי המימוש, נגלה שזה מימוש עם סיבוכיות של O(n) בזמן בפעולת ה pop. כל עוד אנחנו במספר נמוך של איברים – זה כנראה לא יפריע. אבל יש תרחישים שבהם נגיע לכמות גדולה של איברים. למעשה, היה לי תרחיש כזה בפועל (זה יהיה קצת ארוך לתאר את זה, אז תצטרכו פשוט להאמין לי).
טוב, אם אין תור כחלק מהשפה או מה standard library שלה, אז בטח יש איזה package שיתן לי תור נורמלי.
יש בהחלט מימושים לתור בכל מיני packages. הסתכלתי בקוד, וראיתי שחלק מהמימושים הם בסדר, והשאר לא מדהימים. לא ראיתי שום package (חבילה?) שהוא עם מימוש מושלם.
סליחה רגע, אני רק שאלה: מה זה מושלם פה?
אז ככה: מבנה נתונים הוא בד"כ טריידאוף בין צריכת זכרון לבין ביצועים. ה"מושלם" שאני מחפש הוא מימוש של תור שהוא O(1) בזמן על שתי הפעולות enqueue ו dequeue, וגם צריכת זכרון מינימלית.
אם נסתכל, למשל, על מימוש של תור באמצעות רשימה מקושרת, נגלה שלמרות שהוא O(1) בזמן, יש לו צריכת זכרון יחסית גבוהה.
מכיוון שאני אוהב לכתוב קוד, אז התחלתי פרוייקט צד, שיש בו מימושים לתור, עם דגש על צריכת זכרון נמוכה.
הפרויקט נקרא lite-fifo, הוא מאוחסן בגיטהאב, והוא זמין כ package ב npm.
בפוסטים הבאים אני ארחיב על המימושים השונים, על האופטמיזציות ועל הבנצ'מרק, אבל בינתיים מוזמנים להיכנס לקוד עצמו, ואם תרצו לפרגן בכוכב, אני לא אעצור אתכם 🙂
היי,
ראיתי את ההרצאה וקראתי את הפוסט,
רציתי לדעת האם יצא לך להסתכל על –
https://www.npmjs.com/package/fastq
ובכללי על Mnemonist – ספרייה של data structures שממומשים בצורה מאוד יעילה:
https://yomguithereal.github.io/mnemonist/fixed-deque
https://yomguithereal.github.io/mnemonist/queue
https://yomguithereal.github.io/mnemonist/circular-buffer
כמובן שזה לא Chunked Queue כמו שהצעת, אבל עם Mnemonist אפשר לממש את הlite-fifo אולי יותר בקלות
ד״א – הרצאה מעולה, מוסברת היטב 🙂
@yosi
היי יוסי,
תודה על הפידבק! שמח שאהבת את ההרצאה!
לגבי fastq, לא הכרתי. עם זאת, זה כבר task queue שיכול אולי להתאים לתרחיש ההוא ואולי לא.
לגבי Mnemonic, לא הכרתי את הפרוייקט, הוא מרשים מאוד. ספציפית המימוש שם של queue הוא דה פקטו amortized O(1) בהכנסה ובהוצאה. יהיה מעניין להכניס אותו לבנצ׳מארק ולראות איך הביצועים לעומת המימושים הקיימים ב lite-fifo.
שוב תודה על הפידבק 🙂