Способы улучшить распределение памяти строк - PullRequest
Новая
       14

Способы улучшить распределение памяти строк

2 голосов
/ 03 октября 2019

Этот вопрос скорее теоретический, чем практический, но все же.

Я искал шанс улучшить следующий код с точки зрения выделения строковой памяти: 

/* Output for n = 3:
*
*  '  #'
*  ' ##'
*  '###'
*
*/
public static string[] staircase(int n) {
    string[] result = new string[n];

    for(var i = 0; i < result.Length; i++) {
        var spaces = string.Empty.PadLeft(n - i - 1, ' ');
        var sharpes = string.Empty.PadRight(i + 1, '#');

        result[i] = spaces + sharpes;
    }

    return result;
}

PadHelper - это метод, который в конечном итоге вызывается скрытно дважды за итерацию.

Итак, исправьте меня, если я ошибаюсь, но кажется, что память выделяется как минимум 3 раза за итерацию.

Любые улучшения кода будут высоко оценены.

Ответы [ 4 ]

4 голосов
/ 03 октября 2019

как насчет: 

result[i] = new string('#',i).PadLeft(n)

?

Обратите внимание, что это все еще выделяет две строки внутри, но я, честно говоря, не вижу в этом проблемы. Об этом позаботится сборщик мусора.

2 голосов
/ 03 октября 2019

Вы можете сэкономить как на распределении, так и на скорости, начав со строки, содержащей все пробелы и все Шарпы, которые вам когда-либо понадобятся, а затем взяв из этого подстроки, следующим образом: 

public string[] Staircase2()
{
    string allChars = new string(' ', n - 1) + new string('#', n); // n-1 spaces + n sharpes

    string[] result = new string[n];
    for (var i = 0; i < result.Length; i++)
        result[i] = allChars.Substring(i, n);

    return result;
}

Я использовал BenchmarkDotNet для сравнения Staircase1 (ваш исходный подход) с Staircase2 (мой подход выше) от n=2 до n=8, см. Результаты ниже.

Он показывает, что Staircase2 всегда быстрее (см. Столбец Mean), и выделяет меньше байтов, начиная с n=3. 

|     Method | n |        Mean |      Error |     StdDev | Allocated |
|----------- |-- |------------:|-----------:|-----------:|----------:|

| Staircase1 | 2 |   229.36 ns |  4.3320 ns |  4.0522 ns |      92 B |
| Staircase2 | 2 |    92.00 ns |  0.7200 ns |  0.6735 ns |     116 B |

| Staircase1 | 3 |   375.06 ns |  3.3043 ns |  3.0908 ns |     156 B |
| Staircase2 | 3 |   114.12 ns |  2.8933 ns |  3.2159 ns |     148 B |

| Staircase1 | 4 |   507.32 ns |  3.8995 ns |  3.2562 ns |     236 B |
| Staircase2 | 4 |   142.78 ns |  1.4575 ns |  1.3634 ns |     196 B |

| Staircase1 | 5 |   650.03 ns | 15.1515 ns | 25.7284 ns |     312 B |
| Staircase2 | 5 |   169.25 ns |  1.9076 ns |  1.6911 ns |     232 B |

| Staircase1 | 6 |   785.75 ns | 16.9353 ns | 15.8413 ns |     412 B |
| Staircase2 | 6 |   195.91 ns |  2.9852 ns |  2.4928 ns |     292 B |

| Staircase1 | 7 |   919.15 ns | 11.4145 ns | 10.6771 ns |     500 B |
| Staircase2 | 7 |   237.55 ns |  4.6380 ns |  4.9627 ns |     332 B |

| Staircase1 | 8 | 1,075.66 ns | 26.7013 ns | 40.7756 ns |     620 B |
| Staircase2 | 8 |   255.50 ns |  2.6894 ns |  2.3841 ns |     404 B |

Это не означает, что Staircase2 является наилучшим из возможных, но, безусловно, есть способ, который лучше, чем оригинал.

2 голосов
/ 03 октября 2019

StringBuilder всегда является ответом, когда дело доходит до выделения строк;Я уверен, что вы знаете, что, очевидно, вы хотите что-то еще. Итак, поскольку все ваши строки имеют одинаковую длину, вы можете объявить один массив char[], заполнить его каждый раз (требуется только изменение одного элемента массива на каждой итерации), а затем использовать конструктор string(char[]) : 

public static string[] staircase(int n)
{
    char[] buf = new char[n];
    string[] result = new string[n];

    for (var i = 0; i < n - 1; i++)
    {
        buf[i] = ' ';
    }

    for (var i = 0; i < n; i++)
    {
        buf[n - i - 1] = '#';
        result[i] = new string(buf);
    }

    return result;
}
1 голос
/ 03 октября 2019

Вы можете проецировать желаемые результаты, используя метод Linq Select. Например, что-то вроде этого: 

public static string[] staircase(int n) {
    return Enumerable.Range(1, n).Select(i => new string('#', i).PadLeft(n)).ToArray();
}

Альтернативный подход с использованием массива int: 

public static string[] staircase(int n) {
    return (new int[n]).Select((x,i) => new string('#', i+1).PadLeft(n)).ToArray();
}

HTH

...