IEnumerable из рекурсивного метода в 10 раз медленнее, чем тот же IEnumerable, созданный с помощью foreach - PullRequest
Новая
       12

IEnumerable из рекурсивного метода в 10 раз медленнее, чем тот же IEnumerable, созданный с помощью foreach

0 голосов
/ 08 января 2019

Я не понимаю, почему один IEnumerable.Contains () работает быстрее, чем другой в следующем фрагменте, даже если они идентичны. 

public class Group
{
    public static Dictionary<int, Group> groups = new Dictionary<int, Group>();

    // Members, user and groups
    public List<string> Users = new List<string>();
    public List<int> GroupIds = new List<int>();

    public IEnumerable<string> AggregateUsers()
    {
        IEnumerable<string> aggregatedUsers = Users.AsEnumerable();
        foreach (int id in GroupIds)
            aggregatedUsers = aggregatedUsers.Concat(groups[id].AggregateUsers());
        return aggregatedUsers;
    }
}

static void Main(string[] args)
{
    for (int i = 0; i < 1000; i++)
        Group.groups.TryAdd(i, new Group());

    for (int i = 0; i < 999; i++)
        Group.groups[i + 1].GroupIds.Add(i);

    for (int i = 0; i < 10000; i++)
        Group.groups[i/10].Users.Add($"user{i}");

    IEnumerable<string> users = Group.groups[999].AggregateUsers();

    Stopwatch stopwatch = Stopwatch.StartNew();
    bool contains1 = users.Contains("user0");
    Console.WriteLine($"Search through IEnumerable from recursive function was {contains1} and took {stopwatch.ElapsedMilliseconds} ms");

    users = Enumerable.Empty<string>();
    foreach (Group group in Group.groups.Values.Reverse())
        users = users.Concat(group.Users);

    stopwatch = Stopwatch.StartNew();
    bool contains2 = users.Contains("user0");
    Console.WriteLine($"Search through IEnumerable from foreach was {contains2} and took {stopwatch.ElapsedMilliseconds} ms");

    Console.Read();
}

Вот вывод, полученный при выполнении этого фрагмента: 

Search through IEnumerable from recursive function was True and took 40 ms
Search through IEnumerable from foreach was True and took 3 ms

Фрагмент моделирует 10 000 пользователей, распределенных по 1000 группам по 10 пользователей в каждой.

Каждая группа может иметь 2 типа участников, пользователей (строка) или другие группы (целое число, представляющее идентификатор этой группы).

Каждая группа имеет предыдущую группу в качестве участника. Таким образом, группа 0 имеет 10 пользователей, группа 1 имеет 10 пользователей и пользователей из группы 0, группа 2 имеет 10 пользователей и пользователей группы 1 ... и здесь начинается рекурсия.

Цель поиска состоит в том, чтобы определить, является ли пользователь "user0" (который находится ближе к концу списка) членом группы 999 (которая через групповое отношение содержит все 10000 пользователей).

Вопрос в том, почему поиск занимает всего 3 мс для поиска через IEnumerable, построенный с помощью foreach, и в 10 раз больше для того же IEnumerable, построенного с помощью рекурсивного метода?

Ответы [ 2 ]

0 голосов
/ 09 января 2019

Я понял, как преодолеть проблему, прочитав ответ Миколая и комментарий Серви. Спасибо! 

public class Group
{
    public static Dictionary<int, Group> groups = new Dictionary<int, Group>();

    // Members, user and groups
    public List<string> Users = new List<string>();
    public List<int> GroupIds = new List<int>();

    public IEnumerable<string> AggregateUsers()
    {
        IEnumerable<string> aggregatedUsers = Users.AsEnumerable();
        foreach (int id in GroupIds)
            aggregatedUsers = aggregatedUsers.Concat(groups[id].AggregateUsers());
        return aggregatedUsers;
    }

    public IEnumerable<string> AggregateUsers(List<IEnumerable<string>> aggregatedUsers = null)
    {
        bool topStack = false;
        if (aggregatedUsers == null)
        {
            topStack = true;
            aggregatedUsers = new List<IEnumerable<string>>();
        }
        aggregatedUsers.Add(Users.AsEnumerable());
        foreach (int id in GroupIds)
            groups[id].AggregateUsers(aggregatedUsers);

        if (topStack)
            return aggregatedUsers.SelectMany(i => i);
        else
            return null;
    }
}

static void Main(string[] args)
{
    for (int i = 0; i < 1000; i++)
        Group.groups.TryAdd(i, new Group());

    for (int i = 0; i < 999; i++)
        Group.groups[i + 1].GroupIds.Add(i);

    for (int i = 0; i < 10000; i++)
        Group.groups[i / 10].Users.Add($"user{i}");

    Stopwatch stopwatch = Stopwatch.StartNew();
    IEnumerable<string> users = Group.groups[999].AggregateUsers();
    Console.WriteLine($"Aggregation via nested concatenation took {stopwatch.ElapsedMilliseconds} ms");

    stopwatch = Stopwatch.StartNew();
    bool contains = users.Contains("user0");
    Console.WriteLine($"Search through IEnumerable from nested concatenation was {contains} and took {stopwatch.ElapsedMilliseconds} ms");

    stopwatch = Stopwatch.StartNew();
    users = Group.groups[999].AggregateUsers(null);
    Console.WriteLine($"Aggregation via SelectMany took {stopwatch.ElapsedMilliseconds} ms");

    stopwatch = Stopwatch.StartNew();
    contains = users.Contains("user0");
    Console.WriteLine($"Search through IEnumerable from SelectMany was {contains} and took {stopwatch.ElapsedMilliseconds} ms");

    stopwatch = Stopwatch.StartNew();
    users = Enumerable.Empty<string>();
    foreach (Group group in Group.groups.Values.Reverse())
        users = users.Concat(group.Users);
    Console.WriteLine($"Aggregation via flat concatenation took {stopwatch.ElapsedMilliseconds} ms");

    stopwatch = Stopwatch.StartNew();
    contains = users.Contains("user0");
    Console.WriteLine($"Search through IEnumerable from flat concatenation was {contains} and took {stopwatch.ElapsedMilliseconds} ms");

    Console.Read();
}

Вот результаты: 

Aggregation via nested concatenation took 0 ms
Search through IEnumerable from nested concatenation was True and took 43 ms
Aggregation via SelectMany took 1 ms
Search through IEnumerable from SelectMany was True and took 0 ms
Aggregation via foreach concatenation took 0 ms
Search through IEnumerable from foreach concatenation was True and took 2 ms
0 голосов
/ 09 января 2019

интересный вопрос. Когда я скомпилировал его в .NET Framework, время выполнения было примерно одинаковым (мне пришлось изменить метод TryAdd Dictionary на Add).

В .NET Core я получил тот же результат, что и вы.

Я полагаю, что ответ отложено Вы можете увидеть в отладчике, что 

IEnumerable<string> users = Group.groups[999].AggregateUsers();

присвоение переменной пользователя приведет к созданию экземпляра Concat2Iterator, а второй - 

users = Enumerable.Empty<string>();
foreach (Group group in Group.groups.Values.Reverse())
    users = users.Concat(group.Users);

приведет к ConcatNIterator.

Из документации Concat:

Этот метод реализован с использованием отложенного выполнения. Немедленное возвращаемое значение является объектом, который хранит всю информацию, которая требуется для выполнения действия. Запрос, представленный этим методом не выполняется, пока объект не будет перечислен либо путем вызова его GetEnumerator метод напрямую или с помощью foreach в Visual C # или For Каждый в Visual Basic.

Вы можете проверить код concat здесь . Реализации GetEnumerable для ConcatNIterator и Concat2Iterator различны.

Так что я предполагаю, что первый запрос оценивается дольше из-за способа построения запроса с использованием concat. Если вы попытаетесь использовать ToList () для одного из перечисляемых типов: 

IEnumerable<string> users = Group.groups[999].AggregateUsers().ToList();

вы увидите, что прошедшее время снизится почти до 0 мс.

...