הבא בתור – איך ולמה מימשתי 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.
בפוסטים הבאים אני ארחיב על המימושים השונים, על האופטמיזציות ועל הבנצ'מרק, אבל בינתיים מוזמנים להיכנס לקוד עצמו, ואם תרצו לפרגן בכוכב, אני לא אעצור אתכם 🙂
אם יורשה לו להגיב