Как проверить IEnumerable для нескольких условий с одним перечислением без буферизации? - PullRequest
Новая
       11

Как проверить IEnumerable для нескольких условий с одним перечислением без буферизации?

2 голосов
/ 27 октября 2019

У меня очень длинная последовательность данных в форме IEnumerable, и я хотел бы проверить ее на наличие ряда условий. Каждое условие возвращает значение true или false, и я хочу знать, выполняются ли все условия. Моя проблема в том, что я не могу позволить себе материализовать IEnumerable, вызывая ToList, потому что он просто слишком длинный (> 10 000 000 000 элементов). Также я не могу позволить себе перечислять последовательность несколько раз, по одному для каждого условия, потому что каждый раз я получаю другую последовательность. Я ищу эффективный способ выполнить эту проверку, используя существующую функциональность LINQ, если это возможно.

Уточнение: Я прошу общее решение, а не решениеконкретный пример проблемы, который представлен ниже.

Вот фиктивная версия моей последовательности: 

static IEnumerable<int> GetLongSequence()
{
    var random = new Random();
    for (long i = 0; i < 10_000_000_000; i++) yield return random.Next(0, 100_000_000);
}

А вот пример условий, которым последовательность должна удовлетворять:

var source = GetLongSequence();
var result = source.Any(n => n % 28_413_803 == 0)
    && source.All(n => n < 99_999_999)
    && source.Average(n => n) > 50_000_001;

К сожалению, этот подход вызывает в три раза больше GetLongSequence, поэтому он не удовлетворяет требованиям проблемы.

Я попытался написать метод расширения Linqy, описанный выше,надеясь, что это может дать мне несколько идей: 

public static bool AllConditions<TSource>(this IEnumerable<TSource> source,
    params Func<IEnumerable<TSource>, bool>[] conditions)
{
    foreach (var condition in conditions)
    {
        if (!condition(source)) return false;
    }
    return true;
}

Вот как я собираюсь использовать это: 

var result = source.AllConditions
(
    s => s.Any(n => n % 28_413_803 == 0),
    s => s.All(n => n < 99_999_999),
    s => s.Average(n => n) > 50_000_001,
    // more conditions...
);

К сожалению, это не дает никаких улучшений. GetLongSequence снова вызывается три раза.

После того, как я в течение часа ударился головой о стену, не добившись никакого прогресса, я нашел возможное решение. Я мог бы запускать каждое условие в отдельном потоке и синхронизировать их доступ к одному общему перечислителю последовательности. Итак, я закончил с этим чудовищем: 

public static bool AllConditions<TSource>(this IEnumerable<TSource> source,
    params Func<IEnumerable<TSource>, bool>[] conditions)
{
    var locker = new object();
    var enumerator = source.GetEnumerator();
    var barrier = new Barrier(conditions.Length);
    long index = -1;
    bool finished = false;

    IEnumerable<TSource> OneByOne()
    {
        try
        {
            while (true)
            {
                TSource current;
                lock (locker)
                {
                    if (finished) break;
                    if (barrier.CurrentPhaseNumber > index)
                    {
                        index = barrier.CurrentPhaseNumber;
                        finished = !enumerator.MoveNext();
                        if (finished)
                        {
                            enumerator.Dispose(); break;
                        }
                    }
                    current = enumerator.Current;
                }
                yield return current;
                barrier.SignalAndWait();
            }
        }
        finally
        {
            barrier.RemoveParticipant();
        }
    }

    var results = new ConcurrentQueue<bool>();
    var threads = conditions.Select(condition => new Thread(() =>
    {
        var result = condition(OneByOne());
        results.Enqueue(result);
    })
    { IsBackground = true }).ToArray();
    foreach (var thread in threads) thread.Start();
    foreach (var thread in threads) thread.Join();
    return results.All(r => r);
}

Для синхронизации используется Barrier. Это решение на самом деле работает лучше, чем я думал. Он может обрабатывать почти 1 000 000 элементов в секунду на моем компьютере. Это не достаточно быстро, поскольку для обработки полной последовательности из 10 000 000 000 элементов требуется почти 3 часа. И я не могу ждать результата дольше 5 минут. Любые идеи о том, как я мог бы эффективно выполнить эти условия в одном потоке?

Ответы [ 4 ]

4 голосов
/ 27 октября 2019

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

bool Example()
{
    var source = GetLongSequence();

    var conditions = new List<IEvaluate<int>>
    {
        new Any<int>(n => n % 28_413_803 == 0),
        new All<int>(n => n < 99_999_999),
        new Average(d => d > 50_000_001)
    };

    foreach (var item in source)
    {
        foreach (var condition in conditions)
        {
            condition.Evaluate(item);
        }
    }

    return conditions.All(c => c.Result);   
}

static IEnumerable<int> GetLongSequence()
{
    var random = new Random();
    for (long i = 0; i < 10_000_000_000; i++) yield return random.Next(0, 100_000_000);
}

interface IEvaluate<T>
{
    void Evaluate(T item);
    bool Result { get; }
}

class Any<T> : IEvaluate<T>
{
    private bool _result;
    private readonly Func<T, bool> _predicate;

    public Any(Func<T, bool> predicate)
    {
        _predicate = predicate;
        _result = false;
    }

    public void Evaluate(T item)
    {
        if (_predicate(item))
        {
            _result = true;
        }
    }

    public bool Result => _result;
}


class All<T> : IEvaluate<T>
{
    private bool _result;
    private readonly Func<T, bool> _predicate;

    public All(Func<T, bool> predicate)
    {
        _predicate = predicate;
        _result = true;
    }

    public void Evaluate(T item)
    {
        if (!_predicate(item))
        {
            _result = false;
        }
    }

    public bool Result => _result;
}

class Average : IEvaluate<int>
{
    private long _sum;
    private int _count;
    Func<double, bool> _evaluate;
    public Average(Func<double, bool> evaluate)
    {
    }

    public void Evaluate(int item)
    {
        _sum += item;
        _count++;
    }

    public bool Result => _evaluate((double)_sum / _count);
}
2 голосов
/ 27 октября 2019

Если все, что вам нужно, это проверить эти три условия в одном потоке только в одном перечислении, я бы не стал использовать LINQ и вручную объединять проверки: 

bool anyVerified = false;
bool allVerified = true;
double averageSoFar = 0;

foreach (int n in GetLongSequence()) {
    anyVerified = anyVerified || n % 28_413_803 == 0;
    allVerified = allVerified && n < 99_999_999;
    averageSoFar += n / 10_000_000_000;
    // Early out conditions here...
}
return anyVerified && allVerified && averageSoFar > 50_000_001;

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

0 голосов
/ 28 октября 2019

Я нашел однопоточное решение, использующее библиотеку Reactive Extensions . С одной стороны, это отличное решение с точки зрения возможностей и простоты использования, поскольку все методы, доступные в LINQ для IEnumerable, также доступны в RX для IObservable. С другой стороны, это немного разочаровывает с точки зрения производительности, так как он такой же медленный, как мое дурацкое многопоточное решение, представленное в моем вопросе.

Обновление: Я отказалсядве предыдущие реализации (одна с использованием метода Replay, другая с использованием метода Publish) с новой реализацией, использующей класс Subject. Этот класс представляет собой низкоуровневую комбинацию IObservable и IObserver. Я размещаю на нем элементы источника IEnumerable, которые затем распространяются на все IObservable<bool>, предоставленные вызывающей стороной. Производительность теперь приличная, всего на 40% медленнее, чем у превосходного решения Клауса Гюттера . Также теперь я могу рано выйти из цикла, если условие (например, All) может быть определено как ложное до конца перечисления. 

public static bool AllConditions<TSource>(this IEnumerable<TSource> source,
    params Func<IObservable<TSource>, IObservable<bool>>[] conditions)
{
    var subject = new Subject<TSource>();
    var result = true;
    foreach (var condition in conditions)
    {
        condition(subject).SingleAsync().Subscribe(onNext: value =>
        {
            if (value) return;
            result = false;
        });
    }
    foreach (var item in source)
    {
        if (!result) break;
        subject.OnNext(item);
    }
    return result;
}

Пример использования: 

var result = source.AllConditions
(
    o => o.Any(n => n % 28_413_803 == 0),
    o => o.All(n => n < 99_999_999),
    o => o.Average(n => n).Select(v => v > 50_000_001)
);

Каждое условие должно возвращать IObservable, содержащее одно логическое значение. Это не применяется RX API, поэтому я использовал метод System.Reactive.Linq.SingleAsync для его принудительного применения во время выполнения (путем исключения, если результат не соответствует этому контракту).

0 голосов
/ 28 октября 2019

Могу ли я также предложить вам другой метод, основанный на методе расширения Enumerable.Aggregate LINQ. 

public static class Parsing {
    public static bool ParseOnceAndCheck(this IEnumerable<int> collection, Func<int, bool> all, Func<int, bool> any, Func<double, bool> average) {
        // Aggregate the two boolean results, the sum of all values and the count of values...
        (bool allVerified, bool anyVerified, int sum, int count) = collection.Aggregate(
            ValueTuple.Create(true, false, 0, 0),
            (tuple, item) => ValueTuple.Create(tuple.Item1 && all(item), tuple.Item2 || any(item), tuple.Item3 + item, tuple.Item4 + 1)
        );
        // ... and summarizes the result
        return allVerified && anyVerified && average(sum / count);
    }
}

Вы можете вызывать этот метод расширения очень похожим образом, чем обычные методы LINQ, но это будеттолько одно перечисление вашей последовательности: 

IEnumerable<int> sequence = GetLongSequence();
bool result = sequence.ParseOnceAndCheck(
    all: n => n < 99_999_999,
    any: n => n % 28_413_803 == 0,
    average: a => a > 50_000_001
);
...