Javascript-форум (https://javascript.ru/forum/)
-   Ваши сайты и скрипты (https://javascript.ru/forum/project/)
-   -   Случайная пересортировка массива (https://javascript.ru/forum/project/27758-sluchajjnaya-peresortirovka-massiva.html)

9xakep 23.04.2012 23:16

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

B~Vladi 23.04.2012 23:35

Мсье знает толк в извращениях?
alert([1,2,3,4,5,6,7,8,9,0].sort(function () {
  return Math.round(Math.random()) * 0.5;
}));

devote 23.04.2012 23:38

Цитата:

Сообщение от B~Vladi
Мсье знает толк в извращениях?

дауж я тоже сижу и смотрю в его код и думаю, что же там такого нового и отличающего от стандартного метода сортировки :)

9xakep 24.04.2012 00:04

если бы я еще знал этот способ, до написания скрипта =/ Да ну вас, у вас способ скучный :D
=============
Цитата:

Мсье знает толк в извращениях?
где-то я это уже слышал, только в каком посту не помню

B~Vladi 24.04.2012 00:16

Цитата:

Сообщение от 9xakep
где-то я это уже слышал

Частенько проскакивает в интернетах :)

Kolyaj 24.04.2012 01:03

B~Vladi,
не надо так перемешивать http://alljs.ru/articles/array/sort#shuffle

Gvozd 24.04.2012 01:32

Цитата:

Сообщение от B~Vladi
Мсье знает толк в извращениях?

А мне ваше решение кажется извращением, ведь на выходе получается далеко не случайный массив ;)

А вот и код для тестирования результата на случайность, и заодно мой вариант функции сортировки

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)
Цитата:

[14707, 18513]
[12399, 25029]
[16548, 16731]
наиболее равномерное распределение у моего варианта.
И к тому же достаточно очевидно, что распределение будет статистически равномерным(при условии статистической равномерности Math.Random)

А вот для второго кода из топика вполне очевидно, что он может дать равномерное распределение только для массива из двух элементов.
Для большего количества - распределение будет неравномерным, и при этом будет зависеть от браузера(от реализации сортировки в нем), потому что сравниваться будет далеко не все элементы со всеми, и в случае с быстрой сортировкой количество перестановок будет стремится к минимально возможному

Gvozd 24.04.2012 01:34

Kolyaj,
ну, вот.
Только отвлечешься чуть наваять тестирующую систему, да свой вариант случайной сортировки, а на эту тему уже статью написал :D

B~Vladi 24.04.2012 01:51

Цитата:

Сообщение от Gvozd
А мне ваше решение кажется извращением, ведь на выходе получается далеко не случайный массив

Это уже на совести реализаций, как они получают "случайное" число. Зато по коду всё понятно.
Мне известно, что процессор в принципе не может генерировать случайные числа. Только сегодня читал статью про Battle Sity - можно применить подобное решение с несколькими величинами.

9xakep 24.04.2012 07:46

Gvozd,
Что делает функция test?
B~Vladi,
Цитата:

Частенько проскакивает в интернетах :)
Вспомнил от трикадина слышал такое)

Gvozd 24.04.2012 09:51

Цитата:

Сообщение от 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);

Цитата:

[5029, 4923, 48]
[3409, 3301, 3290]
Как видим в первом случае число 2 выпадает гораздо реже остальных, а во втором случае события более равновероятны.

Gvozd 24.04.2012 10:07

Цитата:

Сообщение от 9xakep
Что делает функция test?

тестирует функцию сортировки массива, переданную как параметр, на предмет равномерности распределения(каждый вариант массива на выходе должен получатся примерно с той же частотой, как и любой другой вариант)
Для наглядности и простоты я этот критерий упростил, до сравнения частоты самого встречающегося и редко встречающегося результата

Если более подробно, то пожалуйста:
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]);
}

B~Vladi 24.04.2012 10:12

Цитата:

Сообщение от Gvozd
Как видим в первом случае число 2 выпадает гораздо реже остальных, а во втором случае события более равновероятны.

Не ну конечно будет такой результат, но как это относится к тому, что браузеры генерят случайные числа неравномерно?

Gvozd 24.04.2012 10:28

Цитата:

Сообщение от B~Vladi
но как это относится к тому, что браузеры генерят случайные числа неравномерно?

никак не относится.
я этого и не собирался показать.

Я просто взял ГПСЧ браузера, который выдает статистически достаточно равномерную выборку, и путем преобразований получил на его основе случайное число из {0,1,2}
При этом один из алгоритмов преобразований я намеренно взял такой, чтобы получить заведомо неравномерное распределение на выходе, получая равномерное на входе.

Как по-твоему, приведенные мною алгоритмы получения случайного числа из {0,1,2} равноценны, или один из них лучше за счет более равномерного распределения?

Если ответ да, то перенеси этот ответ на сравнение моего и своего алгоритма случайной сортировки.
Твой выдает распределение с большим размахом частот.

При этом для моего алгоритма несложно математически обосновать что при равномерном распределении исходного ГПСЧ, встроенного в браузер, распределение случайных массивов на выходе будет также равномерно.
А для твоего алгоритма такого математического обоснования скорее всего не найдется, и как по мне очевидно, что наоборот результат не будет равномерным. В любом случае обосновывать равномерность, если бы она была, надо для каждого браузера, для каждой имплементации сортировки в каждом браузере

B~Vladi 24.04.2012 10:31

Это не мой алгоритм :)

Kolyaj 24.04.2012 10:49

Цитата:

Сообщение от B~Vladi
браузеры генерят случайные числа неравномерно?

Браузеры генерят числа очень даже равномерно, иначе они были бы бесполезны чуть менее чем полностью. Причина плохого перемешивания в реализации метода sort.

Gvozd 24.04.2012 10:51

Цитата:

Сообщение от B~Vladi
Это не мой алгоритм

Ок, приведенный тобой.
Приведенный тобою алгоритм хуже приведенного мною.
Хотя и лучше первого алгоритма

Kolyaj 24.04.2012 10:54

Цитата:

Сообщение от Gvozd
Приведенный тобою алгоритм хуже приведенного мною.
Хотя и лучше первого алгоритма

По моей ссылке способ ещё и быстрее. Насчёт твоего не знаю, splice смущает.

Gvozd 24.04.2012 11:14

Цитата:

Сообщение от Kolyaj
По моей ссылке способ ещё и быстрее. Насчёт твоего не знаю, splice смущает.

Так и есть.
Мой способ самый медленный в теме.
Главной целью ставил очевидность его равномерного распределения.

B~Vladi 24.04.2012 11:28

Цитата:

Сообщение от Gvozd
Приведенный тобою алгоритм хуже приведенного мною.

Да вижу я, вижу :)

9xakep 24.04.2012 15:43

Gvozd,
Если я все правильно понял, то ты немного неправильно сравниваешь алгоритмы, точнее специально для таких случаев, и я создал ф-ию doCheck()
===============
Если я не так понял, то вот другой ответ: по-мойму если выпадают такие числа: Math.random()*1000|0: 21,123,765, это лучше чем: 345,376,401
===============
Я правильно понимаю, что у тебя алгоритм более лучше из-за этого:
Math.random()*(s-i) // то есть, те что уже пересортировались трогаться не будут?

===============
Никак не могу понять, что значит эта цифра:
1,2,3: 25654
??

Gvozd 24.04.2012 22:37

Цитата:

Сообщение от 9xakep
Если я все правильно понял, то ты немного неправильно сравниваешь алгоритмы, точнее специально для таких случаев, и я создал ф-ию doCheck()

скорее наоборот: ты превратно понимаешь идею генерации случайного перемешивания.
из-за твоей функции doCheck() ты заведомо отсеиваешь целый класс перестановок "похожих" на исходный массив.
То есть из массива [1,2] может получится только [2,1], а [1,2] ты считаешь "неслучайным" и отбрасываешь.
Это неправильно.
Случайным является перемешивание, если вероятность любой перестановки одинакова, то есть из [1,2] должны получатся [1,2] и [2,1] каждый с вероятностью 50%
Вот именно с этой позиции я и сравниваю алгоритмы.
Цитата:

Сообщение от 9xakep
по-мойму если выпадают такие числа: Math.random()*1000|0: 21,123,765, это лучше чем: 345,376,401

На такой маленькой выборе нельзя характеризовать качество ГПСЧ
Цитата:

Сообщение от 9xakep
Я правильно понимаю, что у тебя алгоритм более лучше из-за этого:

Нет не правильно, так как ты не понял принципе моего алгоритма.
Мой алгоритм следующий:
1) берем случайное число(точнее на случайной позиции) из исходного массива, вырезая его из массива(массив при этом сдвигается чтобы заполнить пропуск)
2)вставляем это число в конец нового массива
3)возвращаемся к шаге 1, пока в исходном массиве есть хотя бы 1 элемент
4) копируем новый массив в исходный массив(просто поддержал стиль остальных функций)

Цитата:

Сообщение от 9xakep
Никак не могу понять, что значит эта цифра:
1,2,3: 25654

Это означает что перестановка [1,2,3] была получена 25654 раз за время теста
То есть если тестировалось 100000раз, то получается что данный результат получался в 26% случаев, что явно больше чем у остальных.
Это плохо - это свидетельствует о неравномерном распределении результата

vflash 25.04.2012 16:33

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);

trikadin 25.04.2012 17:23

vflash, не используйте переменную l, она же абсолютна неотличима от единицы) Я три минуты втыкал, зачем вы умножаете на единицу.

B~Vladi 25.04.2012 20:21

Цитата:

Сообщение от trikadin
не используйте переменную l

Ну и если уж на то пошло, то лучше заюзать while:
while (i++ < l) {}

trikadin 25.04.2012 20:44

Цитата:

Сообщение от B~Vladi
Ну и если уж на то пошло, то лучше заюзать while:

Дело не в этом, дело в шрифтах. В вашем цикле, например, тоже кажется, что условие - i++ меньше единицы.

B~Vladi 25.04.2012 21:35

Ну дк я типо его код правил :)

9xakep 25.04.2012 22:35

Извращению нет границ!!!
Я перевел весь свой код в 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(/\(|&gt;|=|\s+/gi, '').split('')
alert(document.getElementById('div').innerHTML)
}
},1500)

}

a()
check()


</script>

Единственный минус, который для меня даже кажется дибилизмом, так это:
setTimeout, то есть мы надеемся на то, что сервер быстро ответит, а иногда, надежды счетны, что можно сделать?

Раед 25.04.2012 22:46

9xakep,
У XMLHttpRequest'а вообще то onreadystatechange есть.
http://xmlhttprequest.ru - для начала полезно

trikadin 25.04.2012 22:47

Цитата:

Сообщение от Раед
У XMLHttpRequest'а вообще то onreadystatechange есть.

А у новых версий есть onload, кстати)

9xakep, читайте Резига)

9xakep 25.04.2012 22:50

Раед,
неее...это нужно на чистом js писать, я вот что сделал Не без помощи разумеется.
trikadin,
кто это? А что читать?

trikadin 25.04.2012 22:59

Цитата:

Сообщение от 9xakep
А что читать?

John Resig - Pro Javascript Techniques

9xakep 25.04.2012 23:08

trikadin,
Последний год издания 2010?

Раед 25.04.2012 23:27

Цитата:

Сообщение от 9xakep
Раед,
неее...это нужно на чистом js писать

Что-то я про чистый JS не понял. Но если не хочешь через событие, юзай setInterval или на худой конец асинхронные запросы.

trikadin 25.04.2012 23:28

9xakep, у меня вот это. Если есть позднее - берите.

9xakep 26.04.2012 09:04

trikadin,
Держи 2010 года ;)
Раед,
ок, спасибо про асинхронные запросы пошел читать)
P.S. книга зачет, правда пока слишком нового я для себя ничего не открыл, но тонкости не которые узнал)

9xakep 26.04.2012 09:43

Извращение 3: http://gmoryes.bplaced.net/ex-4.html

trikadin 26.04.2012 09:44

Цитата:

Сообщение от 9xakep
Держи 2010 года

Лень регистрироваться и качать. Кстати, дата редактирования её на сайте !== дате издания.

9xakep 26.04.2012 10:58

trikadin,
ой блин...точно, ща в книге посмотрел, 2008)


Часовой пояс GMT +3, время: 10:30.