아두이노 - 배열 값 shuffle, 배열의 값을 무작위 순서대로 섞는 방법

Shuffle: 1 ~ 10까지 번호가 매겨진 10장의 카드가 있을 경우, 이를 무작위로 섞은 다음 순서대로 한 장씩 보여주는 것이다. 10장의 카드가 모두 보이는 동안 번호는 순서에 상관없이 무작위로 나오지만 같은 번호는 나올 수가 없다. 

 

25개의 칸을 갖는 배열이 있고, 이 칸에 1 ~ 25 범위 안의 서로 다른 숫자로 칸을 random(1, 25) 함수를 사용하여 모두 채운다고 가정해보자. 

 

25개의 배열을 정의하고 첫 번째 나온 숫자를 배열 인덱스 0번에 저장한 뒤 두 번째 나온 숫자가 인덱스 0번의 값과 같은지 검사하여 값이 같으면 다른 값이 나올 때까지 랜덤 함수를 실행하고 다른 값이 나오면 배열 인덱스 1번에 저장한다.

같은 방식으로 순서대로 숫자의 중복검사를 하면서 숫자를 저장하면 되는데, 첫 번째 값을 생성하고 두 번째 값을 생성할 때 첫 번째 값과 두 번째 값이 같을 확률이 굉장히 낮지만 24개의 숫자를 생성한 상태에서 마지막 값과 24개의 값이 같을 확률은 굉장히 높게 된다. 마지막 남은 숫자가 xx이라면 random() 함수를 통해 숫자가 나올 때마다 배열 24개의 숫자와 비교하여 모두 중복되지 않으면 xx값이 확정되고, 25번째 배열에 저장되어 종료되겠지만 배열 24개의 숫자와 비교중 중복된 값이 나오면 다시 random() 함수를 실행하고 중복 안된 값이 나올 때까지 무한 검증 및 숫자를 생성하게 된다. 

 

이 방식으로는 25개 정도의 배열이라면 큰 무리가 없으나 100개 이상의 배열에 중복되지 않는 숫자를 채우는 것에는 우리가 인지할 수 있는 시간이 소요되고, 또한 완료되는 시간도 일정치 않게 된다. 

 

아래 스케치를 업로드하고 시리얼 모니터에서 배열이 완성되는 시간을 확인해 보자.

1.shuffle_number.ino.ino

0.00MB

// shuffle 변수
uint16_t shuffle[650] = {0, };   // 배열 정의, 동적 메모리 73%사용
uint16_t shuffle_tracks = 100;   // 셔플 숫자 갯수 
unsigned long int atime;         // 시작 시간, 밀리 초

void shuffle_num() {
  shuffle[0] = random(1, shuffle_tracks+1);
  uint16_t track_count = 1;
  bool duplecate = false;
  while (track_count < shuffle_tracks) {
    uint16_t temp = random(1, shuffle_tracks+1);
    for (int i = 0; i < track_count; i++) {       // 중복검사
      if (shuffle[i] == temp) {
        duplecate = true;
        break;  // 값이 같으면 빠져나가서 새로운 번호 받고 0부터 다시 중복 검사
      }
      else if (i == track_count -1 && shuffle[i] != temp) { // 마지막
        duplecate = false;
      }
    }
    if (duplecate == false) {       // 중복된 값이 아니면
      shuffle[track_count] = temp;  // 값 저장
      track_count++;                // 저장 인덱스 증가
    }
  }
}

void setup() {
  Serial.begin(9600);
  randomSeed(analogRead(0));
  atime = micros();
  shuffle_num();
  Serial.println(micros() - atime);
  Serial.println("shuffle");
  for (int i = 0; i < shuffle_tracks; i++) {
    Serial.print(shuffle[i]); Serial.print(",");
  }
}

void loop() {
}

 

 

uint16_t shuffle_tracks = 100;  // 셔플 숫자 개수 

무작위로 섞을 숫자의 개수를 정의하는 변수이다. 셔플용 배열의 크기를 넘어서지 않는 값을 임의대로 입력하여 테스트해보자.

 

아래 값은 숫자 개수에 따른 소요시간(마이크로초)을 5회에 걸쳐서 수집한 것이다. 

 

uint16_t shuffle_tracks = 100;  // 셔플 숫자 개수: 100 

91496 = 91.496 밀리초 = 0.09초

50420

70388

100760

75164

 

uint16_t shuffle_tracks = 650;  // 셔플 숫자 개수: 650 

1581196 = 1581.196 = 1.58초

2080644

1759004

1724564

2007024

 

숫자 개수가 증가함에 따라 코드의 완료 시간이 급격히 상승하는 것을 볼 수 있고 코드가 완료된 시간이 일정하지 않다. 숫자 개수가 600개 정도 되면 1초 ~ 2초 정도 소요된다고 볼 수 있다.

 

이 문제를 해결하기 위해 코드 접근 방법을 달리해보자. 

앞에서 언급한 "1 ~ 10까지 번호가 매겨진 10장의 카드가 있을 경우, 이를 무작위로 섞은 다음 순서대로 한 장씩 보여주는 것"을 구현하도록 하자. 

 

1. 숫자의 범위가 정해져 있다. -> 셔플 숫자 개수

2. 셔플 숫자 개수에 맞는 배열이나 더 큰 배열이 있다. 

3. 배열에는 인덱스 순서대로 범위 내의 숫자가 순서대로 들어가 있다. 

   1 ~ 25의 숫자면 인덱스 0 = 1, 인덱스 1 = 2.......

4. 배열의 숫자를 무작위로 섞는다. 

   4-1. 랜덤 함수로 중복되지 않는 숫자 범위 내의 두 개의 배열 인덱스 번호를 생성시킨다. 

   4-2. 각각의 배열 인덱스 번호의 숫자를 서로의 배열에 교차 저장시킨다. 

   4-3. 상기의 작업을 배열 개수만큼 실행시킨다. 

 

이전 방법과 큰 차이점은 같은 숫자의 검증 자체를 하지 않는다는 것이다. 인덱스 번호의 생성 시 두 인덱스의 중복 유무만 검사하게 된다.

2.shuffle_index.ino

0.00MB

// shuffle 변수
uint16_t shuffle[650] = {0, };  // 배열 정의, 동적 메모리 73%사용
uint16_t shuffle_tracks = 650;  // 셔플 숫자 갯수
unsigned long int atime;        // 시작 시간, 밀리 초

void shuffle_num() {
  uint16_t track_count = 0;
  uint16_t sh_count = 0;
  uint16_t track_num = 0;
  while (track_count < shuffle_tracks) {
    uint16_t temp = track_count + 1;
    shuffle[track_count] = temp;
    track_count++;
  }
  while (sh_count < shuffle_tracks) {
    uint16_t index1 = random(0, shuffle_tracks);
    uint16_t index2 = random(0, shuffle_tracks);
    while (index1 == index2) {
      index1 = random(0, shuffle_tracks);
      index2 = random(0, shuffle_tracks);
    }
    uint16_t temp1 = shuffle[index1];
    uint16_t temp2 = shuffle[index2];
    shuffle[index1] = temp2;
    shuffle[index2] = temp1;
    sh_count++;
  }
}

void setup() {
  Serial.begin(9600);
  randomSeed(analogRead(0));
  atime = micros();
  shuffle_num();
  Serial.println(micros() - atime);
  Serial.println("shuffle");
  for (int i = 0; i < shuffle_tracks; i++) {
    Serial.print(shuffle[i]); Serial.print(",");
  }
}

void loop() {
  // put your main code here, to run repeatedly:
}

 

uint16_t shuffle_tracks = 100;  // 셔플 숫자 개수: 100 

18460 = 18.460 밀리초 = 0.02초

18812

18264

18640

18448

 

uint16_t shuffle_tracks = 650;  // 셔플 숫자 개수: 650 

118840 = 118.840 밀리초 = 0.12초

118452

118688

118488

118688

 

코드가 완료되는 시간이 많이 줄었을 뿐만 아니라 완료되는 시간들 간의 차도 거의 없어졌다. 이제 아두이노에 두 코드를 업로드하고 숫자 개수를 조정해 가면서 숫자가 잘 섞이는지 확인해 보면 된다.