Форум dkLab и Denwer
Здесь общаются Web-разработчики.
Генеральный спонсор:
Хостинг «Джино»

перетасовка элементов массива без цикла (обсуждение) (AKS)
Author Message
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 8:22 am ()
   Post subject:
Reply with quote


М

Выделено из темы «перетасовка элементов массива без цикла»,
расположенной в форуме Склад готовых решений :: JavaScript (Пн, 10 Июля 2006, 07:17).
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 8:22 am (спустя 1 секунду; написано за 1 минуту 45 секунд)
   Post subject:
Reply with quote

Rumata
А зачем в функцию сортировки переданы два аргумента?
Back to top
View user's profile Send private message Send e-mail
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 9:17 am (спустя 54 минуты; написано за 36 секунд)
   Post subject:
Reply with quote

AKS
wdh.suncloud.ru/js10.htm#hsort wrote:
Метод sort
Синтаксис: массив.sort(функция?)
Аргументы: функция — функция сортировки, описанная ниже
Результат: массив
Метод sort сортирует элементы массива. При этом новый объект Array не создается, перестановка элементов производится в исходном массиве. Способ сортировки задается необязательным аргументом функция; если аргумента нет, то производится сортировка в лексикографическом порядке по возрастанию значений элементов, которые предварительно преобразуются в строки.

Функция должна иметь вид:
Code (JavaScript): скопировать код в буфер обмена
function compare(a, b) {
  if (a меньше b по критерию сортировки)
    return -1;
  if (a больше b по критерию сортировки)
    return 1;
  return 0;        // a равно b
}
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 10:46 am (спустя 1 час 29 минут; написано за 1 минуту 37 секунд)
   Post subject:
Reply with quote

Rumata
Да, это понятно, но в Вашем примере (и у DizzZ тоже) есть ли необходимость в a и b. Может просто вот так:
Code (any language): скопировать код в буфер обмена
function () { return Math.random() - Math.random(); }
Back to top
View user's profile Send private message Send e-mail
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 11:10 am (спустя 23 минуты; написано за 1 минуту 15 секунд)
   Post subject:
Reply with quote

AKS, понял =)

это привычка. в данном случае это лишнее, но для корректного понимания написанного пусть будет :)
Back to top
View user's profile Send private message
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 12:34 pm (спустя 1 час 24 минуты; написано за 7 минут 19 секунд)
   Post subject:
Reply with quote

Rumata wrote:
вполне логично, если почитать описание метода sort
мне понравилось, вот только я бы только сказал, что циклы здесь заданы неявно
Тут не неявные циклы, а неявная рекурсия - поскольку используется метод массивов .sort(), в котором заведомо используется рекурсивный алгоритм QuickSort. И интересно было бы сравнить - это улучшение по скорости или ухудшение по сравнению с обычной перетасовкой через цикл. По идее сложность алгоритма в случае с рекурсией больше, но зато это используется откомилированный код, встроенный в интерпретатор, а не интерпретируемый код скрипта.
Back to top
View user's profile Send private message
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 12:38 pm (спустя 4 минуты; написано за 2 минуты 44 секунды)
   Post subject:
Reply with quote

AKS wrote:
Rumata
Да, это понятно, но в Вашем примере (и у DizzZ тоже) есть ли необходимость в a и b. Может просто вот так:
Code (any language): скопировать код в буфер обмена
function () { return Math.random() - Math.random(); }
Я могу ошибаться, но, насколько я помню, функция сортировки по спецификации должна принимать два параметра.
Поскольку преддполагается, что сортировка все же основана на контенте массива, а не случайная, как у нас :)
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 1:51 pm (спустя 1 час 12 минут; написано за 4 минуты 17 секунд)
   Post subject:
Reply with quote

DizzZ
1. По-поводу скорости выполнения даже говорить нечего, т.к. внутренние методы, как Вы уже написали, используют откомилированный С++, который, как я недавно прочел, быстрее javascript в 5000 раз.
2. Вы точно не ошибаетесь, что функция сортировки принимает два параметра, но принимает она их независимо от того, укажите ли Вы аргументы явно, или нет. Здесь тот же принцип, что и методе String.prototype.replace, о котором мы с Вами на днях вспоминали.
Back to top
View user's profile Send private message Send e-mail
WingedFox
Профессионал



Joined: 29 Apr 2003
Posts: 4064
Карма: 269
   поощрить/наказать

Location: Питер

PostPosted: Fri Jul 07, 2006 2:11 pm (спустя 20 минут; написано за 3 минуты 21 секунду)
   Post subject:
Reply with quote

AKS
Говорить очень даже есть о чём.
Вызов произвольной функции, переданной array.sort() уменьшает скорость сортировки до 1000 раз (или даже больше?).
Даже если с такой функцией:
Code (JavaScript): скопировать код в буфер обмена
array.sort(function(){return 1})
Можете посмотреть мою тему с "сортабельными" таблицами.
Back to top
View user's profile Send private message
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 2:42 pm (спустя 31 минуту; написано за 5 минут 22 секунды)
   Post subject:
Reply with quote

AKS wrote:
DizzZ
1. По-поводу скорости выполнения даже говорить нечего, т.к. внутренние методы, как Вы уже написали, используют откомилированный С++, который, как я недавно прочел, быстрее javascript в 5000 раз.
Не всегда это так :)
Я тоже читал разные доки. Результат может сильно отличаться, на самом деле, в зависимости от интерпретатора - они сильно могут по скорости быть различными.
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 2:46 pm (спустя 4 минуты; написано за 3 минуты 27 секунд)
   Post subject:
Reply with quote

WingedFox
Тут вопрос-то совсем другой.
Я позволил себе предположить, что рандомизатор от DizzZ должен работать быстрее любого другого рандомизатора, использующего какой-нибудь цикл.
Так что пишите цикл, чтобы опровергнуть мои предположения ;)
Я бы сам написал, только я пока не умею...
Back to top
View user's profile Send private message Send e-mail
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 4:02 pm (спустя 1 час 15 минут; написано за 5 минут 37 секунд)
   Post subject:
Reply with quote

кажется, вы все забываете как обрабатываются массивы. любая операция с большим блоком данных предполагает повторение. независимо от используемого языка
Code (assembler): скопировать код в буфер обмена
        MOV        CX,10
        LDS        SI,[From]
        LES        DI,[To]
REP        MOVSB
Code (Visual Basic): скопировать код в буфер обмена
dim A(n), B(n)
B = A
Code (JavaScript): скопировать код в буфер обмена
var a = [];
for (var i = 0; i < 10; i++) a[i] = 0;
проблема, описанная WingedFox, заключается в использовании безымянной функции для сравнения двух элементов, которая при инициализации (за тонкостями уже к WingedFox) резервирует существенной блок памяти, который же не всегда освобождается
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 4:56 pm (спустя 54 минуты; написано за 6 минут 54 секунды)
   Post subject:
Reply with quote

Rumata wrote:
кажется, вы все забываете как обрабатываются массивы. любая операция с большим блоком данных предполагает повторение. независимо от используемого языка...
Да как-будто все в курсе дела, ведь DizzZ писал:
Quote:
...используется рекурсивный алгоритм QuickSort.
И еще:
Rumata wrote:
проблема, описанная WingedFox, заключается в использовании безымянной функции...
Функция лишилась имени в Вашем примере, а у DizzZ все сделано классически...
Back to top
View user's profile Send private message Send e-mail
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 5:02 pm (спустя 6 минут; написано за 2 минуты 27 секунд)
   Post subject:
Reply with quote

Может у кого-нибудь найдется альтернативный вариант для сравнения? Я уже писал, что не знаю, как это сделать, а то бы выложил результаты...
Back to top
View user's profile Send private message Send e-mail
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 5:27 pm (спустя 24 минуты; написано за 3 минуты 8 секунд)
   Post subject:
Reply with quote

тоже перетасовка, но циклом.
Code (JavaScript): скопировать код в буфер обмена
var arr=[1,2,3,4,5], tmp, rnd, len=arr.length
for(var i in arr){
        tmp=arr[i]
        rnd=Math.floor(Math.random()*len)
        arr[i]=arr[rnd]
        arr[rnd]=tmp
}
Алгоритм получается заведомо линейный.
Сравнивать алгоритмы надо на разных по размеру наборах данных - от 100 до 100000 элементов, например.
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 6:05 pm (спустя 38 минут; написано за 2 минуты 18 секунд)
   Post subject:
Reply with quote

А вот и результаты (они, конечно, приблизительные):
Code (any language): скопировать код в буфер обмена
Итак, видно, что вариант с использованием внутреннего метода sort в большинстве случаев проиграл...

p.s. Исправил с на мс.

Last edited by AKS on Fri Jul 07, 2006 7:40 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 6:31 pm (спустя 26 минут; написано за 44 секунды)
   Post subject:
Reply with quote

циклами это делать нельзя, надо делать на большом массиве с определенным кол-вом элементов
Back to top
View user's profile Send private message
WingedFox
Профессионал



Joined: 29 Apr 2003
Posts: 4064
Карма: 269
   поощрить/наказать

Location: Питер

PostPosted: Fri Jul 07, 2006 7:17 pm (спустя 46 минут; написано за 44 секунды)
   Post subject:
Reply with quote

AKS
Sort проиграл именно по указанной мной причине.
Нет никакой разницы как определены функция, передаваемая в этот метод.
Back to top
View user's profile Send private message
AKS
Участник форума



Joined: 28 Dec 2005
Posts: 1174
Карма: 102
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 7:42 pm (спустя 24 минуты; написано за 56 секунд)
   Post subject:
Reply with quote

DizzZ
Попробовал провернуть тест с массивами (length 1000, 10000, 100000) - результаты еще хуже для sort. Тем не менее, думаю, что Ваш первый вариант с использованием этого метода все же привлекательней...
WingedFox
А Вы как думаете, все же sort "интересней" там, где длина массива не превышает какие-нибудь пятизначные цифры?
Back to top
View user's profile Send private message Send e-mail
WingedFox
Профессионал



Joined: 29 Apr 2003
Posts: 4064
Карма: 269
   поощрить/наказать

Location: Питер

PostPosted: Fri Jul 07, 2006 8:27 pm (спустя 44 минуты)
   Post subject:
Reply with quote

AKS
Без разницы.
Back to top
View user's profile Send private message
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Fri Jul 07, 2006 9:15 pm (спустя 48 минут; написано за 2 минуты 37 секунд)
   Post subject:
Reply with quote

Единственное преимущество моего метода - краткость (на самом деле его можно сделать еще короче).
Проигрывает он именно по причине более высокой сложности алгоритма - сортировки никогда не бывают линейными (за исключением, может быть, корневой сортировки - но она требует очень много памяти в наихудшем случае).
Вообще всем рекомендую книжку "Анализ алгортмов" или "Основы алгоримтмов" (Макконелл).
Back to top
View user's profile Send private message
Майоров Павел
Участник форума



Joined: 18 Mar 2007
Posts: 22
Карма: 0
   поощрить/наказать


PostPosted: Fri May 04, 2007 3:18 pm (спустя 9 месяцев 27 дней 18 часов 3 минуты; написано за 4 минуты 44 секунды)
   Post subject:
Reply with quote

Есть поразрядная сортировка, которая линейна (относительно количества элементов массива), и не требует слишком много памяти.
DizzZ wrote:
тоже перетасовка, но циклом.
Code (JavaScript): скопировать код в буфер обмена
var arr=[1,2,3,4,5], tmp, rnd, len=arr.length
for(var i in arr){
        tmp=arr[i]
        rnd=Math.floor(Math.random()*len)
        arr[i]=arr[rnd]
        arr[rnd]=tmp
}
При таком алгоритме возможных вариантов поведения алгоритма len^len, а перестановок len!
Так как len^len в общем случае не делится на len!, алгоритм получает не совсем равнораспределенные результаты.
Поэтому предлагаю заменить его на такой:
Code (JavaScript): скопировать код в буфер обмена
var arr=[1,2,3,4,5], tmp, rnd, len=arr.length
for(var i in arr){
        tmp=arr[i]
        rnd=Math.floor(Math.random()*(len-i));
        arr[i]=arr[i+rnd]
        arr[i+rnd]=tmp
}
Back to top
View user's profile Send private message
DizzZ
Участник форума



Joined: 23 Jan 2006
Posts: 154
Карма: 8
   поощрить/наказать


PostPosted: Mon May 07, 2007 7:57 pm (спустя 3 дня 4 часа 38 минут; написано за 1 минуту 21 секунду)
   Post subject:
Reply with quote

Да, вы правы. Для достижения действительно хорошего результатата вообще стоило бы использовать генераторы случайных чисел с лучшим распределением, чем стандартный. Несколько неплохих видел даже на JS.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic All times are GMT + 3 Hours
Page 1 of 1    Email to a Friend.
You cannot post new topics in this forum. You cannot reply to topics in this forum. You cannot edit your posts in this forum. You cannot delete your posts in this forum. You cannot vote in polls in this forum. You cannot attach files in this forum. You can download files in this forum.
XML