C# цикл FOR (вопрос по тестовому заданию)?

Question

[Nikkuz39]

Из тестового задания:

Укажите проблемные места этого кода и/или как их исправить:
Используется язык C#

List<string> GetNames() 
{
   List<string> ss = new List<string>();
   for (int i = 0; i < 10000000; i++) {
       ss.Insert(0, GetName(i)); // GetName - это просто какая-то функция, которая возвращает нам строку
   }
   return ss;
}

В чём подвох?

Comments

[rundll32]

Используется Insert, причем, всегда по индексу 0, вместо Add. А список это не массив, вставка по индексу, тем более такая, тут не нужна.

Answer 1

[oleg_ods]

Если предположить что цель метода вернуть List с именами в обратном порядке, то можно развернуть цикл и метод Insert заменить на Add.

List<string> GetNames() 
{
   List<string> ss = new List<string>();
   for (int i = 10000000; i >= 0; i--) {
       ss.Add(GetName(i)); // GetName - это просто какая-то функция, которая возвращает нам строку
   }
   return ss;
}

List под капотом содержит массив.
Принцип работы метода Insert:
1) Проверить достаточно ли места во внутреннем массиве. См. свойство Capacity.
2) Если недостаточно, то расширить массив в 2 раза.
3) Сместить все последующие элементы на одну позицию вперед.
4) Добавить в нужный индекс значение.

Принцип работы метода Add:
1) Проверить достаточно ли места во внутреннем массиве. См. свойство Capacity.
2) Если недостаточно, то расширить массив в 2 раза.
3) Вставить значение в конец массива.

Соответственно при использовании метода Insert, в Вашем случае, будет очень много операций копирования значений.

Второе, если на момент создания List в методе известно кол-во элементов которые он должен содержать, то можно использовать конструктор List(int capacity), который изначально создаст List нужного размера. Так Вы избавитесь от необходимости динамически расширять List при переполнении внутреннего массива.

P.S. Для общего образования можете погонять альтернативные реализации методов через библиотеку DotNetBenchmark и сравнить на сколько вырастет производительность в каждом случае.

Comments

[Василий Банников]

Ещё можно заранее выделить место в листе, передав ему в конструктор 10000000.
Правда тогда подкапотный массив мигом улетит в LOH

[4ainik]

Василий Банников, лучше быстрый и ужасный конец, чем ужас без конца

[oleg_ods]

Василий Банников, Разве?

10_000_000 * 64 = 64000000(бит) / 8 = 8000000(байт) / 1024 = 78125(кБ)

Или я неправильно считаю?

Пересмотрел что такое LOH ограничение действительно 85_000 байт, раньше думал что это объекты более 2 Гб.

Век живи — век учись.

Но какое задание — такое и решение)))

[Nikkuz39]

Спасибо за ответы.

Лучше изменить код на:

List<string> GetNames()
            {
                List<string> ss = new List<string>();
                ss.Capacity = 16777216;

                for (int i = 0; i < 10000000; i++)
                {
                    ss.Add(GetName(i));
                }
                return ss;
            }

[Василий Банников]

oleg_ods, вроде правильно.
Если я не затупил, то массив должен около 80 мегабайт получиться.
Вроде это уже считается большим объектом

[Василий Банников]

Nikkuz39, почему именно 16777216?
И почему через свойство Capacity, а не через конструктор?

[oleg_ods]

Василий Банников, Да, правильно. Около 80 Mb.

Просто я до сегодняшнего дня считал что LOH это более 2 Gb, а оказалось

If an object is greater than or equal to 85,000 bytes in size, it's considered a large object.

The large object heap on Windows systems

[Nikkuz39]

Василий Банников, через Console.WriteLine() можно получить размер Capacity, а через конструктор указывается количество объектов.

[Василий Банников]

Nikkuz39, вопрос же про

List<string> ss = new List<string>();
ss.Capacity = 16777216;

Почему именно такое число, и почему не
var list = new List<string>(10_000_000);

[Nikkuz39]

Василий Банников, Ошибся, правильно будет:

List<string> ss = new List<string>(10000000);