Составляя средний поток кусочно

Ответ 1

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

Тогда имеем (a-b) ^ 2 = a ^ 2 + b ^ 2 - 2a.b. Поэтому, если мы сможем быстро найти точечный продукт двух векторов, и мы знаем их абсолютный размер, мы можем быстро найти расстояние. Но используя FFT и http://en.wikipedia.org/wiki/Convolution_theorem, мы можем разработать a.b_i, где a - целевой поток, а b_i - поток b при некотором смещении i, используя FFT для свертки реверсивной версии b - для стоимости выполнения БПФ на a, БПФ на обратном b и БПФ на результат, мы получаем a.b_i для каждого смещения i.

Если мы сделаем жадный поиск, первым шагом будет поиск b_i, который делает (a-b_i) ^ 2 наименьшим и вычитает его из a. Затем мы ищем поток c_j, который делает (a-b_i-c_j) ^ 2 как можно меньшим. Но это a ^ 2 + b_i ^ 2 + c_j ^ 2 - 2a.b_i - 2a.c_j + 2b_i.c_j, и мы уже вычислили все, кроме b_i.c_j, на предыдущем шаге. Если b и c - более короткие потоки, будет дешево вычислять b_i.c_j, и мы можем использовать БПФ, как и раньше.

Таким образом, у нас есть не слишком ужасный способ сделать жадный поиск - на каждом этапе вычесть поток из настроенного целевого потока до сих пор, что делает остаточные наименьшие (считающиеся векторами в евклидовом пространстве) и продолжаться оттуда, На каком-то этапе мы обнаружим, что ни один из доступных нами потоков не делает остаточное меньше. Мы можем остановиться там, потому что наш расчет выше показывает, что использование двух потоков сразу не поможет ни тогда, - это следует из-за того, что b_i.c_j >= 0, поскольку каждый элемент из b_i равен >= 0, потому что это квадрат.

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

Ответ 2

Если я могу использовать С#, LINQ и Rx framework System.Interactive extensions, то это работает:

Вначале - задайте неровный массив для допустимых массивов.

int[][] streams =
    new []
    {
        new [] { 1, 2, 3, 4, },
        new [] { 2, 4, 5, 6, 7, },
        new [] { 1, 5, 6, },
    };

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

IEnumerable<int> steps =
    EnumerableEx.Generate(0, x => true, x => x + 1, x => x);

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

var rnd = new Random();

В моем запросе LINQ я использовал следующие операторы:

• Scan ^ - запускает функцию аккумулятора по последовательности, создающей выходное значение для каждого входного значения
• Где - фильтрует последовательность на основе предиката
• Пусто - возвращает пустую последовательность
• Concat - объединяет две последовательности
• Пропустить - пропускает указанное количество элементов в последовательности
• Any - возвращает true, если последовательность содержит любые элементы
• Выбрать - проецирует последовательность с помощью функции выбора
• Сумма - суммирует значения в последовательности

^ - из Rx System.Interactive library

Теперь для запроса LINQ, который выполняет всю тяжелую работу.

IEnumerable<double> results =
    steps
        // Randomly select which streams to add to this step
        .Scan(Enumerable.Empty<IEnumerable<int>>(), (xs, _) =>
            streams.Where(st => rnd.NextDouble() > 0.8).ToArray())
        // Create a list of "Heads" & "Tails" for each step
        // Heads are the first elements of the current streams in the step
        // Tails are the remaining elements to push forward to the next step
        .Scan(new
        {
            Heads = Enumerable.Empty<int>(),
            Tails = Enumerable.Empty<IEnumerable<int>>()
        }, (acc, ss) => new
        {
            Heads = acc.Tails.Concat(ss)
                .Select(s => s.First()),
            Tails = acc.Tails.Concat(ss)
                .Select(s => s.Skip(1)).Where(s => s.Any()),
        })
        // Keep the Heads only
        .Select(x => x.Heads)
        // Filter out any steps that didn't produce any values
        .Where(x => x.Any())
        // Calculate the square root of the sum of the squares
        .Select(x => System.Math.Sqrt((double)x.Select(y => y * y).Sum()));

Хорошая ленивая оценка за шаг - страшно, хотя...