ES6 range 배열 과 random 배열 생 성

저자 @ zwhu 원문 @ github
배열 을 만 드 는 것 은 글자 의 양 과 new Array() 을 제외 하고 Array(n) 을 통 해 만 들 수 있 습 니 다. n 은 배열 의 길이 입 니 다.Array(n) 길이 가 n 인 빈 배열 을 생 성 했 습 니 다. 배열 의 요소 할당 값 이 undefined 인 것 과 차이 가 있 습 니 다.chrome 에서 빈 배열 [undefined * n] 을 보고 undefined 의 배열 [undefined, undefined, ..... , undefined] 을 할당 합 니 다.range：

let rangeArray = (start, end) => Array(end - start + 1).fill(0).map((v, i) => i + start)

rangeArray(0,10) // return [0,1,2,3,4,5,6,7,8,9,10]

map 배열 에 할당 되 지 않 은 요 소 를 옮 겨 다 닐 수 없 기 때문에 ES6 의 새로운 방법 fill 을 통 해 배열 을 채 우 고 배열 의 모든 수 를 0 (아무것도 아 무 렇 지 않 게 바 꾼 다음 map 방법 으로 배열 의 모든 0 을 대응 하 는 숫자 로 바 꿀 수 있다.
ES5 는 fill 방법 이 없어 도 Array.apply(null, {length: end - start + 1}).map((v, i) => i + start) 을 통 해 해결 할 수 있다.말하자면 첫 번 째 방법 보다 속도 가 더 빠 를 수 있다.random：

let randomArray = (start, end) => {
  let range = rangeArray(start, end)
    , random = []
  while (range.length) {
    let i = Math.random() * range.length | 0
    random.push(range[i])
    range.splice(i, 1)
  }
  return random
}

// test
let random = randomArray(1, 50)

console.log(random.length === 50)
console.log(Math.min.apply(Math, random) === 1)
console.log(Math.max.apply(Math, random) === 50)
console.log(random.sort((a, b) => a - b).every((v, i, a) => v === a[i - 1] || 0 + 1))

구체 적 인 원 리 는 range 배열 을 만 든 다음 에 랜 덤 range 배열 의 길 이 를 얻 고 아래 표 시 된 i 를 얻 으 며 range 에서 아래 표 시 된 요 소 를 꺼 내 새 배열 random 에 넣 고 range 배열 이라는 요 소 를 삭제 한 다음 에 range 배열 이 삭 제 될 때 까지 순환 하 는 것 이다.
최근 에 '알고리즘' 을 보고 있 기 때문에 뻔뻔 하 게 분석 해 보 세 요 . 잘못된 부분 은 range 배열 을 만 들 고 2n 번 순환 하 며 range 배열 n 번 순환 하기 때문에 합치 면 3n 번 입 니 다. 소요 시간 은 선형 이 고 시간 복잡 도 는 O (n) 이기 때문에 빠 른 것 같 습 니 다.
대비 하여 이전에 자주 사 용 했 던 방법 을 분석 하 다.

let randomArray = (start, end) => {
  let o = {}
    , length = end - start + 1
    , random = []
  while (random.length < length) {
    let i = (Math.random() * length + 1) | 0
    if (o[i]) continue
    else {
      o[i] = true
      random.push(i)
    }

  }
  return random
}

// test
let random = randomArray(1, 50)

console.log(random.length === 50)
console.log(Math.min.apply(Math, random) === 1)
console.log(Math.max.apply(Math, random) === 50)
console.log(random.sort((a, b) => a - b).every((v, i, a) => v === a[i - 1] || 0 + 1))

위의 코드 에서 볼 수 있 듯 이 가장 좋 은 상황 에서 (random 결과 가 중복 되 지 않 는 상황) 필요 한 시간 복잡 도 는 O (n) 이 고 최 악의 경우 (매번 반복 되면... 수 차례 순환) 기대 할 수 밖 에 없다. 수학 을 잘 못 하면 함부로 하지 않 는 다.
자신 이 위의 분석 을 한 후에 입력 수가 매우 많은 상황 에서 앞의 방법 은 뒤의 방법 을 찌꺼기 로 만 들 것 이 라 고 생각 했다. 그러나 실제 상황 은 오히려 찌꺼기 로 만 들 었 다. 이 유 는 splice 방법 을 무시 한 것 이다. splice 는 배열 의 요 소 를 이동 하 는 데 많은 시간 을 소모 하기 때문이다.

let a = [], b = []
console.time('push')
for (let i = 0; i < 1e5; i++) {
  a.push(i)
}
console.timeEnd('push')  // ==> 3ms 
console.time('splice')
for (let i = 0; i < 1e5; i++) {
  b.splice(i, 1, i)
}
console.timeEnd('splice') // ==> 21ms

위 에서 볼 수 있 듯 이 splice 는 push 보다 훨씬 많은 시간 을 쓴다.
쓰 여 있 으 면 제목 과 만 팔 천리 차이 가 나 는 것 같은 데................................................................
= = = = = = = 2015 - 11 - 4 업데이트 = = = = = = =

let randomArray1 = (start, end) => {
  let range = rangeArray(start, end)
    , random = []
    , N = range.length


  while (N--) {
    let i = Math.random() * (N + 1) | 0
    random.push(range[i])
    range[i] = range[N]
    //range.splice(i, 1)
  }
  return random
}

splice 방법 을 사용 하지 마 십시오. 알고리즘 은 변화 가 없습니다.속도 가 크게 향상 되 었 습 니 다. 테스트 결 과 는 다음 과 같 습 니 다.

console.time('random1')
let random1 = randomArray1(1, 1e5)
console.timeEnd('random1')
console.time('random2')
let random2 = randomArray2(1, 1e5)
console.timeEnd('random2')

random1: 12ms
random2: 79ms

내 컴퓨터 에서 1 만 개의 데이터 에 대한 처리 속도 가 6 배 가까이 올 라 간 것 을 볼 수 있다.이전의 분석 결과 와 그런대로 일치 하 는 편 이다.