Определите, какой бит установлен для даты, используя сложные битовые маски

Вы можете ненавидеть этот ответ, но, возможно, вы сможете работать с ним в новом направлении. Вы сказали, что производительность чрезвычайно важна, поэтому, возможно, лучше всего просто проиндексировать все ответы заранее в какой-либо структуре данных. Эта структура данных может быть несколько запутанной, но ее можно инкапсулировать в своем собственном маленьком мире и не мешать вашему основному коду. Структура данных, которую я имею в виду, будет массивом целых чисел. Если вы разрешите понедельник, пятницу и субботу, эти целые числа будут:

[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);

Я бы сделал это с помощью битовой маски, некоторого смещения и битового сканирования. Это не очень очевидная процедура, но она должна быть быстрой, так как никогда не разветвляется:

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 — особенно ваш, потому что он заботится только о семи битах — легко реализовать в таблице поиска. На самом деле, если бы вы создали собственную таблицу, вы могли бы назвать младший бит бит 0 и пропустить вычитание в операторе возврата. Я предполагаю, что самой медленной частью всего этого будет функция dayOfWeek(), но это будет зависеть от ее реализации.

Надеюсь это поможет!

Редактировать: пример таблицы битового сканирования (которая обрабатывает младший бит как индекс 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#, если только где-нибудь нет функции-оболочки.

Вот что я бы сделал, переменная 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
}

Вот алгоритм заполнения таблицы поиска. Вам нужно сделать это только один раз, поэтому я не уверен, что имеет значение, насколько это эффективно...

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]);

Я понимаю, что вы сказали, что производительность должна быть принята во внимание, но я бы начал с простого, легкого для понимания подхода и проверил, достаточна ли его производительность, прежде чем переходить к более сложному методу, который может оставить будущих сопровождающих кода немного потерянным.

Сказав это, возможное решение с использованием предварительно инициализированных поисков:

[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;
}

Это должно быть довольно легко сделать. Учтите, что 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("};");

Затем вы можете скопировать и вставить это в свою программу.