7

我有一个位移掩码,代表一周中的几天:

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

我正在使用位掩码,因为几天(至少一天)可能设置为 1。

问题

然后我得到一个约会。任何日期。并且基于date.DayOfWeek我需要返回在位掩码中设置的第一个最近的日期。所以我的方法可以返回同一天或之间的任何其他日期dateand date + 6

示例 1

我的位掩码将所有天数定义为 1。在这种情况下,我的方法应该返回相同的日期,因为在位date.DayOfWeek掩码中设置。

示例 2

我的位掩码定义只有星期三设置为 1。如果我的传入日期是星期二,我应该返回date+1(即星期三)。但如果到来的日期是星期四,我应该回来date+6(又是星期三)。

问题

解决这个问题的最快和最优雅的方法是什么?为什么也最快?因为我需要多次运行它,所以如果我可以使用某种缓存结构来更快地获取日期,那将是首选。

你能建议一些指导以优雅的方式解决这个问题吗?我不想最终得到一个充满 ifs 和 switch-case 语句的长意大利面条代码......

重要:请务必注意,如果位掩码有助于更好的性能和代码的简单性,则可能会更改或替换位掩码。所以位掩码不是一成不变的......

一种可能的方法

每天生成一个偏移量数组并将其保存在私有类变量中会很聪明。生成一次并在之后重用它,例如:

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

Bitscan——尤其是你的,因为它只关心七位——很容易在查找表中实现。事实上,如果你做了一个自定义表,你可以调用 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];

可以让你写一个小&表格,因为你真的只关心最低的七个位。

PS: 至少有些处理器实现了您可以使用的位扫描指令,但您似乎不太可能使用 C# 来处理它们,除非某处有包装函数。

于 2011-09-29T20:46:48.320 回答
1

你可能讨厌这个答案,但也许你可以带着它朝着新的方向前进。你说性能非常重要,所以最好只在某些数据结构中预先索引所有答案。该数据结构可能有些复杂,但它可以封装在自己的小世界中,并且不会干扰您的主要代码。我想到的数据结构将是一个整数数组。如果您允许星期一、星期五和星期六,这些整数将是:

[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

这是填充查找表的算法。你只需要做一次,所以我不确定它的效率有多重要......

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 回答
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;
}

例如,您要匹配的日期是星期三,但掩码仅包含星期一。您可以看到该算法将选择星期一作为最好的一天,然后遍历其余的日子,没有选择任何东西。

如果掩码包含星期一、星期二和星期四,则算法将选择星期一作为最佳候选者,忽略星期二,然后选择星期四作为最佳候选者并退出。

这不会像查找表那么快,但它应该非常快。而且它会比查找表使用更少的内存。

查找表会快得多,而且只占用一千字节的内存。鉴于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];

毫无疑问,有一种更快的方法来生成表格。但是它足够快,并且由于它会在程序启动时执行一次,因此优化它似乎没有多大意义。如果您希望启动更快,请编写一个将表格输出为 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 回答