Код оптимизация и улучшения

Question

проанализируй код и дай свой вердикт. Можно ли его улучшить? Можно ли добавить больше признаков и т.д

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
public class Cutter
{
public int the_best_tail;
private List<int> m_units = new List<int>();

text
    public List<int> m_best_units = new List<int>();
    public List<int> m_best_tails = new List<int>();

    public List<List<int>> m_best_result = new List<List<int>>();
    public List<int> m_best_store = new List<int>();
    public List<int> m_best_store_tail = new List<int>();

    public List<List<int>> a_best_result = new List<List<int>>();
    public List<int> a_best_store = new List<int>();
    public List<int> a_best_store_tail = new List<int>();

    private List<int> m_store = new List<int>();

    public void SetStore(List<int> store) { this.m_store = store; }
    public void SetUnits(List<int> units) { this.m_units = units; }

    public void SwapUnits(int key1, int key2)
    {
        int tmp = this.m_units[key1];
        this.m_units[key1] = this.m_units[key2];
        this.m_units[key2] = tmp;
    }

    public int Review()
    {
        //          Console.Write("\n-------"); foreach(var val in this.m_units) { Console.Write(val + " "); } Console.Write("-------");
        List<int> m_units_used = Enumerable.Repeat(0, this.m_units.Count).ToList();

        int num_units = this.m_units.Count;

        int summ_tails = 0;

        int index_result = 0;
        int last_tail = 0;
        do
        {
            int best_tail = 1000000;
            List<int> best_units_used = new List<int>();
            int best_storekey = 0;

            for (int s_key = 0; s_key < this.m_store.Count; s_key++)
            {
                int tail = this.m_store[s_key];
                List<int> temp_units_used = new List<int>(m_units_used);

                for (int u_key = 0; u_key < this.m_units.Count; u_key++)
                {
                    if (m_units_used[u_key] == 1)
                        continue;

                    if (tail > this.m_units[u_key])
                    {
                        tail -= this.m_units[u_key];
                        temp_units_used[u_key] = 1;
                    }
                }
                if (tail < best_tail)
                {
                    best_tail = tail;
                    best_storekey = s_key;
                    best_units_used = new List<int>(temp_units_used);

                    if (this.m_best_store.Count > index_result)
                        this.m_best_store[index_result] = this.m_store[s_key];
                    else
                        this.m_best_store.Add(this.m_store[s_key]);

                    int add_index = 0;
                    if (this.m_best_result.Count > index_result)
                        this.m_best_result[index_result] = new List<int>();
                    else
                        this.m_best_result.Add(new List<int>());

                    for (int u_key = 0; u_key < this.m_units.Count; u_key++)
                    {
                        if (temp_units_used[u_key] == m_units_used[u_key] || temp_units_used[u_key] != 1)
                            continue;
                        this.m_best_result[index_result].Add(this.m_units[u_key]);
                        add_index++;
                    }
                    if (this.m_best_store_tail.Count > index_result)
                        this.m_best_store_tail[index_result] = best_tail;
                    else
                        this.m_best_store_tail.Add(best_tail);
                }
            }
            //нашли лучший вариант (какую из заготовок брать)
            m_units_used = new List<int>(best_units_used);
            summ_tails += best_tail;
            last_tail = best_tail;

            //          Console.Write("\n----------" + m_units_used.Sum() + "<" + num_units);
            index_result++;
        }
        while (m_units_used.Sum() < num_units);

        return summ_tails - last_tail;
    }

    public void FindTheBest(int limit_iterations)
    {
        this.m_units.Sort();
        this.m_units.Reverse(); // rsort equivalent: descending sort
        int u_len = this.m_units.Count;

        this.the_best_tail = 1000000000;
        Random rnd = new Random();
        for (int iter = 0; iter < limit_iterations; iter++)
        {
            this.m_best_result.Clear();
            this.m_best_store.Clear();
            this.m_best_store_tail.Clear();

            int this_tail = this.Review();

            if (this_tail < this.the_best_tail)
            {
                this.the_best_tail = this_tail;

                this.a_best_result = this.m_best_result.Select(inner => new List<int>(inner)).ToList();
                this.a_best_store = new List<int>(this.m_best_store);
                this.a_best_store_tail = new List<int>(this.m_best_store_tail);
            }

            Shuffle(this.m_units, rnd);
            //this.SwapUnits(rnd.Next(0, u_len), rnd.Next(0, u_len));
        }
    }

    private static void Shuffle<T>(IList<T> list, Random rnd)
    {
        for (int i = list.Count - 1; i > 0; i--)
        {;
            
            int j = rnd.Next(i + 1);
            //int j = list.Count - i;
            T temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }
}

public class Prgram {

List<int> zagot = new List<int> { 6000 };
List<int>detal = new List<int> { 2216, 2216, 2216, 2216, 2216, 2216, 2216, 2216, 2216, 2216 };

Cutter the_cutter = new Cutter(); the_cutter.SetStore(zagot); the_cutter.SetUnits(detal); the_cutter.FindTheBest(1);

for (int i = 0; i < the_cutter.a_best_store.Count(); i++)
{
Console.Write("\n Заготовка:" + the_cutter.a_best_store[i] + " ( "); //
foreach (var unit in the_cutter.a_best_result[i].OrderByDescending(x => x).ToArray())
foreach (var unit in the_cutter.a_best_result[i]) {
Console.Write(unit + " ");
}
Console.Write(") Остаток:" + the_cutter.a_best_store_tail[i]);
}
Console.Write("\nСуммарный остаток (без последнего):" + the_cutter.the_best_tail);
}
}

Answer 1

Анализируя код, можно выделить несколько аспектов, которые можно улучшить:

1. Оптимизация структуры хранения данных

В коде используется большое количество списков (List<int>) для хранения промежуточных и окончательных результатов. Можно попробовать уменьшить их количество, используя структуры (struct) или классы, объединяющие связанные данные.

2. Использование методов LINQ

В Review() есть несколько циклов, которые можно упростить с помощью методов LINQ. Например, вместо:
```
csharp
List<int> m_units_used = Enumerable.Repeat(0, this.m_units.Count).ToList();
```
можно использовать new int[this.m_units.Count].ToList(), что может быть чуть быстрее.

3. Изменение стратегии поиска оптимального решения

В методе FindTheBest() выполняется Shuffle(), чтобы перемешать элементы перед повторной попыткой оптимизации. Однако такой случайный подход можно улучшить с помощью эвристических алгоритмов, таких как:
- Жадные алгоритмы (например, сначала использовать самые длинные детали).
- Генетические алгоритмы или алгоритм имитации отжига.
- Динамическое программирование (если позволяет размер входных данных).

4. Использование многопоточности

В FindTheBest() выполняется многократная проверка Review(), которая по сути является независимым вычислительным процессом. Можно использовать Parallel.For для распараллеливания процесса и ускорения вычислений.

5. Избежание лишних копирований списков

В коде часто создаются новые списки new List<int>(existingList), что может негативно сказаться на производительности. Например, в этом фрагменте:
```
csharp
best_units_used = new List<int>(temp_units_used);
```
вместо создания нового списка можно просто обновлять существующий.

6. Использование `Span<T>` или `ArrayPool<T>` для временных массивов

Если критична скорость работы и выделение памяти, можно использовать Span<int> вместо List<int> для временных переменных или ArrayPool<int>.Shared.Rent() для временных массивов, чтобы избежать лишних аллокаций.

7. Логические ошибки

В Prgram (вероятно, опечатка, должно быть Program) есть двойной цикл foreach, из-за чего элементы дублируются при выводе:
```
csharp
foreach (var unit in the_cutter.a_best_result[i].OrderByDescending(x => x).ToArray()) 
   foreach (var unit in the_cutter.a_best_result[i]) { 
       Console.Write(unit + " "); 
   }
```
Здесь первый цикл можно убрать.

Итог:

Можно улучшить алгоритм: сейчас используется перебор с рандомизацией, но можно применить жадные алгоритмы, динамическое программирование или эвристические методы.
Оптимизировать работу с памятью: уменьшить лишние копии списков, использовать Span<T> или ArrayPool<T>.
Добавить многопоточность в FindTheBest(), если limit_iterations большой.
Упростить код с помощью LINQ, особенно там, где фильтруются или сортируются данные.

Хотите, чтобы я попробовал переписать некоторые ключевые части кода с оптимизациями?

Код оптимизация и улучшения

Frage

Antwort

1. Оптимизация структуры хранения данных

2. Использование методов LINQ

3. Изменение стратегии поиска оптимального решения

4. Использование многопоточности

5. Избежание лишних копирований списков

6. Использование `Span<T>` или `ArrayPool<T>` для временных массивов

7. Логические ошибки

Итог:

Diesen Q&A teilen

Frage

Antwort

1. Оптимизация структуры хранения данных

2. Использование методов LINQ

3. Изменение стратегии поиска оптимального решения

4. Использование многопоточности

5. Избежание лишних копирований списков

6. Использование Span<T> или ArrayPool<T> для временных массивов

7. Логические ошибки

Итог:

Diesen Q&A teilen

6. Использование `Span<T>` или `ArrayPool<T>` для временных массивов