Являются ли запросы быстрее, чем цикл for, при попытке найти несуществующее значение в определенном диапазоне?

Question

У меня есть метод, который должен рассмотреть коллекцию экземпляров класса и найти первое положительное число, отсутствующее как атрибут в этих экземплярах.

Вот моя ситуация: у меня есть класс с именем GestorePersonale (класс менеджера сотрудника), который управляет List экземплярами Dipendente (класс сотрудника). Каждый Dipendente имеет идентификатор, который должен быть уникальным среди всех других экземпляров Dipendente, присутствующих в List.

При создании нового Dipendente Мне нужно найти уникальный идентификатор, чтобы назначить ему.
Для этой задачи я сначала выясняю самый высокий идентификатор (Matricola) среди всех экземпляров в списке, а затем циклически перебираю все числа от 0 до этого идентификатора, чтобы попытаться найти идентификатор пробела для использования в новом Dipendente. Если ничего не помогает, я просто назначу идентификатор, соответствующий max + 1.

Вот метод MatricolaMax(), который отвечает за возвращение самого высокого идентификатора среди идентификаторов всех экземпляров в List (я публикую этот код только для ясности, это не часть вопрос сосредоточен на том, что хотя любые предложения по улучшению производительности также будут высоко оценены здесь) :

private uint MatricolaMax ()
{
    // Looking for the highest ID
    return dipendenti.OrderByDescending( dipendente => dipendente.Matricola ).First().Matricola;
}

и вот метод, к которому относится этот вопрос:

private uint MatricolaLibera ()
{
    var max = MatricolaMax();
    for ( uint i = 0; i < max; i++ )
    {
        var conto = dipendenti.Where( dipendente => dipendente.Matricola == i ).Count();

        if ( conto == 0 )
            return i;
    }
    return max + 1;
}

Как вы можете видеть в приведенном выше коде, чтобы найти идентификатор пропуска, я использую запрос Where, чтобы проверить, существует ли экземпляр Dipendente с Matricola (ID), соответствующим i.

Если бы я делал это, используя цикл for вместо запроса, я бы написал следующий код:

private uint MatricolaLibera ()
{
    var max = MatricolaMax();
    bool found;
    for ( uint i = 0; i < max; i++ )
    {
        found = false;
        for( int j = 0; j < dipendenti.Count; j++)
            if ( dipendenti[j].Matricola == i )
            {
                found = true;
                break;
            }

        if ( !found )
            return i;
    }
    return max + 1;
}

в основном добавляет внутренний цикл for и проверку bool, чтобы увидеть, был ли найден свободный идентификатор.

---

Мой вопрос к вам следующий:

Какой из двух представленных методов (запрос против внутреннего для цикла) работает лучше всего? Существует ли еще лучшее решение?

Answer 1

Конечно, как говорит Эрик, вы должны запустить код, чтобы ответить на ваш вопрос, который работает лучше.(Но он должен работать на размерах, аналогичных тем, которые вы увидите в реальном использовании, а не только на небольших размерах.)

Некоторые вещи, которые я предлагаю:

Ваш метод MatricolaMax сортирует списокнайти самое высокое значение.Сортировка выполняется как минимум O (n * logn), тогда как простое перечисление списка и сравнение значений будет O (n).

Обе функции MatricolaLibra проходят всю коллекцию для каждого возможного значения.Это O (n * m).Я бы предложил один раз просмотреть список, поместить каждый ключ в словарь, а затем перечислить словарь, чтобы найти первый, который не существует.Это должно быть намного быстрее.

Answer 2

Эрик Липперт имеет лучший ответ на ваш главный вопрос, но на ваш вопрос «есть ли лучший способ», вот ответ.

Вы можете использовать целое число для хранения самого высокого найденного параметра, а также массив bool для хранения используемых значений. Предполагая, что у вас есть хорошая верхняя граница, вы можете сделать это с одним массивом, если вы этого не сделаете, вам придется обрабатывать растущий массив по мере необходимости. Затем вы можете просто перечислить ваш список, пометить использованные значения и обновить max, если это необходимо. Если вы не знаете верхней границы или она может быть произвольно высокой, используйте другой алгоритм.

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