Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > JavaScript: Общие вопросы > тяжелые вычисления

Автор: cru3l 7.11.2009, 18:34

есть такой скрипт

Код


function loadpage(){
var aNumbers=new Array();
var bNumbers=new Array();
var cNumbers=new Array();
var dNumbers=new Array();
var x,y,a,b,c,d,i,j,k,z;



for (i=0;i<100;i++)
{
aNumbers[i]=i;
bNumbers[i]=i;
cNumbers[i]=i;
dNumbers[i]=i;
}


x=78.578;



for (i=0;i<100;i+0.00001)
{
    for (j=0;j<100;j+0.00001)
    {
        for (k=0;k<100;k+00001)
        {
            for (z=0;z<100;z+00001)
            {
            
                
                var firstpart=(aNumbers[i]+bNumbers[j]);
                var secondpart=(cNumbers[k]+dNumbers[z]);
                var y=(aNumbers[i]/bNumbers[j])*(cNumbers[k]/dNumbers[z]);
                
                if (firstpart>72&&secondpart>72){                
                    
                    if (x==y)
                    {
                        document.write('x='+aNumbers[i]+'/'+bNumbers[j]+'*'+cNumbers[k]+'/'+dNumbers[z]+'<br>');
                    }
                
                }
            
            }
            
        }
    
    }

}

}

выполняется ооооочень долго (я так и не дождался, пришлось тестировать с цифрами меньше) и вешает браузер, что впрочем не удивительно. Как можно это все оптимизировать? Потоков вроде бы в яваскрипте нет, как с этим борятся люди?

Автор: bars80080 7.11.2009, 19:14

если бы вы описали реальную задачу, то можно было бы предложить более-менее оптимальное решение

а с вашим кодом борются очень просто - не пишут его

Автор: Itsys 7.11.2009, 21:57

Мне интересно, какой результат Вы ожидаете для

Код


aNumbers[0.00001]

Может в приращении цикла всетаки ошибка?

Да и вообще странный алгоритм, для получения результата совершенно не обязательно перебирать все возможные значения.

Но для полного понимания, всетаки необходимо видеть исходную задачу

Автор: sTa1kEr 7.11.2009, 22:17

Цитата(Itsys @ 7.11.2009, 22:57

)

Может в приращении цикла всетаки ошибка?

А там нету вообще никакого приращения smile

Цитата(cru3l @ 7.11.2009, 19:34

)

for (i=0;i<100;i+0.00001)

Автор: cru3l 8.11.2009, 13:18

да напортачил я там с этими +0.00001.

вот задача,

есть такое выражение

a/b * c/d = x

где, x — входные данные

и есть массив чисел например (20,20,20,21,35,36,40,50,70,85,90,88) — каждое значение можно использовать только один раз

a,b,c,d — это подобранные числа из массива, таким образом чтобы выражение было правильным, если конечно это возможно.
И есть условие a+b>72 ; c+d>72

можно упростить формулу до a/b=x (т.е. представить что c=1 и d=1) если решить задачу можно только таким образом

x может быть не целым, например "78.875"

я в коде в качестве массива чисел просто забил массив значениями от нуля до ста (для примера). Ну и я не придумал ничего лучше кроме как "скопировать" массив 4 раза и перебирать все возможные варианты. Там в коде еще не учтено чтобы каждое значение можно было использовать один раз.

Ну что, можно такое сделать на яваскрипте, чтобы быстро работало?

Автор: cru3l 9.11.2009, 12:32

ну что, такое задание остудило ваш пыл? smile

скажите хотя бы, такое вообще резонно делать на javascript'e, может все таки использовать что-нибудь более нативное для ОС

Автор: brother79 9.11.2009, 12:45

Цитата(cru3l @ 9.11.2009, 12:32

)

ну что, такое задание остудило ваш пыл? smile

скажите хотя бы, такое вообще резонно делать на javascript'e, может все таки использовать что-нибудь более нативное для ОС

Какие пределы по исходным данным? Просто мне пока только перебор с отсечением приходит в голову.

Автор: sTa1kEr 9.11.2009, 13:59

Решение перебором (с учетом условия уникальности значений):

Код


var numbers = new Array(20,20,20,21,35,36,40,50,70,85,90,88);
var x = 9.894179894179896 // (88/21) * (85/36) == 9.894179894179896
var m = [0,0,0,0], k = 72;

// Для сравнения вещественных чисел с точностью до 3 знаков после запятой
x = Math.round(x * 1000);

function calculate(n) {
    if (n == 4) {
        if ( (m[0] + m[1]) > k && (m[2] + m[3]) > k ) {

            // Сообственно сама формула
            y = (m[0] / m[1]) * (m[2] / m[3]);

            if (Math.round(y * 1000) == x ) {
                document.write('x = ' + m[0] + '/' + m[1] + ' * ' + m[2] + '/' + m[3] + '<br />');
            }
        }
        return;
    }

    var len = numbers.length;
    for (var i = 0; i < len; i++) {
        m[n] = numbers.shift();
        calculate(n + 1);
        numbers.push(m[n]);
    }
}

calculate(0);

Вывод:

Код


x = 85/21 * 88/36
x = 85/36 * 88/21
x = 88/21 * 85/36
x = 88/36 * 85/21

Profile (115.684ms, 13346 calls)
Function   Calls    Percent  Own Time     Time         Avg          Mi           Max          File
calculate  13345    99.85%   115.511ms    115.511ms    0.009ms      0m           115.511ms    4 (line 9)
eval()     1        0.15%    0.173ms      117.765ms    117.765ms    117.765ms    117.765ms    4 (line 1)

Автор: cru3l 9.11.2009, 16:02

sTa1kEr, спасибо за решение, работает действительно офигенно. но вот если подставить входной массив с такими данными

Код


var numbers = new Array(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100);

то на выходе получаем опять ужасные тормоза. What's the trick?

Автор: cru3l 9.11.2009, 16:24

и да, опять же — я как бы и не против таких тормозов. Но как сделать так, чтобы браузер при этом не зависал намертво. Просто вывести надпись - "Идет расчет" и считать себе спокойно как бы в отдельном треде.
время рассчета не сильно критично (в разумных пределах, конечно)

Автор: sTa1kEr 9.11.2009, 16:28

Цитата(cru3l @ 9.11.2009, 17:02

)

то на выходе получаем опять ужасные тормоза. What's the trick?

Логично, что для большего количества значений такой алгоритм не подойдет.

Автор: cru3l 9.11.2009, 16:34

sTa1kEr, эх, мне бы до 100 включительно ((

Автор: sTa1kEr 9.11.2009, 16:35

Цитата(cru3l @ 9.11.2009, 17:24

)

ремя рассчета не сильно критично (в разумных пределах, конечно)

Ну если несколько сотен часов - это разумный предел...

Для такого количества значений нужен другой алгоритм... надо будет подумать.

Автор: sTa1kEr 9.11.2009, 17:32

Слегка улучшенный алгоритм все того же перебора (при большом значении k сильно уменьшает количество итераций):

Код


var numbers = new Array();
var a = numbers, b = numbers, c = numbers, d = numbers;
var x = 9.894179894179896 // (88/21) * (85/36)= 9.894179894179896
var m = [0,0,0,0], k = 72;

for (var i = 1; i <= 100; i++) {
    numbers.push(i);
}

// Для сравнения вещественных чисел с точностью до 3 знаков после запятой
x = Math.round(x * 1000);

function calculate(n) {
    if ((n + 1) % 2 == 0 && (m[n-1] + m[n]) <= k) {
        return;
    }

    var len = numbers.length;
    for (var i = 0; i < len; i++) {
        m[n] = numbers.shift();
        if (n == 3) {
            // Сообственно сама формула
            var y = (m[0] / m[1]) * (m[2] / m[3]);

            if (Math.round(y * 1000) == x ) {
                console.log('x = ' + m[0] + '/' + m[1] + ' * ' + m[2] + '/' + m[3]);
            }
        } else {
            calculate(n + 1);
        }
        numbers.push(m[n]);
    }
}

calculate(0);

Profile (115.684ms, 13346 calls)
Function Calls Percent Own Time Time Avg Min Max File
calculate 274529 100% 52749.617ms 53553.856ms 0.195ms 0ms 53553.856ms 24 (line 14)

Что-же касается фонового выполнения расчета, то для этого можно воспользоваться хаком с таймером, как описано http://webo.in/articles/habrahabr/13-cpu-intensive-javascript/.

Автор: cru3l 9.11.2009, 19:29

k можно было и не делать переменной. Оно всегда будет равно 72м.

Алгоритм очень клевый. Работает быстро. Спасибо smile