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

יש עוד שימוש נפלא בProxies שטרם ציינתי. השימוש הוא ביצירת Mockים.

למי שלא מכיר, Mockים הם אובייקטים שאנחנו בד”כ משתמשים בהם בUnit Testים על מנת לדמות התנהגות של תלות חיצונית.

למשל, נניח שיש לנו מחלקה שאמורה להתחבר לDatabase ולשלוף טבלאות. את החיבור לDatabase היא מבצעת באמצעות איזשהו ממשק, למשל

1
2
3
4

public interface IDataProvider
{
    DataTable RetrieveBySql(string query);
}

כעת אנחנו מעוניינים לבדוק את המחלקה שמשתמשת בממשק הזה.

בUnit Test לא נרצה להתחבר לDatabase, מכמה סיבות:

• זו פעולה שלוקחת זמן
• זו פעולה שיכולה להכשל

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

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

למחלקה שנממש קוראים בד"כ Mock. כאמור Mockים משמשים בעיקר בUnit Testים.

עד כה דיברנו על מה זה Mock באופן כללי.

עכשיו לבעיה: מה קורה אם יש לנו הרבה ממשקים שאנחנו צריכים לעשות להם Mock? מה אם יש להם הרבה פונקציות ואנחנו לא מעוניינים לממש את כולן, אלא רק את חלקן?

יוצא שאנחנו כותבים הרבה מאוד Mockים, ויכול להיות שMock מסוים שהשקענו בו הרבה עבודה משמש אותנו בUnit Test בודד.

כאן Proxyים נכנסים לתמונה:

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

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

למעשה, אין צורך להמציא את הגלגל – יש Frameworkים מצוינים (שאפילו מתבססים על DynamicProxy) שמאפשרים את היכולת הזאת.

אחד הFrameworkים האלה הוא Moq המאפשר לנו לעשות את זה באמצעות Expression Trees של Framework 3.5 (ראו גם טיפים 173-181)

למשל דוגמה ליצירת Mock:

1
2
3
4
5
6
7

Mock<IFoo> mock = new Mock<IFoo>();
string outString = "ack";
// TryParse will return true, and the out argument will return "ack", lazy evaluated
mock.Setup(foo => foo.TryParse("ping", out outString))
    .Returns(true);

כעת נוכל לקבל אובייקט שמממש IFoo ע"י:

1
2
3
4
5
6
7

IFoo mockObject = mock.Object;
string outValue;
bool parsed =
    mockObject.TryParse("ping", out outValue); // true
// outValue == "ack"

בקיצור, Moq מומלץ בחום לכל מי שנאלץ לכתוב Unit Testים 😃

לזכור ולא לשכוח.

אינו פעם שעברה איך ניתן לממש Proxy כלשהו בעזרת RealProxy של הFramework.

למרבה הצער, ראינו שזה מלווה בקריאות איטיות מאוד למתודות. (פי 500 יותר איטיות בערך)

קיימת עוד דרך לממש Proxy דינאמי והיא באמצעות Reflection.Emit.

Reflection.Emit היא בעצם ספריה המאפשרת לנו לקמפל קוד בזמן ריצה. הדבר הזה כולל בין השאר את הדברים הבאים:

• יצירת מתודות בזמן ריצה - זה קשור לקימפול Expressionים בזמן ריצה. למעשה Expressionים משתמשים בReflection.Emit כדי להתקמפל. ראו גם טיפים על Expressionים: טיפים מספר 173-181.
• יצירת טיפוסים בזמן ריצה.

די קשה להשתמש בReflection.Emit, כי שימוש בזה מצריך כתיבת IL שכנראה רובנו לא דוברים אותה באופן שוטף.

עם זאת, השימוש בReflection.Emit מאפשר לעשות דברים נפלאים.

למשל, נוכל ליצור טיפוס בזמן ריצה שמממש איזשהו ממשק ומפנה כל קריאה אליו לאיזשהו Delegate.

כך בעצם נוכל לממש Proxy בעצמנו בצורה דינאמית.

מאחר ואני לא מבין חובבי כתיבת IL, אני לא אראה כאן איך כותבים דבר כזה.

במקום זאת, אני אספר על איזשהו פרויקט Open source שנקרא DynamicProxy של Castle. זוהי ספריה שעושה את כל התהליך שדיברתי עליו למעלה:

היא יודעת ליצור טיפוס המממש ממשק בצורה של Proxy, כלומר לקרוא למתודה מתאימה בכל קריאה למתודה של הממשק.

איך משתמשים בזה? זה די פשוט: צריך לממש את הממשק ששמו IInterceptor, שם נכתוב מה אנחנו רוצים לעשות כשתקרא מתודה כלשהי (זו בעצם הפונקציה שעושים אליה Proxy, בדומה לInvoke שראינו פעם שעברה):

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class ConsoleWriterInterceptor : IInterceptor
{
    public void Intercept(IInvocation invocation)
    {
        ParameterInfo[] parameters = invocation.Method.GetParameters();
        for (int i = 0; i < parameters.Length; i++)
        {
            Console.WriteLine("{0} := {1}",
                              parameters[i].Name,
                              invocation.Arguments[i]);
        }
    }
}

הממשק IInvocation נותן לנו גישה לכל המידע של הפונקציה: הפרמטרים איתם נקראה, הMethodInfo וכו’ (ראו גם טיפ מספר 345).

בנוסף, אנחנו יכולים לקבוע בו עוד דברים, כמו ערכי ההחזר של הפונקציה (כולל פרמטרים שהם out וref), הException שהפונקציה מחזירה וכו’.

כעת כדי להשתמש בIInterceptor שכתבנו כדי ליצור Proxy משלנו:

1
2
3
4
5
6
7
8
9
10
11
12
13

ProxyGenerator generator = new ProxyGenerator();
IBank bank =
    generator.CreateInterfaceProxyWithoutTarget<IBank>
    (new ConsoleWriterInterceptor());
bank.Deposit("stam", 100);
//id := stam
//amount := 100
bank.Deposit("yossi", 1024);
//id := yossi
//amount := 1024

די מגניב!

מה לגבי ביצועים? ראינו פעם שעברה שקריאה לProxy ריק עלתה פי 500 מקריאה רגילה למתודה.

כאן המצב יותר טוב. אם נערוך השוואה כמו פעם שעברה:

כפי שאנחנו רואים, גם כאן קריאה ישירה למתודה מהירה יותר מקריאה דרך DynamicProxy, אבל הפעם רק פי 17 יותר מהיר (ולא פי 500 כמו פעם שעברה).

שוב שימו לב למספר הקריאות שצריך כדי להרגיש בהבדל.

המשך יום מיופה כוח דינאמי טוב.

אפשר להמשיך את סדרת הטיפים של Proxy בשני אופנים:

הראשון הוא להתחיל לדון כיצד ניתן לממש Proxy

השני הוא להתחיל לפתוח ולחקור את העולם של Interception (זו הכללה לProxy)

אני אתחיל בסקירת שיטות למימוש Proxy.

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

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

אז מה אפשר לעשות?

הדרך הראשונה לפתור את הבעיה שנסקור היא ע”י ירושה מRealProxy. זוהי מחלקה מהFramework, שכפי שרומז שמה, מאפשרת לנו ליצור Proxyים בצורה פשוטה. כל מה שעלינו לעשות זה לרשת מRealProxy ולדרוס את המתודה ששמה Invoke:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class MyProxy : RealProxy
{
    public MyProxy(Type classToProxy) : base(classToProxy)
    {
    }
    public override IMessage Invoke(IMessage msg)
    {
        IMethodCallMessage methodCall = msg as IMethodCallMessage;
        ParameterInfo[] parameters = methodCall.MethodBase.GetParameters();
        for (int i = 0; i < parameters.Length; i++)
        {
            Console.WriteLine("{0} := {1}",
                              parameters[i].Name,
                              methodCall.Args[i]);
        }
        // No return value yet (doesn't deal with functions)
        return new ReturnMessage(null, methodCall);
    }
}

כעת כדי להשתמש בזה פשוט ניצור Instance ונקרא לפונקציה GetTransparentProxy:

1
2
3
4
5
6
7
8
9
10

MyProxy proxyProvider = new MyProxy(typeof(IBank));
IBank bank = (IBank)proxyProvider.GetTransparentProxy();
bank.Deposit("stam", 100);
//id := stam
//amount := 100
bank.Deposit("yossi", 1024);
//id := yossi
//amount := 1024

מגניב ביותר!

אפשר גם לשנות את ערכי ההחזר (כולל הפרמטרים שהם out), ולקבוע Exception וכו’ בעזרת הממשק IMethodReturnMessage (יש טיפוס שנקרא ReturnMessage שמממש אותו שהשתמשנו בו)

איך הדבר הזה עובד?

למעשה יש איזשהו טיפול בCLR שבודק שאם אובייקט מסוים הוא RealProxy, אז מתבצעת הקריאה למתודה לא בצורה הקלאסית שאנחנו מכירים: כל המידע שהועבר לפונקציה בקריאה מועבר לאיזשהו IMessage המכיל את התוכן המתאים, ונקראת הפונקציה Invoke עם הIMessage הנ"ל.

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

יוצא שהקריאות של דרך RealProxy הן יותר מפי 500 יותר איטיות מקריאות למתודה.

מבחינת ביצועים זה לא להיט, אבל בהחלט יש שימוש בזה בFramework. עד כדי כך, שאפילו הProxyים שאנחנו מקבלים מChannelFactory של WCF ממומשים באמצעות RealProxy.

שבוע מיופה כוח טוב!

בהמשך לפעמים הקודמות,

עוד שימוש שיש לProxies של Interface הוא Remoting:

נניח שיש לנו איזשהו ממשק, למשל:

1
2
3
4
5
6

public interface IBank
{
    void Deposit(string id, int amount);
    void Withdraw(string id, int amount);
    int GetAvailableBudget(string id);
}

כעת יצרנו Proxy לממשק, כלומר יש לנו מחלקה שמנתבת את כל הפונקציות של הממשק לפונקציה בודדת.

1
2
3

private void Handle(MethodCallInfo methodCallInfo)
{
}

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

איך נעשה את זה? נצטרך להמיר את הMethodCallInfo לאיזשהו אובייקט שאפשר להעביר ברשת.

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

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

בפונקציה שאליה נכנס (Handle) נצטרך לבצע את ההמרה של הMethodCallInfo להודעה מתאימה, לשלוח את ההודעה, לקבל את התשובה, ולהכניס לMethodCallInfo את התוצאה שחזרה/Exception שחזר.

קיימים מספר מימושים לרעיון זה, למשל WCF הוא Framework המאפשר ליצור Proxy שיודע לשלוח הודעות SOAP לService מרוחק ולהחזיר תשובה.

המשך יום מיופה כוח טוב.

[מבוסס על הפוסט הזה]
למי שיצא לעבוד עם WPF, יצא בוודאי להתקל בXAML (Extensible Application Markup Language) – זהו תקן שמשחק תפקיד חשוב בWPF ומאפשר לנו לבנות יישומים בצורה שניתנת להרחבה בצורה פשוטה.

רובנו לא מכירים, אבל החל מFramework 4.0, נוספה תמיכה בתקן דומה שנקרא CSAML (C# Application Markup Language, נהגה לעתים כScammel) – זהו תקן המהווה אלטרנטיבה לSyntax של C# המבוסס על Xmlו-XAML. למעשה, CSAML משתמש בSyntax של הProperty Element של XAML בשביל לייצג הצהרות מסובכות.

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

כעת נראה מספר דוגמאות לשימוש בCSAML:

הסתכלו על התוכנית Hello World עם הSyntax המיושן של C# שכולנו מכירים:

1
2
3
4
5
6
7
8
9
10

namespace MyNamespace
{
    public class MyClass
    {
        public static void Main()
        {
            Console.WriteLine("Hello, C#");
        }
    }
}

שימו לב לפורמט חסר המבנה החופשי הזה – לא ניתן לסבול אותו בסביבות מחשוב מודרניות: תסתכלו על רצף המילים "public static void Main". מהן המילים האלו? איך הן קשורות אחת לשנייה? אין שום דרך לדעת. מהבעיות הללו התחמקו בימי ALGOL, אבל כיום כבר לא ניתן להתעלם מהן.

מצד שני, הסתכלו על הבהירות של התוצאות כאשר הקוד השקול מבוטא בSyntax שמייצג דיוק והתחשבות. זהו קובץ CSAML עם ההצהרות של הnamespace הנוכחי:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

<CsamlFile xmlns="http://schemas.microsoft.com/winfx/2010/xaml/csaml"
           xmlns:x="http://schemas.microsoft.com/winfx/2010/xaml">
  <NamespaceDeclaration Identifier="MyNamespace">
    <ClassDeclaration Identifier="MyClass"
                      Access="Public">
      <MethodDeclaration Identifier="Main"
                         Access="Public"
                         Modifier="Static"
                         ReturnType="{x:Type void}">
        <InvocationExpression
          MemberAccess="System.Console.WriteLine">
          <InvocationExpression.ArgumentList>
            <Literal Type="{x:Type string}"
                     Value="Hello, CSAML! " />
          </InvocationExpression.ArgumentList>
        </InvocationExpression>
      </MethodDeclaration>
    </ClassDeclaration>
  </NamespaceDeclaration>
</CsamlFile>

כפי שבוודאי תשימו לב, רוב שמות הElementים כן מבוססים על הספציפיקציה של שפת C#, כך שכל מתכנת C# שמכיר את השמות מהספציפיקציה, יכול להתחיל לתכנת בCSAML באופן מיידי.

ע"י כך שנשענת על המבנה ההיררכי של Xml, שפת CSAML מסוגלת לוותר על על הסוגריים המסולסלים, הסוגריים המרובעים וסוגריים שמאפיינים את הSyntax המוכר של C#. כפי ששמתם לב בקובץ לעיל, סוגריים מסולסלים שמורים לשימוש שלהם בהרחבה של XAML, כמו x:Type.

למעשה, CSAML מסוגלת להעיף כל Symbol שקיים בSyntax המוכר של C#. למשל, שימו לב להשמה הבאה בSyntax הישן של C#:

1

A = 5 * (B + 27 * C);

בלי יותר מדי בעיות, הSyntax הזה מתרגם לCSAML הזה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

<ExpressionStatement>
  <Assignment LValue="A">
    <Assignment.Expression>
      <MultiplicationExpression>
        <Multiplication.Multiplier>
          <Literal Type="{x:Type Int32}"
                   Value="5" />
        </Multiplication.Multiplier>
        <Multiplication.Multiplicand>
          <AdditionExpression Augend="B">
            <AdditionExpression.Addend>
              <Multiplication.Multiplier>
                <Literal Type="{x:Type Int32}"
                         Value="27" />
              </Multiplication.Multiplier>
              <MultiplicationExpression Multiplicand="C"/>
            </AdditionExpression.Addend>
          </AdditionExpression>
        </Multiplication.Multiplicand>
      </MultiplicationExpression>
    </Assignment.Expression>
  </Assignment>
</ExpressionStatement>

היתרון של ייצוג כזה ברור:

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

יש סיכוי גדול יותר ששגיאות קימפול לא יופיעו.

הקומפיילר הופך להיות הרבה יותר יעיל, בגלל שכל הצהרה, "פורסרה" ע"י המתכנת.

הנה עוד דוגמה לבעיה האבסורדית האולי הכי ידועה לשמצה בכל תכנות C# מסורתי: לולאת הfor:

1
2
3
4
5
6
7

for (i = 0, j = 0; i < 1000; i++)
{
    if (IsPrime(i))
    {
        j++;
    }
}

בCSAML האוסף של הSymbolים והנקודות-פסיק הנ"ל ננטש לטובת מבנה יפהפה שיכול לגרום למתכנת המודרני להתמוגג מאושר:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

<ForLoop>
  <ForLoop.Initializer>
    <StatementExpressionList>
      <Assignment LValue="i">
        <Assignment.Expression>
          <Literal Type="{x:Type Int32}"
                   Value="0" />
        </Assignment.Expression>
      </Assignment>
    </StatementExpressionList>
  </ForLoop.Initializer>
  <ForLoop.Condition>
    <BooleanExpression>
      <LessThanExpression LeftSide ="i">
        <LessThanExpression.RightSide>
          <Literal Type="{x:Type Int32}"
                   Value="1000" />
        </LessThanExpression.RightSide>
      </LessThanExpression>
    </BooleanExpression>
  </ForLoop.Condition>
  <ForLoop.Iterator>
    <StatementExpressionList>
      <PreIncrementExpression Identifier="i" />
    </StatementExpressionList>
  </ForLoop.Iterator>
  <ForLoop.EmbeddedStatement>
    <IfStatement>
      <IfStatement.Condition>
        <BooleanExpression>
          <InvocationExpression MemberAccess="IsPrime">
            <InvocationExpression.ArgumentList>
              <Variable Identifier="i" />
            </InvocationExpression.ArgumentList>
          </InvocationExpression>
        </BooleanExpression>
      </IfStatement.Condition>
      <IfStatement.EmbeddedStatement>
        <StatementList>
          <PreIncrementExpression Identifier="j" />
        </StatementList>
      </IfStatement.EmbeddedStatement>
    </IfStatement>
  </ForLoop.EmbeddedStatement>
</ForLoop>

בהמשך נראה עוד שימושים מדהימים לCSAML.

בסופו של הדבר הכוח האדיר של שפה זו היא שהיא מאפשרת לנו להרחיב ולתקן את האפליקציה שלנו ללא שינוי קוד!

שבוע סקמלי טוב.

בהמשך לפעם שעברה,

הפעם נדבר טיפה יותר על מה היינו רוצים מProxy שאנחנו מממשים:

כאמור – כאשר אני אומר Proxy, אני מתכוון למימוש של ממשק שמקיים שכל המתודות פונות בסופו של דבר למתודה ספציפית.

היינו מצפים שלמתודה הזאת נקבל את המידע הבא:

• המתודה שהופעלה – אבל אנחנו רוצים יותר מאת השם, אלא את הOverload המתאים שנקרא. כלומר, כנראה את הMethodInfo של המתודה המתאימה שהופעלה.
• הפרמטרים שאיתם נקראה המתודה – מדובר במבנה המכיל את הפרמטרים שנשלחו למתודה. ניתן לשלוח את זה בתור מיפוי כלשהו, או בתור מערך שאליו ניגש לפי הסדר של הפרמטרים בMethodInfo כדי למצוא פרמטר ספציפי.
• בנוסף, היינו מצפים לקבל את הפרמטרים הגנריים של המתודה, אם יש כאלה. אותם אנחנו יכולים לקבל גם בתוך הMethodInfo בהנחה שקראו לMakeGenericType.

בנוסף, היינו מצפים ליכולות הבאות:

• לקבוע את ערך ההחזר של המתודה שהופעלה
• לשנות את הפרמטרים שהם ref או out
• לזרוק Exception ביציאה מהפונקציה

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

יש כמה מימושים כאלה, ביניהם:

• MethodCall שנמצא בRemoting
• IInvocation שנמצא בOpen Source בשם DynamicProxy של Castle

בפעמים הבאות נמשיך לדבר על Proxyים ובהמשך נראה את השימושים שהבטחתי

המשך יום מיופה כוח טוב.

אני מתחיל היום סדרה חדשה שמתעסקת בProxies ומה שמסביב.

למה אני מתכוון כשאני אומר Proxies?

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

1
2
3
4
5
6

public interface IBank
{
    void Deposit(string id, int amount);
    void Withdraw(string id, int amount);
    int GetAvailableBudget(string id);
}

אז נוכל לממש את הממשק ע"י התנהגות אחידה: כתיבת הפרמטרים למסך:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class BankProxy : IBank
{
    public void Deposit(string id, int amount)
    {
       WriteValues(new MethodCallInfo("Deposit")
                        {
                            {"id", id},
                            {"amount", amount}
                        });
    }
    public void Withdraw(string id, int amount)
    {
        WriteValues(new MethodCallInfo("Withdraw")
                        {
                            {"id", id},
                            {"amount", amount}
                        });
    }
    public int GetAvailableBudget(string id)
    {
        WriteValues(new MethodCallInfo("GetAvailableBudget")
                        {
                            {"id", id},
                        });
        return 0;
    }
    private void WriteValues(MethodCallInfo methodCallInfo)
    {
        Console.WriteLine("In method {0}", methodCallInfo.Name);
        foreach (KeyValuePair<string, object> parameter in methodCallInfo)
        {
            Console.WriteLine("Parameter {0}:{1}", parameter.Key, parameter.Value);
        }
    }
}

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

בפעמים הבאות נדבר עוד על Proxyים, נראה שימושים (מדהימים!), ונדבר על דרכים אפשריות למימוש.

שבוע מיופה כוח טוב!

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

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

נתאר את הבעיה: יש לנו מספר ממשי כלשהו המתאר זווית (לצורך העניין נגביל אותה בגודל מסוים, נגיד לבין 0 ל$ \frac{\pi}{4} $ ($ {45}^{\circ} $)) ואנחנו מעוניינים לחשב את ה$ \sin $/$ \cos $/$ \tan $ שלה. לחלופין יכול להיות שנרצה לחשב את אחת הפונקציות ההפוכות הנ”ל.

ראשית אנחנו מחשבים את $ \arctan x $ עבור x שהוא הופכי של חזקה של 2, כלומר $ \displaystyle{\arctan \frac{1}{2^k}} $ לכל הkים בתחום מסוים.

את זה אנחנו עושים ע”י שימוש בטור טיילור של $ \arctan x $: $ \displaystyle{\arctan{x} = \sum_{n = 0}^{\infty}{\frac{\left( -1 \right)^n}{2n + 1} }x^{2n+1}} $ כאשר $ |x| \le 1 $.

את החישובים האלה אנחנו שומרים בטבלה סטטית בצד (איזשהו HashTable של $ k $ ל$ \displaystyle{\arctan \frac{1}{2^k}} $)

כעת אלגוריתם CORDIC עובד כך:

אנחנו מקבלים זווית $x$ שאנחנו מעוניינים לחשב אותה.

אנחנו עובדים עם שלושה משתנים:

• $ \theta$– מייצג את הזווית שחישבנו את ה $ \cos $וה$ \sin $ שלה עד כה.
• $ \mathrm{vector} $ – מספר מרוכב בכיוון של $ \cos\theta + i \sin\theta $
• $ k $ – מספר האיטרציות שעשינו עד כה

המטרה שלנו היא לחשב את $ \mathrm{vector} $ עבור $\theta$ שקרובה מספיק ל$x$ שלנו.

את זה אנחנו עושים באופן הבא: אנחנו מתחילים עם $ \mathrm{vector} = 1 $, $ \theta = 0 $ ו$ k = 0 $.
כעת אנחנו מבצעים את הפעולות הבאות עד שהקירוב מספיק טוב לנו:

• אם $ x > \theta$:
  • $ \displaystyle{\theta := \theta + \arctan\frac{1}{2^k}} $
  • $ \displaystyle{\mathrm{vector} := \mathrm{vector} \cdot\left(1 + \frac{1}{2^k} \cdot i \right)} $
• אחרת אם $ x < \theta$:
  • $ \displaystyle{\theta := \theta - \arctan\frac{1}{2^k}} $
  • $ \displaystyle{\mathrm{vector} := \mathrm{vector} \cdot \left(1 - \frac{1}{2^k} \cdot i \right)} $
• $ k := k + 1 $

הסבר על מה שהולך כאן:

אם $ i $ היחידה המדומה, כלומר המספר המרוכב המקיים $ i^2 = -1 $, אזי מתקיים כי $ (\cos \alpha + i \sin \alpha) \cdot (\cos\beta + i \sin\beta) = \cos(\alpha + \beta) + i \sin(\alpha + \beta) $

כלומר – כפל של שני וקטורים במישור המרוכב הוא וקטור בכיוון סכום הכיוונים שלהם.

נשים לב של $ 1 + \frac{1}{2^k} \cdot i $ יש את אותו כיוון כמו ל$ \cos\arctan\frac{1}{2^k} + i \cdot \sin\arctan\frac{1}{2^k} $. (כי $ \frac{\frac{1}{2^k}}{1} = \frac{1}{2^k} $ ולכן יש להם אותו $ \arctan $)

מה שאנחנו בעצם עושים זה מנסים להתקרב לזווית x כמה שיותר ע”י הוספה או הסרה של$ \displaystyle{ \arctan\frac{1}{2^k} } $ לפי הצורך בכל שלב. בסוף אנחנו מקבלים וקטור עם זווית מאוד קרובה לx. כעת אנחנו יכולים לחשב את $ \sin $ ואת ה$ \cos $ שלו ע”י נירמולו – כלומר ע”י חלוקה בערך המוחלט שלו.

הבעיה בפתרון זה – היא שחילוק יכול להרוס לנו את הדיוק של הפעולות שביצענו עד כה. במקום זאת ניתן להשתמש בטריק הבא: נניח וביצענו אינסוף פעולות, אז קיבלנו ערך מוחלט של: $ \left( 1 + \frac{1}{2^0} \cdot i \right) \cdot \left( 1 + \frac{1}{2^1} \cdot i \right) \cdot \left( 1 + \frac{1}{2^2} \cdot i \right) \cdot \left( 1 + \frac{1}{2^3} \cdot i \right) \cdot \dots $

כלומר הערך המוחלט יהיה $ \sqrt{\left( 1 + \frac{1}{2^{2 \cdot 0}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 1}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 2}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 3}} \right) \cdot \dots} $.

בסוף היינו רוצים לחלק בו, כלומר להכפיל בהופכי שלו: $ \displaystyle{\frac{1}{\sqrt{\left( 1 + \frac{1}{2^{2 \cdot 0}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 1}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 2}} \right) \cdot \left( 1 + \frac{1}{2^{2 \cdot 3}} \right) \cdot \dots}}} $

מסתבר שזה מתכנס לקבוע $ K \approx 0.6072529350088812561694 $, כך שאנחנו יכולים לשמור אותו בצד (עם שאר הקבועים שחישבנו מראש) ובכל פעם להכפיל בו בסוף התהליך.

כאן יש איזשהו מימוש פשוט של CORDIC עם Complex (ראו גם טיפ מספר 128).

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public static double Sin(double x)
{
    Complex vector = 1;
    double theta = 0;
    Complex oldVector = 0;
    
    for (int k = 0; oldVector != vector; k++)
    {
        oldVector = vector;
        double power = 1/Math.Pow(2, k); // Get it faster..
        double powerAngle = Math.Atan(power); // Get it from a hash..
        if (x > theta)
        {
            theta += powerAngle;
            vector *= (1 + power * Complex.ImaginaryOne);
        }
        else if (x < theta)
        {
            theta -= powerAngle;
            vector *= (1 - power * Complex.ImaginaryOne);
        }
    }
    vector /= Complex.Abs(vector); // Multiply by a constant instead.
    return vector.Imaginary;
}

היתרון של CORDIC על אלגוריתמים אחרים הוא שהוא מאוד מהיר בעולם בו אין כפל - אם תסתכלו על האלגוריתם, הוא למעשה משתמש רק בחיבור/חיסור, כפל בחזקה של 2 (שהוא מאוד זול – הוא Shift) וכפל חד פעמי בתוצאה. (אמנם נראה כאן שיש כפל, אבל אפשר לשים לב ש$ \left(1+ai\right)\left(1+bi\right)=1-ab+i\left(a+b\right) $ ואם a או b חזקות של 2 אז המכפלה היחידה שיש פה היא Shift)

תוכלו לקרוא על זה עוד כאן.

סופ"ש נומרי טוב!

לכבוד יום הפאי – נדבר היום על נוסחת BBP לחישוב פאי.

קיימות לא מעט נוסחאות המחשבות את פאי המבוססות על אנליזה מתמטית.

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

ב1995 גילה בחור בשם Simon Plouffe באמצעות תוכנת מחשב שכתב, נוסחה מעט מסובכת לחישוב פאי:

$ \displaystyle{\sum_{k = 0}^{\infty}\left[ \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) \right]} $

היתרון הגדול של הנוסחה הוא שהיא מאפשרת לחשב את הספרה הnית של פאי אחרי הנקודה ללא חישוב קודמותיה.

אבל יש פה קאץ’. הקאץ’ הוא שנקבל את הספרה הnית של הייצוג של פאי בבסיס 16. (הקסה-דצימלי)

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

לרגל יום הפאי, יכתב כאן קוד שמחשב את הספרה הnית של פאי אחרי הנקודה בבסיס 16 לפי נוסחת BBP. שלבי פיתוח הנוסחה (לא כל כך מסובכים) נמצאים כאן.

הקוד:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

public static char PiDigit(int digitIndex)
{
    digitIndex--;
    double approximation =
        4 * PiSeries(1, digitIndex) -
        2 * PiSeries(4, digitIndex) -
        PiSeries(5, digitIndex) -
        PiSeries(6, digitIndex);
    approximation = approximation % 1.0;
    approximation = (1.0 + approximation) % 1.0;
    long digit = (long)(16 * approximation) % 16;
    return digit.ToString("X").First();
}
public static double PiSeries(int remainder, int digitIndex)
{
    return PiFiniteSeries(remainder, digitIndex) + PiInfiniteSeries(remainder, digitIndex);
}
private static double PiFiniteSeries(int remainder, int digitIndex)
{
    double sum = 0;
    for (int i = 0; i <= digitIndex; i++)
    {
        long currentNum = 8 * i + remainder;
        sum += PowerModulo(16, digitIndex - i, currentNum) / (double)currentNum;
        sum = sum % 1.0;
    }
    return sum;
}
private static double PiInfiniteSeries(int remainder, int digitIndex)
{
    double sum = 0;
    double previousSum = 1;
    for (long i = digitIndex + 1; sum != previousSum; i++)
    {
        long currentNum = 8 * i + remainder;
        previousSum = sum;
        sum += Math.Pow(16, digitIndex - i) / currentNum;
    }
    return sum;
}
public static long PowerModulo(long a, long n, long m)
{
    long result = 1;
    long currentPower = a;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result *= currentPower;
            result = result % m;
        }
        currentPower *= currentPower;
        currentPower = currentPower % m;
        n /= 2;
    }
    return result;
}

בגדול: מנסים לחשב את הספרה הראשונה אחרי הנקודה של $ \pi \cdot 16^n $. את זה עושים ע"י חישוב שני טורים: אחד סופי ואחד אינסופי. בדרך מתעלמים מהחלק השלם של כל המספרים (שהרי מעניין אותנו רק הספרה הראשונה אחרי הנקודה של המספר)

שימו לב שגם יש פה אלגוריתם חישוב חזקה מודולו מספר שדומה לאלגוריתם שראינו פעם (ע"י פירוק המעריך לבינארית)

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

המשך יום פאי שמח!

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

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

אנחנו רוצים לחשב את השורש של המספר $ a $.

הגדר $x_0$ כניחוש הראשוני של השורש של המספר. בכל שלב הגדר את $x_{n + 1}$ כך:

$ \displaystyle{x_{n + 1} = \frac{1}{2} \left( \frac{a}{x_n} + x_n \right)} $

קרי: הגדר את $x_{n + 1}$ בתור הממוצע של $ x_n $ ו$ \displaystyle{\frac{a}{x_n}} $.

השיטה הזאת מתכנסת לשורש של a בצורה מאוד מהירה (למי שלמד אנליזה נומרית – ההתכנסות היא ריבועית, כלומר באיטרציה ה$ n $ יש פוטנציאלית $ 2^n$ ספרות מדויקות אחרי הנקודה)

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

אנחנו רוצים לחשב שורש של פונקציה $ f(x) $, כלומר למצוא $ x_0$ כך ש $ f(x_0) = 0 $.

הגדר את $x_0$ להיות ניחוש לשורש של הפונקציה. בכל שלב הגדר את $x_{n + 1}$ כך:

$ \displaystyle{x_{n + 1} = x_n - \frac{f(x_n)}{f’(x_n)}} $

השיטה בתנאי התחלה מסוימים מתכנסת לשורש של המספר, ובמקרים מסוימים (ש($ f’(x_0) $ הוא לא 0 למשל), מתקיים שההתכנסות ריבועית.

אם נגדיר $ f(x) = x^2 - a $ נקבל בדיוק את שיטת הרון.

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

המשך יום נומרי טוב!