Эффективно выберите целое число, отличное от всех элементов списка

Ответ 1

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

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

Преимущество такого вероятностного подхода состоит в том, что вы невосприимчивы к плохим последовательностям ценностей. Такие последовательности всегда возможны с подходами на основе диапазона. Если вы вычисляете минимальные и максимальные данные, вы рискуете, что данные содержат как 0, так и 2^32-1. Если вы последовательно разделяете интервал, вы рискуете всегда получать значения в середине интервала, который может сжать его до нуля на 32 шага. С вероятностным подходом эти последовательности не могут причинить вам вреда.

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

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

Ответ 2

Если вы можете поместить один указатель в каждый объект, вы легко получаете алгоритм наихудшего случая O(n) (стандартный разделитель и победа):

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

Пример кода с использованием двух поддиапазонов на итерацию:

unsigned getunusedid(element* h) {
    unsigned start = 0, stop = -1;
    for(;h;h = h->mainnext)
        h->next = h->mainnext;
    while(h) {
        element *l = 0, *r = 0;
        unsigned cl = 0, cr = 0;
        unsigned mid = start + (stop - start) / 2;
        while(h) {
            element* next = h->next;
            if(h->id < mid) {
                h->next = l;
                cl++;
                l = h;
            } else {
                h->next = r;
                cr++;
                r = h;
            }
            h = next;
        }
        if(cl < cr) {
            h = l;
            stop = mid - 1;
        } else {
            h = r;
            start = mid;
        }
    }
    return start;
}

Еще несколько замечаний:

• Beware of bugs in the above code; I have only proved it correct, not tried it.
• Использование большего количества ведер (лучше всего использовать 2 для простой и эффективной обработки), каждая итерация может быть быстрее из-за лучшей локализации данных (хотя только попытайтесь измерить, если это не так быстро), а @MarkDickson справедливо замечает.
• Без этих дополнительных указателей вам нужна полная развертка на каждой итерации, повышая привязку до O(n*lg n).

Альтернативой может быть использование 2+ дополнительных указателей на элемент для поддержания сбалансированного дерева. Это ускорит поиск id файлов за счет нехватки памяти и времени наложения/удаления.

Ответ 3

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

Добавьте два целых числа без знака в ваш класс списка:

unsigned int rangeMinId = 0;
unsigned int rangeMaxId = 0xFFFFFFFF ;

Или, если не возможно изменить класс List, добавьте их в качестве глобальных переменных.

Когда список пуст, вы всегда будете знать, что диапазон, если он свободен. Когда вы добавляете новый элемент в список, проверьте, находится ли его идентификатор между rangeMinId и rangeMaxId, и если это так изменит ближайший из них на этот идентификатор.

Это может произойти после того, как много времени, которое rangeMinId станет равным rangeMaxId-1, вам понадобится простая функция, которая пересекает весь список и ищет другой свободный диапазон. Но это не произойдет очень часто.

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

Update:

Функция поиска свободного диапазона может быть выполнена в O (n * log (n)). Пример такой функции приведен ниже (я ее не тестировал). Пример для целочисленного массива, но легко может быть адаптирован для списка.

int g_Calls = 0;

bool _findFreeRange(const int* value, int n, int& left, int& right)
{
    g_Calls ++ ;

    int l=left, r=right,l2,r2;
    int m = (right + left) / 2 ;
    int nl=0, nr=0;
    for(int k = 0; k < n; k++)
    {
        const int& i = value[k] ;

        if(i > l && i < r)
        {
            if(i-l < r-i)
                l = i;
            else
                r = i;
        }

        if(i < m)
            nl ++ ;
        else
            nr ++ ;

    }


    if ( (r - l) > 1 )
    {
        left = l;
        right = r;
        return true ;
    }

    if( nl < nr)
    {
        // check first left then right
        l2 = left;
        r2 = m;
        if(r2-l2 > 1 && _findFreeRange(value, n, l2, r2))
        {
            left = l2 ;
            right = r2 ;
            return true;
        }

        l2 = m;
        r2 = right;
        if(r2-l2 > 1 && _findFreeRange(value, n, l2, r2))
        {
            left = l2 ;
            right = r2 ;
            return true;
        }

    }

    else
    {
        // check first right then left
        l2 = m;
        r2 = right;
        if(r2-l2 > 1 && _findFreeRange(value, n, l2, r2))
        {
            left = l2 ;
            right = r2 ;
            return true;
        }

        l2 = left;
        r2 = m;
        if(r2-l2 > 1  && _findFreeRange(value, n, l2, r2))
        {
            left = l2 ;
            right = r2 ;
            return true;
        }
    }

    return false;
}

bool findFreeRange(const int* value, int n, int& left, int& right, int maxx)
{
    g_Calls = 1;
    left = 0; 
    right = maxx;

    if(!_findFreeRange(value, n, left, right))
        return false ;

    left++;
    right--;

    return (right - left) >= 0 ;
}

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

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

Ответ 4

Если вы не против сканирования O (n) для каждого изменения в списке и двух дополнительных битов на элемент, всякий раз, когда элемент вставлен или удален, выполните сканирование и используйте два бита, чтобы представить, является ли целое (элемент + 1) или (element-1) существует в списке.

Например, вставив элемент 2, дополнительные биты для каждого 3 и 1 в списке будут обновлены, чтобы показать, что 3-1 (в случае 3) и 1+1 (в случае 1) теперь существуют в списке.

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

Ответ 5

Это напоминает мне книгу "Программирование жемчуга" и, в частности, самый первый столбец "Cracking the Oyster" . Какова реальная проблема, которую вы пытаетесь решить?

Если ваш список невелик, тогда простой линейный поиск для поиска max/min будет работать, и он будет работать быстро.

Когда ваш список становится большим, а линейный поиск становится громоздким, вы можете создать растровое изображение для представления неиспользуемых номеров для гораздо меньшего объема памяти, чем добавление 2 дополнительных указателей в каждом node в связанном списке. Фактически, это было бы только 2 ^ (32-8) = 16 КБ ОЗУ по сравнению с вашим связанным списком, потенциально превышающим 10 ГБ.

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

Ответ 6

Одно из возможных решений - взять min и max списка с простой итерацией O(n), а затем выбрать число между max и min + (1 << 32). Это просто сделать, поскольку поведение переполнения/нижнего потока хорошо определено для целых чисел без знака:

uint32_t min, max;
// TODO: compute min and max here

// exclude max from choice space (min will be an exclusive upper bound)
max++;

uint32_t choice = rand32() % (min - max) + max; // where rand32 is a random unsigned 32-bit integer

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

Примечание: единственный случай, когда это не удается, - это если min равно 0, а max - UINT32_MAX (aka 4294967295).

Ответ 7

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

1.Ваш список Добавить участника:

unsigned int NextFreeId = 1;

• добавить также std:: set < unsigned int > Идентификаторы

• Когда вы добавляете элемент в список, добавьте также целое число в набор и отслеживайте значение NextFreeId:

int insert (unsigned int id)   {      ids.insert(ID);

if (NextFreeId == id) //will not happen too frequently
{
    unsigned int TheFreeId ;
    unsigned int nextid = id+1, previd = id-1;
    while(true )
    {
        if(nextid < 0xFFFFFFF && !ids.count(nextid))
        {
            NextFreeId = nextid ;
            break ;
        }

        if(previd > 0 && !ids.count(previd))
        {
            NextFreeId = previd ;
            break ;
        }

        if(prevId == 0 && nextid  == 0xFFFFFFF)
          break;  // all the range is filled, there is no free id

        nextid++ ;
        previd -- ;
    }
}

return 1;

}

Наборы очень эффективны, чтобы проверить, содержится ли значение, поэтому сложность будет равна O (log (N)). Он быстро реализуется. Также задается поиск не каждый раз, а только при заполнении NextFreeId. Список не проходит вообще.