Оптимальный алгоритм заполнения массива

Программирование
,
81

Читать Д.Кнута сейчас это как читать эпос Гильгамеша на месопотамском языке. Интересно, но для определенных кругов.
ПС: Искусство программирования — Википедия

82

Это кто такой? Кем работает? Чем торгует?)

83

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


#define tblsize	255*2

volatile boolean flg;
volatile uint8_t rnd0;

byte	MaxNum = 20;
byte	rndt [tblsize];

void setup() {

  Serial.begin(115200);
  Serial.setTimeout(20);

  TCCR2A = 0;
  TCCR2B = _BV(CS20);	// no prescaling
  cli();
  wdt_reset();
  WDTCSR |= (_BV(WDCE) | _BV(WDE) | _BV(WDIE));
  WDTCSR  =  _BV(WDIE) | WDTO_250MS;
  sei();
  while (!flg) {}
  wdt_enable (WDTO_1S);
  srand(rnd0);
  GenTbl();
  ShowTbl();
}

// ------------------------------------------------ //
ISR (WDT_vect) {

  rnd0 = TCNT2;
  flg = true;
}

// ------------------------------------------------ //
void loop() {

  if (Serial.available() > 0) {
    char cmd = Serial.read();
    if (cmd == 's') {
      byte tmp = Serial.parseInt();
      if (tmp > 1 && tmp <= 255)
	MaxNum = tmp;
      GenTbl();
      ShowTbl();
    }
    else if (cmd == 'r')
      asm ("jmp 0");
  }
  wdt_reset();
}
// ------------------------------------------------ //
void ShowTbl() {

  for (int i = 0; i < MaxNum; i++) {
    byte num = rndt[i];
    if (num < 10)
      Serial.print("0");
    Serial.print(num);
    Serial.print(" ");
  }
  Serial.println();
}

// ------------------------------------------------ //
void GenTbl() {

  for (byte i = 0; i < MaxNum; i++) {
    rndt[i*2+1] = rand();
    rndt[i*2]=i;
  }

  sortw();
  for (byte i = 1; i < MaxNum; i++) {
    rndt[i] = rndt[i*2];
  }
}

// ------------------------------------------------ //
void sortw() {

  word tmp;
  word *tbl_w = (word *)&rndt;

  for (byte i = 0; i < MaxNum-1; i++) {
    for (byte j = 0; j < MaxNum-1-i; j++) {
      if (rndt[j*2+1] > rndt[j*2+3]) {
	tmp	   = tbl_w[j];
	tbl_w[j]   = tbl_w[j+1];
	tbl_w[j+1] = tmp;
      }
    }
  }
}

seed получается за счет нестабильного WDT гнератора.
Управление:
s <число> - задание размера и генерация
просто s - генерация следуюшего массива
r - перезапуск для проверки seed

84

Моя реализация в коде алгоритма glukmaker.
“Даёшь” тесты скорости заполнения массива! :slightly_smiling_face:

Устарело 
const int16_t variablN = 20;
const int16_t variablK = -10;
const int16_t variablM = 30;

void setup() {
  Serial.begin(9600);
  randomSeed(A0);

  // Start
  uint32_t lenArray = variablN+variablM-variablK;
  uint32_t startIndex = 0;
  uint32_t randomIndex = 0;
  int16_t  variablTemp = 0;
  int32_t randomArray[lenArray]{}; 
  
  for (uint32_t i = 0; i < lenArray; i++)
    randomArray[i] = i + variablK;
  
  for (uint32_t i = 0; i < variablN; i++) {
    variablTemp = randomArray[startIndex];
    randomIndex = random(startIndex, lenArray);
    randomArray[startIndex] = randomArray[randomIndex];
    randomArray[randomIndex] = variablTemp;
    startIndex++;
  }
  //Stop

  for (uint8_t i = 0; i < variablN; i++) {
    Serial.print(randomArray[i]);
    Serial.print(" ");
  }

}

void loop() {}
85

На втором проходе перемешивать нужно весь массив. Заодно минус строка кода.

86

А это же Ваша идея была изначально в это теме.
Так?

const int16_t variablN = 20;
const int16_t variablK = -10;
const int16_t variablM = 30;

void setup() {
  Serial.begin(9600);
  randomSeed(A0);

  // Start
  uint32_t lenArray = variablM-variablK;
  uint32_t randomIndex = 0;
  int16_t  variablTemp = 0;
  int32_t randomArray[lenArray]{}; 
  
  for (uint32_t i = 0; i < lenArray; i++)
    randomArray[i] = i + variablK;
  
  for (uint32_t i = 0; i < variablN; i++) {
    variablTemp = randomArray[i];
    randomIndex = random(0, lenArray);
    randomArray[i] = randomArray[randomIndex];
    randomArray[randomIndex] = variablTemp;
  }
  //Stop

  for (uint8_t i = 0; i < variablN; i++) {
    Serial.print(randomArray[i]);
    Serial.print(" ");
  }

}

void loop() {}
87

Идея не моя, но я её помню.

...
for (uint32_t i = 0; i < lenArray; i++) {
    variablTemp = randomArray[i];
...
88

Небольшая поправка:

...
  for (uint32_t i = 0; i < variablN; i++) {
    variablTemp = randomArray[i];
    randomIndex = random(i, lenArray);  //  с точки зрения равномерного распределения так должно быть лучше
    randomArray[i] = randomArray[randomIndex];
    randomArray[randomIndex] = variablTemp;
  }
...

а смысл?

1 лайк
89

Хотя в таком случае проще будет так:

...
  for (uint32_t i = 0; i < variablN; i++) {
    randomIndex = random(i, lenArray);  
    randomArray[i] = randomArray[randomIndex];
    randomArray[randomIndex] = i + variablK;
  }
...
90

Может покачественней замесится.

91

Не может качественнее замеситься. Не умеет. Меси не меси результат один и тот же.

92

Вероятность попадания чисел из хвоста массива в рабочую область не увеличивается? В противном случае заданный диапазон не используется целиком.
Я тервер сдал и забыл. Увы.

1 лайк
93

Общаяя вероятность последовательности не меняется.