Случайное число

[rommster]

Имеются два массива чисел - два "чёрных списка" (ч.с). Нужно сгенерировать число (0<=X<=49), отличное от элементов ч.с. Делаю так: генерирую число и сравниваю с элементами ч.с, пока не получится подходящее число. Хотя этот конкретный пример работает довольно быстро но код неэффективен при большом размере ч.с. Возникают т.н. неопределённые отсрочки. Подскажите хотя бы, в каком направлении мне думать? Спасибо.

Вот код. Написан наверное коряво, только учусь...

#include <iostream.h>

void getNumber()
{
	const int aSize = 7;
	const int bSize = 8;
	const int limit = 50;
	int a[aSize]={1,5,8,15,23,44,49}; // Ч.с 1
	int b[bSize]={3,7,9,16,30,32,40,42}; // Ч.с. 2

	int x,i;
	bool f=true;	// Признак совпадения с ч.с.

	while(f==true)	// Выполнять, пока X попадает в ч.с
	{
		f=false;
		x=rand()%limit;	// Генерация X
		for(i=0; i<aSize; i++) // Сравнение с ч.с. 1
			if(x==a[i])
			{
				f=true;
				break;
			}

		if (!f)
			for(i=0; i<bSize; i++) // Сравнение с ч.с. 2
				if(x==b[i])
				{
					f=true;
					break;
				}
	}
	cout<<"X = "<<x<<endl;
}

int main()
{
	int j;
	srand(time(NULL));
	clock_t t0 = clock();
	for(j = 0; j<100000; j++)	// Прогон функции 10000 раз
		getNumber();
	clock_t t1 = clock();
	cout << "\ntime: " << (double)(t1 - t0) / CLOCKS_PER_SEC << endl;


	cout<<endl;
	system("pause");
	return 0;
}

[Serge_Bliznykov]

ну, как я понимаю, других вариантов и быть не может!
Единственное, в Ч.С. нужно ввести сортировку и проверять очередное случайное число на наличие в Ч.С. по ключу (чтобы избавиться от перебора).


ДОБАВЛЕНО

0<=X<=49

речь идёт о целых числах, как я понимаю?!
Дык, тогда чисел в чёрном списке может быть не больше 50 ?!! Тогда, как не крути - будет всё равно быстро )

А по поводу того, что других вариантов и быть не может - я не прав!
Тут, как раз, раз множесто чисел такое маленькое - вариантов пруд пруди.
Например, заполняем матрицу числами от 0 до 49
потом удаляем из неё те числа, которые есть в обоих Ч.С. - как удалить число из массива - думаю, вопросов не вызывает?
Потом берём любое число из этого массива (получаем случайный индекс).
Всё.
плюс такого подхода ещё в том, что если вдруг Ч.С. полностью закрывают диапазон от 0 до 49 - то это сразу можно будет увидеть - в исходном массиве не останется ни одного числа!
А в случае с перебором цикл будет крутиться до бесконечности!

[rommster]

Serge_Bliznykov, спасибо за советы. Ну 50 это у меня так, к примеру, на самом деле может быть до 10000) Попробовал сделать, как вы советовали, не знаю насколько правильно, но работает.

#include <iostream.h>

void getNumber()
{
	const int aSize = 7;
	const int bSize = 8;
	const int limit = 50;
	int a[aSize]={1,5,8,15,23,44,49}; // Ч.с 1
	int b[bSize]={3,7,9,16,30,32,40,42}; // Ч.с. 2

	int x,i,j,k;
	int tmp[limit], tmpN;
	int size = limit;
	for(i=0; i<size; i++)
		tmp[i] = i;

	for(i=0; i<aSize; i++)  // отмечаю -1 те эл-ты, которые надо удалить,
		tmp[a[i]]=-1;    // ибо как удалить сразу и при этом быстро - не могу придумать


	for(i=0; i<bSize; i++)
		tmp[b[i]]=-1;


	for(i=0; i<size; i++) // удаляю сдвигом, не уверен, что правильно
	{
		if(tmp[i]==-1)
		{
			for(j=i; j<size-1; j++)
			{
				tmp[j]=tmp[j+1];
			}
			i--;
			size--;
		}
	}
	x = tmp[rand()%size];
	cout<<"X = "<<x<<endl;;

}

int main()
{
	int j;
	srand(time(NULL));
	clock_t t0 = clock();

	for(j = 0; j<100000; j++)
		getNumber();

   	clock_t t1 = clock();
	cout << "\ntime: " << (double)(t1 - t0) / CLOCKS_PER_SEC << endl;
	cout<<endl;
	system("pause");
	return 0;
}

Проблема только в том, что этот код работает ещё медленнее. Так время 100000 прогонов первой проги = 0.032c, второй 0.927 (без учёта печати на экран). Если же увеличить limit 1000, а размер ч.с. до 500, то первая выполняется за 7.031с, а вторая - 104.141(!!!). Первый вариант работает таки быстрее, но при рандомной генерации числа ведь можно попадать несколько раз в одну и ту же точку? Означает ли это вероятность бесконечно долгого выполнения?

[Stilet]

rommster

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

[rommster]

Попробовал с бинарным поиском, если правильно конечно написал. Массивы по умолчанию уже отсортированы.

bool binarySearch(int a[], int size, int key)
{
	int middle, high, low;
	low=0;
	high=size-1;
	while (low <= high)
	{
		middle = (low + high) / 2;
		if (a[middle] == key)
			return true;
		if (a[middle] < key)
			low = middle + 1;
		if (a[middle] > key)
			high = middle - 1;
	}
	return false;
}


void getNumber()
{
	const int aSize = 7;
	const int bSize = 8;
	const int limit = 50;
	int a[aSize]={1,5,8,15,23,44,49};
	int b[bSize]={3,7,9,16,30,32,40,42};
	int x,i,step=0;
	bool f=true;

	while(f==true)
	{
		step++;
		f=false;
		x=rand()%limit;	// Генерация X
			if(binarySearch (a, aSize, x))
			{
				f=true; continue;
			}

			if(binarySearch (b, bSize, x))
				f=true;
	}
	cout<<"\t\tX = "<<x<<"\tStep = "<<step<<endl;
}

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

[Stilet]

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

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

ДОПИСАНО:
Вот что я имел ввиду:

// sfsdf.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
#include <locale>
#include <math.h>
#include <list>
#include <conio.h>
using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"russian");
    list<int> l1;
    int b;
    b=1;    l1.push_back(b);
    b=5;    l1.push_back(b);
    b=34;    l1.push_back(b);
    b=100;    l1.push_back(b);
    b=120;    l1.push_back(b);

    do{
    for(list<int>::iterator i=l1.begin();i!=l1.end();i++){
        int bb, l=*i,h=*++i;
        
        if (l<h){
            bb=(double)rand() / (RAND_MAX + 1) * (h - l)+ l;
            
            
            if(bb!=l&&bb!=h){ 
                l1.insert(i,bb);
                cout<<" new="<<bb<<'\t';
                break;
            }
        }
    }
    for(list<int>::iterator i=l1.begin();i!=l1.end();i++){
        int bb, l=*i;
        cout<<l<<'\t';
    }
    cout<<'\n';
    }while(getch()!=13);
    system("pause");
    return 0;
}

[rommster]

Сообщение от Stilet

Запоминать места где есть дырки и генерировать не со всей последовательности а только по тем частям массива где заведомо извесны дырки

Ага, тоже об этом думал) Но ничего путного так и не получилось) Спасибо, пойду разбираться!

[coinkrsk]

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

[coinkrsk]

Бывает же такое. Заинтерисовал своей задачкой. Я даже сел и написал.

#include <iostream>
#include <vector>
#include <time.h>
using std::cout;
using std::endl;

class UnicNumGenerator
{
public:
	UnicNumGenerator(	const int* pBlackList_1, int blackListSize_1, 
						const int* pBlackList_2, int blackListSize_2,
						int limit);
	int generate();
private:
	bool binarySearch(const int* a, int length, int key);
	std::vector<int> unicNumList;
	//int unicNumListSize;

};

bool UnicNumGenerator::binarySearch(const int* a, int length, int key) 
{
	int low = 0;
	int high = length - 1;

	while (low <= high) 
	{
		int mid = low + ((high - low) / 2);
		int midVal = a[mid];

		if (midVal < key)
			low = mid + 1;
		else if (midVal > key)
			high = mid - 1;
		else
			return true; // key found
	}
	return false;  // key not found.
}

UnicNumGenerator::UnicNumGenerator(	const int* pBlackList_1, int blackListSize_1, 
									const int* pBlackList_2, int blackListSize_2,
									int limit)
{
	for(int i = 0; i < limit; i++)
		if (!binarySearch( pBlackList_1, blackListSize_1, i ) &&
			!binarySearch( pBlackList_2, blackListSize_2, i ) )
				unicNumList.push_back(i);
}

int UnicNumGenerator::generate()
{
	return unicNumList[ rand() % unicNumList.size() ];
}


int main()
{
	std::srand( (unsigned)time(0) );

	const int aSize = 7;
	const int bSize = 8;
	const int limit = 50;
	int a[aSize]={1,5,8,15,23,44,49}; // Ч.с 1
	int b[bSize]={3,7,9,16,30,32,40,42}; // Ч.с. 2


	clock_t begin, end;

	begin = clock();

	UnicNumGenerator myGenerator( a, aSize, b, bSize, limit );

	for(int j = 0; j < 100000; j++)
		myGenerator.generate();
		//cout << myGenerator.generate() << ' ';

	end = clock();
	cout << "\ntime: " << (double)(end - begin) / CLOCKS_PER_SEC << endl;
	
	return 0;
}

на моем тормозном ноутбуке:
при limit=50 время 0.004 секунды
при больших лимитах выйгрыш вообще будет несравнимым.

[rommster]

coinkrsk, спасибо, шустро летает! Я в своём посте #3 выкладывал свой код с такой же по сути идеей - составлять массив уникальных элементов. Только работает он слишком тормозно. Я конечно понимаю, что код жуткий: использую простой поиск вместо бинарного, тупое удаление элемента массива и.т.п. Но неужто только из-за этого прога может выполняться аж 100 секунд вместо долей секунды, как у вас? Дело в использовании вектора что ли?