Определите, какой бит установлен для даты, используя сложные битовые маски - PullRequest
7 голосов
/ 30 сентября 2011

У меня есть маска сдвига битов, которая представляет дни недели:

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

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

Проблема

Тогда я получаю свидание.Любая дата.И на основе date.DayOfWeek мне нужно вернуть первую ближайшую дату после того, как она установлена ​​в битовой маске.Таким образом, мой метод может вернуть тот же или любой другой день между date и date + 6.

Пример 1

Моя битовая маска определяет все дни, установленные на 1. В этом случае мой методдолжен вернуть ту же дату, потому что в битовой маске установлено date.DayOfWeek.

Пример 2

Моя битовая маска определяет, что только среда установлена ​​в 1. Если моя дата поступления вторник, я долженвозврат date+1 (это среда).Но если в качестве входящей даты указан четверг, я должен вернуть date+6 (что опять-таки среда).

Вопрос

Какой самый быстрый и элегантный способ решения этой проблемы?Почему также самый быстрый?Потому что мне нужно выполнить это несколько раз, поэтому, если я смогу использовать какую-то кэшированную структуру для более быстрого получения дат, это было бы предпочтительным.

Можете ли вы предложить некоторые рекомендации, чтобы решить эту проблему элегантным способом?Я не хочу заканчивать с длинным кодом спагетти, полным ifs и операторов switch-case ...

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

Возможный подход

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

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

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

Ответы [ 6 ]

2 голосов
/ 30 сентября 2011

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

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

1 голос
/ 30 сентября 2011

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

[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);
0 голосов
/ 30 сентября 2011

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

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

[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;
}
0 голосов
/ 30 сентября 2011

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

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

0 голосов
/ 30 сентября 2011

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

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

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]);
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...