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



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

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

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

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

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

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

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

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

да напортачил я там с этими +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 - 8.11.2009, 17:19

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

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

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

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

Вывод:


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)

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



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

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

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

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

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

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

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


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)


Что-же касается фонового выполнения расчета, то для этого можно воспользоваться хаком с таймером, как описано здесь.

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

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