Exclure dynamiquement certains nombres d'une séquence générée aléatoirement

Question

Je souhaite produire une séquence aléatoire de nombres entre une plage, par exemple 100 to 200. Après un certain temps, en fonction de certains événements, je veux produire une nouvelle séquence entre la même gamme (100 à 200), mais cette fois je veux exclure certains nombres. Par exemple, je ne veux pas [150,165,170].

Et la prochaine fois, ces numéros exclus peuvent être inclus ou non dans la séquence.

Une approche possible pourrait être un tableau de nombres comme ceci:

int rndm[] {100,101,102,103,...}; 

et utiliser l'index du tableau pour générer un nombre aléatoire à un moment:

random(rndm[0-99]); 

Mais je dois utiliser le moins de structures d'instructions/de données possible afin d'atteindre la performance.

J'utilise C pour ce code et j'utilise random() ou randomSeed(seed) et je veux savoir ce que l'approche la plus efficace pour traiter cette question est, en termes de structures de données devraient être utilisées pour la vitesse et de la mémoire.

Answer 1

Cette solution est efficace dans le cas où il n'y a pas beaucoup d'exclusions pendant la durée de vie, une fois que la fonction d'exclusion est quadratique.

Il existe une structure appelée RandomArray qui contient un pointeur vers et un tableau avec la taille N. N est la taille souhaitée de la séquence. La complexité temporelle et spatiale est linéaire O (N) pour la fonction de création.

Lorsqu'un événement se produit, il doit appeler la fonction excludeValue, avec une complexité temporelle de O (N) et de la complexité de l'espace 1.

Si l'on souhaite exclure un groupe de valeurs, la fonction excludeValues ​​ (faites attention à s à la fin) doit être appelé. Dans ce cas, la complexité est O (N x K) et la complexité de l'espace est 1. K est la quantité de valeurs qui doit être exclue.

#include <stdio.h> 
#include <stdlib.h> 

struct RandomArray { 
    int *pData; 
    size_t dataLen; 
    int excludedIdx; 
}; 
struct RandomArray *excludeValue(struct RandomArray *pAr, int val) { 
    size_t i; 
    for (i = 0; i < pAr->excludedIdx; ++i) { 
    if (pAr->pData[i] == val) { 
     pAr->excludedIdx--; 
     int tmp = pAr->pData[i]; 
     pAr->pData[i] = pAr->pData[pAr->excludedIdx]; 
     pAr->pData[pAr->excludedIdx] = tmp; 
     // Do test again the position 
     --i; 
    } 
    } return pAr; 
} 

struct RandomArray *excludeValues(struct RandomArray *pAr, int *pVals, size_t len) { 
    size_t i; 
    for (i = 0; i < len; ++i) 
    excludeValue(pAr, pVals[i]); 
} 

struct RandomArray *destroyRandomArray(struct RandomArray *pAr) { 
    if (pAr) { 
    if (pAr->pData) 
     free(pAr->pData); 
    pAr->dataLen = 0; 
    } 
    return pAr; 
} 

struct RandomArray *createRandomArray(
struct RandomArray *pAr, 
size_t dataLen, 
int lowLimit, int highLimit) { 
    int i; 
    int range = (highLimit - lowLimit); 
    pAr->pData = (int*)malloc(sizeof(int) * dataLen); 
    pAr->dataLen = dataLen; 
    srand(time(NULL)); 
    for (i = 0; i < dataLen; ++i) { 
    pAr->pData[i] = rand() % (range + 1) + lowLimit; 
    } 
    // Clear excluded indexs 
    pAr->excludedIdx = pAr->dataLen; return pAr; 
} 

void printRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Random Array (len = %d): ", pAr->dataLen); 
    for (i =0; i < pAr->dataLen; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printValidRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Valid Random Array (len = %d): ", pAr->excludedIdx); 
    for (i =0; i < pAr->excludedIdx; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printExcludedRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Excluded Random Array (len = %d): ", pAr->dataLen - pAr->excludedIdx); 
    for (i = pAr->excludedIdx; i < pAr->dataLen; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printAllRandomArray(struct RandomArray *pAr) { 
    printRandomArray(pAr); 
    printValidRandomArray(pAr); 
    printExcludedRandomArray(pAr); 
} 

int main() { 
    int lowLimit = 100; 
    int highLimit = 105; 
    int arrayLen = 10; 
    struct RandomArray myAr; 
    createRandomArray(&myAr, arrayLen, lowLimit, highLimit); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 100); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 101); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 102); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 103); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 104); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 105); 
    printAllRandomArray(&myAr); 
    destroyRandomArray(&myAr); 
    createRandomArray(&myAr, arrayLen, lowLimit, highLimit); 
    printf("\n\n\n"); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    int vals[] = { 102, 105, 104 }; 
    excludeValues(&myAr, vals, sizeof(vals)/sizeof(vals[0])); 
    printAllRandomArray(&myAr); 
    destroyRandomArray(&myAr); 
} 

Answer 2

Cela a été demandé here on the Arduino forum mais je l'ai vu ici aussi. Ma réponse est dans la saveur de C++ d'Arduino depuis qu'il a été posté là ...

Bien sûr, la performance varie à mesure que l'ensemble des nombres exclus augmente par rapport à l'ensemble des nombres à utiliser pour créer votre "nouvelle séquence".

void setup() { 
    Serial.begin(115200); 
    randomSeed(analogRead(A0)); 
} 
void loop() { 
    // create an arbitray sized array to be filled with unique values to exclude from desired array 
    const int arraySize = 5; 
    int exclusions[arraySize]; 
    for (int i = 0; i < arraySize; i++) { 
    // fill the array with unique values... 
    int val; 
    do { 
     val = random(100, 200); 
    } while([&]() { 
     for (auto j : exclusions) { 
     if (val == j) { 
      return true; 
     } 
     } 
     return false; 
    }()); 
    exclusions[i] = val; 
    } 
    Serial.print(F("Exclusion Array: ")); 
    for (int i = 0; i < arraySize; i++) { 
    Serial.print(exclusions[i]); 
    if (i < arraySize - 1) 
    Serial.print(F(", ")); 
    } 
    Serial.println(); 
    // create a new array of arbitrary length of unique random numbers in >>>the same<<< range as above (but not necessary) 
    Serial.print(F("Starting...\n")); 
    uint32_t start = millis(); 
    const int listSize = 32; 
    int list[listSize]; 
    for (int i = 0; i < listSize; i++) { 
    // fill the array with unique values that will exclude exclusions[] 
    int val; 
    do { 
     val = random(100, 200); 
    } while([&]() { 
     for (auto j : list) { 
     if (val == j) { 
      return true; 
     } 
     for (auto k : exclusions) { 
      if (val == k) { 
      return true; 
      } 
     } 
     } 
     return false; 
    }()); 
    list[i] = val; 
    } 
    uint32_t end = millis(); 
    Serial.println(end - start); 
    // OPTIONAL -> lets sort the final arry to make spotting the duplicates easier: 
    for (int i = 0; i < listSize; i++) { 
    for (int j = i + 1; j < listSize; j++) { 
     if (list[j] < list[i]) { 
     int temp = list[i]; 
     list[i] = list[j]; 
     list[j] = temp; 
     } 
    } 
    } 

    // output the final array 
    Serial.print(F("Final Array: ")); 
    for (int i = 0; i < listSize; i++) { 
    Serial.print(list[i]); 
    if (i < listSize - 1) 
    Serial.print(F(", ")); 
    } 
    Serial.print(F("\n\n\n")); 
    delay(1000); 
}