אחד המנגנונים שאהבתי ב Python מהרגע הראשון היה מנגנון ה Generators או בעברית פונקציה יוצרת: אנחנו מגדירים לפייתון איך סידרת ערכים מסוימת נראית ופייתון כבר יבנה את הערכים מהסידרה על פי דרישה. לא תמיד קל לראות מהשניה הראשונה ש Generators עובדים ממש טוב יחד (לפחות כל עוד אנחנו לא שוברים את השרשרת).

1. איך זה עובד

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

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

>>> players = itertools.cycle(['Tom', 'Jane'])
>>> print(f"It's {next(players)}'s turn")
It's Tom's turn
>>> print(f"It's {next(players)}'s turn")
It's Jane's turn
>>> print(f"It's {next(players)}'s turn")
It's Tom's turn
>>> print(f"It's {next(players)}'s turn")
It's Jane's turn
>>> print(f"It's {next(players)}'s turn")
It's Tom's turn
>>> print(f"It's {next(players)}'s turn")
It's Jane's turn

הפונקציה itertools.islice חותכת רק "פרוסה" מתוך Generator. ומה שיפה שאני יכול לשלב אותה עם cycle:

>>> ''.join(list(itertools.islice(itertools.cycle('hello '), 50)))
'hello hello hello hello hello hello hello hello he'

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

>>> list(itertools.islice(itertools.accumulate(itertools.cycle([10, 20, 30, 40]), operator.add), 10))
[10, 30, 60, 100, 110, 130, 160, 200, 210, 230]

2. איך זה נשבר

מאחר ו Generators עובדים כל כך טוב יחד חשוב לשים לב כשאנחנו כותבים Generator חדש לא לשבור את השרשרת. שימו לב לקוד הבא:

import itertools
from collections import OrderedDict

def nodups(collection):
    s = OrderedDict()

    for item in collection:
        s[item] = True

    for item in s:
        yield item

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

בגלל החלוקה לשני שלבים אי אפשר יהיה לחבר פונקציה זו לשרשרת Generators: אם היא תנסה להריץ את הלולאה הראשונה על collection אינסופי, הלולאה לעולם לא תסתיים ואף פעם לא יהיה שום yield.

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

list(itertools.islice(nodups(itertools.cycle('aaaaaaaaaaaaabbbbbbbbbbbbbbbbccccccccccc')), 10))

גישה טובה יותר תיראה כך:

def better_nodups(collection):
    s = set()
    for item in collection:
        if item not in s:
            yield item

        s.add(item)

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

3. שילוב Generators

בואו נשלב את כל ה Generators שראינו ונכתוב משהו מועיל - למשל קוד שמוצא ומדפיס את האלמנט הכפול הראשון ברשימה:

1. רשימת הערכים תהיה ה Collection הבסיסי שלי. אפעיל עליה iter כדי להפוך אותה ל Iterator.

2. את הרשימה אשלח ל itertools.tee שישכפל אותה לשני איטרטורים.

3. אחד מהם אשלח ל better_nodups כך שלא יכיל כפילויות.

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

הנה הקוד לאמיצים:

import itertools
from collections import OrderedDict

# 1. Create a base list
# (note 2 is the first duplicate item)
base = iter([1, 2, 3, 5, 4, 11, 12, 15, 2, 10, 20, 99])

def uniq(collection):
    s = set()
    for item in collection:
        if item not in s:
            yield item

        s.add(item)

# 2. Send the list to tee
[c1, c2] = itertools.tee(base)

# 3. Remove duplicates from c2
# (though this is still a noop until we start taking elements)
c2 = uniq(c2)

# 4. Create an iterator on the pairs
# (still a no-op)
pairs = zip(c1, c2)

# 5. Find the first different element
# (still a no-op, until someone will request its next)
duplicates = itertools.dropwhile(lambda p: p[0] == p[1], pairs)

# 6. Print the first duplicate running everything
print(next(duplicates)[0])

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