2.5 - אלגוריתמים טווחים ותצוגות - הרצאה

הצינור עוד לא עשה את העבודה

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

התוכנית הבאה משתמשת ב־ranges וב־views של C++20:

#include <cstdio>
#include <ranges>
#include <vector>

int main() {
    std::vector<int> input{-2, 1, 0, 3, 4};

    auto selected = input
        | std::views::filter([](int n) { return n > 0; })
        | std::views::transform([](int n) { return n * n; });

    for (int value : selected) std::printf("%d ", value);
    std::puts("");
}

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

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

תצוגה אינה תמיד בעלים

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

הפונקציה הבאה מציגה באג לניתוח בלבד:

#include <ranges>
#include <vector>

auto bad_numbers() {
    std::vector<int> values{1, 2, 3};
    return values | std::views::filter([](int n) { return n > 1; });
}

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

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

איטרטור וסמן סוף

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

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

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

חיפוש ותוצאה שאסור להשתמש בה

חלק מאלגוריתמי ranges מחזירים טיפוס dangling במקום iterator כאשר אי אפשר להבטיח שהתוצאה תישאר שימושית אחרי השמדת טווח זמני.

הדוגמה הבאה היא תוכנית מלאה:

#include <algorithm>
#include <ranges>
#include <type_traits>
#include <vector>

int main() {
    auto result = std::ranges::find(std::vector<int>{1, 2, 3}, 2);
    static_assert(std::is_same_v<decltype(result), std::ranges::dangling>);
}

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

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

שינוי המקור באמצע

ה־view אינו snapshot. אם input משתנה, התוצאה עשויה להשתנות, ואם השינוי פוסל iteratorים או references, ה־view עלול להיפגע.

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

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

השוואה היא חוזה של האלגוריתם

אלגוריתם מיון דורש יחס סדר מתאים. השוואה באמצעות less-than רגיל היא לרוב נקודת פתיחה, אבל comparator מותאם חייב לספק strict weak ordering.

הקטע הבא מדגים comparator שגוי ואין להשתמש בו למיון:

// Invalid ordering for sorting:
// bool bad_less(int a, int b) { return a <= b; }

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

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

בחירת שדה להשוואה - Projection

אפשר למיין רשומות לפי שדה באמצעות projection. נשנה את הדוגמה לאוסף משימות:

#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

struct Job {
    int priority;
    int id;
};

int main() {
    std::vector<Job> jobs{{3, 10}, {1, 20}, {2, 30}};
    std::ranges::sort(jobs, std::ranges::less{}, &Job::priority);
    for (const auto& job : jobs) {
        std::printf("%d:%d ", job.id, job.priority);
    }
    std::puts("");
}

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

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

מתי מממשים את התוצאה

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

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

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