Эффективный способ получить сначала недостающий элемент в заказанной последовательности?
Остерегайтесь, Работа SiteDataQuery ухудшает в большой степени его больше подсайтов, которые Вы имеете. Сто подсайтов могут занять 20 секунд для запросов.
8 ответов
Изменить: Я только что заметил, что enumerable - это IQueryable , но ] selectFunc и , где Func имеют тип Func . Это приведет к вызову Enumerable версий OrderBy и Where вместо использования вызовов базы данных. Вы, вероятно, захотите вместо этого переключить их на Expression .
Если вы не хотите сначала заказывать regNums , вот O (n) Решение в стиле гольфа:
var max = regNums.Max(i => (int?)i) ?? 0;
return Enumerable.Range(1, max + 1)
.Except(regNums)
.Min();
По строке:
При приведении к
int?,МаксвернетnullifregNumsпусто, объединено с0.Создайте последовательность из всех возможных регистров, включая следующее значение, если оно заполнено.
Вычтите текущий набор регистров.
Выберите самый низкий.
Как уже упоминалось, сначала используйте профилировщик, чтобы найти, где он работает медленно. Если последовательность действительно большая и порядок медленный, вы можете использовать Radix sort , то есть O (kn), где k - максимальное количество цифр, а n - количество элементов в последовательность. Алгоритмы сортировки, основанные на сравнении, обычно O (n logn).
Таким образом, весь алгоритм будет O (kn), который в зависимости от n асимптотически быстрее и, следовательно, более масштабируем.
Предполагая, что ваши OrderBy и Где уже были применены:
int firstMissing = collection.TakeWhile((x, i) => x == ++i).LastOrDefault() + 1;
Я бы, наверное, посмотрел на что-то вроде ниже; Где может быть выполнено снаружи (как и селектор, если честно):
Если вы ожидаете начать с 1:
public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
Func<T, int> selectFunc)
{
int expected = 1;
foreach (T item in enumerable) {
if (selectFunc(item) != expected) return expected;
expected++;
}
return expected;
}
Чтобы начать с первого элемента в списке:
public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
Func<T, int> selectFunc)
{
bool first = true;
int prev = -1;
foreach (T item in enumerable)
{
int val = selectFunc(item);
if(first) {
prev = val;
first = false;
} else if (val != prev + 1) {
return prev + 1;
}
prev = val;
}
return first ? 1 : prev + 1;
}
Это неясно, как вы хотели обрабатывать нули, поэтому я этого не сделал. Обратите внимание, что это только повторяет один раз и не буферизует все.
Предполагая, что входящая последовательность значений уже отсортировано, как насчет:
var upperBoundValue = values.Last() + 1;
var firstMissingItem = Enumerable.Range(1, upperBoundValue).Except(values).First();
Если вы выполняете эту операцию итеративно,
Почему бы не сделать что-то вроде двоичного поиска?
Допустим, у вас есть список из 10 элементов. Прочтите первый элемент. Затем прочтите пятый элемент. Если пятый элемент не является первым элементом + 4, значит, вы знаете, что число отсутствует, иначе вы знаете, что его нет. Затем просто повторяйте так, пока не найдете первый отсутствующий элемент или не дойдете до конца списка.
Это, конечно, предполагает, что вы знаете размер (который не был
Вы добавили тег LinqToSql в свой вопрос. Я предполагаю, что вы ищете "первый доступный" идентификатор, чтобы вы могли создать новую запись, используя этот идентификатор. Попробуйте вместо этого включить IDENTITY в базе данных.
Предложение: запустить ваш код через профилировщик. Тогда вы узнаете, где он медленный. Интуитивно понятно, что OrderBy - самая медленная вещь в этой программе. Но интуиция относительно самой медленной вещи часто очень и очень ошибочна. Используйте профилировщик.
Конечно, вам также следует устранить серьезные недостатки в этой программе. Помните, что Count () подсчитывает последовательность путем ее повторного перечисления. Count () не знает, что вы не меняли последовательность с момента ее последнего подсчета! Вероятно, вы захотите сохранить счетчик, а не пересчитывать его каждый раз, или использовать Length,