Thread-safe Random

2015-07-20

היי,

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

ברגע שהClient מצליח להתחבר לServer, הServer צריך להקצות לו מזהה ייחודי (הנקרא גם SessionId) - זהו מספר רנדומלי שלם בין 0 ל$ 2^{50} $ (לא כולל הקצוות. יכול להיות שהקצה הוא לא בדיוק $ 2^{50} $ אלא משהו שאני לא זוכר כרגע, אבל זה לא מהותי להמשך הפוסט).

אילוסטרציה:

public class Server
{
    private readonly Random mRandom = new Random();
    private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
    private const long MAX_RANDOM_SIZE = 2 >> 50;
    public void OnNewClient(IConnection connection)
    {
        ClientProxy clientProxy = new ClientProxy(connection);
        clientProxy.SessionId = mRandom.Next(MAX_RANDOM_SIZE);
        mClientContainer.Add(clientProxy);
        
        // ...
    }
    // ...
}

(פישטתי קצת את הסיפור, כעקרון צריך שהClientContainer יבחר את הSessionId, באופן שיצא חד-חד-ערכי. בנוסף, אין Overload לRandom שמקבל long, אבל אנחנו נתעלם מהבעיות האלה כיוון שהן לא מהותיות בהקשר של הבעיה)

הספריה כמובן מקבלת את הClientים בצורה א-סינכרונית, מה שאומר שכשClient מתחבר, מתעורר Thread מהThreadPool (באמצעות מנגנון הIOCP) ומתחיל לטפל בו. בדרך כלל הסיפור עבד בסדר גמור, אבל במקרי קיצון (מספר גדול מאוד של קליינטים או הרבה חיבורים/ניתוקים בו זמנית), יצא מצב שכל הקליינטים שהתחברו קיבלו את אותו SessionId שערכו היה 0.
(למי שקורא את מה שכתוב בסוגריים - במימוש הראשון לא וידאתי שאכן הSessionId חד-חד-ערכי. במידה והייתי מוודא זאת, במקום לקבל SessionId=0 בכל הקליינטים, השרת היה נתקע בלולאות אינסופיות)

דיבגתי את הקוד וראיתי שRandom מחזיר במקרה קיצון זה 0 תמיד. חיפשתי באינטרנט על כך, ומצאתי פוסט בבלוג של MSDN מ2009. בפוסט זה מציינים שRandom אינו Thread-safe והוא ממומש בצורה שגורמת לכך שאם הוא נקרא ממספר Threadים במקביל, הוא יחזיר 0.
בפוסט זה מציעים שני פתרונות לבעיה זו. הפתרון הראשון שהוא מאוד פשוט הוא להשתמש במנגנון נעילה:

public class Server
{
    private readonly Random mRandom = new Random();
    private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer(
    private readonly object mLock = new object();
    private const long MAX_RANDOM_SIZE = 2 >> 50;
    public void OnNewClient(IConnection connection)
    {
        ClientProxy clientProxy = new ClientProxy(connection);
        lock (mLock)
        {
            clientProxy.SessionId = mRandom.Next(MAX_RANDOM_SIZE);
        }
        mClientContainer.Add(clientProxy);
        
        // ...
    }
    // ...
}

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

פתרון נוסף שמציינים בפוסט זה הוא שימוש בThreadStatic - למי שלא מכיר, זהו משתנה סטטי הנוצר פר Thread הפתרון הראשוני יראה כך:

public class Server
{
    [ThreadStatic]
    private static Random mRandom = GetRandom();
    private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
    private const long MAX_RANDOM_SIZE = 2 >> 50;
    public void OnNewClient(IConnection connection)
    {
        ClientProxy clientProxy = new ClientProxy(connection);
        Random random = GetRandom();
        clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
        mClientContainer.Add(clientProxy);
        
        // ...
    }
    private static Random GetRandom()
    {
        if (mRandom == null)
        {
            mRandom = new Random();
        }
        return mRandom;
    }
    // ...
}

למי ששואל מדוע יצרתי פונקציה בשם GetRandom, זה מכיוון שהField Initializer לא נקרא פר Thread, אלא בפעם הראשונה בלבד.

פתרון טיפה יותר טוב הוא לשנות את הSeed פר Thread:

public class Server
{
    [ThreadStatic]
    private static Random mRandom;
    private readonly object mLock = new object();
    private readonly Random mSeedGenerator = new Random();
    private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
    private const long MAX_RANDOM_SIZE = 2 >> 50;
    public void OnNewClient(IConnection connection)
    {
        ClientProxy clientProxy = new ClientProxy(connection);
        Random random = GetRandom();
        clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
        mClientContainer.Add(clientProxy);
        
        // ...
    }
    private Random GetRandom()
    {
        if (mRandom == null)
        {
            int seed;
            lock (mLock)
            {
                seed = mSeedGenerator.Next();
            }
            mRandom = new Random(seed);
        }
        return mRandom;
    }
    // ...
}

שימו לב שאנחנו נועלים רק בפעם הראשונה בכל Thread כשנוצר הRandom הפנימי.
הבעיה בפתרונות אלה שמוצעים בפוסט המדובר היא שמדובר במשתנה סטטי. עדיף לעבוד עם משתנה שהוא גם פר Instance.

למזלנו קיים בFramework טיפוס בשם ThreadLocal המאפשר את הסיפור הזה. (למי שלא מכיר, זהו טיפוס שעוטף את LocalThreadStorage בצורה נוחה)

public class ThreadSafeRandom
{
    private readonly ThreadLocal<Random> mRandom;
    private readonly object mLock = new object();
    private readonly Random mSeedGenerator = new Random();
    public ThreadSafeRandom()
    {
        mRandom = new ThreadLocal<Random>(() => GetRandom());
    }
    private Random GetRandom()
    {
        int seed;
        lock (mLock)
        {
            seed = mSeedGenerator.Next();
        }
        Random random = new Random(seed);
        return random;
    }
    public Random Random
    {
        get
        {
            return mRandom.Value;
        }
    }
}
public class Server
{
    private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
    private readonly ThreadSafeRandom mThreadSafeRandom = new ThreadSafeRandom();
    private const long MAX_RANDOM_SIZE = 2 >> 50;
    public void OnNewClient(IConnection connection)
    {
        ClientProxy clientProxy = new ClientProxy(connection);
        Random random = mThreadSafeRandom.Random;
        clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
        mClientContainer.Add(clientProxy);
        
        // ...
    }
    // ...
}

ככה גם העברנו את הקוד שמטפל בRandom בצורה Thread-safe למחלקה חיצונית, כך שאנחנו יכולים לעשות לה Reuse, וגם המשתנה הוא באמת per-instance.

המשך יום עם אקראיות שהיא לא קבועה טוב

LibLog

2015-03-05

Logging

מדי פעם יוצא לנו לכתוב ספריות Reusable. (נקרא מדי פעם גם "תשתיות תוכנה")

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

לצערנו אין בFramework כלי Log סביר, ולכן בדרך כלל אנו פונים לספריה חיצונית שעושה זאת בצורה מצטיינת. בד”כ log4net היא הספריה הנבחרת לצרכים אלה. אלא שלעתים מתכנת המשתמש בספריה שלנו משתמש כבר בתשתית Logים אחרת. (למשל NLog, Enterprise Library וכו’)

הדבר הזה מכריח את המשתמש להוסיף Reference לספריית Logם של הספריה, ומכריחה אותו בדרכים לא דרכים לגרום לספריית הLogים של הספריה להשתמש בספריית הLogים של האפליקציה, כדי שהLogים ירשמו למקומות הנכונים.

למרבה המזל, הדבר אפשרי, מאחר ותשתית Logים המכבדת את עצמה בד”כ מאפשרת מנגנון של Appenderים - מקומות אליהם לכתוב את הLog, ולכן ניתן ליצור Appender שיפנה למנגנון Logים אחר.

היו בעבר כבר כמה ניסיונות לגשר על פער זה: הרבה ספריות מכילות ממש אבסטרקטי לLog לו יש מימושים בDllים חיצוניים, למשל לCastle יש ממשק בשם ILogger שנראה כך:

public interface ILogger
{
    bool IsDebugEnabled { get; }
    bool IsErrorEnabled { get; }
    bool IsFatalEnabled { get; }
    bool IsInfoEnabled { get; }
    bool IsWarnEnabled { get; }
    ILogger CreateChildLogger(String loggerName);
    void Debug(String message);
    void Debug(Func<string> messageFactory);
    void Debug(String message, Exception exception);
    void DebugFormat(String format, params Object[] args);
    void DebugFormat(Exception exception, String format, params Object[] args);
    void DebugFormat(IFormatProvider formatProvider, String format, params Object[] args);
    void DebugFormat(Exception exception, IFormatProvider formatProvider, String format, params Object[] args);
    void Error(String message);
    void Error(Func<string> messageFactory);
    void Error(String message, Exception exception);
    void ErrorFormat(String format, params Object[] args);
    void ErrorFormat(Exception exception, String format, params Object[] args);
    void ErrorFormat(IFormatProvider formatProvider, String format, params Object[] args);
    void ErrorFormat(Exception exception, IFormatProvider formatProvider, String format, params Object[] args);
    void Fatal(String message);
    void Fatal(Func<string> messageFactory);
    void Fatal(String message, Exception exception);
    void FatalFormat(String format, params Object[] args);
    void FatalFormat(Exception exception, String format, params Object[] args);
    void FatalFormat(IFormatProvider formatProvider, String format, params Object[] args);
    void FatalFormat(Exception exception, IFormatProvider formatProvider, String format, params Object[] args);
    void Info(String message);
    void Info(Func<string> messageFactory);
    void Info(String message, Exception exception);
    void InfoFormat(String format, params Object[] args);
    void InfoFormat(Exception exception, String format, params Object[] args);
    void InfoFormat(IFormatProvider formatProvider, String format, params Object[] args);
    void InfoFormat(Exception exception, IFormatProvider formatProvider, String format, params Object[] args);
    void Warn(String message);
    void Warn(Func<string> messageFactory);
    void Warn(String message, Exception exception);
    void WarnFormat(String format, params Object[] args);
    void WarnFormat(Exception exception, String format, params Object[] args);
    void WarnFormat(IFormatProvider formatProvider, String format, params Object[] args);
    void WarnFormat(Exception exception, IFormatProvider formatProvider, String format, params Object[] args);
}

יש גם פרויקט ממש מגניב בשם Common.Logging שכתב Appenderים המאפשרים להמיר כתיבה לכל תשתית Logים מוכרת לתשתית Logים מוכרת אחרת. הם אפילו תומכים במספר גרסאות של תשתיות logים, למשל הם מאפשרים לכתוב מגרסה 1.1 של log4net לגרסה 1.2 של log4net!

אלא שכל הפתרונות הנ”ל לוקים בבעיה ההתחלתית: אנו מכריחים את המשתמש להוסיף Reference לתשתית Logים שהוא לא רוצה להשתמש בה ישירות.

אז על מה הטיפ? מסתבר שיש פרויקט בשם LibLog הפותר את הבעיה הזו. השימוש הוא כנ”ל: מתקינים מהNuGet חבילה בשם LibLog, ויש Logים בפרויקט. אלא שלא נוסף Reference:

ואז נוסף לנו קובץ cs לcsproj:

עם namespace בשם SuperLibrary.Logging (כאשר SuperLibrary הnamespace של הספריה שלנו). קובץ זה מכיל הרבה ממשקים ומימושים שלהם.

בקובץ זה יש מחלקה בשם LogProvider תחת הnamespace הנ”ל המספק ממשק בשם ILog שנראה כמו לוג סטנדרטי:

/// <summary>
/// Simple interface that represent a logger.
/// </summary>
public interface ILog
{
    /// <summary>
    /// Log a message the specified log level.
    /// </summary>
    /// <param name="logLevel">The log level.</param>
    /// <param name="messageFunc">The message function.</param>
    /// <param name="exception">An optional exception.</param>
    /// <param name="formatParameters">Optional format parameters for the message generated by the messagefunc. </param>
    /// <returns>true if the message was logged. Otherwise false.</returns>
    /// <remarks>
    /// Note to implementers: the message func should not be called if the loglevel is not enabled
    /// so as not to incur performance penalties.
    /// 
    /// To check IsEnabled call Log with only LogLevel and check the return value, no event will be written.
    /// </remarks>
    bool Log(LogLevel logLevel, Func<string> messageFunc, Exception exception = null, params object[] formatParameters );
}

כעת ניתן להשתמש במחלקה זו: קבלת Log:

1	private ILog mLog = LogProvider.GetLogger(typeof(MyReusableClass));

ואז כתיבה לLog:

1	mLog.Info("Hello log!");

אבל איך עובדת הכתיבה לLog? הכתיבה עובדת עם ספריה פופולרית, בהנחה והReference שלה זמין. איך זה עובד? הספריה בודקת בReflection האם אחת מהספריות הפופולריות זמינה ובמידה וכן, היא משתמשת בה בReflection. לדוגמה, כך נראה חלק מהמימוש הlog4netי של הספריה: (חתכתי את הרוב, אבל תסתכלו בקובץ)

private static Func<string, object> GetGetLoggerMethodCall()
{
    Type logManagerType = GetLogManagerType();
    MethodInfo method = logManagerType.GetMethodPortable("GetLogger", new[] { typeof(string) });
    ParameterExpression nameParam = Expression.Parameter(typeof(string), "name");
    MethodCallExpression methodCall = Expression.Call(null, method, nameParam);
    return Expression.Lambda<Func<string, object>>(methodCall, nameParam).Compile();
}
public override ILog GetLogger(string name)
{
    return new Log4NetLogger(_getLoggerByNameDelegate(name));
}
internal static bool IsLoggerAvailable()
{
    return ProviderIsAvailableOverride && GetLogManagerType() != null;
}
private static Type GetLogManagerType()
{
    return Type.GetType("log4net.LogManager, log4net");
}
public class Log4NetLogger : ILog
{
    private readonly dynamic _logger;
    internal Log4NetLogger(dynamic logger)
    {
        _logger = logger;
    }
    public bool Log(LogLevel logLevel, Func<string> messageFunc, Exception exception, params object[]
    {
        if (messageFunc == null)
        {
            return IsLogLevelEnable(logLevel);
        }
        messageFunc = LogMessageFormatter.SimulateStructuredLogging(messageFunc, formatParameters);
        if (exception != null)
        {
            return LogException(logLevel, messageFunc, exception);
        }
        switch (logLevel)
        {
            case LogLevel.Info:
                if (_logger.IsInfoEnabled)
                {
                    _logger.Info(messageFunc());
                    return true;
                }
                break;
            case LogLevel.Warn:
                if (_logger.IsWarnEnabled)
                {
                    _logger.Warn(messageFunc());
                    return true;
                }
                break;
            case LogLevel.Error:
                if (_logger.IsErrorEnabled)
                {
                    _logger.Error(messageFunc());
                    return true;
                }
                break;
            case LogLevel.Fatal:
                if (_logger.IsFatalEnabled)
                {
                    _logger.Fatal(messageFunc());
                    return true;
                }
                break;
            default:
                if (_logger.IsDebugEnabled)
                {
                    _logger.Debug(messageFunc()); // Log4Net doesn't have a 'Trace' level, so all Tra
                    return true;
                }
                break;
        }
        return false;
    }
    private bool LogException(LogLevel logLevel, Func<string> messageFunc, Exception exception)
    {
        switch (logLevel)
        {
            case LogLevel.Info:
                if (_logger.IsDebugEnabled)
                {
                    _logger.Info(messageFunc(), exception);
                    return true;
                }
                break;
            case LogLevel.Warn:
                if (_logger.IsWarnEnabled)
                {
                    _logger.Warn(messageFunc(), exception);
                    return true;
                }
                break;
            case LogLevel.Error:
                if (_logger.IsErrorEnabled)
                {
                    _logger.Error(messageFunc(), exception);
                    return true;
                }
                break;
            case LogLevel.Fatal:
                if (_logger.IsFatalEnabled)
                {
                    _logger.Fatal(messageFunc(), exception);
                    return true;
                }
                break;
            default:
                if (_logger.IsDebugEnabled)
                {
                    _logger.Debug(messageFunc(), exception);
                    return true;
                }
                break;
        }
        return false;
    }
    private bool IsLogLevelEnable(LogLevel logLevel)
    {
        switch (logLevel)
        {
            case LogLevel.Debug:
                return _logger.IsDebugEnabled;
            case LogLevel.Info:
                return _logger.IsInfoEnabled;
            case LogLevel.Warn:
                return _logger.IsWarnEnabled;
            case LogLevel.Error:
                return _logger.IsErrorEnabled;
            case LogLevel.Fatal:
                return _logger.IsFatalEnabled;
            default:
                return _logger.IsDebugEnabled;
        }
    }
}

LibLog תומכת בספריות הבאות: NLog, EnterpriseLibrary, log4net, SeriLog, Loupe ~~וכתיבה לConsole בצבע~~.
בנוסף, ניתן לספק מימוש אחר (ברמת האפליקציה) ע”י מימוש הממשקים ILogProvider וILog, וקריאה למתודה SetCurrentLogProvider של LogProvider.

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

סופ”ש עם לוגים טוב

Consumer/Producer queue

2015-03-04

Design Patterns, Thread-safety

נתקלתי לאחרונה בבעיה הבאה:

יש לי ספריה שמשתמשת בספריית WebSockets נחמדה (בשם WebSocketListener של vtortola).

בעזרת הספריה של vtortola אני כותב הודעות Json לClientים.
הבעיה: הספריה שלי יכולה לכתוב הודעות מכמה Threadים לClient, אבל vtortola לא מרשה לכתוב לClient ביותר מThread אחד בו זמנית.

בעיה זו ניתן לפתור בעזרת טכנולוגיות שונות המממשות את הPattern של Consumer/Producer. למשל בעזרת TPL Dataflow הפתרון נראה כך:

public class MyConnection : IDisposable
{
    private readonly TcpClient mClient;
    private readonly ActionBlock<string> mActionBlock;
    public MyConnection(TcpClient client)
    {
        mActionBlock = new ActionBlock<string>(x => InnerSend(x));
        mClient = client;
    }
    private async Task InnerSend(string json)
    {
        try
        {
            StreamWriter streamWriter = new StreamWriter(mClient.GetStream());
            await streamWriter.WriteAsync(json)
                              .ConfigureAwait(false);
        }
        catch (Exception ex)
        {
            // Log ex
        }
    }
    public void Dispose()
    {
        mActionBlock.Complete();
        mActionBlock.Completion.Wait();
    }
}

הסבר קצר: ActionBlock היא מחלקה המקבלת בConstructor פונקציה שמקבלת T ומחזירה Task. עבור כל אובייקט שנכנס לActionBlock, מורצת הפונקציה. הActionBlock דואג לכמה פעמים יכולה הפונקציה לרוץ במקביל: באופן דיפולטי יכול לרוץ בו-זמנית רק Task בודד. (ניתן לשנות זאת ע”י העברת פרמטרים בConstructor)

המשמעות היא שבכל פעם שנכנס אובייקט לActionBlock, הוא נכנס לתור. כשמגיע תורו, נוצר Task (ע”י הפונקציה). רק לאחר שTask זה מסתיים, תרוץ הפונקציה עבור האובייקט הבא בתור.
זה מבטיח לנו שThread אחד בלבד פורק את ההודעות בו-זמנית.

נתקלתי בבעיה, כיוון שTPL Dataflow לא נתמך בFramework 4.0 ובMono.

שאלתי בStackOverflow, ומסתבר שניתן לממש ActionBlock בסיסי בעזרת rx. למי שלא מכיר את rx, זהו Framework גאוני לתכנות Event driven המאפשר לא מעט יכולות (ביניהן גם LINQ), שמאפשר להשתמש בהרבה עקרונות מתמטיים, כגון קומפוזיציה ועוד. הרצאתי על rx לא אחת, אני ממליץ לקרוא על זה באינטרנט ולראות הרצאות בנושא. (יש מימושים לrx בשפות הבאות: C#, C++, Java, Ruby, Python, Clojure, JavaSciprt ועוד!)

אני מסביר את הפתרון כי אני חושב שהוא מעניין. (אם אתם יכולים להשתמש בTPL Dataflow זה כמובן עדיף!)

public class ActionBlock<T>
{
    private readonly ISubject<T> mSubject = new Subject<T>();
    private readonly Task mCompletion;
    public ActionBlock(Func<T, Task> action)
    {
        mCompletion =
            mSubject.Select(x => Observable.FromAsync(() => action(x)))
                    .Concat()
                    .Count()
                    .ToTask();
    }
    public Task Completion
    {
        get
        {
            return mCompletion;
        }
    }
    public void Post(T item)
    {
        mSubject.OnNext(item);
    }
    public void Complete()
    {
        mSubject.OnCompleted();
    }
}

מה שאנחנו רואים זה את הדבר הבא: יש לנו במחלקה Member מסוג ISubject<T>, זהו אובייקט שניתן להפיץ אליו אירועים מצד אחד, ולהרשם לאירועים שלו מצד שני. אנחנו מפיצים אליו אירועים בפונקציה Post (ע”י קריאה לפונקציה OnNext).

בConstructor אנחנו יוצרים Task שמייצג את הסיום של הBlock (הTask ששמו Completion מסתיים אחרי שקוראים לComplete והסתיימה ריצת הTaskים עבור כל איברי התור).

אני אסביר כעת את היצירה:
השורה

1	mSubject.Select(x => Observable.FromAsync(() => action(x)))

יוצרת IObservable<IObservable<Unit>>. הפונקציה Observable.FromAsync היא פונקציה שמקבלת [פונקציה המייצרת Task]. היא יוצרת Observable קר (זהו Observable שמתחיל לייצר אירועים רק לאחר שנרשמו אליו) המסתיים לאחר שהTask הנוצר מהפונקציה הפנימית מסתיים.

השורה

.Concat()

היא קריאה לפונקציה Concat. הפונקציה Concat משטחת את הIObservable<IObservable<Unit>> לIObservable<Unit> באופן הבא: היא נרשמת ראשית לIObserable הראשון שחוזר מהIObservable<IObservable<Unit>>. לאחר מכן, לאחר שהIObservable הראשון מסתיים, היא נרשמת לIObservable השני עד שהוא מסתיים וכו’. בסופו של דבר הIObservable השטוח מפיץ את כל התוצאות הנ”ל, ומסתיים כאשר הIObservable הפנימי האחרון מסתיים.

השורה

1	.ToTask();

היא קריאה למתודה ToTask. מתודה זו יוצרת Task מIObservable נתון. Task זה מסתיים כאשר הIObservable מסתיים וערכו הוא הערך האחרון של הIObservable. אלא שפונקציה זו מחזירה Task שהוא Faulted במידה והIObservable לא הפיץ אף ערך. כדי לתקן זאת, אנחנו קוראים לCount:

.Count();

Count זהו אופרטור המחזיר IObservable המסתיים כאשר הIObservable המקורי מסתיים, ומפיץ ערך בודד: מספר האיברים שהופצו ע”י הIObservable המקורי.

זהו מימוש נחמד. מה אם נרצה לקבוע את מספר הThreadים המטפלים במקביל למספר אחר? נוכל לעשות זאת ע”י אופרטור אחר ששמו Merge. אופרטור זה הוא אופרטור נוסף המשטח IObservable<IObservable> לIObservable בודד המפיץ את ערכים של כל הIObservableים הפנימיים. לאופרטור זה overload המקבל int ששמו maxConcurrent - זהו מספר המאפשר להחליט לכמה IObservableים פנימיים של הIObservable הגדול ניתן להרשם בו-זמנית.

לכן הקוד יכול להראות כך:

public ActionBlock(Func<T, Task> action, int maxConcurrent)
{
    mCompletion =
        mSubject.Select(x => Observable.FromAsync(() => action(x)))
                .Merge(maxConcurrent)
                .Count()
                .ToTask();
}

הערה: מסתבר שמימוש זה סובל מבעיה של StackOverflowException כאשר יש מספר רב של איברים בתור. ראו כאן. מומלץ לא להשתמש במימוש זה.

סופ”ש בלי בעיות סנכרון טוב

Convert Uri to local path

2014-03-16

FileSystem, Uri

היי,

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

לשם כך, ניתן לגשת לProperty ששמו CodeBase:

Assembly givenAssembly = typeof(int).Assembly;
string assemblyPath = givenAssembly.CodeBase;
// file:///C:/Windows/Microsoft.NET/Framework/v4.0.30319/mscorlib.dll

זה נותן לנו כמעט את מה שאנחנו רוצים.
מה הבעיה? שאנחנו מקבלים את התוצאה כUri עם הקידומית file:// והרבה סלאשים (/) במקום בק סלאשים (\).

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

הפתרון המתבקש:

Assembly givenAssembly = typeof(int).Assembly;
Uri assemblyUri = new Uri(givenAssembly.CodeBase);
string assemblyPath = assemblyUri.LocalPath;
// C:\Windows\Microsoft.NET\Framework\v4.0.30319\mscorlib.dll

נראה טוב.

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

Assembly givenAssembly = typeof(Program).Assembly;
Uri assemblyUri = new Uri(givenAssembly.CodeBase);
// file:///C:/C# For Fun/Tip/Tips/bin/Debug/Tips.exe
string assemblyPath = assemblyUri.LocalPath;
// C:\C

מה קורה כאן? הUri מתייחס ל# בתור חלק מפריד של הUri ולכן לא מכניס את כל מה שנמצא שהחל ממקום זה לLocal path.

איך ניתן להתגבר על הבעיה? הפתרון המוצע מStackOverflow (תודות לג’ייסון פיין):

public static string ConvertUriToLocalPath(string uri)
{
    Uri uriObject = new Uri(Assembly.GetExecutingAssembly().CodeBase);
    return uriObject.LocalPath + Uri.UnescapeDataString(uriObject.Fragment).Replace('/', '\\');
}
Assembly givenAssembly = typeof(Program).Assembly;
string assemblyPath = ConvertUriToLocalPath(givenAssembly.CodeBase);
// C:\C# For Fun\Tip\Tips\bin\Debug\Tips.exe

קצת מכוער, אבל עובד 😃

יום טוב מקומית

ReflectionContext

2013-10-01

Framework 4.5, Reflection

אחד הדברים שקרו בFramework 4.5 הוא ששדרגו את העבודה עם Reflection.

זה בא לידי ביטוי בכל מיני Extension Methods חדשים, ביניהם הExtension Methods שיש לעבודה עם Custom Attributes במחלקה CustomAttributeExtensions והExtension Methods במחלקה RuntimeReflectionExtensions, מתודות חדשות שנוספו לכל מיני MemberInfoים (כגון CreateDeleage של MethodInfo) ובעוד מספר Featureים חדשים (למשל TypeInfo).

אחד הדברים שקרו הוא שנוספה אפשרות לCustomized Reflection.

למה הכוונה?

לא אחת יוצא לנו לכתוב איזשהו מנגנון המרה משלנו שממיר אובייקטים מסוג אחד לאובייקטים מסוג אחר באמצעות Reflection. למשל, סירלוז אובייקטים לפורמט אחר (בינארי/Xml/Json), או העתקת Properties מאובייקט אחד לאובייקט אחר, וכו’.

בד”כ המנגנונים האלה עוברים על הProperties של הType שאנחנו מעוניינים לעבד בReflection ועושים איתם משהו.
מה קורה אם אנחנו מעוניינים שמנגנון כזה יתייחס (או לחלופין לא יתייחס) לProperty מסוים? בד”כ בכדי לציין זאת, אנחנו שמים Attribute מעל הProperty שמציין, למשל, שאת הProperty הזה אנחנו רוצים לסרלז. (לפעמים אנחנו מציינים עוד הגדרות בAttribute, כמו באיזה שם לסרלז את הProperty, אבל לא נתייחס לזה כרגע)

כלומר, בד”כ המנגנונים האלה שאנחנו כותבים שרצים על המחלקות בReflection, ניזונים מAttributeים שהמשתמש שם על הTypeים והMemberים שלו.

מה הבעיה?

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

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

כבר בעבר ניסו לפתור בעיה זו, למשל ע”י שימוש בTypeDescriptor המאפשר לנו לערוך Typeים בצורה Customized. הבעיה היא שמדובר בשפה מקבילה לReflection, וקשה לעבוד עם שתיהן בו זמנית.

RelectionContext נוסף בFramework 4.5 לבקשת צוות MEF, והוא נותן מענה לחלק מהבעיות.

אז מה זה בכלל? ReflectionContext היא מחלקה אבסטרקטית היושבת בmscorlib תחת הnamespace ששמו System.Reflection עם המתודות הבאות:

public abstract class ReflectionContext
{
  public abstract Assembly MapAssembly(Assembly assembly);
  public abstract TypeInfo MapType(TypeInfo type);
  public virtual TypeInfo GetTypeForObject(object value);
}

יש כאן שלוש מתודות: MapAssembly הממפה Assembly אחד לAssembly אחר, MapType הממפה TypeInfo אחד לTypeInfo אחר וGetTypeForObject המקבלת אובייקט ומחזירה את הType המתאים לו. (אני לא ארחיב כאן על TypeInfo, אבל בגדול מדובר בApi יותר נוח לType שנוסף בFramework 4.5)

הרעיון הוא שהמנגנונים שנכתוב יעבדו עם ReflectionContext, ואז במקום לקרוא לGetType ישירות על האובייקטים שמועברים למנגנון שלנו, כמו שנהגנו עד כה, נקרא לGetTypeForObject וכך נקבל תצוגה של הType של האובייקט כפי המנגנון מעוניין לראות אותו.

באופן דומה, קיימות המתודות שממפות TypeInfo לTypeInfo וAssembly לAssembly, שהמנגנון שלנו ישתמש בהן במקומות שבהם הוא מקבל Type או Assembly, כדי לראות את אלה בתצוגה שרלוונטית אליו.

שימו לב שאפשרות מעניינת היא שהמנגנון שנכתוב יאפשר להזריק אליו מבחוץ ReflectionContext, וכך למשתמש תהיה שליטה על הMetadata שהמנגנון שלנו רואה.

איך משתמשים בזה?

לצורך השימוש הנפוץ, נכתבה מחלקה בשם CustomReflectionContext היושבת בdll חדש בשם System.Reflection.Context.dll.

נוכל לרשת ממנה בכדי לפתור את שתי הבעיות שציינתי בהתחלה: (יש לה מספר פונקציות שנוח לדרוס)

הפתרון של הבעיה הראשונה:
יהיה לנו נוח לדרוס את המתודה GetCustomAttributes בכדי להשפיע על איזה Attributeים יש לType שנקבל.

public class MyReflectionContext : CustomReflectionContext
{
    protected override IEnumerable<object> GetCustomAttributes
        (MemberInfo member,
         IEnumerable<object> declaredAttributes)
    {
        if (IsKeyValuePairProperty(member))
        {
            return new[] {new MyAttribute(member.Name)};
        }
        return base.GetCustomAttributes(member, declaredAttributes);
    }
    private static bool IsKeyValuePairProperty(MemberInfo member)
    {
        return (member is PropertyInfo) &&
               IsTypeKeyValuePair(member.DeclaringType);
    }
    private static bool IsTypeKeyValuePair(Type type)
    {
        return type.IsGenericType &&
               type.GetGenericTypeDefinition() == typeof (KeyValuePair<,>);
    }
}
#region Attribute
[AttributeUsage(AttributeTargets.All, Inherited = false, AllowMultiple = false)]
public sealed class MyAttribute : Attribute
{
    private readonly string mName;
    public MyAttribute(string name)
    {
        mName = name;
    }
    public string Name
    {
        get
        {
            return mName;
        }
    }
}
#endregion

שימוש:

MyReflectionContext reflectionContext = new MyReflectionContext();
KeyValuePair<string, int> keyValuePair = 
    new KeyValuePair<string, int>("Ten", 10);
Type contextType =
    reflectionContext.GetTypeForObject(keyValuePair);
PropertyInfo keyProperty = contextType.GetProperty("Key");
MyAttribute attribute =
    keyProperty.GetCustomAttribute<MyAttribute>();
string name = attribute.Name; // Key

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

לCustomReflectionContext יש מתודה בשם AddProperties שניתן לדרוס על מנת להוסיף Properties דינאמיים לType. אלה Properties קבועים לכל הInstanceים של הType ולא Properties לפי Instance.

למשל, נניח שיש לנו את הטיפוס הזה שלא שייך לנו

public class Person
{
    public string FirstName { get; set; }
    public string LastName { get; set; }
}

אז נוכל להוסיף לו Property דינאמי בשם FullName בצורה הבאה:

public class MyOtherReflectionContext : CustomReflectionContext
{
    protected override IEnumerable<PropertyInfo> AddProperties(Type type)
    {
        if (type == typeof (Person))
        {
            PropertyInfo fullName =
                this.CreateProperty
                    (this.MapType(typeof (string).GetTypeInfo()),
                     "FullName",
                     x =>
                         {
                             // Getter
                             Person person = x as Person;
                             return person.FirstName + " " + person.LastName;
                         },
                     (x, value) =>
                         {
                             // TODO: write setter
                         }
                    );
            yield return fullName;
        }
    }
}

ואז הקוד הבא יעבוד לנו:

MyOtherReflectionContext reflectionContext = new MyOtherReflectionContext();
Person person = new Person() {FirstName = "Davis", LastName = "Motomiya"};
TypeInfo type = reflectionContext.GetTypeForObject(person);
foreach (PropertyInfo propertyInfo in type.GetProperties())
{
    Console.WriteLine("{0} - {1}", propertyInfo.Name,
                      propertyInfo.GetValue(person));
}
//FirstName - Davis
//LastName - Motomiya
//FullName - Davis Motomiya

המשך יום עם קונטקסט משתקף לטובה,
אלעד

CallerMemberName, CallerFilePath, CallerLineNumber Attributes

2013-07-30

C# 5.0, Debugging

אחת היכולות שנוספו בC# 5.0 היא יכולת לא כל כך מפורסמת והיא הבאה:

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

CallerMemberNameAttribute - זהו Attribute שאם נשים מעל פרמטר מסוג string, נקבל את שם הMember שקרא למתודה שלנו (לקונבנציית השמות, ראו את הפירוט המלא בMSDN)
CallerFilePathAttribute- אם נשים Attribute זה מעל פרמטר מסוג string, נקבל את שם הקובץ (הcs) שבו נכתבה השורה שקוראת למתודה שלנו
CallerLineNumberAttribute- אם נשים Attribute זה מעל פרמטר מסוג int, נקבל את השורה בקובץ הנ”ל

השימוש בAttributeים הוא באופן הבא:

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

דוגמה:

public class Person
{
    private string mName;
    private int mAge;
    public string Name
    {
        get
        {
            Log();
            return mName;
        }
        set
        {
            Log();
            mName = value;
        }
    }
    public int Age
    {
        get
        {
            Log();
            return mAge;
        }
        set
        {
            Log();
            mAge = value;
        }
    }
    public void Save()
    {
        Log();
    }
    private void Log([CallerMemberName] string memberName = null,
                     [CallerFilePath] string filePath = null,
                     [CallerLineNumber] int lineNumber = 0)
    {
        Console.WriteLine("Called by member: {0}, " +
                          "file path: {1}, line number: {2}",
                          memberName,
                          filePath,
                          lineNumber);
    }
}

כעת נקרא למתודות ולProperties ונראה מה קורה:

Person person = new Person();
person.Age = 18; 
// Called by member: Age, file path: c:\TipSharp\Program.cs, line number: 39
person.Name = "Danny";
// Called by member: Name, file path: c:\TipSharp\Program.cs, line number: 25
int age = person.Age;
// Called by member: Age, file path: c:\TipSharp\Program.cs, line number: 34
string name = person.Name;
// Called by member: Name, file path: c:\TipSharp\Program.cs, line number: 20
person.Save();
// Called by member: Save, file path: c:\TipSharp\Program.cs, line number: 46

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

אם נסתכל על הקוד שקימפלנו בReflector/ILSpy נראה כי הקומפיילר פשוט שתל את הערכים האלה hard-coded בקריאות למתודות:

ככה נראה הPerson הdecompiled (לC# 4.0) שכתבנו:

public class Person
{
    private string mName;
    private int mAge;
    public string Name
    {
        get
        {
            this.Log("Name", "c:\\TipSharp\\Program.cs", 20);
            return this.mName;
        }
        set
        {
            this.Log("Name", "c:\\TipSharp\\Program.cs", 25);
            this.mName = value;
        }
    }
    public int Age
    {
        get
        {
            this.Log("Age", "c:\\TipSharp\\Program.cs", 34);
            return this.mAge;
        }
        set
        {
            this.Log("Age", "c:\\TipSharp\\Program.cs", 39);
            this.mAge = value;
        }
    }
    public void Save()
    {
        this.Log("Save", "c:\\TipSharp\\Program.cs", 46);
    }
    private void Log([CallerMemberName] string memberName = null,
                     [CallerFilePath] string filePath = null,
                     [CallerLineNumber] int lineNumber = 0)
    {
        Console.WriteLine("Called by member: {0}, " +
                          "file path: {1}, line number: {2}",
                          memberName,
                          filePath,
                          lineNumber);
    }
}

הערה: שימו לב שהFilePath שאנחנו מקבלים הוא מה שהקומפיילר רואה כשהוא מקמפל את הקריאה שלנו למתודה. מאחר ואנחנו מקמפלים בד"כ על מכונות בילדים, אם אתם מאיזשהי סיבה רוצים להשתמש בCallerFilePathAttribute, תדאגו לחלץ מהPath הזה איזשהו path רלטיבי או משהו שלא תלוי באיפה התוכנה התקמפלה (למשל, בעזרת המחלקה Path).

כעקרון אני מעודד לא להשתמש בCallerFilePath וCallerLineNumber. באשר לCallerMemberName, הוא כן שימושי ואני אכתוב על זה בהמשך.

המשך יום קורא טוב,
אלעד

Finding consecutive subsequences of a given sequence

2013-07-28

Functional Programming, LINQ, Math Puzzles

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

בבעיה הזאת אפשר להתקל במספר מקומות:

קריאת קובץ, סינון כל השורות שעונות על קריטריון מסוים (למשל, כל השורות שכתובות באנגלית), ויצירת קובץ חדש בו יש פסקה המכילה כל רצף כנ”ל של שורות:

string[] lines = File.ReadAllLines(fileLocation);
var relevantLines =
    lines.Select((x, i) => new
                               {
                                   Line = x,
                                   Index = i
                               })
         .Where(x => IsRelevant(x.Line));
// Group elements that their indexes form a consecutive subsequence

מציאת מספרים בטקסט (בלי Regex)
איגוד ימי חופש רצופים של עובד

הבעיה היא בעיה שיחסית קל לפתור ע"י קוד אימפרטיבי:
נגדיר מבנה שמייצג תת-סדרה רצופה:

public class ConsecutiveSubsequence
{
    public int StartIndex { get; set; }
    public int EndIndex { get; set; }
}

וניצור מתודה שמוצאת את כל התת-סדרות הרצופות הנ"ל:

public static IEnumerable<ConsecutiveSubsequence> FindConsecutiveSubsequences<T>
    (IEnumerable<T> sequence,
     Func<T, int> indexSelector)
{
    List<ConsecutiveSubsequence> result = new List<ConsecutiveSubsequence>();
    ConsecutiveSubsequence currentSequence = null;
    foreach (T current in sequence)
    {
        int currentIndex = indexSelector(current);
        if ((currentSequence == null) ||
            (currentSequence.EndIndex + 1 != currentIndex))
        {
            currentSequence = new ConsecutiveSubsequence();
            currentSequence.StartIndex = currentIndex;
            result.Add(currentSequence);
        }
        currentSequence.EndIndex = currentIndex;
    }
    return result;
}

נוכל להשתמש במתודה כך:

1
2
3

IEnumerable<ConsecutiveSubsequence> subsequences =
    FindConsecutiveSubsequences(relevantLines,
                               x => x.Index);

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

כל זה טוב ויפה, אבל מעניין האם ניתן לפתור את הבעיה בעזרת תכנות פונקציונאלי?

התשובה שהיא שכן, להלן הפתרון:

public static IEnumerable<ConsecutiveSubsequence> FindConsecutiveSubsequences<T>
    (IEnumerable<T> sequence,
     Func<T, int> indexSelector)
{
    List<int?> indexes = 
        sequence.Select(x => (int?)indexSelector(x)).ToList();
    IEnumerable<int?> nullAndIndexes =
        new int?[] {null}.Concat(indexes);
    IEnumerable<int?> indexesAndNull =
        indexes.Concat(new int?[] {null});
    var zipped =
        nullAndIndexes.Zip(indexesAndNull,
                           (x, y) => new
                                         {
                                             Current = x,
                                             Next = y
                                         });
    var disconsecutive =
        zipped.Where((x, index) => x.Next != x.Current + 1)
              .ToList();
    var disconsecutiveShifted = disconsecutive.Skip(1);
    IEnumerable<ConsecutiveSubsequence> result =
        disconsecutive.Zip
            (disconsecutiveShifted,
             (x, y) => new ConsecutiveSubsequence()
                           {
                               StartIndex = x.Next.Value,
                               EndIndex = y.Current.Value,
                           });
    return result;
}

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

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

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

לכן כדי למצוא את התת-סדרות הרצופות, מספיק לנו להסתכל על האיבר Next של איבר בזוג ועל האיבר Current של הזוג העוקב. זאת אנחנו עושים שוב אמצעות המתודה Zip, אבל הפעם גם באמצעות האופרטור Skip המדלג לנו על האיבר הראשון בסדרה, כדי שנקבל זוגות של איברים עוקבים.

שבוע מאונדקס לטובה,
אלעד

393. Happy Passover

2013-03-25

Math Puzzles

הנה טיפ באווירת פסח.

חידה: מה סכום המספרים בשיר “אחד מי יודע”? (כולל חזרות)

תשובה: ובכן, אם מנתחים את השיר, הוא נראה ככה:

אחד מי יודע? אחד - אני יודע! אחד אלוהינו
שניים מי יודע? שניים - אני יודע! שני לוחות הברית, אחד אלוהינו
שלושה מי יודע? שלושה - אני יודע! שלושה אבות, שני לוחות הברית, אחד אלוהינו
…

קיצר אנחנו רואים שבשורה ה$ n $ בשיר סכום המספרים הוא:

$ n + n + n + (n - 1) + (n - 2) + \dots + 1 $

שהסכום של זה שווה לפי הנוסחה לסדרה חשבונית של גאוס: $ \displaystyle{ 2n + \frac{n (n+1)}{2} } $.
עכשיו צריך לסכום את כל השורות מ1 עד $ n $: כלומר צריך לסכום את $ \displaystyle{ 2k + \frac{k (k+1)}{2} } $ מ$ k = 1 $ עד $ n $.

איך עושים את זה?

טוב, כאן מגיע החלק האומנותי של והיצירתי של הטיפ -
נעבור לבעיה אחרת שלכאורה לא קשורה:

בכמה דרכים אפשר לחלק $ n $ תפוזים ל$ k $ ילדים? (כלומר, לא משנה מי מקבל איזה תפוז, אלא משנה כמה תפוזים הוא מקבל)

נסמן מספר זה ב$ F(n,k)$, אז מתקיימת נוסחת הנסיגה:

$ F(n, k) = F(n, k - 1) + F(n - 1, k - 1) + F(n - 2, k - 1) + \dots + F(0, k - 1) $

אכן: נבחר את אחד הילדים: אם הוא קיבל $ 0 $ תפוזים, אנחנו צריכים לחלק $ n $ תפוזים ל $ k - 1$ ילדים, אם הוא קיבל תפוז אחד, אנחנו צריכים לחלק $ n -1 $ תפוזים ל$ k-1 $ ילדים וכו’. כל אפשרות כזאת מתאימה למחובר מתחילת הסכום ( $ F(n,k-1) $ מתאים לאפשרות שהילד שבחרנו קיבל 0 תפוזים, $ F(n-1,k-1) $ מתאים לאפשרות שהילד שבחרנו קיבל תפוז אחד וכו’)

מסתבר שאפשר לחשב את $ F(n,k)$ בצורה מפורשת:

ניקח את כל ה$ n $ תפוזים ונשים ביניהם $ k -1 $ מקלות של ארטיק. כעת בין כל שני מקלות נוצרת מחיצה, ובסה”כ נוצרות $ k $ מחיצות. הילד ה$ i $ יקבל את התפוזים שנמצאים במחיצה ה$ i $.

מספר הדרכים לשים $ k - 1 $ מקלות של ארטיק בין $ n $ תפוזים הוא $ F(n,k) = \binom{n + k - 1}{k-1}$ כאשר $ \binom{n}{k} $ הוא המקדם הבינומי.

נזכור שמתקיים

$ F(n, k) = F(n, k - 1) + F(n - 1, k - 1) + F(n - 2, k - 1) + \dots + F(0, k - 1) $

נבחר $ k =4 $, $ n = N - 1$ ונקבל

$ F(N-1, 4) = F(N - 1, 3) + F(N - 2, 3) + F(N - 3, 3) + \dots + F(0, 3) $

אבל $ F(N - 1, 3) = \binom{N-1+3-1}{3-1} = \binom{N + 1}{2} = \frac{N (N+1)}{2} $

הדבר הזה נותן בעצם סכום לסכום של סדרה חשבונית:

$$ 1 + (1+2) + (1+2+3) + \dots + (1+2+3+\dots+N) = \\ F(N-1,4) = \binom{N-1+4-1}{4-1} = \binom{N+2}{3} = \frac{(N+2)(N+1)N}{6} $$

לכן סכום השורות עד השורה ה$ N $ בשיר אחד מי יודע היא $ \frac{(N+2)(N+1)N}{6} + N(N+1) $

בשיר אחד מי יודע יש 13 שורות ולכן התשובה היא: $ \frac{15\cdot 14 \cdot 13}{6} + 13 \cdot 14 = 637$.

להלן קוד מאת אלירן מויאל שכותב את השיר אחד מי יודע (האחריות על שימוש בסדר על המשתמש בלבד…)

var whoKnows = new string[]
               {
                   "ehad elohinu",
                   "shti luhot a brit",
                   "shlosha avot",
                   "arbaa imaot",
                   "hamisha humshi tora",
                   "shisha sidri mishna",
                   "shiva yemi shbta",
                   "shmona yemi mila",
                   "tishaa yerhi lida",
                   "asara dibria",
                   "ahad asar kohvaia",
                   "shnim asar shivtaia",
                   "shlosh asar midaia"
               };
var numbersToHebrew = new Dictionary<int, string>
                      {
                          {1, "ehad" },
                          {2, "shnaim" },
                          {3, "shlosha" },
                          {4, "arbaa" },
                          {5, "hamisha" },
                          {6, "shisa" },
                          {7, "shiva" },
                          {8, "shmona" },
                          {9, "tishaa" },
                          {10, "asara" },
                          {11, "ahad asar" },
                          {12, "shnim asar" },
                          {13, "shlosh asar" }
                      };
const string ending = "elohinu , elohinu , elohinu , elohinu shbashamim ve baaretez ";
for (int i = 0; i < whoKnows.Length; i++)
{
    Console.WriteLine("{0} mi yodea? {0} ani yodea!", numbersToHebrew[i + 1]);
    for (int j = i; j >= 0; j--)
    {
        Console.WriteLine(whoKnows[j]);
    }
    Console.WriteLine(ending);
    Console.WriteLine();
}

חג שמח!

392. Using AppDomains in order to load a different app.config

2013-02-21

AppDomain

בהמשך לפעם הקודמת שהייתה לפני הרבה זמן,

השימוש הראשון של AppDomain שנדבר עליו הוא הצורך הבא:

כאשר אפליקציה עולה היא טוענת קובץ app.config באופן דיפולטי:

לפי השם של הExecutable שמריץ את האפליקציה בתוספת config. (למשל MyApplication.exe.config).
לפי web.config במידה ואנחנו מוארחים בIIS

לפעמים עולה לנו צורך להעלות את האפליקציה שלנו עם app.config שונה מהapp.config הדיפולטי.

לדוגמה, האפליקציה WcfSvcHost.exe מקבלת בתור פרמטרים את הPath לdll של הService שאנחנו רוצים להריץ ואת הapp.config של הService שאנחנו מעוניינים להריץ. (זה מה שרץ כאשר אנחנו מריצים Wcf Service Library)

הנתון של הקובץ app.config שאיתו האפליקציה שלנו עובדת קשור לAppDomain שלנו וניתן לגשת אליו ככה:

1 2	string path = AppDomain.CurrentDomain.SetupInformation.ConfigurationFile;

כך אנחנו ניגשים לקובץ הקונפיגורציה של הAppDomain הנוכחי.

במידה ואנחנו מעוניינים שהאפליקציה שלנו תעבוד עם קובץ קונפיגורציה אחר, נוכל לעשות זאת ע"י פתיחת AppDomain חדש:

AppDomainSetup appDomainSetup = new AppDomainSetup();
appDomainSetup.ConfigurationFile = path;
AppDomain newAppDomain =
    AppDomain.CreateDomain("MyNewAppDomain",
                           AppDomain.CurrentDomain.Evidence,
                           appDomainSetup);

כאן יצרתי AppDomain חדש שמשתמש בקובץ קונפיגורציה שמצוין במשתנה path.

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

סוף שבוע ממקום לא צפוי טוב

391. Introduction to AppDomains

2012-12-25

AppDomain

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

נתחיל בלהסביר מהו AppDomain.

כאשר אפליקציה .netית שלנו עולה, יש איזשהו “מרחב” שבו היא חיה.

כדי להמחיש את המרחב הזה, נסתכל על מספר דוגמאות

באפליקציה שלנו אנחנו יכולים לגשת למשתנים סטטיים. איפה משתנים אלה בדיוק נשמרים? שהרי בInstanceים אחרים של האפליקציה שלנו למשתנים האלה ערכים אחרים.
למי “שייכים” הThreadים של האפליקציה שלנו?
איך האפליקציה שלנו יודעת מאיפה לטעון DLLים?

התשובות לשאלות האלה כרוכות במושג של הAppDomain. הAppDomain הוא שכבה מבודדת שמהווה את המרחב של האפליקציה שלנו.

לרובנו לא יצא ליצור AppDomainים בעצמנו. כשהאפליקציה שלנו עולה, נוצר AppDomain דיפולטי עבורה בה היא רצה.

למעשה, זה לא מדויק:

כשאנחנו כותבים Process שהוא Stand-alone, כגון Console Application/Windows Form Application/WPF Application, אז נוצר באמת AppDomain דיפולטי יחיד עבורנו, בו האפליקציה שלנו חיה,

אבל לפעמים אנחנו לא כותבים Process שהוא Stand-alone, אלא מתארחים בProcess אחר. למשל, לפעמים אנחנו כותבים שירות WCF שמוארח על IIS. במקרה כזה הProcess שמריץ אותנו הוא הw3p.exe של IIS. במקרה כזה, הProcess שמארח אותנו מנהל את הAppDomainים שלו. במקרה של IIS, למשל, לכל שירות שהוא מארח, הוא פותח AppDomain נפרד (בערך), כך שבעצם אנחנו עובדים עם מספר AppDomainים בProcess יחיד.

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