Случайная пересортировка массива
Понадобилось сделать этакую штуку, решил сюда выложить:
var m = [1, 2, 3, 4, 5, 6] var done = m.slice() function resort(arr1) { var did = [] sort1() function sort1() { var i = 0; do { var r1 = Math.random() * m.length | 0 var r2 = Math.random() * m.length | 0 var m1 = arr1[r1] var m2 = arr1[r2] arr1[r1] = m2 arr1[r2] = m1 did.push(r1) did.push(r2) i += 2 } while (i != 6) } } function doCheck(arr3, arr4) { var repeat = 0; var max_repeat = Math.floor(arr4.length * 0.75) for (i = 0; i < arr3.length; i++) { for (k = 0; k < arr4.length; k++) { if (arr3[i] == arr4[k]) { ++repeat break; } else continue; } } if (repeat >= max_repeat) { resort(arr3) } } resort(m) // пересортировываем нужный массив doCheck(m, done) /* для параноиков проверяем, не получился ли массив похожим с исходным, для этого вначале нужно создать массив аналогичный исходному:var done = m.slice() */ alert(m) // результат alert(done) // исходный массив Скрипт конечно не доработан для общего пользования :) Но в будущем можно будет сделать как методы Array :victory: |
Мсье знает толк в извращениях?
alert([1,2,3,4,5,6,7,8,9,0].sort(function () { return Math.round(Math.random()) * 0.5; })); |
Цитата:
|
если бы я еще знал этот способ, до написания скрипта =/ Да ну вас, у вас способ скучный :D
============= Цитата:
|
Цитата:
|
B~Vladi,
не надо так перемешивать http://alljs.ru/articles/array/sort#shuffle |
Цитата:
А вот и код для тестирования результата на случайность, и заодно мой вариант функции сортировки var test_count = 100000; var test_result; var array = [1, 2, 3]; test(resort1); console.log('========='); test(resort2); console.log('========='); test(resort3); function test(func) { test_result = {}; for(var i = 0; i < test_count; i++) { var arr = array.slice(); func(arr); if(test_result[arr] == undefined) { test_result[arr] = 0; } test_result[arr]++; } var test_list = []; for(var i in test_result) { test_list.push([i,test_result[i]]); } min = max = test_result[i]; test_list.sort(function(a,b) { min = Math.min(min, a[1], b[1]); max = Math.max(max, a[1], b[1]); return a[0] < b[0] ? -1 : 1; }); for(var i =0; i< test_list.length; i++) { console.log(test_list[i][0] + ': ' + test_list[i][1]); } console.log([min, max]); } function resort1(arr1) { var did = [] sort1() function sort1() { var i = 0; do { var r1 = Math.random() * arr1.length | 0 var r2 = Math.random() * arr1.length | 0 var m1 = arr1[r1] var m2 = arr1[r2] arr1[r1] = m2 arr1[r2] = m1 did.push(r1) did.push(r2) i += 2 } while (i != 6) } } function resort2(arr1) { arr1.sort(function () { return Math.round(Math.random()) * 0.5; }); } function resort3(arr) { var new_arr = [0,0]; for(var i = 0, s = arr.length; i < s; i++) { new_arr.push(arr.splice(Math.floor(Math.random()*(s-i)), 1)[0]); } arr.splice.apply(arr, new_arr) } И примеры полученных результатов(для краткости только min/max) Цитата:
И к тому же достаточно очевидно, что распределение будет статистически равномерным(при условии статистической равномерности Math.Random) А вот для второго кода из топика вполне очевидно, что он может дать равномерное распределение только для массива из двух элементов. Для большего количества - распределение будет неравномерным, и при этом будет зависеть от браузера(от реализации сортировки в нем), потому что сравниваться будет далеко не все элементы со всеми, и в случае с быстрой сортировкой количество перестановок будет стремится к минимально возможному |
Kolyaj,
ну, вот. Только отвлечешься чуть наваять тестирующую систему, да свой вариант случайной сортировки, а на эту тему уже статью написал :D |
Цитата:
Мне известно, что процессор в принципе не может генерировать случайные числа. Только сегодня читал статью про Battle Sity - можно применить подобное решение с несколькими величинами. |
Gvozd,
Что делает функция test? B~Vladi, Цитата:
|
Цитата:
Случайное число случайному числу рознь, и у них есть ряд качеств и характеристик, по которым вполне определенно можно сказать, ч случайные числа полученные одни алгоритмом лучше других. Одним из таких качеств/требований является равномерное распределение генерируемых чисел по всему множеству Есть и более строгие критерии: http://ru.wikipedia.org/wiki/%D0%A2%...%D1%8B_diehard Приведу более очевидный пример хорошого и плохого случайного числа(целое от 0 до 2) var q = [0,0,0]; for(var i = 0; i < 10000; i++) { q[Math.floor(Math.random()*2.01)]++ } console.log(q); var q = [0,0,0]; for(var i = 0; i < 10000; i++) { q[Math.floor(Math.random()*3)]++ } console.log(q); Цитата:
|
Цитата:
Для наглядности и простоты я этот критерий упростил, до сравнения частоты самого встречающегося и редко встречающегося результата Если более подробно, то пожалуйста: function test(func) { //сюда помещаем количество выпадений того или иного варианта результата test_result = {}; for(var i = 0; i < test_count; i++) { var arr = array.slice(); func(arr); if(test_result[arr] == undefined) { test_result[arr] = 0; } //увеличиваем счетчик данного результата test_result[arr]++; } //делаем из объекта test_result массив пар "ключ-значение", для того чтобы можно было отсортировать по ключу //сделано из соображений читаемости var test_list = []; for(var i in test_result) { test_list.push([i,test_result[i]]);//ложим пару "ключ-значение" } min = max = test_result[i];//иницииализируем минимальное и максимальное значение значением последнего элемента test_list.sort(function(a,b) {//сортируем test_list по "ключу" //попутно определяем максимальное и минимальное значение min = Math.min(min, a[1], b[1]); max = Math.max(max, a[1], b[1]); return a[0] < b[0] ? -1 : 1; }); //выводим упорядочненный массив пар "ключ-значение" for(var i =0; i< test_list.length; i++) { console.log(test_list[i][0] + ': ' + test_list[i][1]); } //выводим минимальное и максимальное встреченное значение. //Чем они ближе, тем лучше данный алгоритм случайно сортировки. //Критерий конечно сильно упрощен, но для задач не связанных с криптографией его вполне можно взять console.log([min, max]); } |
Цитата:
|
Цитата:
я этого и не собирался показать. Я просто взял ГПСЧ браузера, который выдает статистически достаточно равномерную выборку, и путем преобразований получил на его основе случайное число из {0,1,2} При этом один из алгоритмов преобразований я намеренно взял такой, чтобы получить заведомо неравномерное распределение на выходе, получая равномерное на входе. Как по-твоему, приведенные мною алгоритмы получения случайного числа из {0,1,2} равноценны, или один из них лучше за счет более равномерного распределения? Если ответ да, то перенеси этот ответ на сравнение моего и своего алгоритма случайной сортировки. Твой выдает распределение с большим размахом частот. При этом для моего алгоритма несложно математически обосновать что при равномерном распределении исходного ГПСЧ, встроенного в браузер, распределение случайных массивов на выходе будет также равномерно. А для твоего алгоритма такого математического обоснования скорее всего не найдется, и как по мне очевидно, что наоборот результат не будет равномерным. В любом случае обосновывать равномерность, если бы она была, надо для каждого браузера, для каждой имплементации сортировки в каждом браузере |
Это не мой алгоритм :)
|
Цитата:
|
Цитата:
Приведенный тобою алгоритм хуже приведенного мною. Хотя и лучше первого алгоритма |
Цитата:
|
Цитата:
Мой способ самый медленный в теме. Главной целью ставил очевидность его равномерного распределения. |
Цитата:
|
Gvozd,
Если я все правильно понял, то ты немного неправильно сравниваешь алгоритмы, точнее специально для таких случаев, и я создал ф-ию doCheck() =============== Если я не так понял, то вот другой ответ: по-мойму если выпадают такие числа: Math.random()*1000|0: 21,123,765, это лучше чем: 345,376,401 =============== Я правильно понимаю, что у тебя алгоритм более лучше из-за этого: Math.random()*(s-i) // то есть, те что уже пересортировались трогаться не будут? =============== Никак не могу понять, что значит эта цифра: 1,2,3: 25654 ?? |
Цитата:
из-за твоей функции doCheck() ты заведомо отсеиваешь целый класс перестановок "похожих" на исходный массив. То есть из массива [1,2] может получится только [2,1], а [1,2] ты считаешь "неслучайным" и отбрасываешь. Это неправильно. Случайным является перемешивание, если вероятность любой перестановки одинакова, то есть из [1,2] должны получатся [1,2] и [2,1] каждый с вероятностью 50% Вот именно с этой позиции я и сравниваю алгоритмы. Цитата:
Цитата:
Мой алгоритм следующий: 1) берем случайное число(точнее на случайной позиции) из исходного массива, вырезая его из массива(массив при этом сдвигается чтобы заполнить пропуск) 2)вставляем это число в конец нового массива 3)возвращаемся к шаге 1, пока в исходном массиве есть хотя бы 1 элемент 4) копируем новый массив в исходный массив(просто поддержал стиль остальных функций) Цитата:
То есть если тестировалось 100000раз, то получается что данный результат получался в 26% случаев, что явно больше чем у остальных. Это плохо - это свидетельствует о неравномерном распределении результата |
var m = [1,2,3,4,5,6,7,8,9,0], l = m.length, i = 0, x, j; for(;i<l; i+=1) { j = Math.floor(Math.random()*l)%l; x = m[i]; m[i] = m[j]; m[j] = x; }; alert(m); |
vflash, не используйте переменную l, она же абсолютна неотличима от единицы) Я три минуты втыкал, зачем вы умножаете на единицу.
|
Цитата:
while (i++ < l) {} |
Цитата:
|
Ну дк я типо его код правил :)
|
Извращению нет границ!!!
Я перевел весь свой код в php(какой же он все-таки мудае*ский, js - просто ангел!!) Ну так вот: Что принимаем: ![]() Что должны получить: 2,5,3,1,6,4 <div id='div'></div> <script src='data/aj_post3.js'></script> <script> // отправляем запрос function a() { ajax_post('test-3.php', null, function (data) { document.getElementById('div').innerHTML = data; }) } // ответ от сервера(см. скриншот) заполняем в div.innerHTML // редактируем запрос под наше усмотрение function check() { setTimeout(function () { alert(document.getElementById('div').innerHTML) with(document.getElementById('div')) { innerHTML = innerHTML.replace(/\n/gim, '').replace(/Array/gim, '').replace(/\[\d+\]/gim, '').replace(/\)\d+/gim, '').replace(/\(|>|=|\s+/gi, '').split('') alert(document.getElementById('div').innerHTML) } },1500) } a() check() </script> Единственный минус, который для меня даже кажется дибилизмом, так это: setTimeout, то есть мы надеемся на то, что сервер быстро ответит, а иногда, надежды счетны, что можно сделать? |
9xakep,
У XMLHttpRequest'а вообще то onreadystatechange есть. http://xmlhttprequest.ru - для начала полезно |
Цитата:
9xakep, читайте Резига) |
Раед,
неее...это нужно на чистом js писать, я вот что сделал Не без помощи разумеется. trikadin, |
Цитата:
|
trikadin,
Последний год издания 2010? |
Цитата:
|
9xakep, у меня вот это. Если есть позднее - берите.
|
trikadin,
Держи 2010 года ;) Раед, ок, спасибо про асинхронные запросы пошел читать) P.S. книга зачет, правда пока слишком нового я для себя ничего не открыл, но тонкости не которые узнал) |
Извращение 3: http://gmoryes.bplaced.net/ex-4.html
|
Цитата:
|
trikadin,
ой блин...точно, ща в книге посмотрел, 2008) |
Часовой пояс GMT +3, время: 23:25. |