Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/18: Рейтинг темы: голосов - 18, средняя оценка - 4.72
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
1

Оптимизация производительности C#.NET (Алгоритм, Многопоточность, Debug, Release, .Net Core, Net Native)

26.03.2017, 13:39. Просмотров 3233. Ответов 19
Метки нет (Все метки)


Решил поделится своим небольшим опытом по оптимизации вычислений на C#.NET.
НЕ профи, палками не кидать, конструктив приветствуется!
Тестом будет служить время вычисление всех переменных в заданном диапазоне (до 100000) в уравнении x^3 + y^3 = z^3 - 1
Симметричные решения по x и y не учитываем, т.е. из вариантов х=6,у=8,z=9 и х=8,у=6,z=9 - берем один (любой).
Оборудование/Софт:
Кликните здесь для просмотра всего текста
Тип ЦП QuadCore AMD Phenom II X4 Black Edition 955, 3200 MHz (16 x 200)
Системная плата Asus M4A89GTD Pro (2 PCI, 1 PCI-E x1, 1 PCI-E x4, 2 PCI-E x16, 4 DDR3 DIMM, Audio, Video, Gigabit LAN, IEEE-1394)
Чипсет системной платы AMD 890GX, AMD K10
Системная память 8192 МБ (DDR3-1333 DDR3 SDRAM)
Софт Win10x64, Excel2016x64, Visual Studio 2017

ШАГ1. Все кажется просто, берем и перебором ищем значения. Здесь сражу же упираемся в большое количество итераций - время выполнение неприлично большое.

Поэтому ШАГ2 - Оптимизируем алгоритм, создаем массив из степеней Z, переберем значения х, у, обрезаем ненужные итерации, оставляем только один вариант x,y и обрезаем итерации на суммах x^3 + y^3 > z^3. Здесь (код) пальма первенства справедливо принадлежит m-ch - опять неприлично долго в VBA более 10 мин.

ШАГ3. Берем этот алгоритм, переносим на C# и делим потоки, благо это задача хорошо бьется по потокам.
Код (Сборка Debug x64):
Кликните здесь для просмотра всего текста
C#
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
using System;
using System.Collections.Generic;
using System.Threading;
 
//поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
class Program
{
    static long n; static long k = 0;
    static long[] a;
 
    static void Main(string[] args)
    {
        var threads = new List<Thread>();
 
        for (int i = 2; i <= 9; i++)
        {
            int k = i;
            threads.Add(new Thread(() => func(k)));
        }
 
        Console.Write("Задайте диапазон расчета переменных, до..., нажмите Enter: ");
        n = Convert.ToInt64(Console.ReadLine());
        a = new long[n + 1];
 
        DateTime dold = DateTime.Now;
 
        for (long i = 1; i <= n; i++)
        {
            a[i] = (long)Math.Pow(i, 3);
        }
 
        threads.ForEach(t => t.Start());
        threads.ForEach(t => t.Join()); //ждем выполнения всех потоков
 
        TimeSpan sp = DateTime.Now - dold;
        Console.WriteLine(sp);
        Console.Write("Программа завершена. Нажмите Enter для выхода...");
        Console.ReadLine();
    }
 
    static void func(long start)
    {
        // здесь код, который будет выполняться в отдельном потоке
        for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x = x + 8)//на 8 потоков
        {
            for (long y = x; y <= (long)Math.Pow(((a[n]) - 1 - a[x]), 1.0 / 3.0); y++)
            {
                long z3 = a[x] + a[y] + 1;
                long z = (long)(Math.Pow(z3, 1.0 / 3.0) + 0.5);
 
                if (a[z] == z3)
                {
                    k = ++k;
                    Console.WriteLine(k + "   " + x + "   " + y + "   " + z);
                }
            }
        }
    }
}

Время выполнения чуть более 4 минут (по ссылке выше есть так же расчет и на Freebasic). Пока прохладно.

ШАГ4. В C# (как проверено и не только в C#) расчет корня 3 степени медленнее, чем прямой перебор в массиве с некоторой хитростью (т.к. он отсортирован и перебор всегда ведется от меньшего к большему, или наоборот, легко запоминать последнюю найденную позицию и искать начиная с неё в след. цикле). Эта мысль меня посетила и была сразу реализована. Код (Сборка Debug x64) - делю на 4 потока, т.к. больше для моего ЦП -нет смысла:
Кликните здесь для просмотра всего текста
C#
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
using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;
 
namespace ConsoleApplication1
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static long n; static long k = 0; static long[] a;
        static long threadsN = 4;  //задать 4 потоков
 
        static void Main(string[] args)
        {
            var threads = new List<Thread>();
            for (int i = 1; i <= threadsN; i++)
            {
                int k = i;
                threads.Add(new Thread(() => func(k)));
            }
 
            Console.Write("Задайте диапазон расчета переменных, до..., нажмите Enter: ");
            n = Convert.ToInt64(Console.ReadLine());
            a = new long[n + 1];
 
            //DateTime dold = DateTime.Now;
            Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
            for (long i = 1; i <= n; i++) a[i] = (i * i * i); // Math.Pow не использовал из-за ошибок округления
 
            threads.ForEach(t => t.Start());//стартуем потоки
            threads.ForEach(t => t.Join()); //ждем выполнения всех потоков
 
            sw.Stop();
            //Console.WriteLine(sp);
            Console.WriteLine("Время вычисления: {0}", sw.Elapsed);
            Console.Write("Программа завершена. Нажмите Enter для выхода...");
            Console.ReadLine();
        }
 
        static void func(long start)
        {
            // здесь код, который будет выполняться в отдельном потоке
            long m = n;
            for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x = x + threadsN)//на 4 потоков
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x]) m--;
 
                for (long y = x; y <= m; y++)
                {
                    long z3 = a[x] + a[y] + 1;
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            Console.WriteLine(k + "   " + x + "   " + y + "   " + s);
                        }
                        s++;
                    }
                }
            }
        }
    }
}

Время выполнения - 41 сек. Уже теплее.

ШАГ5. Как же я забыл про Release, срочно исправляюсь - Сборка Release x64.
За счет оптимизации при компилировании получаем время выполнения - 17 секунд. Уже тепло.
Появляются мысли про оптимизацию цикла (в сети множество советов и примеров), т.к. для вычисления требуется несколько миллиардов итераций. Думаю.

ШАГ6. Почитав про .Net Core, решил попробовать.
Новый проект - Консольное приложение .Net Core - вставляем предыдущий код и ...
Время выполнения - 10,5 сек.
Здесь мне кажется, что сделан максимум на C#.

ШАГ7. Решил добить тему и погуглить.
Есть интересный зверь net native, подробно писать здесь не буду. Кратко: В Windows 10 универсальные Windows-приложения на управляемых языках (C#, VB) проходят в магазине процедуру компиляции в машинный код с использованием .NET Native.
Поэтому: создать проект-пустое приложение (универсальное приложение Windows)(UWP).
Создаем button, textBox (на кнопку код, в textBox - переменные).
Здесь нас поджидает проблемы с Threading.
Переходим на Task, двигаем дальше.
Код (Сборка Release x64)
Кликните здесь для просмотра всего текста
C#
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
using System;
using System.Collections.Generic;
using Windows.UI.Xaml;
using Windows.UI.Xaml.Controls;
using System.Threading.Tasks;
using System.Diagnostics;
 
namespace App1
{
    public sealed partial class MainPage : Page
    {
        static long n; static long k = 0; static long[] a; static string str = "";
        static long TaskN = 4;  //задать 4 task
 
        public MainPage()
        {
            this.InitializeComponent();
        }
            private void Button_Click(object sender, RoutedEventArgs e)
        {
            n = 100000;
            a = new long[n + 1];
            Stopwatch sw = Stopwatch.StartNew();
 
            for (long i = 1; i <= n; i++) a[i] = (i * i * i); // Math.Pow не использовал из-за ошибок округления
 
            var task = new List<Task>();
            for (int i = 1; i <= TaskN; i++)
            {
                int k = i;
                task.Add(new Task(() => func(k)));
            }
            task.ForEach(t => t.Start());//стартуем task
            task.ForEach(t => t.Wait()); //ждем выполнения всех task
            sw.Stop();
            button.Content = sw.Elapsed.TotalSeconds;
            textBox.Text = str;
        }
 
        static void func(long start)
        {
            // здесь код, который будет выполняться в отдельном task
            long m = n;
            
            for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x=x+TaskN) //на 4 task
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x]) m--;
 
                for (long y = x; y <= m; y++)
                {
 
                    long z3 = a[x] + a[y] + 1;
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            str = str + Environment.NewLine + (k + "   " + x + "   " + y + "   " + s);
                        }
                        s++;
                    }
                }
            }
        }
    }
}

Время выполнения 7,5 сек.
Без вывода строки 5 сек.(подумать со строкой)

ШАГ8. АССЕМБЛЕР... здесь мои знания заканчиваются...

Что скажут ОТЦЫ, есть ли дальнейшая оптимизация?

В блоге.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2017, 13:39
Ответы с готовыми решениями:

Объясните на пальцах совместимость библиотек в .Net Core, .Net Framework, .Net Standart
Изучаю .Net. Хочу написать некое серверное приложение (думаю что учеба лучше на реальном примере,...

Разница между ASP.NET Core 2, ASP.NET Core MVC, ASP.NET MVC 5 и ASP.NET WEBAPI 2
Здравствуйте. Я в бекенд разработке полный ноль. В чем разница между вышеперечисленными...

Сравнение производительности MariaDb и PostgreSql на .NET CORE
Решил присоединиться к кроссплатформенной разработке на .NET CORE и переписать одно из API на...

ASP.NET Core. Старт - что нужно знать, чтобы стать ASP.NET Core разработчиком?
Попалось хор краткое обзорное видео 2016 года с таким названием - Что нужно знать, чтобы стать...

19
589 / 474 / 184
Регистрация: 19.04.2016
Сообщений: 1,872
26.03.2017, 19:02 2
bedvit, я не батька, поэтому напишу здесь.
В общем, проверил этот же код на своем компьютере, немного изменив, выдает следующие результаты:
На 4 ядра:
Код
1 8,419543
2 8,1585624
3 8,10069
4 8,4201469
5 8,0496835
6 8,1739722
7 8,2498671
8 8,323654
9 8,2459111
10 8,3008305
На 8 ядер:
Код
1 5,7588025
2 5,9268395
3 5,6187675
4 5,6644015
5 5,6105386
6 5,6451581
7 5,6278141
8 5,7674422
9 5,7655258
10 5,7187006
Код

C#
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
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Threading.Tasks;
 
namespace CoreConsoleTester
{
    class Program
    {
        static long n;
        static long k = 0;
        static long[] a;
        static StringBuilder sb = new StringBuilder();
        static long TaskN = 4;  //задать 4 task
 
        static void Main(string[] args)
        {
            n = 100000;
            a = new long[n + 1];
 
            for (int j = 0; j < 10; j++)
            {
 
                Stopwatch sw = Stopwatch.StartNew();
                for (long i = 1; i <= n; i++)
                    a[i] = (i * i * i);
 
                var task = new Task[TaskN];
 
                for (int i = 1; i <= TaskN; i++)
                {
                    int k = i;
                    task[k - 1] = Func(k);
                }
 
                Task.WaitAll(task);
                sw.Stop();
 
                Console.WriteLine((j+1) + " " + sw.Elapsed.TotalSeconds);
                //Console.WriteLine();
                //Console.WriteLine(sb.ToString());
                sb = new StringBuilder();
            }
 
            Console.ReadKey();
        }
 
        static Task Func(long start)
        => Task.Run(() =>
        {
            long m = n;
 
            for (long x = start; x <= Math.Round(Math.Pow(((a[n]) - 1) / 2, 1d / 3d)); x = x + TaskN) //на 4 task
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x])
                    m--;
 
                for (long y = x; y <= m; y++)
                {
                    long z3 = a[x] + a[y] + 1;
 
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            sb.Append(k).Append(" ").Append(x).Append(" ").Append(y).Append(" ").Append(s).Append(Environment.NewLine);
                        }
                        s++;
                    }
                }
            }
        });
    }
}

Затем решил поискать варианты с кодов, где реализован интерфейс TaskScheduler
В итоге, вроде как, не чего не изменилось:
Код
1 8,4415179
2 8,157661
3 8,3211735
4 8,280029
5 8,3083202
6 8,1099499
7 8,2338602
8 8,2312203
9 8,3099153
10 8,6700347

1 5,7908688
2 5,8020905
3 5,5635274
4 5,6112798
5 5,5907419
6 5,5647906
7 5,7027833
8 5,5974618
9 5,5683131
10 5,5568128
Код с TaskScheduler

C#
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
 
namespace CoreConsoleTester
{
    class Program
    {
        static TaskCompletionSource<object> source = new TaskCompletionSource<object>();
        static TaskScheduler scheduler = new CustomTaskScheduler();
 
        static long n;
        static long k = 0;
        static long[] a;
        static StringBuilder sb = new StringBuilder();
        static long TaskN = 4;
 
        static void Main(string[] args)
        {
            n = 100000;
            a = new long[n + 1];
 
            for (int j = 0; j < 10; j++)
            {
 
                Stopwatch sw = Stopwatch.StartNew();
                for (long i = 1; i <= n; i++)
                    a[i] = (i * i * i);
 
                var task = new Task[TaskN];
 
                for (int i = 1; i <= TaskN; i++)
                {
                    int k = i;
                    task[k - 1] = Func(k);
                }
 
                Task.WaitAll(task);
                sw.Stop();
 
                Console.WriteLine((j + 1) + " " + sw.Elapsed.TotalSeconds);
                //Console.WriteLine();
                //Console.WriteLine(sb.ToString());
                sb = new StringBuilder();
            }
 
            Console.ReadKey();
        }
 
        static async Task Func(long start)
         => await Task.Run(() =>
         {
             long m = n;
 
             for (long x = start; x <= Math.Round(Math.Pow(((a[n]) - 1) / 2, 1d / 3d)); x = x + TaskN) //на 4 task
             {
                 long s = 1;
                 while (a[m] > (a[n]) - 1 - a[x])
                     m--;
 
                 for (long y = x; y <= m; y++)
                 {
                     long z3 = a[x] + a[y] + 1;
 
                     while ((a[s]) <= z3)
                     {
                         if (a[s] == z3)
                         {
                             k++;
                             sb.Append(k).Append(" ").Append(x).Append(" ").Append(y).Append(" ").Append(s).Append(Environment.NewLine);
                         }
                         s++;
                     }
                 }
             }
         }).ConfigureScheduler(scheduler);
    }
 
    public struct CustomTaskAwaitable
    {
        CustomTaskAwaiter awaitable;
 
        public CustomTaskAwaitable(Task task, TaskScheduler scheduler)
        {
            awaitable = new CustomTaskAwaiter(task, scheduler);
        }
 
        public CustomTaskAwaiter GetAwaiter() { return awaitable; }
 
        public struct CustomTaskAwaiter : INotifyCompletion
        {
            Task task;
            TaskScheduler scheduler;
 
            public CustomTaskAwaiter(Task task, TaskScheduler scheduler)
            {
                this.task = task;
                this.scheduler = scheduler;
            }
 
            public void OnCompleted(Action continuation)
            {
                task.ContinueWith(x => continuation(), scheduler);
            }
 
            public bool IsCompleted { get { return task.IsCompleted; } }
            public void GetResult() { }
        }
    }
 
    public static class TaskExtension
    {
        public static CustomTaskAwaitable ConfigureScheduler(this Task task, TaskScheduler scheduler)
        {
            return new CustomTaskAwaitable(task, scheduler);
        }
    }
 
    public class CustomTaskScheduler : TaskScheduler
    {
        protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) { return false; }
        protected override void QueueTask(Task task)
        {
            TryExecuteTask(task);
        }
    }
}


Ну и на ресурсе itvdn есть свои примеры с реализацией этого интерфейса, но они выкидывают наллреференс, через раз =))
Проверил на 4 ядрах, на 8 не вышло без исключений.
Код
1 8,5955904
2 7,9822086
3 8,434502
4 8,2540836
5 8,2939003
6 8,2409619
7 8,1733663
8 8,0794589
9 8,1387315
10 8,0360592
Код с классов с ресурсов itvdn

C#
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
101
102
103
104
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
 
namespace CoreConsoleTester
{
    class Program
    {
        static long n;
        static long k = 0;
        static long[] a;
        static StringBuilder sb = new StringBuilder();
        static long TaskN = 4;
 
        static void Main(string[] args)
        {
            n = 100000;
            a = new long[n + 1];
 
            TaskScheduler scheduler = new DelayTaskScheduler();
            TaskFactory factory = new TaskFactory(scheduler);
 
            for (int j = 0; j < 10; j++)
            {
 
                Stopwatch sw = Stopwatch.StartNew();
                for (long i = 1; i <= n; i++)
                    a[i] = (i * i * i);
 
                var task = new Task[TaskN];
 
                for (int i = 1; i <= TaskN; i++)
                {
                    int k = i;
                    task[k - 1] = factory.StartNew(() => Func(k));
                }
 
                Task.WaitAll(task);
                sw.Stop();
 
                Console.WriteLine((j + 1) + " " + sw.Elapsed.TotalSeconds);
                //Console.WriteLine();
                //Console.WriteLine(sb.ToString());
                sb = new StringBuilder();
            }
 
            Console.ReadKey();
        }
 
        static void Func(long start)
        {
            long m = n;
 
            for (long x = start; x <= Math.Round(Math.Pow(((a[n]) - 1) / 2, 1d / 3d)); x = x + TaskN) //на 4 task
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x])
                    m--;
 
                for (long y = x; y <= m; y++)
                {
                    long z3 = a[x] + a[y] + 1;
 
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            sb.Append(k).Append(" ").Append(x).Append(" ").Append(y).Append(" ").Append(s).Append(Environment.NewLine);
                        }
                        s++;
                    }
                }
            }
        }
    }
 
    class DelayTaskScheduler : TaskScheduler
    {
        Queue<Task> queue = new Queue<Task>();
 
        protected override void QueueTask(Task task)
        {
            queue.Enqueue(task);
 
            WaitCallback callback = (object state) => base.TryExecuteTask(queue.Dequeue());
            ThreadPool.QueueUserWorkItem(callback, null);
        }
 
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued)
        {
            return false;
        }
 
        protected override IEnumerable<Task> GetScheduledTasks()
        {
            return queue;
        }
    }
}

Еще один класс с itvdn
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    class DelayTaskScheduler : TaskScheduler
    {
        Queue<Task> queue = new Queue<Task>();
 
        protected override void QueueTask(Task task)
        {
            queue.Enqueue(task);
 
            WaitCallback callback = (object state) => base.TryExecuteTask(queue.Dequeue());
            ThreadPool.QueueUserWorkItem(callback, null);
        }
 
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued)
        {
            return false;
        }
 
        protected override IEnumerable<Task> GetScheduledTasks()
        {
            return queue;
        }
    }
1
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
26.03.2017, 20:47  [ТС] 3
Все возможные значения на текущем алгоритме (с int64). Отсортировано по Z. Итого 84 решения. Диапазон переменных 1:2097151((2^63)^(1/3)-1). См.под спойлер
Кликните здесь для просмотра всего текста
xyz
1689
271138144
3135138172
4372426505
5426486577
6242720729
7566823904
87918121010
923612071210
1057522922304
11193828203097
12267632303753
13112456105625
14219659846081
15194367026756
16185186758703
1719431164611664
1876761190312884
1933181680616849
20108661732818649
2130862158821609
2234532496524987
23173282763029737
2446073684036864
25281823121237513
26102303788738134
27257653385738239
28312123456641545
2972514940949461
30341994621251762
3165605902259049
32152186619866465
33291966616768010
34541015650369709
35328826947971852
36512936416573627
37173847824478529
3889998997090000
39584628738395356
407526394904108608
418450789559109747
4299800104383128692
4311978131736131769
4481404130119139974
4586103153422161976
4693066152526163297
4715551186588186624
48146996204290227033
49105570237095243876
5019772257010257049
51152526249972267625
52120039275616283006
5357055339590340126
5424695345702345744
55113208342719346788
56289511331954393316
57315750340623414082
58151499434305440365
59293999403346449846
6030374455580455625
6136863589776589824
62257118664572677161
63197144708282713337
6444216751638751689
65309874746831764206
66283896815498826809
67658625743413886447
68375703902654923848
6952487944730944784
7031199910525401061600
7138655910766641093024
726173011728321172889
739262719516901183258
7434264812401191248778
7559581512245161269838
7629424112983451303363
7797129811593521352601
787199914399401440000
7994290213091081455241
80115078213886721613673
81107793615689781722969
8266457217177101750249
838334817502661750329
84155784617244422073025

конфигурация та же, 4 ядра и т.д. (см. выше)
Расчет по алгоритму ШАГ6 - 1час 29мин.
По алгоритму ШАГ7 через (универсальное приложение Windows)(UWP) и компиляцию в машинный код, на таких больших диапазонах вылетает ошибка - причину пока не определил.

Добавлено через 2 минуты
А понять хочется ибо этот алгоритм/способ у меня самый быстрый сейчас.

Добавлено через 3 минуты
EveKS, насколько я понял, вы тоже через Console .Net Core, не через (универсальное приложение Windows)(UWP)?
0
589 / 474 / 184
Регистрация: 19.04.2016
Сообщений: 1,872
27.03.2017, 08:41 4
Цитата Сообщение от bedvit Посмотреть сообщение
n = 100000;
Цитата Сообщение от bedvit Посмотреть сообщение
Итого 84 решения.
Не срастается...
Код
╨Ч╨░╨┤╨░╨╣╤В╨╡ ╨┤╨╕╨░╨┐╨░╨╖╨╛╨╜ ╤А╨░╤Б╤З╨╡╤В╨░ ╨┐╨╡╤А╨╡╨╝╨╡╨╜╨╜╤Л╤Е, ╨┤╨╛..., ╨╜╨░╨╢╨╝╨╕╤В╨╡ Enter: 100000
1   6   8   9
2   71   138   144
3   135   138   172
4   236   1207   1210
5   242   720   729
6   372   426   505
7   575   2292   2304
8   426   486   577
9   566   823   904
10   791   812   1010
11   1124   5610   5625
12   1851   8675   8703
13   1943   6702   6756
14   1943   11646   11664
15   1938   2820   3097
16   2196   5984   6081
17   2676   3230   3753
18   3086   21588   21609
19   3453   24965   24987
20   3318   16806   16849
21   4607   36840   36864
22   6560   59022   59049
23   7251   49409   49461
24   7676   11903   12884
25   8999   89970   90000
26   10230   37887   38134
27   10866   17328   18649
28   15218   66198   66465
29   17328   27630   29737
30   17384   78244   78529
31   25765   33857   38239
32   28182   31212   37513
33   29196   66167   68010
34   32882   69479   71852
35   31212   34566   41545
36   34199   46212   51762
37   51293   64165   73627
38   54101   56503   69709
39   58462   87383   95356
╨Т╤А╨╡╨╝╤П ╨▓╤Л╤З╨╕╤Б╨╗╨╡╨╜╨╕╤П: 00:00:08.7553762
╨Я╤А╨╛╨│╤А╨░╨╝╨╝╨░ ╨╖╨░╨▓╨╡╤А╤И╨╡╨╜╨░. ╨Э╨░╨╢╨╝╨╕╤В╨╡ Enter ╨┤╨╗╤П ╨▓╤Л╤Е╨╛╨┤╨░...
Добавлено через 11 часов 14 минут
bedvit, еще немного оптимизировал текущий алгоритм, ниже результат на 8 и 4 ядрах:
Код
1 6,5317791
2 6,3221177
3 6,243117
4 6,2358343
5 6,2946634
6 6,4695762
7 6,1462388
8 6,4305404
9 6,3767552
10 6,4534968

1 4,4163211
2 3,9745174
3 3,9574649
4 3,9847986
5 4,017022
6 3,9952074
7 4,0651204
8 4,0272239
9 3,9591864
10 3,9934772
Код
C#
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Text;
using System.Linq;
using System.Runtime.CompilerServices;
 
namespace ConsoleApplication1
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static TaskCompletionSource<object> source = new TaskCompletionSource<object>();
        static TaskScheduler scheduler = new CustomTaskScheduler();
 
        static long n;
        static long n3;
        static long[] a;
        static int threadsN = 4;
        //static StringBuilder _sb = new StringBuilder();
        static List<Test> listTest = new List<Test>(100);
 
        static void Main(string[] args)
        {
            for (int j = 0; j < 10; j++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                //n = (long)Math.Pow(long.MaxValue, (1d / 3d));
                n = 100000;
                n3 = n * n * n;
                a = new long[n + 1];
 
                for (long i = 1; i <= n; i++)
                    a[i] = i * i * i;
 
                var task = new Task[threadsN];
                for (int i = 2; i - 2 < threadsN; i++)
                {
                    int k = i;
                    task[k - 2] = Func(k);
                }
 
 
                Task.WaitAll(task);
                sw.Stop();
 
                //Console.WriteLine(_sb.ToString().TrimEnd('\n'));
                //Console.WriteLine(string.Join("\n", listTest.Select(l => $"{l.Prop1} {l.Prop2} {l.Prop3}")));
                Console.WriteLine((j + 1) + " " + sw.Elapsed.TotalSeconds);
                //_sb = new StringBuilder();
            }
 
            Console.ReadLine();
        }
 
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            long m = n;
 
            for (long x = start; x <= Math.Round(Math.Pow((n3 - 1) / 2, 1d / 3d)); x = x + threadsN)
            {
                long ax = a[x];
 
                while (a[m] > n3 - ax - 1)
                    m--;
 
                long z = 1;
                for (long y = x; y <= m; y++)
                {
                    long z3 = ax + a[y] + 1;
 
                    for (long az = a[z]; az <= z3; z++, az = a[z])
                    {
                        if (az == z3)
                        {
                            //Console.WriteLine(x + "   " + y + "   " + z);
                            //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                            Test test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                            listTest.Add(test);
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
    }
 
    class Test
    {
        public long Prop1 { get; set; }
        public long Prop2 { get; set; }
        public long Prop3 { get; set; }
    }
 
    public struct CustomTaskAwaitable
    {
        CustomTaskAwaiter awaitable;
 
        public CustomTaskAwaitable(Task task, TaskScheduler scheduler)
        {
            awaitable = new CustomTaskAwaiter(task, scheduler);
        }
 
        public CustomTaskAwaiter GetAwaiter() { return awaitable; }
 
        public struct CustomTaskAwaiter : INotifyCompletion
        {
            Task task;
            TaskScheduler scheduler;
 
            public CustomTaskAwaiter(Task task, TaskScheduler scheduler)
            {
                this.task = task;
                this.scheduler = scheduler;
            }
 
            public void OnCompleted(Action continuation)
            {
                task.ContinueWith(x => continuation(), scheduler);
            }
 
            public bool IsCompleted { get { return task.IsCompleted; } }
            public void GetResult() { }
        }
    }
 
    public static class TaskExtension
    {
        public static CustomTaskAwaitable ConfigureScheduler(this Task task, TaskScheduler scheduler)
        {
            return new CustomTaskAwaitable(task, scheduler);
        }
    }
 
    public class CustomTaskScheduler : TaskScheduler
    {
        protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) { return false; }
        protected override void QueueTask(Task task)
        {
            TryExecuteTask(task);
        }
    }
}

Цитата Сообщение от bedvit Посмотреть сообщение
вы тоже через Console .Net Core
Да верно.
// *************
Нужно вкорне менять подход, т.к. переборы от 1 до нужного числа, не есть хороше. Возможно, стоит посмотреть в сторону деревьев или поискать другое решение.

Не по теме:

Вчерашний комент связан с недопониманием :)

0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
27.03.2017, 11:59  [ТС] 5
Срастается, потому как диапазон переменных взят больше - до 2097151. Вы и сами наверное уже поняли, судя по последнему коменту Это максимальное число для этого расчета/алгоритма.
Пока алгоритм сильно улучшить не удалось.
0
589 / 474 / 184
Регистрация: 19.04.2016
Сообщений: 1,872
27.03.2017, 12:59 6
bedvit, делать было нечего, решил дальше тестить, что да как:
Первые два варианта, вроде как дали маленький плюс, но не большой, выложу результаты на 4 ядра:
4 ядра, 2 варианта
Здесь я изменял только метод
Код
1 6,2182376
2 5,8958073
3 5,9115026
4 5,9840357
5 5,9454266
6 6,0558848
7 5,9110155
8 5,9936423
9 5,8191501
10 5,9548775
C#
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
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            Test test;
            long m = n;            
 
            for (long x = start, ax = a[x]; ax <= n3 / 2 ; x += threadsN, ax = a[x])
            {
                //var x = Math.Round(Math.Pow(ax, 1d / 3d) + 1d);
                while (a[m] > n3 - ax - 1)
                    m--;
 
                long z = 1;
                for (long y = x; y <= m; y++)
                {
                    long z3 = ax + a[y] + 1;
 
 
                    for (long az = a[z]; az <= z3; z++, az = a[z])
                    {
                        if (az == z3)
                        {
                            //Console.WriteLine(x + "   " + y + "   " + z);
                            //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                            test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                            listTest.Add(test);
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
Код
1 6,0103062
2 5,9340868
3 6,0284483
4 5,974301
5 5,9692474
6 6,0021498
7 5,9640035
8 6,0357201
9 5,8541525
10 6,1153229
C#
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
        static async Task Func(long x)
        => await Task.Run(() =>
        {
            Test test;
            long m = n;            
 
            for (long ax = a[x]; ax <= n3 / 2 ; x += threadsN, ax = a[x])
            {
                //var x = Math.Round(Math.Pow(ax, 1d / 3d) + 1d);
                while (a[m] > n3 - ax - 1)
                    m--;
 
                long z = 1;
                for (long y = x; y <= m; y++)
                {
                    long z3 = ax + a[y] + 1;
 
 
                    for (long az = a[z]; az <= z3; z++, az = a[z])
                    {
                        if (az == z3)
                        {
                            //Console.WriteLine(x + "   " + y + "   " + z);
                            //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                            test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                            listTest.Add(test);
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);

Но, в итоге, на данный момент, этот вариант выдает самые быстрые результаты, но с ошибкой в решении, и этому есть причина. Тесты на 8 и 4 ядрах:
Код
1 5,7573051
2 5,5737364
3 5,6891549
4 5,6648332
5 5,60078
6 5,6390717
7 5,5251576
8 5,7240282
9 5,4985922
10 5,6186098

1 3,757608
2 3,5626847
3 3,4670908
4 3,4441495
5 3,4428092
6 3,4634318
7 3,4660047
8 3,5239459
9 3,6314177
10 3,4205503
Текущий код метода
C#
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
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            Test test;
            long m = n;
 
            for (long ax = a[start]; ax <= n3 / 2; start += threadsN, ax = a[start])
            {
                double x = Math.Round(Math.Pow(ax, 1d / 3d));
                x++;
 
                while (a[m] > n3 - ax - 1)
                    m--;
 
                long z = 1;
                for (long y = (long)x; y <= m; y++)
                {
                    long z3 = ax + a[y];
                    z3++;
 
                    for (long az = a[z]; az <= z3; z++, az = a[z])
                    {
                        if (az == z3)
                        {
                            //Console.WriteLine(x + "   " + y + "   " + z);
                            //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                            test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                            listTest.Add(test);
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
 
// --//--
 
    class Test
    {
        public double Prop1 { get; set; }
        public long Prop2 { get; set; }
        public long Prop3 { get; set; }
    }

Весь код
C#
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Text;
using System.Linq;
using System.Runtime.CompilerServices;
 
namespace ConsoleApplication1
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static TaskCompletionSource<object> source = new TaskCompletionSource<object>();
        static TaskScheduler scheduler = new CustomTaskScheduler();
 
        static long n;
        static long n3;
        static long[] a;
        static int threadsN = 4;
        //static StringBuilder _sb = new StringBuilder();
        static List<Test> listTest = new List<Test>(100);
 
        static void Main(string[] args)
        {
            for (int j = 0; j < 10; j++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                //n = (long)Math.Pow(long.MaxValue, (1d / 3d));
                n = 100000;
                n3 = n * n * n;
                a = new long[n + 1];
 
                for (long i = 1; i <= n; i++)
                    a[i] = i * i * i;
 
                var task = new Task[threadsN];
                for (int i = 2; i - 2 < threadsN; i++)
                {
                    int k = i;
                    task[k - 2] = Func(k);
                }
 
                Task.WaitAll(task);
                sw.Stop();
 
                //Console.WriteLine(_sb.ToString().TrimEnd('\n'));
                //Console.WriteLine(string.Join("\n", listTest.OrderBy(l => l.Prop3).Select((l, n) => $"{n + 1} {(long)l.Prop1} {l.Prop2} {l.Prop3}")));
                Console.WriteLine((j + 1) + " " + sw.Elapsed.TotalSeconds);
                //_sb = new StringBuilder();
                //listTest = new List<Test>(100);
            }
 
            Console.ReadLine();
        }
 
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            Test test;
            long m = n;
 
            for (long ax = a[start]; ax <= n3 / 2; start += threadsN, ax = a[start])
            {
                double x = Math.Round(Math.Pow(ax, 1d / 3d));
                x++;
 
                while (a[m] > n3 - ax - 1)
                    m--;
 
                long z = 1;
                for (long y = (long)x; y <= m; y++)
                {
                    long z3 = ax + a[y];
                    z3++;
 
                    for (long az = a[z]; az <= z3; z++, az = a[z])
                    {
                        if (az == z3)
                        {
                            //Console.WriteLine(x + "   " + y + "   " + z);
                            //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                            test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                            listTest.Add(test);
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
    }
 
    class Test
    {
        public double Prop1 { get; set; }
        public long Prop2 { get; set; }
        public long Prop3 { get; set; }
    }
 
    public struct CustomTaskAwaitable
    {
        CustomTaskAwaiter awaitable;
 
        public CustomTaskAwaitable(Task task, TaskScheduler scheduler)
        {
            awaitable = new CustomTaskAwaiter(task, scheduler);
        }
 
        public CustomTaskAwaiter GetAwaiter() { return awaitable; }
 
        public struct CustomTaskAwaiter : INotifyCompletion
        {
            Task task;
            TaskScheduler scheduler;
 
            public CustomTaskAwaiter(Task task, TaskScheduler scheduler)
            {
                this.task = task;
                this.scheduler = scheduler;
            }
 
            public void OnCompleted(Action continuation)
            {
                task.ContinueWith(x => continuation(), scheduler);
            }
 
            public bool IsCompleted { get { return task.IsCompleted; } }
            public void GetResult() { }
        }
    }
 
    public static class TaskExtension
    {
        public static CustomTaskAwaitable ConfigureScheduler(this Task task, TaskScheduler scheduler)
        {
            return new CustomTaskAwaitable(task, scheduler);
        }
    }
 
    public class CustomTaskScheduler : TaskScheduler
    {
        protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) { return false; }
        protected override void QueueTask(Task task)
        {
            TryExecuteTask(task);
        }
    }
}


А теперь, о том об ошибке в вычислении:
X всегда получается на 1 больше, чем нужно, из-за x++;. Y и Z верны(но всегда-ли это будет).
Стоит убрать x++;, и решение становится верным, но время выполнения становится больше чем с x++;
Результаты тестов без x++;
Код
1 6,3557662
2 6,2554463
3 6,0935981
4 6,0851149
5 6,2010127
6 6,2236964
7 5,9953513
8 6,1165849
9 6,0466032
10 6,3141701

1 4,5086063
2 3,9724535
3 4,0155356
4 3,9471268
5 3,9767078
6 3,9217126
7 3,9868509
8 4,0765498
9 3,9430604
10 3,9768568

И этого мало, казалось бы, если посмотреть весь код, то эту часть:
C#
1
2
3
            for (long ax = a[start]; ax <= n3 / 2; start += threadsN, ax = a[start])
            {
                double x = Math.Round(Math.Pow(ax, 1d / 3d));
нужно заменить на:
C#
1
2
3
            for (long ax = a[start]; ax <= n3 / 2; start += threadsN, ax = a[start])
            {
                long x = start;
Т.к. -- зачем искать кубический корень от ax, если нам известно, что ax - это a[x], где хранится x^3.
Но и тут нелепость, время выполнения становится дольше , т.е.:
как не странно:
C#
1
long x = start;
выполняется дольше чем:
C#
1
2
3
4
long ax = a[start];
// --//--
double x = Math.Round(Math.Pow(ax, 1d / 3d));
x++;

Результаты тестов с long x = start;
Код
1 6,1252225
2 5,9866461
3 5,9865261
4 5,9215376
5 6,0631918
6 6,0891908
7 6,0323686
8 5,8800278
9 5,9198172
10 6,0492911

1 4,2965829
2 3,9311391
3 3,9362909
4 3,9484388
5 4,2992103
6 3,9220456
7 4,1234166
8 3,9944103
9 3,9705379
10 3,966697
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
27.03.2017, 13:41  [ТС] 7
EveKS, на первый взгляд странно. У вас не Win10 случаем? Хочу понять почему вариант/ШАГ7 не хочет работать на больших диапазонах переменных. Дело в компиляции или я чего-то не знаю/не учитываю. Пока у меня этот самый быстрый вариант за счет компиляции в машинный код (диапазон переменных до 500-600 тыс. далее вылетает ошибка). И да, спасибо за тесты!
0
589 / 474 / 184
Регистрация: 19.04.2016
Сообщений: 1,872
27.03.2017, 14:00 8
Цитата Сообщение от bedvit Посмотреть сообщение
Win10
Да 10.
Цитата Сообщение от bedvit Посмотреть сообщение
пасибо за тесты!
Пожалуйста
0
Эксперт .NET
14842 / 11229 / 2947
Регистрация: 17.09.2011
Сообщений: 18,812
27.03.2017, 14:40 9
В алгоритм не вникал, но можно малость производительности выжать, если убрать проверку индексов массива:
C#
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
var lim = Math.Round(Math.Pow((n3 - 1) / 2, 1d / 3d));
unsafe
{
    fixed (long* a = Program.a)
    {
        for (long x = start; x <= lim; x = x + threadsN)
        {
            long ax = a[x];
 
            var r = n3 - ax - 1;
            while (a[m] > r)
                m--;
 
            long z = 1;
            for (long y = x; y <= m; y++)
            {
                long z3 = ax + a[y] + 1;
 
                for (long az = a[z]; az <= z3; z++, az = a[z])
                {
                    if (az == z3)
                    {
                        //Console.WriteLine(x + "   " + y + "   " + z);
                        //_sb.Append(x).Append(" ").Append(y).Append(" ").Append(z).Append(Environment.NewLine);
 
                        Test test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                        listTest.Add(test);
                    }
                }
            }
        }
    }
}
Смущает в коде постоянное метание по всему массиву, возможно из-за плохой локальности данных происходят промахи в кэш и приходится часто лезть в основную память, на что косвенно указывает вот этот момент:
Цитата Сообщение от EveKS Посмотреть сообщение
Но и тут нелепость, время выполнения становится дольше , т.е.: long x = start;
выполняется дольше чем:
C#
1
2
3
4
long ax = a[start];
// --//--
double x = Math.Round(Math.Pow(ax, 1d / 3d));
x++;
Но надо, конечно, прогнать алгоритм через профайлер, чтобы быть точно уверенным.
2
589 / 474 / 184
Регистрация: 19.04.2016
Сообщений: 1,872
27.03.2017, 15:45 10
kolorotur, интересно
Вот что выдает у меня на 4 и 8:
Код
1 3,9415387
2 3,8029825
3 3,8341182
4 3,8432329
5 3,8694087
6 3,835299
7 3,8366115
8 3,8796129
9 3,8616481
10 3,8809787

1 2,2449393
2 2,4353302
3 2,3207624
4 2,2331703
5 2,1698065
6 2,1182683
7 2,1475558
8 2,1078534
9 2,1545005
10 2,2029385
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
28.03.2017, 11:43  [ТС] 11
уже лучше Кто сможеть протестить на win10 - создать проект-пустое приложение (универсальное приложение Windows)(UWP) - Relesex64 ? на работе win7 стоит. думаю на 30% прирост должен быть от текущего.

Добавлено через 3 часа 17 минут
На рабочем ПК (4 потока)
1 2,8962823
2 2,6269334
3 2,4891711
4 2,5352926
5 2,506776
6 2,6244866
7 2,4657208
8 2,6768925
9 2,6411654
10 2,7957069
8 потоков
1 2,303569
2 2,0143803
3 1,979296
4 1,9627874
5 1,9977648
6 2,0108957
7 1,948315
8 1,9988185
9 1,9334973
10 2,0892887

Добавлено через 16 часов 3 минуты
Прогнал дома код через .Net Native, ожидаемого прироста не получил. Разница небольшая от .Net Core
0
22 / 20 / 3
Регистрация: 12.10.2016
Сообщений: 62
28.03.2017, 13:11 12
Я думаю Вам стоит обратить внимание на выступления Андрея Акиньшина. Много хорошего подчерпнёте на тему перфоманса и, кстати, правильном способе его измерять. Потому что Ваш способ, конечно, не самый корректный
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
29.03.2017, 14:34  [ТС] 13
За инфо Спасибо, глянем.

Добавлено через 22 часа 27 минут
Развернул данное решение на .NET Core (.exe). Методика.
Итого стандартный вариант на netcoreapp1.1, win7-x64 - 50 метров.
Сокращенный вариант на netstandard1.6, win7-x64 - 30 метров.
Плата за автономность (и некоторый прирост скорости по отношению к .NET Framework).

Добавлено через 2 часа 22 минуты
Выходит следующее(Тип ЦП (рабочий) QuadCore Intel Core i7-3770, 3700 MHz (37 x 100) - 8 лог.ядер):
С#.NET Core - 2.0 сек. (скорость+, переносимость-)
С#.NET Framework - 5,6 сек. (скорость-, переносимость+)
0
5683 / 891 / 298
Регистрация: 25.02.2011
Сообщений: 1,264
Записей в блоге: 1
29.03.2017, 15:42 14
Как измениться производительность, если вместо long z = 1; записать long z = x;?
Не нужно проверять весь массив с первого элемента, достаточно начинать с позиции x

Добавлено через 4 минуты
или
Visual Basic
1
z = Int(x * 1.2599)
1
4653 / 3205 / 1365
Регистрация: 09.05.2015
Сообщений: 7,878
29.03.2017, 16:20 15
Цитата Сообщение от bedvit Посмотреть сообщение
переносимость-
Это почему минус? .NET Core наоборот работает на гораздо большем количестве систем... И сборка .NET Core легко подключается к проектам на .NET Framework.
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
29.03.2017, 18:43  [ТС] 16
m-ch, сейчас проверим, Someone007, согласен с тем, что не везде есть Framework, но под win проблем нет (а вот .NET Core есть точно не на всей win), поэтом что бы поделится своим решение на С#.NET Core нужно переслать - 50 МБайт(.exe+библиотеки), что бы С#.NET Framework - 50 КБайт(.exe)
Если не под Win, ситуация конечно меняется.
Поправьте, если что-то упускаю.
Цитата Сообщение от Someone007 Посмотреть сообщение
И сборка .NET Core легко подключается к проектам на .NET Framework.
сможете поделится информацией?

Тестовый код:
Кликните здесь для просмотра всего текста
C#
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
 
namespace NET_Core_netcoreapp
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static TaskCompletionSource<object> source = new TaskCompletionSource<object>();
        static TaskScheduler scheduler = new CustomTaskScheduler();
 
        static long n;
        static long an;
        static long lim;
        static long[] a;
        static int threadsN = Environment.ProcessorCount; //задать количество потоков
        static List<Test> listTest = new List<Test>(100);
 
        static void Main(string[] args)
        {
                Console.WriteLine("Enter the maximum limit for variables, followed by <Enter>:\n");
                n = Convert.ToInt64(Console.ReadLine());
            
            for (int j = 0; j < 10; j++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                an = n * n * n;
                a = new long[n + 1];
                lim = (long)Math.Round(Math.Pow((an - 1) / 2, 1d / 3d));
 
                for (long i = 1; i <= n; i++)
                    a[i] = i * i * i;
 
                var task = new Task[threadsN];
                for (int i = 2; i - 2 < threadsN; i++)
                {
                    int k = i;
                    task[k - 2] = Func(k);
                }
 
                Task.WaitAll(task);
                sw.Stop();
                Console.WriteLine((j + 1) + " " + sw.Elapsed.TotalSeconds);
            }
            Console.Write("\nPress any key to continue... ");
            Console.ReadKey();
        }
 
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            long m = n;
            unsafe
            {
                fixed (long* a = Program.a)
                {
                    for (long x = start; x <= lim; x = x + threadsN)
                    {
                        long ax = a[x];
                        long r = an - ax - 1;
                        while (a[m] > r) m--;
                        long z = (long)(x * 1.2599);
 
                        for (long y = x; y <= m; y++)
                        {
                            long z3 = ax + a[y] + 1;
 
                            for (long az = a[z]; az <= z3; z++, az = a[z])
                            {
                                if (az == z3)
                                {
                                    //Console.WriteLine(x + "   " + y + "   " + z);
                                    Test test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                                    listTest.Add(test);
                                }
                            }
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
    }
 
    class Test
    {
        public double Prop1 { get; set; }
        public long Prop2 { get; set; }
        public long Prop3 { get; set; }
    }
 
    public struct CustomTaskAwaitable
    {
        CustomTaskAwaiter awaitable;
 
        public CustomTaskAwaitable(Task task, TaskScheduler scheduler)
        {
            awaitable = new CustomTaskAwaiter(task, scheduler);
        }
 
        public CustomTaskAwaiter GetAwaiter() { return awaitable; }
 
        public struct CustomTaskAwaiter : INotifyCompletion
        {
            Task task;
            TaskScheduler scheduler;
 
            public CustomTaskAwaiter(Task task, TaskScheduler scheduler)
            {
                this.task = task;
                this.scheduler = scheduler;
            }
 
            public void OnCompleted(Action continuation)
            {
                task.ContinueWith(x => continuation(), scheduler);
            }
 
            public bool IsCompleted { get { return task.IsCompleted; } }
            public void GetResult() { }
        }
    }
 
    public static class TaskExtension
    {
        public static CustomTaskAwaitable ConfigureScheduler(this Task task, TaskScheduler scheduler)
        {
            return new CustomTaskAwaitable(task, scheduler);
        }
    }
 
    public class CustomTaskScheduler : TaskScheduler
    {
        protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) { return false; }
        protected override void QueueTask(Task task)
        {
            TryExecuteTask(task);
        }
    }
}


Добавлено через 5 минут
z = (long)(x * 1.2599) выигрывает:
Кликните здесь для просмотра всего текста
z=1 
100000 
12,1110943
21,9450654
31,9511239
42,0257331
51,9344945
61,9745772
71,9662312
82,0138797
91,9941009
101,954841
z=x 
100000 
11,7556538
21,6321776
31,6598229
41,6571433
51,6293431
61,6631514
71,6663989
81,681839
91,6532973
101,6936577
z = (long)(x * 1.2599) 
100000 
11,5326302
21,3855489
31,3822823
41,3915494
51,3806963
61,4359642
71,3672701
81,4751226
91,3672852
101,4179782


Добавлено через 30 минут
С#.NET Framework догоняет С#.NET Core, разница всего в 5%
Была поднята мин. граница массива в переборе, видимо С#.NET Core быстрее обрабатывает большие массивы.
Кликните здесь для просмотра всего текста
100000.NET Core.NET Framework%
11,54437771,5849673103%
21,46439631,5704608107%
31,43504361,5595892109%
41,49021281,5637244105%
51,52234021,473899897%
61,51596951,565652103%
71,52009861,506414399%
81,49759371,5807666106%
91,42715211,5844598111%
101,45244651,5524314107%
ср.знач1,48696311,55423656105%
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
31.03.2017, 14:07  [ТС] 17
Подведя промежуточные итоги, последний вариант решения на .NETCoreApp1.1 (благодаря EveKS,kolorotur,m-ch).
Кликните здесь для просмотра всего текста
C#
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
using System.Linq;
 
namespace NET_Core_netcoreapp11
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static TaskCompletionSource<object> source = new TaskCompletionSource<object>();
        static TaskScheduler scheduler = new CustomTaskScheduler();
 
        static long n;
        static long an;
        static long lim;
        static long[] a;
        static int threadsN = Environment.ProcessorCount; //задать количество потоков
        static List<Test> listTest = new List<Test>(100);
 
        static void Main(string[] args)
        {
            Console.WriteLine("Enter the maximum limit for variables, followed by <Enter>:\n");
            n = Convert.ToInt64(Console.ReadLine());
 
                Stopwatch sw = Stopwatch.StartNew();
                an = n * n * n;
                a = new long[n + 1];
                lim = (long)Math.Round(Math.Pow((an - 1) / 2, 1d / 3d));
 
                for (long i = 1; i <= n; i++)
                    a[i] = i * i * i;
 
                var task = new Task[threadsN];
                for (int i = 2; i - 2 < threadsN; i++)
                {
                    int k = i;
                    task[k - 2] = Func(k);
                }
                Task.WaitAll(task);
                sw.Stop();
                Console.WriteLine(string.Join("\n", listTest.OrderBy(l => l.Prop3).Select((l, n) => $"{n + 1} {(long)l.Prop1} {l.Prop2} {l.Prop3}")));
                Console.WriteLine("Time " + sw.Elapsed);
            Console.Write("\nPress any key to continue... ");
            Console.ReadKey();
        }
 
        static async Task Func(long start)
        => await Task.Run(() =>
        {
            long m = n;
            unsafe
            {
                fixed (long* a = Program.a)
                {
                    for (long x = start; x <= lim; x = x + threadsN)
                    {
                        long ax = a[x];
                        long r = an - ax - 1;
                        while (a[m] > r) m--;
                        long z = (long)(x * 1.2599);
 
                        for (long y = x; y <= m; y++)
                        {
                            long z3 = ax + a[y] + 1;
 
                            for (long az = a[z]; az <= z3; z++, az = a[z])
                            {
                                if (az == z3)
                                {
                                    Test test = new Test { Prop1 = x, Prop2 = y, Prop3 = z };
                                    listTest.Add(test);
                                }
                            }
                        }
                    }
                }
            }
        }).ConfigureScheduler(scheduler);
    }
 
    class Test
    {
        public double Prop1 { get; set; }
        public long Prop2 { get; set; }
        public long Prop3 { get; set; }
    }
 
    public struct CustomTaskAwaitable
    {
        CustomTaskAwaiter awaitable;
 
        public CustomTaskAwaitable(Task task, TaskScheduler scheduler)
        {
            awaitable = new CustomTaskAwaiter(task, scheduler);
        }
 
        public CustomTaskAwaiter GetAwaiter() { return awaitable; }
 
        public struct CustomTaskAwaiter : INotifyCompletion
        {
            Task task;
            TaskScheduler scheduler;
 
            public CustomTaskAwaiter(Task task, TaskScheduler scheduler)
            {
                this.task = task;
                this.scheduler = scheduler;
            }
 
            public void OnCompleted(Action continuation)
            {
                task.ContinueWith(x => continuation(), scheduler);
            }
 
            public bool IsCompleted { get { return task.IsCompleted; } }
            public void GetResult() { }
        }
    }
 
    public static class TaskExtension
    {
        public static CustomTaskAwaitable ConfigureScheduler(this Task task, TaskScheduler scheduler)
        {
            return new CustomTaskAwaitable(task, scheduler);
        }
    }
 
    public class CustomTaskScheduler : TaskScheduler
    {
        protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
        protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) { return false; }
        protected override void QueueTask(Task task)
        {
            TryExecuteTask(task);
        }
    }
}

Решение на NET Framework 4.0 (макс. охват на win), здесь немного доработал свой код из стартового сообщения.
Незначительно проигрывает
Кликните здесь для просмотра всего текста
C#
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
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
 
namespace NET_Framework4
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static long n;
        static long an;
        static long lim;
        static long k = 0;
        static long[] a;
        static int threadsN = Environment.ProcessorCount; //задать количество потоков
 
        static void Main(string[] args)
        {
            Console.WriteLine("Enter the maximum limit for variables, followed by <Enter>:\n");
            n = Convert.ToInt64(Console.ReadLine());
            Stopwatch sw = Stopwatch.StartNew();
            an = n * n * n;
            a = new long[n + 1];
            lim = (long)(Math.Pow((an - 1) / 2, 1d / 3d));
 
                for (long i = 1; i <= n; i++)
                    a[i] = i * i * i;
 
            var task = new List<Task>();
                for (int i = 1; i <= threadsN; i++)
                {
                    int k = i;
                    task.Add(new Task(() => Func(k)));
                }
            task.ForEach(t => t.Start());//стартуем task
            task.ForEach(t => t.Wait()); //ждем выполнения всех task
            sw.Stop();
            Console.WriteLine("Time {0}", sw.Elapsed);
            Console.Write("\nPress any key to continue... ");
            Console.ReadKey();
        }
 
        static void Func(long start)
        {
            long m = n;
            unsafe
            {
                fixed (long* a = Program.a)
                {
                    for (long x = start; x <= lim; x = x + threadsN)
                    {
                        long ax = a[x];
                        long r = an - ax - 1;
                        while (a[m] > r) m--;
                        long z = (long)(x * 1.2599);
 
                        for (long y = x; y <= m; y++)
                        {
                            long z3 = ax + a[y] + 1;
 
                            for (long az = a[z]; az <= z3; z++, az = a[z])
                            {
                                if (az == z3) Console.WriteLine(k++ + "   " + x + "   " + y + "   " + z);
                            }
                        }
                    }
                }
            }
        }
    }
}
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
31.03.2017, 14:13  [ТС] 18
Зато компилируется в один .exe 7 Кб и работает почти на всех win.
0
Вложения
Тип файла: rar XYZ_NET_Framework4.rar (3.2 Кб, 5 просмотров)
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
07.04.2017, 12:48  [ТС] 19
На С++, данный алгоритм, работает несколько быстрее. Примерно на 6-8%.
0
654 / 213 / 21
Регистрация: 20.05.2016
Сообщений: 921
Записей в блоге: 15
07.04.2017, 16:04  [ТС] 20
Причем на более слабом ПК, разрыв увеличился до 20%. Видимо, CLR использует лучше более быстрые(?) ЦП (возможно оптимальнее использует инструкции(?) чем С++ скомпилированный под все х64)
0
Вложения
Тип файла: rar C++(x^3+y^3=z^3-1).rar (198.4 Кб, 2 просмотров)
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.04.2017, 16:04

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

Библиотека NETSquirrel для .NET и .NET Core - формат вывода индексаторов
Предположим, что мы выводим через AutoPrintLine все поля, свойства и индексаторы экземпляра...

Можно ли использовать сборку из .NET Core в обычном ASP .NET проекте ?
Microsoft.Extensions.Logging очень удобная штука, в обычном .NET её никак нельзя задействовать ?...

Можно ли использовать библиотеки написанные на .net Core для .net FW
Можно ли подключить библиотеку написанную на .net Core к WinForm приложению написанному на .net FW?...

Как подключить к ConsoleApp(.Net Core) библиотеку (.Net Standart)
Привет товарищи!) Решил чутка по изучать нововведения(ну лично для меня ConsoleApp(.Net Core) и...

Библиотека NETSquirrel для .NET и .NET Core - решение задач
Тема для решения задач с применением NETSquirrel. Просьба вопросы и замечания писать здесь.

ASP.NET .NET Core Web Api -- почему параметры всегда null?
Что я делаю не так? using Microsoft.AspNetCore.Mvc; namespace WebApiServer.Controllers { ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.