Оптимизация генератора комбинаций c#

168
15 февраля 2018, 12:50

Мне нужно получить все возможные сочетания символов из массива определенной длины, немного погуглив (дабы не изобретать велосипед) нашел такой код :

public static void Main(string[] args)
{
    char[] arAlphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9','A','B' }; // используемый алфавит
    int n = 20; // количество мест в комбинации
    char[] arBuffer = new char[n];
    const string fileName = "ResultGenerate.txt";
    // файл при каждом запуске должен создаваться заново
    StreamWriter writer = File.CreateText(fileName);
    writer.Close();
    // Накопитель строк.
    StringBuilder stringBuilder = new StringBuilder((int)Math.Pow(arAlphabet.Length, n) * (n + 2));
    RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, 0, stringBuilder);
    // Записываем полученный результат в файл.
    writer = File.AppendText(fileName);
    writer.Write(stringBuilder.ToString());
    writer.Close();
}
private static void RecursionGenerateCombinationsToFile(char[] arAlphabet, char[] arBuffer, int order,
                                                        StringBuilder stringBuilder)
{
    if (order < arBuffer.Length)
        for (int i = 0; i < arAlphabet.Length; i++)
        {
            arBuffer[order] = arAlphabet[i];
            RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, order + 1, stringBuilder);
        }
    else
    {
        for (int i = 0; i < arBuffer.Length; i++)
            stringBuilder.Append(arBuffer[i]);
        stringBuilder.AppendLine();
    }
}

Работает, вроде бы, хорошо, но нужно оптимизировать, что бы не потреблял столько памяти (жрет более 4гб оперативы), но при этом был максимально быстрым ?

можно вместо промежуточного stringBuilder записывать сразу в файл, тогда память почти не жрет, но очень медленно работает. Мб у вас будут еще какие идеи решения данной проблемы ?

С использованием временного stringBuilder

public static void Main(string[] args)
        {
            char[] arAlphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };     // используемый алфавит
            int n = 20;      // количество мест в комбинации
            char[] arBuffer = new char[n];
            string fileName = "ResultGenerate.txt";
            StreamWriter writer = File.CreateText(fileName);    // файл при каждом запуске должен создаваться заново
            writer.Close();
            StringBuilder stringBuilder = new StringBuilder((int)Math.Pow(arAlphabet.Length, n) * (n + 2));
            RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, 0, fileName, stringBuilder);
        }
        // Рекурсивный медод
        static int count = 0;
        static int allcount = 0;
        static void RecursionGenerateCombinationsToFile(char[] arAlphabet, char[] arBuffer, int order, string fileName, StringBuilder stringBuilder)
        {
            if (order < arBuffer.Length)
                for (int i = 0; i < arAlphabet.Length; i++)
                {
                    arBuffer[order] = arAlphabet[i];
                    RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, order + 1, fileName, stringBuilder);
                }
            else
            {
                for (int i = 0; i < arBuffer.Length; i++)
                    stringBuilder.Append(arBuffer[i]);
                        stringBuilder.AppendLine();
                count++;
                if (count > 500000)
                {
                    StreamWriter writer = File.AppendText($"ResultGenerate{allcount}.txt" );
                    writer.Write(stringBuilder.ToString());
                    writer.Close();
                    count = 0;
                    stringBuilder.Clear();
                    allcount++;
                }
            }
        }
Answer 1

Переписал немного ваш пример. Заменил StringBuilder на StreamWriter, сделал запись с буфером. Запись ведется в 1 файл (для записи в несколько файлом можете легко сами переделать код). Памяти это будет есть примерно 10 мегабайт - размер буфера.

void Main()
{
    char[] arAlphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };     // используемый алфавит
    int n = 20;      // количество мест в комбинации
    char[] arBuffer = new char[n];  
    string fileName = @"ResultGenerate.txt";
    if (File.Exists(fileName)) File.Delete(fileName);
    // Будем писать в файл с буфером в 10 мегабайт. При этом никакой string builder не нужен
    // Каждые 10 мегабайт буфер будет сливаться в файл. Если будет медлено работать, увеличте размер буфера. 
    using (var sw = new StreamWriter(new BufferedStream(File.OpenWrite(fileName), 10 * 1024 * 1024)))
    {       
        RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, 0, fileName, sw);
    }
}
static void RecursionGenerateCombinationsToFile(char[] arAlphabet, char[] arBuffer, int order, string fileName, StreamWriter writer)
{
    if (order < arBuffer.Length)
        for (int i = 0; i < arAlphabet.Length; i++)
        {
            arBuffer[order] = arAlphabet[i];
            RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, order + 1, fileName, writer);
        }
    else
    {
        writer.Write(arBuffer);
        writer.Write(Environment.NewLine);      
    }
}

UPD Чтобы писать в несколько файлов.

Добавим нехитрый класс

public class MuliWriter : IDisposable
{
    private StreamWriter _writer;
    public StreamWriter CurrentWriter
    {
        get { return _writer; }
    }
    public void SwitchOutput(string fileName)
    {
        _writer?.Dispose();             
        _writer =  new StreamWriter(new BufferedStream(File.OpenWrite(fileName), 10 * 1024 * 1024));
    }
    public void Dispose()
    {       
        _writer?.Dispose();     
    }
}

Перепишем чуть чуть код

void Main()
{
    char[] arAlphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };     // используемый алфавит
    int n = 20;      // количество мест в комбинации
    char[] arBuffer = new char[n];  
    string fileName = @"ResultGenerate.txt";
    if (File.Exists(fileName)) File.Delete(fileName);
    // Будем писать в файл с буфером в 10 мегабайт. При этом никакой string builder не нужен
    // Каждые 10 мегабайт буфер будет сливаться в файл. Если будет медлено работать, увеличте размер буфера. 
    using (var sw = new MuliWriter())
    {       
        sw.SwitchOutput(fileName);
        RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, 0, fileName, sw);
    }
}
private static int count = 0;
private static int files = 0;
static void RecursionGenerateCombinationsToFile(char[] arAlphabet, char[] arBuffer, int order, string fileName, MuliWriter writer)
{
    if (order < arBuffer.Length)
        for (int i = 0; i < arAlphabet.Length; i++)
        {
            arBuffer[order] = arAlphabet[i];
            RecursionGenerateCombinationsToFile(arAlphabet, arBuffer, order + 1, fileName, writer);
        }
    else
    {
        writer.CurrentWriter.Write(arBuffer);
        writer.CurrentWriter.Write(Environment.NewLine);
        count++;
        if (count > 10000000)
        {
            writer.SwitchOutput($"ResultGenerate{++files}.txt");
            count = 0;
        }
    }
}
READ ALSO
C# Scaling нарисованного сверху PictureBox

C# Scaling нарисованного сверху PictureBox

Здравствуйте, рисую квадратные зоны на PictureBox который масштабируется вот так:

277
Аудио плеер на C# .NET

Аудио плеер на C# .NET

Хочу сделать плеер на C#Сугубо для аудио

183
Как хранить в БД многомерный массив?

Как хранить в БД многомерный массив?

Правильный ли подход для хранения такой конструкции в базе данных?

267
Умножить каждый элемент массива через LINQ

Умножить каждый элемент массива через LINQ

Есть массив, нужно каждый элемент умножить, что бы каждый элемент массива получил свое новое значение

264