7

週の日を表すビット シフト マスクがあります。

Sunday = 1
Monday = 2
Tuesday = 4
...
Saturday = 64

数日 (少なくとも 1 日) が 1 に設定される可能性があるため、ビットマスクを使用しています。

問題

それから私はデートをします。任意の日付。それに基づいてdate.DayOfWeek、ビットマスクに設定されている最初の最も近い日付を返す必要があります。dateしたがって、私のメソッドは、同じ日または ～ の間の任意の日に返すことができdate + 6ます。

例 1

私のビットマスクは、すべての日が 1 に設定されていることを定義します。この場合、date.DayOfWeekビットマスクに が設定されているため、メソッドは同じ日付を返す必要があります。

例 2

私のビットマスクは、水曜日のみが 1 に設定されていることを定義しています。受信日が火曜日の場合、戻る必要がdate+1あります (これは水曜日です)。ただし、受信日が木曜日の場合は、戻る必要がdate+6あります (これも水曜日です)。

質問

これを解決する最も速くてエレガントな方法は何ですか? なぜ最速なのですか？これを数回実行する必要があるため、何らかのキャッシュ構造を使用して日付をより速く取得できる場合は、それが優先されます。

これをエレガントな方法で解決するためのガイダンスを提案できますか? ifs ステートメントと switch-case ステートメントでいっぱいの長いスパゲッティ コードで終わりたくありません...

重要: ビットマスクがパフォーマンスの向上とコードの単純化に役立つ場合は、ビットマスクを変更または別のものに置き換えることができることに注意することが重要です。したがって、ビットマスクは石に設定されていません...

可能なアプローチ

1 日あたりのオフセットの配列を生成し、それをプライベート クラス変数に保存するのが賢明です。一度生成し、後で次のように再利用します。

return date.AddDays(cachedDayOffsets[date.DayOfWeek]);

この方法では、ビットマスクをまったく使用しません。唯一の問題は、配列をできるだけ速く、できるだけ短いコードで生成する方法です。

4

6 に答える 6

2

これについては、ビットマスク、シフト、およびビットスキャンを使用します。これは非常に明白なルーチンではありませんが、分岐しないため高速である必要があります。

original_date = Whatever                    //user input
bitmask = Whatever                          //user input
bitmask |= (bitmask << 7)                   //copy some bits so they don't get
                                            //lost in the bitshift
bitmask >>= original_date.dayOfWeek()       //assuming Sunday.dayOfWeek() == 0
return original_date + bitscan(bitmask) - 1 //the position of the least
                                            //significant bit will be one greater
                                            //than the number of days to add

ビットスキャン - 特にあなたのものは、7 ビットしか気にしないため、ルックアップ テーブルに簡単に実装できます。実際、カスタム テーブルを作成した場合は、LSB ビット 0 を呼び出すことができ、return ステートメントで減算をスキップできます。このすべての中で最も遅い部分は dayOfWeek() 関数だと思いますが、それはその実装に依存します。

お役に立てれば！

編集：ビットスキャンテーブルの例（lsbをインデックス1として扱います-おそらくゼロとして扱いたいと思うでしょうが、これはより良い例になります）：

int[128] lsb = {
    0, //0 = 0b00000000 - Special case!
    1, //1 = 0b00000001
    2, //2 = 0b00000010
    1, //3 = 0b00000011
    3, //4 = 0b00000100
    1, //5 = 0b00000101
    2, //6 = 0b00000110
    ....
    1 //127 = 0b01111111
};

次に、でテーブルを使用するにはmask、次を使用します。

first_bit_index = lsb[mask & 127];

を使用&すると、小さいテーブルを作成できます。これは、最下位 7 ビットのみを気にするためです。

PS: 少なくとも一部のプロセッサは、代わりに使用できるビットスキャン命令を実装していますが、ラッパー関数がどこかにない限り、C# でそれらを取得できる可能性は低いようです。

于 2011-09-29T20:46:48.320 に答える
1

あなたはこの答えを嫌うかもしれませんが、おそらくあなたはそれで新しい方向に走ることができるでしょう. パフォーマンスは非常に重要だとおっしゃいましたので、何らかのデータ構造ですべての回答を前もってインデックス化するのが最善かもしれません。そのデータ構造はやや複雑かもしれませんが、独自の小さな世界にカプセル化することができ、メイン コードに干渉することはありません。私が念頭に置いているデータ構造は、int の配列です。月曜日、金曜日、土曜日を許可する場合、これらの整数は次のようになります。

[1][0][3][2][1][0][0]

わかりました 変ですよね？これは基本的に、その週の「離れた日」のリストです。日曜日には、「次の許可された曜日まで 1 日」があります。月曜日は 0 です。火曜日は 3 日後です。さて、このリストを作成すると、次の予定を取得するために日付に何日追加する必要があるかを非常に簡単かつ迅速に把握できます. うまくいけば、これは役に立ちますか??

これらのオフセットの生成

これらのオフセットを生成するコードは次のとおりです。

this.dayOffsets = new int[] {
    this.Sundays ? 0 : this.Mondays ? 1 : this.Tuesdays ? 2 : this.Wednesdays ? 3 : this.Thursdays ? 4 : this.Fridays ? 5 : 6,
    this.Mondays ? 0 : this.Tuesdays ? 1 : this.Wednesdays ? 2 : this.Thursdays ? 3 : this.Fridays ? 4 : this.Saturdays ? 5 : 6,
    this.Tuesdays ? 0 : this.Wednesdays ? 1 : this.Thursdays ? 2 : this.Fridays ? 3 : this.Saturdays ? 4 : this.Sundays ? 5 : 6,
    this.Wednesdays ? 0 : this.Thursdays ? 1 : this.Fridays ? 2 : this.Saturdays ? 3 : this.Sundays ? 4 : this.Mondays ? 5 : 6,
    this.Thursdays ? 0 : this.Fridays ? 1 : this.Saturdays ? 2 : this.Sundays ? 3 : this.Mondays ? 4 : this.Tuesdays ? 5 : 6,
    this.Fridays ? 0 : this.Saturdays ? 1 : this.Sundays ? 2 : this.Mondays ? 3 : this.Tuesdays ? 4 : this.Wednesdays ? 5 : 6,
    this.Saturdays ? 0 : this.Sundays ? 1 : this.Mondays ? 2 : this.Tuesdays ? 3 : this.Wednesdays ? 4 : this.Thursdays ? 5 : 6
};

これは前方オフセットを生成します。したがって、任意の日付について、次の方法で実際に該当する日付を取得できます。

SomeDate.AddDays(this.dayOffsets[(int)SomeDate.DayOfWeek]);

過去の最も近い日付を取得する必要がある場合は、同じ配列を再利用して、次の式を使用して計算できます。

SomeDate.AddDays((this.dayOffsets[(int)SomeDate.DayOfWeek] - 7) % 7);
于 2011-09-29T20:47:52.663 に答える
0

これは非常に簡単に行うことができます。DayOfWeek.Sunday == 0、Monday == 1などを考慮してください。

あなたのマスクはこれに対応します。つまり、あなたのマスクでは：

Sunday = 1 << 0
Monday = 1 << 1
Tuesday = 1 << 2

ここで、指定された曜日から、条件に一致する曜日を簡単に判断できます。

[Flags]
enum DayMask
{
    Sunday = 1,
    Monday = 2,
    Tuesday = 4,
    Wednesday = 8,
    Thursday = 16,
    Friday = 32,
    Saturday = 64
}

static DayOfWeek FindNextDay(DayMask mask, DayOfWeek currentDay)
{
    DayOfWeek bestDay = currentDay;

    int bmask = 1;

    for (int checkDay = 0; checkDay < 7; ++checkDay)
    {
        if (((int)mask & bmask) != 0)
        {
            if (checkDay >= (int)currentDay)
            {
                bestDay = (DayOfWeek)checkDay;
                break;
            }
            else if (bestDay == currentDay)
            {
                bestDay = (DayOfWeek)checkDay;
            }
        }
        bmask <<= 1;
    }
    return bestDay;
}

たとえば、一致させたい日は水曜日ですが、マスクには月曜日しか含まれていません。アルゴリズムが月曜日を最適な日として選択し、残りの日は何も選択せずに処理することがわかります。

マスクに月曜日、火曜日、および木曜日が含まれている場合、アルゴリズムは月曜日を最良の候補として選択し、火曜日を無視してから、木曜日を最良の候補として選択して終了します。

これはルックアップ テーブルほど高速ではありませんが、かなり高速になるはずです。また、ルックアップ テーブルよりもはるかに少ないメモリを使用します。

ルックアップ テーブルの方がはるかに高速で、1 キロバイトのメモリしか必要としません。そして、FindNextDay上記の方法を考えると、構築するのは簡単です:

    static byte[,] LookupTable = new byte[128, 7];

    static void BuildLookupTable()
    {
        for (int i = 0; i < 128; ++i)
        {
            DayMask mask = (DayMask)i;
            for (int day = 0; day < 7; ++day)
            {
                LookupTable[i, day] = (byte)FindNextDay(mask, (DayOfWeek)day);
            }
        }
    }

ここで、マスクと当日の任意の組み合わせの翌日を取得するには、次のようにします。

DayOfWeek nextDay = (DayOfWeek)LookupTable[(int)mask, (int)currentDay];

テーブルを生成するより高速な方法は間違いなくあります。しかし、これは十分に高速であり、プログラムの起動時に 1 回実行されるため、最適化する意味がないように思われます。起動を高速化する場合は、テーブルを C# コードとして出力する小さなプログラムを作成します。何かのようなもの：

Console.WriteLine("static byte[,] LookupTable = new byte[128,7] {");
for (int i = 0; i < 128; ++i)
{
    Console.Write("    {");
    for (int j = 0; j < 7; ++j)
    {
        if (j > 0)
        {
            Console.Write(",");
        }
        Console.Write(" {0}", LookupTable[i, j]);
    }
    Console.WriteLine(" },");
}
Console.WriteLine("};");

次に、それをコピーしてプログラムに貼り付けることができます。

于 2011-09-29T21:16:53.513 に答える
0

パフォーマンスを考慮に入れる必要があるとおっしゃったことは理解していますが、単純でわかりやすいアプローチから始めて、そのパフォーマンスが十分かどうかを確認してから、コードの将来のメンテナーが少し迷子になる可能性のあるより複雑な方法にジャンプします。

そうは言っても、事前に初期化されたルックアップを使用した可能な解決策：

[Flags]
enum DaysOfWeek
{
    None = 0,
    Sunday = 1,
    Monday = 2,
    Tuesday = 4,
    Wednesday = 8,
    Thursday = 16,
    Friday = 32,
    Saturday = 64
}

前の列挙を仮定すると:

private static Dictionary<DayOfWeek, List<DaysOfWeek>> Maps { get; set; }

static void Main(string[] args)
{
    Maps = CreateMaps();

    var date = new DateTime(2011, 9, 29);

    var mask = DaysOfWeek.Wednesday | DaysOfWeek.Friday;

    var sw = Stopwatch.StartNew();

    for (int i = 0; i < 10000; i++)
    {
        GetNextDay(date, mask);
    }

    sw.Stop();

    Console.WriteLine(sw.ElapsedMilliseconds);
}

private static DaysOfWeek GetNextDay(DateTime date, DaysOfWeek mask)
{
    return Maps[date.DayOfWeek].First(dow => mask.HasFlag(dow));
}

そして最後にCreateMaps実装:

private static Dictionary<DayOfWeek, List<DaysOfWeek>> CreateMaps()
{
    var maps = new Dictionary<DayOfWeek, List<DaysOfWeek>>();

    var daysOfWeek = new List<DaysOfWeek>(7)
    {
        DaysOfWeek.Sunday, 
        DaysOfWeek.Monday, 
        DaysOfWeek.Tuesday, 
        DaysOfWeek.Wednesday, 
        DaysOfWeek.Thursday, 
        DaysOfWeek.Friday, 
        DaysOfWeek.Saturday 
    };

    foreach (DayOfWeek dayOfWeek in Enum.GetValues(typeof(DayOfWeek)))
    {
        var map = new List<DaysOfWeek>(7);

        for (int i = (int)dayOfWeek; i < 7; i++)
        {
            map.Add(daysOfWeek[i]);
        }

        for (int i = 0; i < (int)dayOfWeek; i++)
        {
            map.Add(daysOfWeek[i]);
        }

        maps.Add(dayOfWeek, map);
    }

    return maps;
}
于 2011-09-29T21:28:08.273 に答える
0

ルックアップ テーブルに入力するアルゴリズムを次に示します。1回でいいので、効率はどうでもいいのですが…。

int[] DaysOfWeek = (int[])Enum.GetValues(typeof(DayOfWeek));
int NumberOfDaysInWeek = DaysOfWeek.Length;
int NumberOfMasks = 1 << NumberOfDaysInWeek;
int[,] OffsetLookup = new int[NumberOfDaysInWeek, NumberOfMasks];

//populate offset lookup
for(int mask = 1; mask < NumberOfMasks; mask++)
{
    for(int d = 0; d < NumberOfDaysInWeek; d++)
    {
        OffsetLookup[d, mask] = (from x in DaysOfWeek
                                 where ((1 << x) & mask) != 0
                                 orderby Math.Abs(x - d)
                                 select (x - d) % NumberOfDaysInWeek).First();
    }
}

次に、次を使用します。

DateTime SomeDate = ...; //get a date
DateTime FirstDate = SomeDate.AddDays(OffsetLookup[SomeDate.DayOfWeek, DayOfWeekMask]);
于 2011-09-29T20:56:59.460 に答える
0

これが私がすることです。変数dateDiffはあなたが探しているものになります。

DoW mask      = DoW.Wednesday | DoW.Friday;
DoW? todayDoW = null;
int dateDiff  = 0;

do
{
    DateTime date = DateTime.Today.AddDays(dateDiff);
    todayDoW      = (DoW)Enum.Parse(typeof(DoW), date.DayOfWeek.ToString());

    if ((mask & todayDoW.Value) != 0)
    {
        todayDoW = null;
    }
    else
    {
        dateDiff++;
    }

}
while(todayDoW.HasValue);

enum DoW
{
    Sunday = 1,
    Monday = 2,
    Tuesday = 4,
    Wednesday = 8,
    Thursday = 16,
    Friday = 32,
    Saturday = 64
}
于 2011-09-29T20:57:21.717 に答える