Мне дано 6 чисел: 65, 96, 124, 152, 183, 218 я хотел используя готовый генератор псевдослучайных чисел из какой нибудь библиотеки, сгенерировать случайные числа,но сделать это так что эти числа не совпадали с исходными 6 числами,и находились в промежутки между ними,но проблема в том если чисел дано было не 6 а 150 000 насколько это было сложно реализовать ?
Вместо того чтобы генерировать числа и проверять их, нужно сразу генерировать число из правильного интервала.
Интервал кодируется двумя числами, число кодируется одним числом. Сравнение числа с интервалом это два сравнения, сравнение числа с числом - одно. Для 150000 чисел будет 150001 интервалов. Получается, что самый оптимальный с точки зрения использования памяти и машинного времени способ - самый тупой из всех: хранить запрещенные числа и каждое значение гпсч сравнивать с каждым из них.
Если интервалы почти равномерные можно бросать кубик два раза - сперва в какой интервал выпадает очередное число, а потом какое оно внутри этого интервала. Если границы интервалов не сильно велики по размеру можно снизить сложность до линейной построив вспомогательный массив смещений. Пусть граничных чисел 3 - назовём это числом N. Для простоты вычтем из них первое число чтобы базис отталкивался от 0 (потом всегда можно добавить чтобы вернуться в исходную область). Пусть получатся 0, 3 и 8. Последний элемент 8 - значит нам нужен вспомогательный массив размером [0..8-N] и это будет: 0->1 1->2 2->4 3->5 4->6 5->7 Т.е. мы линейно заполняем его увеличивающимися числами, но там где должно получится интервальное число прибавляем еще 1 чтобы его пропустить. Если массив интервалов отсортирован по возрастанию, то строится тоже линейным проходом. Теперь останется только выкидывать числа от 0 до 5 и берем результат по этому индексу в этом массиве и добавлять поправку которую вычли в начале. Если же границы интервалов сильно велики и не получится промежуточный массив выделить разумный в памяти, то можно тем не менее удерживать сложность в рамках O(N*logN) если по сути делать то же самое, если превратить этот массив в похожую по смыслу структуру данных где будем искать бинарным поиском в каком интервале оказались и извлекать из него нужные смещения и добавки.
БитМап --- Сообщение объединено, 24 сен 2025 --- дольше отсортированным списком - самый простой поиск по деревяшке.
aa_dav, получается что нужно найти разность между интеревальными числами,то есть 96 - 65 = 31 (1 интеревал 65,96 152 - 124 = 28 (2 интеревал 124,152 218 - 183 = 35 (3 интеревал 183,218 если ГПСЧ сгенерирует значение больше или равно разности одного из интервалов,придётся сравнивать все разности интервалов,то есть если ГПСЧ выдаёт число 17,надо сравнить это число со всеми 3 разностями интеревалов,а это число меньше 31,28,35 а если его прибавить к начальному числу любого из интервалов,65 + 17 = 82,это число находится между 65 и 96,но если ГПСЧ сгенерирует равное число разности придётся уменьшить на 1,то есть по потреблению ресурсов,нужен массив котором будут находится разности интеревалов,чем больше интервалов тем сравнений придётся проводить --- Сообщение объединено, 30 сен 2025 --- если я правильно понял,битмап это представить в виде последовательности битов
Можно вычислить X=max(N-N-1) и генерировать Random(X*R), где R количество запрещенных. После просто делим на X и остаток от деления +1 будет смещением от K-го запрещенного числа, где K частное. Для X степени 2 можно обойтись логическими операциями. Если значение совпало со следующими запрещенным(и), тогда просто уменьшаем X на 1 пока X > 0, а при X=0 повторяем генерацию. Или, в случае совпадения, можно сразу повторять генерацию для Random(X). Хотя жадный алгоритм в таком подходе может давать сбои (зацикливания). Лучше, для современных компьютеров, сделать bitmap - памяти предостаточно. Тогда проверки будут сильно упрощены (сводиться к проверке одного бита). Но вот, в зависимости от диапазона, этот подход с bitmap может и не подойти. Числа больше (128 или 512)×109 вызовут проблемы даже у современных компьютеров. Да и сама инициализация такого блока памяти может быть дольше чем жадный алгоритм.
Моя идея заключается в том, чтобы уйти от сравнения со всеми интервалами. Мой пример с интервалами (0), 1, 2, (3), 4, 5, 6, 7, (8) где в скобках стоят границы интервалов. Их нельзя выбирать, значит чисел для выбора всего 6: 1, 2, 4, 5, 6, 7. Так и будем выбирать сразу только из них построив промежуточный массив и выкидывая рандом от 0 до 5 (индексация массивов с нуля). Но выкинув число надо понять в какой оно интервал попало, чтобы пропустить все предыдущие запрещенные числа. Если по памяти возможно построить промежуточный массив (что по сложности линейная операция O(N)), то он еще может выглядеть вот так: 0 -> 1 1 -> 1 2 -> 2 3 -> 2 4 -> 2 5 -> 2 Назовём этот массив A. Это просто немного переформатированный вариант массива что я предлагал выше - вместо абсолютных значений хранятся смещения к ним от текущего индекса. Фактически каждая ячейка такого массива соответствует ровно одному "числу из которого можно выбрать" (1, 2, 4, 5, 6, 7) уплотнённому в пространство без промежутков, но каждый элемент содержит сколько ранее в исходном ряде было запрещенных чисел чтобы пропустить их добавив к полученному числу. если выпало X=random(0, 5) , то искомое значение есть X + A[ X ] Например для X=0 получится 0 + 1 = 1 Для X=1 получится 1 + 1 = 2 А для X = 2 получится 2 + 2 = 4 Мы сразу получаем нужное число без сравнений после предзаготовки промежуточного массива. Однако если размеры промежутков очень большие и промежуточный массив занимает слишком много памяти, то придётся уплотнить его информацию в отсортированный массив данных где будут лежать только начала промежутков и их смещения: 0 -> [ 0, 1 ] 1 -> [ 2, 2 ] (нетрудно заметить, что смещение это тупо индекс + 1, т.е. это всего лишь сводится к отсортированному массиву начала промежутков: 0 -> 0 1 -> 2 Но это верно только если запрещенные числа не могут соседствовать - идти без промежутков - если могут, то надо делать структуру в предыдущем виде, ибо где то смещения будут больше чем +1. Задача встаёт теперь в том чтобы максимально быстро в этой структуре данных найти в какой из промежутков мы попали чтобы извлечь смещение единое для всего этого промежутка. Если в этом массиве не больше около десятка элементов то из-за кешей быстрее делать линейный поиск. Если же речь про гигантские его размеры - есть двоичный поиск который даст к сложности множитель log2(N), а не N.
aa_dav, если я тебя правильно понял, то нужно получить индекс в промежуточном массиве MaKsIm, если я правильно думаю, то что бы сделать bitmap, это таблица степеней двойки, если это попробовать применить к интервалу какому-нибудь, например 65,96 то получается 26= 64 ,27= 128 числа 65 и 96 находятся между 64 и 128
Если я правильно понял. Для промежуточных массивов получить массив средних чисел - centroids_arr. Сгенерировать случаное число в диапазоне от min(centroids_arr) до max(centroids_arr). Вычислить к какому из элементов centroids_arr ближе всего сгенерированное random_num. Код (Text): dist[i] = Abs(centroids_arr[i] - random_num). В диапазоне где dist(i) минимально, генерировать промежуточное число(для этого сделать отдельную функцию).
Если диапазон значений близок к 0, тогда можно не морочиться с оффсетом. Но если надо вычислять в диапазоне +1000000 .. +9999999, тогда можно задать оффсет (+1000000) для проверки и сократить на 256 Кб объем памяти (т.е. длина битмапа будет 8999999 бит или 1125000 байт).
Главная идея - выкидывать случайное число только над множеством элементов без граничных. Для этого надо как то выкинуть граничные элементы и оставить только полезные. Это можно сделать напрямую - взять массив где есть все числа и удалить из него граничные. И выкидывать рандом на оставшемся массиве сразу доставая из него номер куда рандом попал. Это максимально быстро. А далее я развиваю идею до варианта когда промежуточный массив непомерно большой - чтобы обойтись без него, но не упереться в квадратичную сложность можно снизить сложность до log(N) слегка поменяв что мы храним и как.
Ничего не перемножал. Поделил: Начало диапазона: 1000000 Конец диапазона: 9999999 9999999-1000000=8999999/8=1125000 (округляем до целого в большую сторону т.к. байты занять частично не выйдет)=1125000/1кб=1125кб/1024=1,125Мб В прошлый раз обсчитался и сказал 256 Кб, но это от деления на 4, а не на 8. Правильно 128 Кб.
MaKsIm, я думаю,если bitmap применить к меньшему диапазону,например к 65,96,то есть если эти числа представить в битов 65 = 100 0001b , 96 = 110 0000b оба эти числа 8 бит,если биты считать справа налево то с 0 до 7,если посмотреть на последние 5 бит 96 то это нули,если установить еденицу в промежутки с 5:1 бит числа 65,то получится 69 = 100 0101b это число попадает в диапазон 65,96
