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

@bedvit · Регистрация: 20.05.2016

Author24 — интернет-сервис помощи студентам

Решил поделится своим небольшим опытом по оптимизации вычислений на 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. АССЕМБЛЕР... здесь мои знания заканчиваются...

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

В блоге.

@EveKS · 26.03.2017, 19:02

bedvit, я не батька, поэтому напишу здесь.
В общем, проверил этот же код на своем компьютере, немного изменив, выдает следующие результаты:
На 4 ядра:

Code
1
2
3
4
5
6
7
8
9
10
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 ядер:

Code
1
2
3
4
5
6
7
8
9
10
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
В итоге, вроде как, не чего не изменилось:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 не вышло без исключений.

Code
1
2
3
4
5
6
7
8
9
10
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;
        }
    }

@bedvit · 26.03.2017, 20:47 **[ТС]**

Все возможные значения на текущем алгоритме (с int64). Отсортировано по Z. Итого 84 решения. Диапазон переменных 1:2097151((2^63)^(1/3)-1). См.под спойлер

Кликните здесь для просмотра всего текста

№	x	y	z
1	6	8	9
2	71	138	144
3	135	138	172
4	372	426	505
5	426	486	577
6	242	720	729
7	566	823	904
8	791	812	1010
9	236	1207	1210
10	575	2292	2304
11	1938	2820	3097
12	2676	3230	3753
13	1124	5610	5625
14	2196	5984	6081
15	1943	6702	6756
16	1851	8675	8703
17	1943	11646	11664
18	7676	11903	12884
19	3318	16806	16849
20	10866	17328	18649
21	3086	21588	21609
22	3453	24965	24987
23	17328	27630	29737
24	4607	36840	36864
25	28182	31212	37513
26	10230	37887	38134
27	25765	33857	38239
28	31212	34566	41545
29	7251	49409	49461
30	34199	46212	51762
31	6560	59022	59049
32	15218	66198	66465
33	29196	66167	68010
34	54101	56503	69709
35	32882	69479	71852
36	51293	64165	73627
37	17384	78244	78529
38	8999	89970	90000
39	58462	87383	95356
40	75263	94904	108608
41	84507	89559	109747
42	99800	104383	128692
43	11978	131736	131769
44	81404	130119	139974
45	86103	153422	161976
46	93066	152526	163297
47	15551	186588	186624
48	146996	204290	227033
49	105570	237095	243876
50	19772	257010	257049
51	152526	249972	267625
52	120039	275616	283006
53	57055	339590	340126
54	24695	345702	345744
55	113208	342719	346788
56	289511	331954	393316
57	315750	340623	414082
58	151499	434305	440365
59	293999	403346	449846
60	30374	455580	455625
61	36863	589776	589824
62	257118	664572	677161
63	197144	708282	713337
64	44216	751638	751689
65	309874	746831	764206
66	283896	815498	826809
67	658625	743413	886447
68	375703	902654	923848
69	52487	944730	944784
70	311999	1052540	1061600
71	386559	1076664	1093024
72	61730	1172832	1172889
73	926271	951690	1183258
74	342648	1240119	1248778
75	595815	1224516	1269838
76	294241	1298345	1303363
77	971298	1159352	1352601
78	71999	1439940	1440000
79	942902	1309108	1455241
80	1150782	1388672	1613673
81	1077936	1568978	1722969
82	664572	1717710	1750249
83	83348	1750266	1750329
84	1557846	1724442	2073025

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

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

Добавлено через 3 минуты
EveKS, насколько я понял, вы тоже через Console .Net Core, не через (универсальное приложение Windows)(UWP)?

@EveKS · 27.03.2017, 08:41

Сообщение от bedvit

n = 100000;

Сообщение от bedvit

Итого 84 решения.

Не срастается...

Code
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
╨Ч╨░╨┤╨░╨╣╤В╨╡ ╨┤╨╕╨░╨┐╨░╨╖╨╛╨╜ ╤А╨░╤Б╤З╨╡╤В╨░ ╨┐╨╡╤А╨╡╨╝╨╡╨╜╨╜╤Л╤Е, ╨┤╨╛..., ╨╜╨░╨╢╨╝╨╕╤В╨╡ 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 ядрах:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 до нужного числа, не есть хороше. Возможно, стоит посмотреть в сторону деревьев или поискать другое решение.

Не по теме:

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

@bedvit · 27.03.2017, 11:59 **[ТС]**

Срастается, потому как диапазон переменных взят больше - до 2097151. Вы и сами наверное уже поняли, судя по последнему коменту

Это максимальное число для этого расчета/алгоритма.
Пока алгоритм сильно улучшить не удалось.

@EveKS · 27.03.2017, 12:59

bedvit, делать было нечего, решил дальше тестить, что да как:
Первые два варианта, вроде как дали маленький плюс, но не большой, выложу результаты на 4 ядра:

4 ядра, 2 варианта

Здесь я изменял только метод

Code
1
2
3
4
5
6
7
8
9
10
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);

Code
1
2
3
4
5
6
7
8
9
10
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 ядрах:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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++;

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

@bedvit · 27.03.2017, 13:41 **[ТС]**

EveKS, на первый взгляд странно. У вас не Win10 случаем? Хочу понять почему вариант/ШАГ7 не хочет работать на больших диапазонах переменных. Дело в компиляции или я чего-то не знаю/не учитываю. Пока у меня этот самый быстрый вариант за счет компиляции в машинный код (диапазон переменных до 500-600 тыс. далее вылетает ошибка). И да, спасибо за тесты!

@EveKS · 27.03.2017, 14:00

Сообщение от bedvit

Win10

Да 10.

Сообщение от bedvit

пасибо за тесты!

Пожалуйста

@kolorotur · 27.03.2017, 14:40

В алгоритм не вникал, но можно малость производительности выжать, если убрать проверку индексов массива:

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++;

Но надо, конечно, прогнать алгоритм через профайлер, чтобы быть точно уверенным.

@EveKS · 27.03.2017, 15:45

kolorotur, интересно

Вот что выдает у меня на 4 и 8:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

@bedvit · 28.03.2017, 11:43 **[ТС]**

уже лучше

Кто сможеть протестить на 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

@gvt · 28.03.2017, 13:11

Я думаю Вам стоит обратить внимание на выступления Андрея Акиньшина. Много хорошего подчерпнёте на тему перфоманса и, кстати, правильном способе его измерять. Потому что Ваш способ, конечно, не самый корректный

@bedvit · 29.03.2017, 14:34 **[ТС]**

За инфо Спасибо, глянем.

Добавлено через 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 сек. (скорость-, переносимость+)

@m-ch · 29.03.2017, 15:42

Как измениться производительность, если вместо long z = 1; записать long z = x;?
Не нужно проверять весь массив с первого элемента, достаточно начинать с позиции x

Добавлено через 4 минуты
или

Visual Basic
1
z = Int(x * 1.2599)

Someone007 · 29.03.2017, 16:20

Сообщение от bedvit

переносимость-

Это почему минус? .NET Core наоборот работает на гораздо большем количестве систем... И сборка .NET Core легко подключается к проектам на .NET Framework.

@bedvit · 29.03.2017, 18:43 **[ТС]**

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
1	2,1110943
2	1,9450654
3	1,9511239
4	2,0257331
5	1,9344945
6	1,9745772
7	1,9662312
8	2,0138797
9	1,9941009
10	1,954841

z=x
100000
1	1,7556538
2	1,6321776
3	1,6598229
4	1,6571433
5	1,6293431
6	1,6631514
7	1,6663989
8	1,681839
9	1,6532973
10	1,6936577

z = (long)(x * 1.2599)
100000
1	1,5326302
2	1,3855489
3	1,3822823
4	1,3915494
5	1,3806963
6	1,4359642
7	1,3672701
8	1,4751226
9	1,3672852
10	1,4179782

Добавлено через 30 минут
С#.NET Framework догоняет С#.NET Core, разница всего в 5%
Была поднята мин. граница массива в переборе, видимо С#.NET Core быстрее обрабатывает большие массивы.

Кликните здесь для просмотра всего текста

100000	.NET Core	.NET Framework	%
1	1,5443777	1,5849673	103%
2	1,4643963	1,5704608	107%
3	1,4350436	1,5595892	109%
4	1,4902128	1,5637244	105%
5	1,5223402	1,4738998	97%
6	1,5159695	1,565652	103%
7	1,5200986	1,5064143	99%
8	1,4975937	1,5807666	106%
9	1,4271521	1,5844598	111%
10	1,4524465	1,5524314	107%
ср.знач	1,4869631	1,55423656	105%

@bedvit · 31.03.2017, 14:07 **[ТС]**

Подведя промежуточные итоги, последний вариант решения на .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);
                            }
                        }
                    }
                }
            }
        }
    }
}

@bedvit · 31.03.2017, 14:13 **[ТС]**

Зато компилируется в один .exe 7 Кб и работает почти на всех win.

@bedvit · 07.04.2017, 12:48 **[ТС]**

На С++, данный алгоритм, работает несколько быстрее. Примерно на 6-8%.

@bedvit · 07.04.2017, 16:04 **[ТС]**

Причем на более слабом ПК, разрыв увеличился до 20%. Видимо, CLR использует лучше более быстрые(?) ЦП (возможно оптимальнее использует инструкции(?) чем С++ скомпилированный под все х64)

Новые блоги и статьи Все статьи Все блоги /
Реализация многопоточных сетевых серверов на Python py-thonny 16.05.2025 Когда сталкиваешься с необходимостью писать высоконагруженные сетевые сервисы, выбор технологии имеет критическое значение. Python, со своей элегантностью и высоким уровнем абстракции, может. . .	C# и IoT: разработка Edge приложений с .NET и Azure IoT UnmanagedCoder 16.05.2025 Мир меняется прямо на наших глазах, и интернет вещей (IoT) — один из главных катализаторов этих перемен. Если всего десять лет назад концепция "умных" устройств вызывала скептические улыбки, то. . .	Гибридные квантово-классические вычисления: Примеры оптимизации EggHead 16.05.2025 Гибридные квантово-классические вычисления — это настоящий прорыв в подходах к решению сложнейших вычислительных задач. Представьте себе союз двух разных миров: классические компьютеры, с их. . .	Использование вебсокетов в приложениях Java с Netty Javaican 16.05.2025 HTTP, краеугольный камень интернета, изначально был спроектирован для передачи гипертекста с минимальной интерактивностью. Его главный недостаток в контексте современных приложений — это. . .	Реализация операторов Kubernetes Mr. Docker 16.05.2025 Концепция операторов Kubernetes зародилась в недрах компании CoreOS (позже купленной Red Hat), когда команда инженеров искала способ автоматизировать управление распределёнными базами данных в. . .
Отражение в C# и динамическое управление типами stackOverflow 16.05.2025 Reflection API в . NET — это набор классов и интерфейсов в пространстве имён System. Reflection, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .	Настройка гиперпараметров с помощью Grid Search и Random Search в Python AI_Generated 15.05.2025 В машинном обучении существует фундаментальное разделение между параметрами и гиперпараметрами моделей. Если параметры – это те величины, которые алгоритм "изучает" непосредственно из данных (веса. . .	Сериализация и десериализация данных на Python py-thonny 15.05.2025 Сериализация — это своего рода "замораживание" объектов. Вы берёте живой, динамический объект из памяти и превращаете его в статичную строку или поток байтов. А десериализация выполняет обратный. . .	Чем асинхронная логика (схемотехника) лучше тактируемой, как я думаю, что помимо энергоэффективности - ещё и безопасность. Hrethgir 14.05.2025 Помимо огромного плюса в энергоэффективности, асинхронная логика - тотальный контроль над каждым совершённым тактом, а значит - безусловная безопасность, где безконтрольно не совершится ни одного. . .	Многопоточные приложения на C++ bytestream 14.05.2025 C++ всегда был языком, тесно работающим с железом, и потому особеннно эффективным для многопоточного программирования. Стандарт C++11 произвёл революцию, добавив в язык нативную поддержку потоков,. . .

@bedvit 1204 / 255 / 22 Регистрация: 20.05.2016 Сообщений: 1,125 Записей в блоге: 21
	27.03.2017, 11:59 [ТС]
	Срастается, потому как диапазон переменных взят больше - до 2097151. Вы и сами наверное уже поняли, судя по последнему коменту Это максимальное число для этого расчета/алгоритма. Пока алгоритм сильно улучшить не удалось. 0

@bedvit 1204 / 255 / 22 Регистрация: 20.05.2016 Сообщений: 1,125 Записей в блоге: 21
	27.03.2017, 13:41 [ТС]
	EveKS, на первый взгляд странно. У вас не Win10 случаем? Хочу понять почему вариант/ШАГ7 не хочет работать на больших диапазонах переменных. Дело в компиляции или я чего-то не знаю/не учитываю. Пока у меня этот самый быстрый вариант за счет компиляции в машинный код (диапазон переменных до 500-600 тыс. далее вылетает ошибка). И да, спасибо за тесты! 0

@gvt 22 / 20 / 3 Регистрация: 12.10.2016 Сообщений: 62
	28.03.2017, 13:11
	Я думаю Вам стоит обратить внимание на выступления Андрея Акиньшина. Много хорошего подчерпнёте на тему перфоманса и, кстати, правильном способе его измерять. Потому что Ваш способ, конечно, не самый корректный 0

@bedvit 1204 / 255 / 22 Регистрация: 20.05.2016 Сообщений: 1,125 Записей в блоге: 21
	29.03.2017, 14:34 [ТС]
	За инфо Спасибо, глянем. Добавлено через 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

@bedvit 1204 / 255 / 22 Регистрация: 20.05.2016 Сообщений: 1,125 Записей в блоге: 21
	07.04.2017, 12:48 [ТС]
	На С++, данный алгоритм, работает несколько быстрее. Примерно на 6-8%. 0