Показать сообщение отдельно
  #19 (permalink)  
Старый 23.12.2020, 23:18
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 03.02.2020
Сообщений: 2,745

Ну завершающий тест
<pre>
<script>
let t0, t1;
let nloop=0;
function splitSet  (set) {
    let sub1, sub2;
    do {
        nloop++;
         sub1 = [];
         sub2 = [];
         for(let i = 0; i < set.length; i++) {
            (Math.random()<0.5? sub1 : sub2).push(set[i]);
         }
    } while (sub1.length == 0 || sub2.length == 0);
    return [sub1, sub2];
}
let obj = {};
t0 = performance.now()
for (let i = 0; i < 100_000; i++) {
    let [s1, s2] = splitSet([1, 2, 3, 4, 5, 6, 7])
    obj[[s1]] = (obj[[s1]] >> 0) + 1;
    obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
t1 = performance.now()

document.write(JSON.stringify(obj, "", " "))
document.write(`<br>Time ${t1-t0}    nloop  ${nloop}`)

document.write('<br><br>')


const randomNetto = length => {
    let n = length, ar = [n], sum = n, k = n;
    for (let i = 2; i < length; i++) {
            n *= --k;
            n /= i;
            sum += n;
            ar.push(sum);
            }
    ar = ar.map(a => a / sum);
    return random => {
        let len = 0;
        for (let k of ar) {
            len++;
            if (random < k) break;
        }
        return len
    }
}
 
function splitSet1(set) {
    const random = a => Math.trunc(Math.random() * a),
        sort = (a, b) => a - b;
    let {length} = set = set.slice(0),
    ar = [],
    count = randomNetto(length),
    n = count(Math.random());
    for (let i = 0; i < n; i++) {
        let k = random(length - i);
        ar.push(...set.splice(k, 1))
    }
    ar.sort(sort);
    return ar[0] == 1 ? [ar, set] : [set, ar];
}
obj = {};
t0 = performance.now()
for (let i = 0; i < 100_000; i++) {
    let [s1, s2] = splitSet1([1, 2, 3, 4, 5, 6, 7])
    obj[[s1]] = (obj[[s1]] >> 0) + 1;
    obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
t1 = performance.now()

document.write(JSON.stringify(obj, "", " "))
document.write(`<br>Time ${t1-t0}`)

</script>
</pre>


Примерно 1500 "лишних" циклов. Как я и писал (пост #9) вероятность 1/64 = 1.56%

Последний раз редактировалось voraa, 23.12.2020 в 23:47.
Ответить с цитированием