// An efficient program to randomly select a number from stream of numbers.
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <time.h>
/* A program to randomly select a item from stream[0], stream[1], ..
stream[i-1]*/int main()
{
int stream[] = { 1, 2, 3, 4 };
int n = sizeof(stream) / sizeof(stream[0]);
// Use a different seed value for every run.
srand(time(0));
cout << "Random no. selected: " << stream[(rand() % n)] << "\n";
return 0;
}
Приведенный выше код C ++ требует памяти в диапазоне от 2,9 … (что-то) МБ или больше, до 3,04 … (что-то) МБ или больше.
И рассмотрим следующий код C:
/* An efficient program to randomly select a number from
stream of numbers.*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* A function to randomly select a item from stream[0], stream[1], ..
stream[i - 1]*/
int selectRandom(int x)
{
static int res; // The resultant random number
static int count = 0; //Count of numbers visited so far in stream
count++; // increment count of numbers seen so far
// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
int i = rand() % count;
// Replace the prev random number with new number with 1/count
//probability
if (i == count - 1)
res = x;
}
return res;
}
// Driver program to test above function.
int main()
{
int stream[] = { 1, 2, 3, 4 };
int n = sizeof(stream) / sizeof(stream[0]);
// Use a different seed value for every run.
srand(time(NULL));
for (int i = 0; i < n; ++i)
printf("Random number from first %d numbers is %d \n",
i + 1, selectRandom(stream[i]));
return 0;
}
Приведенный выше код требует памяти в диапазоне 1,28 .. (что-то) МБ или больше, но, безусловно, менее 2 МБ.
У меня вопрос: почему первая программа занимает больше места, чем вторая, и как?
При использовании предоставленного онлайн-редактора использование памяти не соответствует фактическому распределению. Если я напишу программу с malloc(1);
статистика «памяти» такая же, как и malloc(10000000);
. Я уверен, что эта статистика — просто размер исполняемого файла.
Других решений пока нет …