Другой логический мозговой штурм: мне нужен быстрый алгоритм, чтобы получить последние значения из большого List <> в соответствии с некоторым условием

Question

У меня есть структура данных следующим образом:

public struct StateItem
{
    public DateTime Moment;
    public int SomeValue;

    public int Id
    {
        get
        {
            return Moment.Hour
            + Moment.Minute
            + Moment.Second
            + SomeValue
            ;
        }
    }

    public override bool Equals(object obj)
    {
        return Id.Equals(((StateItem)obj).Id);
    }

    public override int GetHashCode()
    {
        return Id;
    }

    public override string ToString()
    {
        return Moment.ToString("HH:mm:ss");
    }

}

и в другом классе я постоянно собираю такие предметы в Список <StateItem> _items, как это:

    public void Add(StateItem item)
    {
            if (!_items.Contains(item))
            {
                _items.Add(item);
            }
    }

Поскольку элементы времени собираются непрерывно, список должен содержать

"2010-11-11 12:33", 1

"2010-11-11 12:33", 2

"2010-11-11 12:33", 1

"2010-11-11 12:33", 5

"2010-11-11 12:32", 5

"2010-11-11 12:32", 4

последний пункт последний раз - это важно!

Теперь давайте предположим, что конец списка является начальной точкой, и мне нужно получить N моментальных кадров с помощью M stepOff, e. g.:

• 1 моментный кадр с 0 stepOff вернет все элементы в данный момент "2010-11-11 12:33"

• 2-минутный кадр с 0 stepOff вернет все элементы в момент "2010-11-11 12:33" и в "2010-11-11 12:32"

• 1 моментный кадр с 1 stepOff вернет все элементы в данный момент "2010-11-11 12:32"

Любое решение высоко ценится!

Вот решение, которое я нашел сам:

 public List<StateItem> GetItems(int cnt, int cntOffset)
    {
            var r = new List<StateItem>();

            int i = 0;
            int iOffset = 0;

            int idx = _items.Count - 1;
            DateTime moment = _items[idx].Moment;

            while (i <= cnt)
            {
                if (iOffset != cntOffset)
                {
                    if (!_items[idx].Moment.Equals(moment))
                    {
                        iOffset++;
                        moment = _items[idx].Moment;
                        continue;
                    }
                    moment = _items[idx].Moment;
                    idx--;
                    continue;
                }

                if (_items[idx].Moment.Equals(moment))
                {
                    r.Add(_items[idx]);
                }
                else
                {
                    i++;
                    moment = _items[idx].Moment;
                    continue;
                }

                moment = _items[idx].Moment;
                idx--;

            }
            r.Sort((item, logItem) => item.SomeValue.CompareTo(logItem.SomeValue));

            return r;

    }

Answer 1

Правильно ли я понял ваш вопрос с помощью этого метода? Дайте ему ваши элементы, размер кадра и значение stepOff, и вы увидите окно результатов, сгруппированное по Moment.

static IEnumerable<IGrouping<DateTime, StateItem>> Foo(IEnumerable<StateItem> items, int frameSize, int stepOff)
{
    return items.GroupBy(i => i.Moment).OrderByDescending(i => i.Key).Skip(stepOff).Take(frameSize);
}

Если это дает правильный вывод, вы можете использовать его в качестве основы для повышения производительности, возможно, заменив GroupBy и OrderByDescending требованиями о том, что входные данные предварительно отсортированы. Skip и Take очень изящны.

Обновление

Странно, я думал об этом за обедом. Вот альтернативное решение, основанное на операторе yield, который работает при условии, что список ввода отсортирован по Moment.

static IEnumerable<StateItem> BetterFoo(IEnumerable<StateItem> items, int frameSize, int stepOff)
{
    // Handle empty sequence
    if (!items.Any())
        yield break;

    DateTime currentMoment = items.First().Moment;

    foreach (StateItem item in items)
    {
        // stepOff is how many moments to skip
        if (stepOff == 0)
        {               
            // Return the specified number of distinct moments
            if (currentMoment != item.Moment)
            {
                frameSize--;
                currentMoment = item.Moment;
            }

            if (frameSize == 0)
                // Break when we've returned the specified number of frames
                break;
            else
                // Yield the current item
                yield return item;
        }
        else
        {
            // Skip the specified number of distinct moments
            if (currentMoment != item.Moment)
            {
                stepOff--;
                currentMoment = item.Moment;
            }

            if (stepOff == 0)
                yield return item;
        }
    }
}

Answer 2

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

Если я прав, то выбыло бы неплохо взглянуть на Rx Framework , который позволяет вам рассматривать источник событий как IEnumerable и использовать на нем Linq.