[ μλ°μ€ν¬λ¦½νΈ(JavaScript) ] shuffle ν¨μλ₯Ό λ§λ€μ΄λ³΄μ
π shuffle ν¨μλ₯Ό λ§λ€μ΄λ³΄μ
JS
λ‘ shuffle
ν¨μλ₯Ό λ§λ€ λ κ°μ₯ λ¨Όμ μκ°λλ λ©μλλ sort()
μΌ κ²μ΄λ€. μλ§λ λ€μ μ½λμ²λΌ ꡬμ±νμ§ μμμκΉ??
// sort shuffle
const arr = [1, 2, 3, 4, 5];
const shuffle = arr.sort(() => Math.random() - 0.5)
console.log(shuffle);
ππΎ [ 5, 3, 2, 1, 4 ]
ꡬν λ‘μ§μ μ΄ν΄λ³΄λ©΄ λ°°μ΄μ μννλ©΄μ Math.random()
λ©μλλ₯Ό μ¬μ©νμ¬ λμ¨ λλ€ ν κ°μ -0.5
λ₯Ό νμ¬ sort()
λ©μλλ₯Ό κ±°μΉκ² λλ€. λ§μ½, Math.random() - 0.5
λ₯Ό ν κ°μ΄ μμλΌλ©΄ μ€λ¦μ°¨μμΌλ‘ μ λ ¬λκ³ , μμλ₯Ό 리ν΄νλ©΄ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬λλ€. arr
λ°°μ΄μ λͺ¨λ μννκ² λλ©΄ μλ¨ μ½λ λΈλ‘ 6λ² Lineμ²λΌ λ°°μ΄μ΄ shuffle
λ κ²μ μ μ μλ€.
sort
ν¨μλ‘ κ΅¬ννμ λμ μ₯μ μ μ½λκ° κ°λ¨ν΄μ§λ λ°λ©΄, λ¨μ μ λͺ¨λ νλ₯ μ΄ κ· μΌνκ² μΌμ΄λμ§ μλλ€. (JS μμ§λ§λ€ κ²°κ³Όκ° λ€λ₯Ό μ μλ€.) κ·Έ μ΄μ λ sort
λ μ΄λ° μ©λλ‘ λ§λ€μ΄μ§ λ©μλκ° μλκΈ° λλ¬Έμ΄λ€. μ΄λ₯Ό μ¦λͺ
νκΈ° μν΄ λ€μ μ½λλ₯Ό μ΄ν΄λ³΄μ. sort
λ©μλλ₯Ό μ΄μ©ν΄ λ°°μ΄ [1, 2, 3]
μ λ°±λ§ λ² shuffle
ν΄λ΄€λ€.
const arr = [1, 2, 3];
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1_000_000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
ππΎ
123: 375285,
132: 62554,
213: 125270,
231: 62429,
312: 62557,
321: 311905
count
λ₯Ό μ΄ν΄λ³΄λ©΄ λΉλκ° μ²μ, μ€κ°, λμ μ λ €μλ κ²μ μ μ μλ€. κ·Έ μ΄μ λ sort
λ©μλ λλ¬ΈμΈλ°, sort
λ₯Ό μ€ννλ©΄ μΈμλ‘ λκΈ΄ μ λ ¬ ν¨μκ° λ°°μ΄μ μ 리ν΄μ£Όλλ°, μ΄ κ³Όμ μμ element
λΉκ΅κ° μμ 무μμλ‘ μ΄λ£¨μ΄μ§κΈ° λλ¬Έμ΄λ€. JS μμ§λ§λ€ λ΄λΆ ꡬν λ°©μλ λ¬λΌ μ΄λ° νΌλμ λ 컀μ§κ² λλ€.
μ΄λ₯Ό ν΄κ²°νκΈ° μν΄ νΌμ
-μμ΄μΈ (Fisher-Yates)
μ
νμ μ΄μ©νλ©΄ νΈν₯λμ§ μμ λΉλλ‘ shuffle
μ ν μ μκ³ , μκ°λ³΅μ‘λλ sort
λ©μλλ³΄λ€ μ΄μ μ΄ μλ€. Tim sortλ₯Ό μ¬μ©ν sort
λ©μλλ νκ· O(nlogn)
μ λ§μ‘±νμ§λ§, νΌμ
-μμ΄μΈ λ O(N)
μ λ§μ‘±νκΈ° λλ¬Έμ΄λ€. νΌμ
-μμ΄μΈ (Fisher-Yates)
μ ꡬνμμλ λ€μκ³Ό κ°λ€.
- 1λΆν° NκΉμ§μ μ μ€ μμμ μ«μλ₯Ό μ ννλ€.
- 1κ³Ό μ νλμ§ μκ³ λ¨μ μλ μ μ¬μ΄μ μμμ μ kλ₯Ό μ ννλ€.
- kλ₯Ό μ νλμ§ μμ λ§μ§λ§ μ«μμ μ리λ₯Ό λ°κΎΌλ€.
- 1λΆν° N-1κΉμ§μ μ μ€ μμμ μ«μλ₯Ό μ ννλ€.
- λ μ΄μ μ νν μ«μκ° μμ λκΉμ§ 2~4λ²μ κ³Όμ μ λ°λ³΅νλ€.
μ΄λ₯Ό JSμ½λλ‘ μμ±νλ©΄ λ€μκ³Ό κ°λ€.
// Fisher-Yates shuffle
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) { // λ°°μ΄μ λ§μ§λ§λΆν° μμνλ€. iκ° 0μ΄λλ©΄ λ°λ³΅λ¬Έμ μ’
λ£νλ€.
let j = Math.floor(Math.random() * (i + 1)); // λλ€ν κ°κ³Ό νμ¬ μΈλ±μ€ μμΉ + 1μ κ³±νκ³ μμμ μ μ κ±°νλ€.
[array[i], array[j]] = [array[j], array[i]]; // νμ¬ μΈλ±μ€μ λλ€νκ°μ μΈλ±μ€ μμΉ + 1μ κ³±νκ³ μμμ μ μ κ±°ν κ°κ³Ό μ리λ₯Ό λ°κΎΌλ€.
}
}
νμ
μ€ν¬λ¦½νΈλ‘ μ½λλ₯Ό κ°λ
μ± μκ² μμ±ν΄λ΄€λ€. κ·Έλ¦¬κ³ λ°±λ§ λ² shuffle
ν΄λ΄€κ³ κ²°λ‘ μ μΌλ‘ νλ₯ μ΄ κ· μΌνκ² λμ€λ κ²μ μ μ μλ€.
function shuffle<T>(array: T[]) {
for (let index = array.length - 1; index > 0; index--) {
const randomIndex = Math.floor(Math.random() * (index + 1))
[array[index], array[randomIndex]] = [array[randomIndex], array[index]]
}
return array
}
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
ππΎ
123: 166693
132: 166647
213: 166628
231: 167517
312: 166199
321: 166316
μ΄λ κ² shuffle
ν¨μλ₯Ό μμλ΄€λλ°, λ°μ΄ν°μ ν¬κΈ°κ° μκ³ λΉλμ μκ΄μμ΄ κ°νΈνκ² shuffle
μ ꡬννλ €λ©΄ sort
λ₯Ό μ¬μ©ν΄λ λμ§λ§, λ°μ΄ν°μ ν¬κΈ°κ° ν¬κ³ λ°μ λΉλκ° κ· μΌνκ² μΌμ΄λμΌ νλ€λ©΄ νΌμ
-μμ΄μΈ μ λ‘μ§μ μ¬μ©νλ κ²μ΄ μ΄λ¨κΉ?λΌκ³ μκ°νλ©΄μ κΈμ λ§μΉλ€.
Reference