Как я могу обнаружить «отсутствующие» элементы в IEnumerable <T>?

Question

У меня есть IEnumerable<T>, содержащий список элементов данных с постоянными интервалами в одном из свойств:

List<Interval> list = new List<Interval>
            { 
                new Interval{ TIME_KEY = 600},
                new Interval{ TIME_KEY = 605},
                new Interval{ TIME_KEY = 615},
                new Interval{ TIME_KEY = 620},
                new Interval{ TIME_KEY = 630}
            };

Как можно запросить этот список (предпочтительно с использованием Linq), чтобы получитьСписок, который выглядит следующим образом:

 List<Interval> list = new List<Interval>
                { 
                    new Interval{ TIME_KEY = 610},
                    new Interval{ TIME_KEY = 625}
                };

?

РЕДАКТИРОВАТЬ: Я, вероятно, буду знать, каким должно быть интервальное расстояние, но если есть способ определить его, изучив данные, это было бы огромным бонусом!

РЕДАКТИРОВАТЬ: изменено на числовые значения

Answer 1

var newList = 
     Enumerable.Range(0, 6)
               .Select(r=> new Interval() {TIME_KEY = ((r*5)+600) })
               .Except(list )

Answer 2

Посмотрите на этот вопрос для метода расширения, который выбирает последовательные значения. Оттуда вы можете сделать что-то вроде:

// I'd probably rename SelectBetween to SelectConsecutive
list.SelectConsecutive((x, y) => new { Original = x, Interval = y - x})
    .Where(pair => pair.Interval != 5)
    .Select(pair => new Interval(pair.Original + 5));

(Несколько псевдокод, но я надеюсь, что вы видите, куда я иду.)

Однако это сгенерирует только один элемент, когда он отсутствует ... если вы перейдете от 0 до 20, он не сгенерирует 5, 10, 15.

Чтобы добавить немного мяса ко второму предложению Хенка:

var missing = Enumerable.Range(0, expectedElementCount)
                        .Select(x => new Interval(baseInterval + 5 * x)
                        .Except(list);

Answer 3

Эффективным и простым способом было бы просто просмотреть этот список с помощью foreach и обнаружить пробелы.
Я предполагаю, что 5-минутный такт исправлен?

Чтобы использовать LINQ, вы можете создатьПолный список и найти разницу, но это кажется излишним.

---

Учитывая 2-ю часть, определим интервал:

Из вашего примера, вероятно, подойдет выборка из 3 или 4 значений.Но вы не можете быть абсолютно уверены даже после изучения всех значений.Данные вашего примера не исключают частоту в 1 минуту с большим количеством пропущенных значений.

Так что вам нужны очень хорошие спецификации по этой части.

Answer 4

Это будет работать, если интервал известен, если у вас есть доступ к методу Zip (поставляется с .NET 4):

list.Zip(list.Skip(1), (x,y) => new { x, delta = y - x })
    .SelectMany(a => Enumerable.Range(1, a.delta/interval - 1)
                               .Select(i => a.x + i*interval));

Обратите внимание, что это повторяет список дважды, поэтому в случае, если источник является ленивым перечислимым, вам нужно сначала его буферизовать. Эта конструкция с Zip и Skip - это быстрый и грязный способ проецирования последовательных элементов вместе. Библиотека System.Interactive Reactive Extensions имеет метод Scan для этого, и Джон показал возможную реализацию в другом ответе . Ни один из них не повторяет список дважды, так что это был бы гораздо лучший выбор.

Если интервал должен быть определен, вы можете получить минимальную дельту:

var deltas = list.Zip(list.Skip(1), (x,y) => y - x );
var interval = deltas.Min();
list.Zip(deltas, (x, delta) => new { x, delta })
    .SelectMany(a => Enumerable.Range(1, a.delta/interval - 1)
                               .Select(i => a.x + i*interval));

Есть некоторые предположения, которые я сделал, хотя:

• все различия между элементами кратны интервалу;
• вход отсортирован.

Как это работает:

1. Сначала он строит последовательность пар с каждым элементом, кроме последнего и интервалом до элемента, который следует за ним;
2. Затем для каждой из этих пар создаются все пропущенные значения в дельте: в каждой дельте есть ровно a.delta/interval - 1 значений, и каждое из них находится на определенном количестве интервалов от хранилища элементов в паре, следовательно a.x + i*interval.
3. SelectMany заботится о сведении всех этих последовательностей пропущенных значений в одно целое.

Answer 5

IEnumerable<Interval> missingIntervals =
    Enumerable.Range(list.Min(listMember => listMember.TIME_KEY), list.Max(listMember => listMember.TIME_KEY))
              .Where(enumMember => enumMember % intervalDistance == 0)
              .Select(enumMember => new Interval { TIME_KEY = enumMember}
              .Except(list);

Answer 6

Попробуйте это:

private static IEnumerable<Interval> CalculateMissingIntervals(IEnumerable<Interval> list, int step) {
  return list.Zip(list.Skip(1), 
    (i1, i2) => IntervalRange(i1.TIME_KEY + step, i2.TIME_KEY, step)).
    SelectMany(x => x);
}
private static IEnumerable<Interval> IntervalRange(int start, int end, int step) {
  for (var i = start; i < end; i += step) {
    yield return new Interval { TIME_KEY = i };
  }
}

Предполагается, что первоначальный список отсортирован.