Случайная пересортировка массива
Понадобилось сделать этакую штуку, решил сюда выложить:
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, время: 15:18. |