1

Тема: javascript: Сортировка массива с отображением процесса

Бывало я раньше вечерами от скуки решал "решебник" для поступающих в вузы со всякими там уравнениями.
Когда попадаются в интернете интересные и посильные мне задачки я всегда их решаю, что бы черепушка работала. 8)
Прочитал интересную статью об оптимизации javascript-вычислений. В статье рассматривается лишь один пример. Сначала хотел сразу выложить ссылку на статью и узнать ваше мнение. Но, писать код с нуля, не опираясь на чужие мысли, всегда интереснее, не правда ли? Для начала попрошу местных гуру javascript-инга написать функцию-сортировку массива. Вот "рыба":

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
  <head>
    <title>Running long JavaScript processes in a web browser</title>
    <style>

body {
  padding:0;
  margin:1em;
}

#progressbar {
  position:relative;
  width:300px; height:20px;
  border:1px solid black;
  overflow:hidden;
}

#progressbar div {
  background:#316AC5;
  width:0; height:100%;
}
    </style>
  </head>
  <body>
    <p>Sorting, please wait...</p>
    <div id="progressbar"><div></div></div>

    <script>

(function () {

    var i, length, data, el, start;

    // Initialize a few things...
    length = 5000;
    data = [];
    el = document.getElementById("progressbar").firstChild;

    // Setup an array of random integers...
    for (i = 0; i < length; i++) {
        data[i] = Math.floor(Math.random() * length);
    }
Begin =======================
    FUNCTION {el.style.width = (100 * value / total) + "%";}
End  ========================
    alert("Total duration: " + ((new Date().getTime() - start) / 1000) + " seconds");

})();

    </script>
  </body>
</html>

Прошу многоуважаемых написать между begin/end функцию сортировку массива, при обязательном условии: Что бы работал индикатор прогресса. В дальнейшем, если будет > 1 примера кода, будем сравнивать скорость выполнения выших скриптов, со скриптами из статьи. Посмотри, где она оптимизация.

В FUNCTION {el.style.width = (100 * value / total) + "%";} как видите, уже стоит строка для изменения индикатора.
где total, value - общее, текущее соответственно количество/значение элементов/циклов/проходов и пр.

На данный момент у меня вообще не получается сделать сортировку при работающем прогресс баре. Ищу свои ошибки.

Я думаю, что ту статью читал не я один, поэтому прошу тех, кто в теме не копипастить, а попробовать абстрагироваться и написать свой собственный код.
Чуть позже я конечно же дам ссылочку.

PS если у кого-нибудь очень мощный комп, выставьте количество элементов больше (сейчас там стоит 5000), что бы было видно, что индикатор пашет.

Нас невозможно сбить с пути, нам пофигу куда идти.

2

Re: javascript: Сортировка массива с отображением процесса

1) Внимательно читаем пункт правил 4.2 и принимаем меры.

ИМХО, не в обиду, но странная затея.

2)

DnsIs пишет:

Когда попадаются в интернете интересные и посильные мне задачки я всегда их решаю, что бы черепушка работала. 8)

Могу ошибаться, но мне кажется, тренировать черепушку, можно только ударами головой о стену. Она же ведь кость. И то, не думаю, что это особо полезно. А вот тренировать мозг, это да... Наверное полезно. Может стоить решать задачки реально требующие решения ? Если просто интересно посмотреть на наработки других, то пожалуйста вот недавняя тема VBS: Сортировка массива. Пускай на VBS, но Вы же хотите потренировать свою черепушку. ) Либо вот примеры, которые предлагает GOOGLE

Результаты поиска по запросу: "сортировка массива javascript"

3)

DnsIs пишет:

На данный момент у меня вообще не получается сделать сортировку при работающем прогресс баре. Ищу свои ошибки.

Подозреваю, что основная проблема "неработоспособности" Вашего прогрессбара кроется в частичной синхронности процесса сортировки. Т.к, пока крутятся циклы и двигаются элементы массива, отрисовка элементов на экране может не происходить. Есть варианты создания псевдоасинхронности для таких задач, но это сильно сокращает быстродействие...

Передумал переделывать мир. Пашет и так, ну и ладно. Сделаю лучше свой !

3 (изменено: DnsIs, 2012-03-11 13:30:42)

Re: javascript: Сортировка массива с отображением процесса

Не в обиду. 8)
Тем не менее вы меня поняли.

В данном примере сложности по функции сортировки нет. Обычный sort(function (){return a-b}) справится.
Сейчас мне как раз стало интересно, от чего же у кого-то получилось заставить работать прогрессбар, а у меня нет.

Нас невозможно сбить с пути, нам пофигу куда идти.

4

Re: javascript: Сортировка массива с отображением процесса

DnsIs, дайте ссылку. Очень почитать хочется.

Коллега Xameleon прав. Я всего лишь поправлю его. Сортировка - полностью синхронный процесс. Вообще задача решаема, и может показаться весьма интересной - асинхронная сортировка ну очень большого массива. Но проблема в том, что это будет ну очень долго. Чтобы хоть что-то показать, так как браузер будет "висеть" в этот момент... Можно сделать, например, так


<script type="text/javascript">

function doSort()
{
	loadinfo = document.createElement('div');
	loadinfo.innerHTML = '<img src="loadinfo.gif" /> Sorting...';
	loadinfo.style.position = 'absolute';
	document.body.appendChild(loadinfo);

	array.sort();

	document.body.removeChild(loadinfo);
};

</script>

И анимированную картинку, например, такую
http://atcasa.corriere.it/Speciali/annual-bravacasa/loadinfo.gif

( 2 * b ) || ! ( 2 * b )

5

Re: javascript: Сортировка массива с отображением процесса

Rumata пишет:

Сортировка - полностью синхронный процесс.

Не соглашусь ) Я говорил о частичной синхронности, т.к все остальные процессы компьютера продолжают работать как и работали. )

Передумал переделывать мир. Пашет и так, ну и ладно. Сделаю лучше свой !

6

Re: javascript: Сортировка массива с отображением процесса

Ссылку я не хотел сразу давать, как раз что бы увидеть как бы решили такую задачу мастера скриптинга. Понятно, что писать не нужный код код с нуля не охота. 8)

Чтож. Rumata, давайте сначала не ссылку а вариант решения. В статье идет речь о таком коде:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
  <head>
    <title>Running long JavaScript processes in a web browser</title>
    <style>

body {
  padding:0;
  margin:1em;
}

#progressbar {
  position:relative;
  width:300px; height:20px;
  border:1px solid black;
  overflow:hidden;
}

#progressbar div {
  background:#316AC5;
  width:0; height:100%;
}
    </style>
  </head>
  <body>
    <p>Sorting, please wait...</p>
    <div id="progressbar"><div></div></div>

    <script>

(function () {

    var i, length, data, el, start;

    // Initialize a few things...
    length = 5000;
    data = [];
    el = document.getElementById("progressbar").firstChild;

    // Setup an array of random integers...
    for (i = 0; i < length; i++) {
        data[i] = Math.floor(Math.random() * length);
    }

    function sort (progressFn) {
        i = 0;

        (function () {
            var j, value;

            for (j = length; j > i; j--) {
                if (data[j] < data[j - 1]) {
                    value = data[j];
                    data[j] = data[j - 1];
                    data[j - 1] = value;
                }
            }

            i++;
            progressFn(i, length);

            if (i < length) {
                setTimeout(arguments.callee, 0);
            }

        })();
    }

    start = new Date().getTime();
    sort(function (value, total) {
        el.style.width = (100 * value / total) + "%";
        if (value >= total) {
            alert("Total duration: " + ((new Date().getTime() - start) / 1000) + " seconds");
        }
    });

})();

    </script>
  </body>
</html>

Далее идет его оптимизация.

В исходном тексте length = 1000, я же изменил на length = 5000; У меня при таком варианте сортировка происходит за ~26 секунд.

Раз писать код никто не хочет, давайте попробуем оптимизировать уже готовый.

ps, в статье код после оптимизации отрабатывает за ~.62 секунды.
Rumata, ну хоть вы не откажите. Ну очень хочется увидеть как вы справитесь.
Скажу сразу, я так бы не смог, как там написано.

Нас невозможно сбить с пути, нам пофигу куда идти.

7

Re: javascript: Сортировка массива с отображением процесса

Xameleon пишет:

процессы компьютера

Разные точки зрения. Я подразумеваю js  в рамках одной страницы. Вот здесь Вы правы и подразумевается выполнение js в рамках одной страницы (процесса ?)

Xameleon пишет:

пока крутятся циклы и двигаются элементы массива, отрисовка элементов на экране может не происходить

.

( 2 * b ) || ! ( 2 * b )

8

Re: javascript: Сортировка массива с отображением процесса

Rumata, именно так. ) Я просто более глобально смотрю на этот процесс, поэтому говоря о синхронности стараюсь учитывать и остальные события.

Передумал переделывать мир. Пашет и так, ну и ладно. Сделаю лучше свой !

9

Re: javascript: Сортировка массива с отображением процесса

В общем Rumata, вот статья.

Нас невозможно сбить с пути, нам пофигу куда идти.

10 (изменено: Rumata, 2012-03-18 00:52:08)

Re: javascript: Сортировка массива с отображением процесса

DnsIs, спасибо.
Не мог сразу ответить, хотя времени, чтобы зайти на форум было. Первой моей мыслью было оптимизировать сам алгоритм сортировки - все-таки там используется алгоритм пузырьковой сортировки. Вторая - поискать само описание, кстати я нашел оригинальную статью. Правда мелькала мысль - пореже вызывать функцию таймера.

Решение, приведенное в статье, меня удивило.
-- Частота вызова функции таймера "не изменилась". Изменилось время исполнения каждого цикла
-- Внутренний цикл прерывается и повторно выполняется с прерванной итерации. Фактически, новый алгоритм это функцию-генератор, которая эмулирует оператор yield из JavaScript 1.7
-- Скорость вычислений изменилась примерно в 50 раз! С учетом того, что чистое время исполнения алгоритма без таймера превышает время, затраченное алгоритмом с использованием таймера. Либо парадокс, либо ошибка автора - я не проверял качественно.
-- В МСИЕ безобразно медленные алгоритмы: 15-16 сек и 1.3 сек. против 5-6 сек. и 0.06-0.13 сек в мозилле для примеров из статьи.

( 2 * b ) || ! ( 2 * b )

11

Re: javascript: Сортировка массива с отображением процесса

Вот это использую для замера, быстро, просто, кроссбраузерно.

var vcb=new Date().getTime();
сам цикл чего то
vcb=(new Date().getTime()-vcb)/1000;
alert(vcb);

Несколько раз пытался сделать такой бар, браузер просто игнорирует вывод на экран.
А вот идея с остановкой цикла  меня не посещала, надо попробовать.

Rumataб на эту ссылку браузер ругается, yield из JavaScript 1.7

12

Re: javascript: Сортировка массива с отображением процесса

Любитель пишет:

на эту ссылку браузер ругается, yield из JavaScript 1.7

МСИЕ банит сайт мозиллы ))

( 2 * b ) || ! ( 2 * b )

13

Re: javascript: Сортировка массива с отображением процесса

На данный момент у меня вообще не получается сделать сортировку при работающем прогресс баре. Ищу свои ошибки

Не понял, а чего их самому искать, когда есть кому это можно спихнуть?


Валидатор сразу ругнулся на отсутствие

<meta http-equiv="Content-Type" content="text/html; charset=Windows-1251">

А сафари написала кракозяблами, правильно и сделала.

Консоль лисы сразу показала на эту строку

el = document.getElementById("progressbar").firstChild;

Исправляем на

el=document.getElementById("progressbar").getElementsByTagName("div")[0];

и всё начинает работать.

Total duration: (округлённо)
Осёл 6 = 93сек
Опера 11.50 = 24сек
Лиса 5.01 = 23сек
ГуглХром 12 = 24сек
Сафари 5.0 = 57сек

14

Re: javascript: Сортировка массива с отображением процесса

Ни на кого я не спихивал. Я просто хотел посмотреть как бы решили такую задачу местные. 6)
Писать же прогресс бар я хотел сам, но у меня нифига не получилось.

У меня огнелис не ругается на ".firstChild;" почему то.

Нас невозможно сбить с пути, нам пофигу куда идти.

15 (изменено: Любитель, 2012-03-23 14:27:08)

Re: javascript: Сортировка массива с отображением процесса

У меня огнелис не ругается на ".firstChild;" почему то.

И работает?
Две разных лисы, 5.01 и 3.56

Ошибка: el.style is undefined
Источник: file:
Строка: 29

16 (изменено: DnsIs, 2012-03-24 07:26:35)

Re: javascript: Сортировка массива с отображением процесса

Нe честно, не ругается и работает. (firstChild)
Firefox 12.0

Нас невозможно сбить с пути, нам пофигу куда идти.

17

Re: javascript: Сортировка массива с отображением процесса

Нe честно, не ругается и работает.

Казнить нельзя помиловать.
Где будем ставить запятую?:)


Firefox 12.0

За новыми не гоняюсь, а тем что версия от версии отличаются устранением старых и внесением новых ошибок нас не запугаешь.:)