Информация об изменениях

Сообщение Re[7]: [забыл математику] Оптимизация алгоритма от 16.09.2022 23:47

Изменено 17.09.2022 1:02 xma

Re[7]: [забыл математику] Оптимизация алгоритма
Здравствуйте, Xander Zerge, Вы писали:

XZ>Ты свой туда же подложи, и посмотрим, это код не работает, или ты просто эксплойтишь ограниченное количество знаков после точки в decimal.

пофиксил также метод Serge Novikoff в виде test_optimal_Serge_Novikoff_fixed — теперь и он работает идеально

P.S.: ещё один fix на сравнение с нулём

  source code (fixed)
проверяйте тут,
https://dotnetfiddle.net/

using System;
                    
public class Program
{
    // работоспособный минимум (на конкретных тестах) это (1 / Math.Pow(10, 24))
    public static decimal DecimalEpsilon = (decimal) (1 / Math.Pow(10, 6));
    
    public static void Main()
    {
        Console.WriteLine("Hello World");
        
        /*
        decimal marketBuyPrice = 736.72m, overwriteMinStep = 7.3671999999999999999999999999m;
        ////decimal marketBuyPrice = 0.000000001m, overwriteMinStep = 0.1m;
        
        var ret = test_original(marketBuyPrice, overwriteMinStep);
        var ret_opt2 = test_optimal2(marketBuyPrice, overwriteMinStep);
        var ret_opt_Serge_Novikoff = test_optimal_Serge_Novikoff(marketBuyPrice, overwriteMinStep);
        
        var ret_opt_Serge_Novikoff_fixed = test_optimal_Serge_Novikoff_fixed(marketBuyPrice, overwriteMinStep);
        
        Console.WriteLine("marketBuyPrice = " + marketBuyPrice + ", overwriteMinStep = " + overwriteMinStep);
        
        Console.WriteLine("ret_original = " + ret);
        Console.WriteLine("ret_opt2 = " + ret_opt2);
        Console.WriteLine("ret_opt_Serge_Novikoff = " + ret_opt_Serge_Novikoff);
        
        Console.WriteLine("ret_opt_Serge_Novikoff_fixed = " + ret_opt_Serge_Novikoff_fixed);
        
        bool flag_test_optimal2 = Math.Abs(ret - ret_opt2) < DecimalEpsilon ;
        Console.WriteLine("flag_test_optimal2 = " + flag_test_optimal2);
        
        bool flag_test_Serge_Novikoff = Math.Abs(ret - ret_opt_Serge_Novikoff) < DecimalEpsilon ;
        Console.WriteLine("flag_test_Serge_Novikoff = " + flag_test_Serge_Novikoff);
        
        bool flag_test_Serge_Novikoff_fixed = Math.Abs(ret - ret_opt_Serge_Novikoff_fixed) < DecimalEpsilon ;
        Console.WriteLine("flag_test_Serge_Novikoff_fixed = " + flag_test_Serge_Novikoff_fixed);
        */
        
        ///*
        Random rand = new Random();
        
        bool flag_test_optimal2 = true;
        bool flag_test_Serge_Novikoff = true;
        bool flag_test_Serge_Novikoff_fixed = true;
        
        for (int i=0; i<10000; i++) {
            
            decimal marketBuyPrice = rand.Next(0, 1000000) / 100.0m; 
            decimal overwriteMinStep = rand.Next(1, 10000000) / 100.0m; 
            
            if (marketBuyPrice / overwriteMinStep > 100)
                overwriteMinStep *= marketBuyPrice / (overwriteMinStep * 100.0m);
            
            var ret = test_original(marketBuyPrice, overwriteMinStep);
            var ret_opt2 = test_optimal2(marketBuyPrice, overwriteMinStep);
            
            var ret_opt_Serge_Novikoff = test_optimal_Serge_Novikoff(marketBuyPrice, overwriteMinStep);
            
            var ret_opt_Serge_Novikoff_fixed = test_optimal_Serge_Novikoff_fixed(marketBuyPrice, overwriteMinStep);
            
            bool temp_flag_test_optimal2 = Math.Abs(ret - ret_opt2) < DecimalEpsilon;
            bool temp_flag_test_Serge_Novikoff = Math.Abs(ret - ret_opt_Serge_Novikoff) < DecimalEpsilon;
            bool temp_flag_test_Serge_Novikoff_fixed = Math.Abs(ret - ret_opt_Serge_Novikoff_fixed) < DecimalEpsilon;
            
            if ( (false == temp_flag_test_optimal2) || (false == temp_flag_test_Serge_Novikoff) || (false == temp_flag_test_Serge_Novikoff_fixed) ) {
                
                flag_test_optimal2 &= temp_flag_test_optimal2 ;
                flag_test_Serge_Novikoff &= temp_flag_test_Serge_Novikoff;
                flag_test_Serge_Novikoff_fixed &= temp_flag_test_Serge_Novikoff_fixed;
                
                Console.WriteLine("");
                Console.WriteLine("marketBuyPrice = " + marketBuyPrice + ", overwriteMinStep = " + overwriteMinStep);
                
                Console.WriteLine("ret_original = " + ret);
                Console.WriteLine("ret_opt2 = " + ret_opt2);
                
                Console.WriteLine("ret_opt_Serge_Novikoff = " + ret_opt_Serge_Novikoff);
                
                Console.WriteLine("ret_opt_Serge_Novikoff_fixed = " + ret_opt_Serge_Novikoff_fixed);
            }
        }
        
        Console.WriteLine("");
        Console.WriteLine("flag_test_optimal2 = " + flag_test_optimal2);
        Console.WriteLine("flag_test_Serge_Novikoff = " + flag_test_Serge_Novikoff);
        Console.WriteLine("flag_test_Serge_Novikoff_fixed = " + flag_test_Serge_Novikoff_fixed);
        //*/
    }
    
    public static decimal test_original(decimal marketBuyPrice, decimal overwriteMinStep)
    {        
        decimal mediumPrice2 = 0;

        do
        {
            mediumPrice2 += overwriteMinStep;
        } while (mediumPrice2 < marketBuyPrice);
        
        return mediumPrice2;
    }

    public static decimal test_optimal2(decimal marketBuyPrice, decimal overwriteMinStep)
    {        
        //if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
            return overwriteMinStep;

        decimal mediumPrice2 = (decimal.Floor(marketBuyPrice / overwriteMinStep) + 1) * overwriteMinStep;
        
        //if ( mediumPrice2 == marketBuyPrice + overwriteMinStep )
        //if ( Math.Abs(mediumPrice2 - (marketBuyPrice + overwriteMinStep)) <= 0.0001m )
        if ( Math.Abs(mediumPrice2 - (marketBuyPrice + overwriteMinStep)) < DecimalEpsilon )
            mediumPrice2 -= overwriteMinStep;
            
        return mediumPrice2;
    }
    
    public static decimal test_optimal_Serge_Novikoff(decimal marketBuyPrice, decimal minStep)
    {        
        ////if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        //if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
        //    return minStep;
        
        var imin = (int)(marketBuyPrice / minStep);
        
        if (minStep * imin < marketBuyPrice)
            ++imin;

        decimal mediumPrice2 = minStep * imin;
            
        return mediumPrice2;
    }
    
    public static decimal test_optimal_Serge_Novikoff_fixed(decimal marketBuyPrice, decimal minStep)
    {        
        //if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
            return minStep;
        
        //var imin = (int)(marketBuyPrice / minStep); // можно было оставить
        int imin = (int)decimal.Floor(marketBuyPrice / minStep); // для наглядности
        
        //if (minStep * imin < marketBuyPrice) // в это проблема метода Serge_Novikoff
        if ( (minStep * imin + DecimalEpsilon < marketBuyPrice) && (minStep * imin - DecimalEpsilon < marketBuyPrice))
            ++imin;

        decimal mediumPrice2 = minStep * imin;
    
            
        return mediumPrice2;
    }
}


test_optimal_Serge_Novikoff — это не пофикшенный (криво работающий) метод Serge Novikoff'а .. (для наглядности оставил, для сравнения результатов работы),

test_optimal2 — это ещё в прошлый раз пофикшенный мой метод (также работающий идеально) ..

P.S.:

проверено для overwriteMinStep > 0 и marketBuyPrice >= 0,

(если нужна бОльшая точность, то регулируйте степень (Pow) десятки в DecimalEpsilon, (для делителя))

P.S.2:

Xander Zerge, в целом у тебя тоже верная и интересная идея, и как и у меня тут лишь точность сравнения (по окрестностям) с погрешностью DecimalEpsilon обыграть надо было .. (если не ошибаюсь, то я эту фишку сравнения чисел с плавающей точкой изначально вроде в книге Андре Ламота подчерпнул, более 15 лет назад — на сравнении float с нулём)

P.S.3:

кстате, про сравнение decimal с нулём — так и знал что надо тоже через окрестности DecimalEpsilon, иначе (проверил) глючит .. (уже поправил),

общая точность DecimalEpsilon по умолчанию задана как 1/(10^6), т.е. одна миллионная ..
Re[7]: [забыл математику] Оптимизация алгоритма
Здравствуйте, Xander Zerge, Вы писали:

XZ>Ты свой туда же подложи, и посмотрим, это код не работает, или ты просто эксплойтишь ограниченное количество знаков после точки в decimal.

пофиксил также метод Serge Novikoff в виде test_optimal_Serge_Novikoff_fixed — теперь и он работает идеально

P.S.: ещё один fix на сравнение с нулём

  source code (fixed)
проверяйте тут,
https://dotnetfiddle.net/

using System;
                    
public class Program
{
    // работоспособный минимум (на конкретных тестах) это (1 / Math.Pow(10, 24))
    public static decimal DecimalEpsilon = (decimal) (1 / Math.Pow(10, 6));
    
    public static void Main()
    {
        Console.WriteLine("Hello World");
        
        /*
        decimal marketBuyPrice = 736.72m, overwriteMinStep = 7.3671999999999999999999999999m;
        ////decimal marketBuyPrice = 0.000000001m, overwriteMinStep = 0.1m;
        
        var ret = test_original(marketBuyPrice, overwriteMinStep);
        var ret_opt2 = test_optimal2(marketBuyPrice, overwriteMinStep);
        var ret_opt_Serge_Novikoff = test_optimal_Serge_Novikoff(marketBuyPrice, overwriteMinStep);
        
        var ret_opt_Serge_Novikoff_fixed = test_optimal_Serge_Novikoff_fixed(marketBuyPrice, overwriteMinStep);
        
        Console.WriteLine("marketBuyPrice = " + marketBuyPrice + ", overwriteMinStep = " + overwriteMinStep);
        
        Console.WriteLine("ret_original = " + ret);
        Console.WriteLine("ret_opt2 = " + ret_opt2);
        Console.WriteLine("ret_opt_Serge_Novikoff = " + ret_opt_Serge_Novikoff);
        
        Console.WriteLine("ret_opt_Serge_Novikoff_fixed = " + ret_opt_Serge_Novikoff_fixed);
        
        bool flag_test_optimal2 = Math.Abs(ret - ret_opt2) < DecimalEpsilon ;
        Console.WriteLine("flag_test_optimal2 = " + flag_test_optimal2);
        
        bool flag_test_Serge_Novikoff = Math.Abs(ret - ret_opt_Serge_Novikoff) < DecimalEpsilon ;
        Console.WriteLine("flag_test_Serge_Novikoff = " + flag_test_Serge_Novikoff);
        
        bool flag_test_Serge_Novikoff_fixed = Math.Abs(ret - ret_opt_Serge_Novikoff_fixed) < DecimalEpsilon ;
        Console.WriteLine("flag_test_Serge_Novikoff_fixed = " + flag_test_Serge_Novikoff_fixed);
        */
        
        ///*
        Random rand = new Random();
        
        bool flag_test_optimal2 = true;
        bool flag_test_Serge_Novikoff = true;
        bool flag_test_Serge_Novikoff_fixed = true;
        
        for (int i=0; i<10000; i++) {
            
            decimal marketBuyPrice = rand.Next(0, 1000000) / 100.0m; 
            decimal overwriteMinStep = rand.Next(1, 10000000) / 100.0m; 
            
            if (marketBuyPrice / overwriteMinStep > 100)
                overwriteMinStep *= marketBuyPrice / (overwriteMinStep * 100.0m);
            
            var ret = test_original(marketBuyPrice, overwriteMinStep);
            var ret_opt2 = test_optimal2(marketBuyPrice, overwriteMinStep);
            
            var ret_opt_Serge_Novikoff = test_optimal_Serge_Novikoff(marketBuyPrice, overwriteMinStep);
            
            var ret_opt_Serge_Novikoff_fixed = test_optimal_Serge_Novikoff_fixed(marketBuyPrice, overwriteMinStep);
            
            bool temp_flag_test_optimal2 = Math.Abs(ret - ret_opt2) < DecimalEpsilon;
            bool temp_flag_test_Serge_Novikoff = Math.Abs(ret - ret_opt_Serge_Novikoff) < DecimalEpsilon;
            bool temp_flag_test_Serge_Novikoff_fixed = Math.Abs(ret - ret_opt_Serge_Novikoff_fixed) < DecimalEpsilon;
            
            if ( (false == temp_flag_test_optimal2) || (false == temp_flag_test_Serge_Novikoff) || (false == temp_flag_test_Serge_Novikoff_fixed) ) {
                
                flag_test_optimal2 &= temp_flag_test_optimal2 ;
                flag_test_Serge_Novikoff &= temp_flag_test_Serge_Novikoff;
                flag_test_Serge_Novikoff_fixed &= temp_flag_test_Serge_Novikoff_fixed;
                
                Console.WriteLine("");
                Console.WriteLine("marketBuyPrice = " + marketBuyPrice + ", overwriteMinStep = " + overwriteMinStep);
                
                Console.WriteLine("ret_original = " + ret);
                Console.WriteLine("ret_opt2 = " + ret_opt2);
                
                Console.WriteLine("ret_opt_Serge_Novikoff = " + ret_opt_Serge_Novikoff);
                
                Console.WriteLine("ret_opt_Serge_Novikoff_fixed = " + ret_opt_Serge_Novikoff_fixed);
            }
        }
        
        Console.WriteLine("");
        Console.WriteLine("flag_test_optimal2 = " + flag_test_optimal2);
        Console.WriteLine("flag_test_Serge_Novikoff = " + flag_test_Serge_Novikoff);
        Console.WriteLine("flag_test_Serge_Novikoff_fixed = " + flag_test_Serge_Novikoff_fixed);
        //*/
    }
    
    public static decimal test_original(decimal marketBuyPrice, decimal overwriteMinStep)
    {        
        decimal mediumPrice2 = 0;

        do
        {
            mediumPrice2 += overwriteMinStep;
        } while (mediumPrice2 < marketBuyPrice);
        
        return mediumPrice2;
    }

    public static decimal test_optimal2(decimal marketBuyPrice, decimal overwriteMinStep)
    {        
        //if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
            return overwriteMinStep;

        decimal mediumPrice2 = (decimal.Floor(marketBuyPrice / overwriteMinStep) + 1) * overwriteMinStep;
        
        //if ( mediumPrice2 == marketBuyPrice + overwriteMinStep )
        //if ( Math.Abs(mediumPrice2 - (marketBuyPrice + overwriteMinStep)) <= 0.0001m )
        if ( Math.Abs(mediumPrice2 - (marketBuyPrice + overwriteMinStep)) < DecimalEpsilon )
            mediumPrice2 -= overwriteMinStep;
            
        return mediumPrice2;
    }
    
    public static decimal test_optimal_Serge_Novikoff(decimal marketBuyPrice, decimal minStep)
    {        
        ////if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        //if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
        //    return minStep;
        
        var imin = (int)(marketBuyPrice / minStep);
        
        if (minStep * imin < marketBuyPrice)
            ++imin;

        decimal mediumPrice2 = minStep * imin;
            
        return mediumPrice2;
    }
    
    public static decimal test_optimal_Serge_Novikoff_fixed(decimal marketBuyPrice, decimal minStep)
    {        
        //if (decimal.Zero == marketBuyPrice) // == 0 // косячок
        if (Math.Abs(marketBuyPrice) < DecimalEpsilon) // == 0
            return minStep;
        
        //var imin = (int)(marketBuyPrice / minStep); // можно было оставить
        int imin = (int)decimal.Floor(marketBuyPrice / minStep); // для наглядности
        
        //if (minStep * imin < marketBuyPrice) // в это проблема метода Serge_Novikoff
        if ( (minStep * imin + DecimalEpsilon < marketBuyPrice) && (minStep * imin - DecimalEpsilon < marketBuyPrice))
            ++imin;

        decimal mediumPrice2 = minStep * imin;
    
            
        return mediumPrice2;
    }
}


test_optimal_Serge_Novikoff — это не пофикшенный (криво работающий) метод Serge Novikoff'а .. (для наглядности оставил, для сравнения результатов работы),

test_optimal2 — это ещё в прошлый раз пофикшенный мой метод (также работающий идеально) ..

P.S.:

проверено для overwriteMinStep > 0 и marketBuyPrice >= 0,

(если нужна бОльшая точность, то регулируйте степень (Pow) десятки в DecimalEpsilon, (для делителя))

P.S.2:

Xander Zerge, в целом у тебя тоже верная и интересная идея, и как и у меня тут лишь точность сравнения (по окрестностям) с погрешностью DecimalEpsilon обыграть надо было .. (если не ошибаюсь, то я эту фишку сравнения чисел с плавающей точкой изначально вроде в книге Андре Ламота подчерпнул, более 15 лет назад — на сравнении float с нулём)

P.S.3:

кстате, про сравнение decimal с нулём — так и знал что надо тоже через окрестности DecimalEpsilon, иначе (проверил) глючит (на мелких числах) ..

(уже поправил),

общая точность DecimalEpsilon по умолчанию задана как 1/(10^6), т.е. одна миллионная ..