Самый быстрый способ найти наименьшее отсутствующее целое число из списка целых

Question

У меня есть список из 100 случайных чисел.Каждое случайное целое число имеет значение от 0 до 99. Допускаются дубликаты, поэтому список может выглядеть примерно так:

56, 1, 1, 1, 1, 0, 2, 6, 99...

Мне нужно найти наименьшее целое число (> = 0), которое равно , а не содержится в списке.

Мое первоначальное решение таково:

vector<int> integerList(100); //list of random integers
...
vector<bool> listedIntegers(101, false);
for (int theInt : integerList)
{
    listedIntegers[theInt] = true;
}
int smallestInt;
for (int j = 0; j < 101; j++)
{
    if (!listedIntegers[j])
    {
        smallestInt = j;
        break;
    }
}

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

Answer 1

Потенциально вы можете уменьшить последний шаг до O (1), используя некоторые битовые манипуляции, в вашем случае __ int128 , установить соответствующие биты в первом цикле и вызвать что-то вроде __ builtin_clz или используйте соответствующий битовый хак

Answer 2

Поскольку вам нужно сканировать весь список, несмотря ни на что, ваш алгоритм уже довольно хорош.Единственное улучшение, которое я могу предложить, не измеряя (что, безусловно, ускорит процесс), - это избавиться от вашего vector<bool> и заменить его выделенным в стеке массивом из 4 32-разрядных целых или 2 64-разрядных целых чисел.

Тогда вам не придется каждый раз платить за размещение массива в куче, и вы можете получить первое неиспользуемое число (положение первого 0-битного) намного быстрее.Чтобы найти слово, содержащее первый бит 0, вам нужно найти только первый бит, который не является максимальным значением, и есть хаки, которые можно использовать, чтобы очень быстро получить первый бит 0 в этом слове.

Answer 3

Ваша программа уже очень эффективна, в O (n).Можно найти только предельный выигрыш.Одна возможность состоит в том, чтобы разделить число возможных значений на блоки размером block и зарегистрировать не в массиве bool, а в массиве int, в этом случае запоминание значения по модулю block.
На практикемы заменяем цикл размером N на цикл размером N/block плюс цикл размером block.
Теоретически мы можем выбрать block = sqrt(N) = 12, чтобы минимизировать количество N/block + block.
Далее в программе выбирается блок размером 8, при условии, что деление целых чисел на 8 и вычисление значений по модулю 8 должны быть быстрыми.
Однако ясно, что усиление, если оно есть, может быть получено только для минимумазначение довольно большое!

constexpr int N = 100;
int find_min1 (const std::vector<int> &IntegerList) {
    constexpr int Size = 13;    //N / block
    constexpr int block = 8;
    constexpr int Vmax = 255;   // 2^block - 1

    int listedBlocks[Size] = {0};
    for (int theInt : IntegerList) {
        listedBlocks[theInt / block] |= 1 << (theInt % block);
    }
    for (int j = 0; j < Size; j++) {
        if (listedBlocks[j] == Vmax) continue;
        int &k = listedBlocks[j];
        for (int b = 0; b < block; b++) {
            if ((k%2) == 0) return block * j + b;
            k /= 2;
        }
    }
    return -1;
}

Answer 4

Я считаю, что нет более быстрого способа сделать это.В вашем случае вы можете повторно использовать vector<bool>, вам нужно иметь только один такой вектор на поток.

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