Оптимизация алгоритмов. - страница 5

[TheXpert]

Mathemat:
В принципе да. Но все равно не больше О(n).

Не меньше :) с хорошей фантазией можно и экспоненциальную зависимость запилить :)

[Vasiliy Sokolov]

Mathemat:

Ну это не оптимизационная проблема. 

Поиск экстремума - всегда проблема порядка О(n), где n - число данных. Как можно сделать эту асимптотику хуже - даже не представляю.

Простейший алгоритм - сортировка ArraySort(), встроенная достаточно быстра.  Но она, вероятно, избыточна для этой задачи.

Можно придумать что-нибудь рекурсивное, которое будет быстрее.

Сколько времени у тебя ищется минимум и для какого кoличества барoв?

Я привел статистику в первом посте. Рассчет на 1 000 000 баров арифметически растет с увеличением периода. Так для периода 3, расчет занимает 0.54 секунды, для периода 51 0.94 секунды, а для периода 99 уже 1,59 секунды.

Хуже получается потому, что используется цикл в цикле, а это ошибка. Так для периода 3 количество итераций будет 1 000 000 * (3-1/2) = 1 000 000, а вот для перида 99 уже 1 000 000  * (99-1)/2 = 49 000 000! Поэтому алгоритм нужно переписать таким образом, что бы количество итераций при неизменном количестве данных качественно не увеличивалось с увеличением периода, а это уже чисто оптимизационная задача. Сейчас этим и занимаюсь. Пока написал вот что:

static void Up(Bars MyQuotes)
        {
            BitArray bits = new BitArray(MyQuotes.Count);
            double max = double.MinValue;
            int pperiod = (23 - 1) / 2;
            int bar = pperiod;
            int count = MyQuotes.Count - pperiod;
            //последняя позиция второго перебора.
            int pos = bar;
            while (bar < count)
            {
                for (int i = 1; i <= pperiod; i++)
                {
                    max = MyQuotes.High[bar - i] > MyQuotes.High[bar + i]
                              ? MyQuotes.High[bar - i]
                              : MyQuotes.High[bar + i];
                    pos = bar + i;
                    if(max > MyQuotes.High[bar])
                    {
                        //Начинаем с последнего бара
                        bar = pos;
                        break;
                    }
                    if(i == pperiod)
                    {
                        bits[bar + i] = true;
                        bar = pos;
                    }
                }
            }
        }

Для поиска минимума будет сотвествующая функция Down(), запущенная в паралельном потоке. После завершения работы обоих функций, их результаты будут заноситься в общий список. Как-то так.

[Sceptic Philozoff]

C-4: Я привел статистику в первом посте. Рассчет на 1 000 000 баров арифметически растет с увеличением периода. Так для периода 3, расчет занимает 0.54 секунды, для периода 51 0.94 секунды, а для периода 99 уже 1,59 секунды.

Ну вот, таки напутал. Это не сумма рихметической прогрессии, С-4. Сумма растет квадратично.

OCL однозначно.

[Vasiliy Sokolov]

Mathemat:

Простейший алгоритм - сортировка ArraySort(), встроенная достаточно быстра, что-то в районе O(n * ln( n ) ).  Но она, вероятно, избыточна для этой задачи.

 Думал. Любая сортировка будет заведомо медленней перебора всего массива через for. For дает одну итерацию, а arraysort в лучшем случае будет сортировать значения в каждом подокне n, что само по себе будет означать десятки действий.

Нет, все-таки здесь нужно стремиться к тому, что бы общее количество итераций качественно не отличалось от количества баров.

[Vasiliy Sokolov]

Mathemat:

Ну вот, таки напутал. Это не сумма рихметической прогрессии, С-4. Сумма растет квадратично.

OCL однозначно.

Если квадратично, - еще хуже. Без многопоточности, как я понимаю не обойтись.

[hrenfx]

Условие такого поиска экстремумов мягко-говоря странное... Но даже несмотря на это, использовать лобовой способ поиска крайне неразумно.

Сразу в голову приходит однопроходный классический ЗигЗаг с ExtDepth = n с небольшой подгонкой под текущее условие. OCL здесь 100% не нужен.

[TheXpert]

Жжоте мужыки. Все трое.

[Vasiliy Sokolov]

hrenfx:

Условие такого поиска экстремумов мягко-говоря странное... Но даже несмотря на это, использовать лобовой способ поиска крайне неразумно.

Сразу в голову приходит однопроходный классический ЗигЗаг с ExtDepth = n с небольшой подгонкой под текущее условие. OCL здесь 100% не нужен.

Ну в принципе мне и нужны эти экстремумы для а-ля зиг-зага. Тогда конкретно какие алгоритмы лучше использовать? Есть ли более эффективный код, чем тот что я привел во второй версии?

[hrenfx]

Посмотрите однопроходные ЗигЗаги в CodeBase MT4 - O(N).

[Sceptic Philozoff]

TheXpert: Жжоте мужыки. Все трое.

А чего? O(n) все равно будет, как ни крути.

Если ничего не помогает - попробуй OCL. Других способов без извращений типа dll в пятере нет.