Лучшая структура данных для конкретного типа запроса

Question

Решено это давным-давно, но этот вопрос недавно привлек к себе внимание, поэтому я добавляю свое решение (и некоторые пояснения).См. Ниже.

---

У меня есть список 32-битных целых чисел, и я хочу найти подмножество их, для которых ((item ^ bits) & mask) == 0 является истинным.Проблема в том, что bits и mask могут принимать любое значение (хотя mask смещено в сторону установки не очень большого количества битов), поэтому я не могу просто предварительно рассчитать все возможные комбинации.

Список не очень большой, обычно около 500 элементов, поэтому вещи, которые хорошо выглядят в теории (например, двоичное дерево, где для каждого бита в маске может быть пропущено целое поддерево), на самом деле работают медленнопрактика.Даже дерево с двумя уровнями было немного медленнее, чем наивный подход, несмотря на то, что пропущено значительное количество тестов.

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

foreach (var row in validRows.Keys)
{
    // this single line here takes 40% of the total program time, according to ANTS 5
    if (((oldrow ^ row) & oldused) == 0)
    // the other magic takes no significant time, according to ANTS
    {
        if (y > 1 && ((((row ^ prev) | yminone) + 1) >> rows.Length) == 0)
        {
            continue;
        }
        if (dict.ContainsKey(row))
            continue;

        dict.Add(row, true);

        rows[y] = row;
        count(y + 1, dict);   // this is a recursive call.

        dict.Remove(row);
    }
}

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

---

Для этой конкретной подзадачи предварительная обработка очень помогла.Теперь я создаю массив возможностей для каждой строки во входных данных, который просто validRows (теперь массив вместо словаря) фильтруется по (int row) => ((inputrow ^ row) & inputfilledmask) == 0.

Фактическая проблема, учитывая частично заполненную логическую матрицу 8x8, состоит в подсчете всех назначений, которые удовлетворяют следующим правилам:

1. 4 единицы и 4 нуля в каждой строке
2. 4 единицы и 4 нуля в каждом столбце
3. Не более 2 единиц рядом друг с другом по вертикали или горизонтали
4. Не более 2 нулей рядом друг с другом по вертикали или горизонтали
5. Нет двух строк, которые могут быть равны
6. Нет двух столбцов, которые могут быть равны

Вот как я могу решить это сейчас:

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

Затем рекурсивно заполните следующую строку каждой возможной строкой в ​​этой точке.Это означает, что он должен быть в отфильтрованном списке, он еще не должен был использоваться (то есть не в хэш-наборе), и выполняется тест, чтобы убедиться, что он не нарушает 3-е из 4-х правил.Чтобы обрезать еще несколько поддеревьев дерева рекурсии, я также использую два дополнительных целых числа: одно для отслеживания количества нулей в каждом столбце (по одному куску на столбец) и одно для отслеживания этих.Потенциальные строки, которые нарушают второе правило, игнорируются кратким тестом.Эти целые числа инициализируются в соответствии со входом (плюс 0x33333333, так что 4 в столбце не устанавливают старший бит клочка, а 5 или более), и обновляются только с ячейками, которые ранее были пустыми.

Наконец, в нижней части дерева рекурсии последняя строка полностью продиктована двумя целыми числами, которые считают единицы и нули в столбцах (даже одного из них достаточно для определения последней строки).Затем выполняется проверка для дублирующих столбцов - это единственное, что не гарантируется автоматически при построении.В целом время сократилось с минуты до десятой доли секунды (обычно меньше).

Я все еще открыт для предложений (хотя это действительно сделало бы этот вопрос совершенно другим).Эта процедура подсчета используется для генерации «хороших» начальных конфигураций с помощью грубой силы - чем быстрее она работает, тем лучше может быть результат за отведенное время.

Answer 1

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

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

Вы должны посмотреть за пределы цикла на то, что на самом деле означают данные, чтобы найти способ упростить часть работы.

Answer 2

Вы запрашиваете лучшую структуру данных, но что, если ее нет?

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