«отсортированный 1-й итератор» на основе «2-го итератора» (декартово произведение итераторов)

Question

Я ищу чистый способ сделать это в Python:

Допустим, у меня есть два итератора "iter1" и "iter2": возможно, генератор простых чисел и itertools.count (). Я априори знаю, что оба они бесконечны и монотонно растут. Теперь я хочу взять простую операцию с двумя аргументами «op» (возможно, operator.add или operator.mul) и вычислить каждый элемент первого итератора с каждый элемент затем, используя указанную операцию, затем выдайте их по одному, отсортировав. Очевидно, это сама бесконечная последовательность. (Как упомянуто в комментарии @RyanThompson: это будет называться декартовым произведением этих последовательностей ... или, точнее, 1-мерным видом этого произведения.)

Как лучше всего:

• Заключение "iter1", "iter2" и "op" в итерацию, которая сама дает значения в монотонно увеличивающемся выводе.

Допустимые упрощающие предположения:

• Если это поможет, мы можем предположить, что op (a, b)> = a и op (a, b)> = b.
• Если это поможет, мы можем принять op (a, b)> op (a, c) для всех b> c.

Также допустимо:

• Также приемлемым был бы итератор, который выдает значения в «обычно возрастающем» порядке ... я имею в виду, что итерируемое время от времени может давать мне число меньше, чем предыдущее, но оно каким-то образом делает доступной «дополнительную информацию» ( как с помощью метода объекта), который сказал бы: «Я не гарантирую, что следующее значение, которое я дам вам, будет больше, чем то, которое я только что дал вам, но я уверен, что все будущие значения будут, по крайней мере, больше, чем N. ".... а само" N "монотонно возрастает.

Единственный способ, которым я могу думать об этом, - это своего рода процесс «диагонализации», где я сохраняю все большее количество частично обработанных итераций и «смотрю вперед» на минимум всех возможных значений next (), и дать это. Но эта странная агломерация heapq и группы deques кажется просто диковинной, даже прежде, чем я начну ее кодировать.

Пожалуйста: не делайте , а не , чтобы основывать свой ответ на том факте, что в моих примерах упоминались простые числа или число () .... У меня есть несколько вариантов использования этого понятия, которые НЕ связаны с простыми числами и числом () .

---

ОБНОВЛЕНИЕ: Боже мой! Какая отличная дискуссия! И некоторые отличные ответы с действительно подробными объяснениями. Спасибо. StackOverflow породы; вы, ребята, рок.

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

FWIW: вот официальный «тестовый пример», если вы хотите попробовать свои решения.

import operator

def powers_of_ten():
    n = 0
    while True:
        yield 10**n
        n += 1

def series_of_nines():
    yield 1
    n = 1
    while True:
        yield int("9"*n)
        n += 1

op = operator.mul
iter1 = powers_of_ten()
iter2 = series_of_nines()

# given (iter1, iter2, op), create an iterator that yields:
# [1, 9, 10, 90, 99, 100, 900, 990, 999, 1000, 9000, 9900, 9990, 9999, 10000, ...]

Answer 1

import heapq
import itertools
import operator


def increasing(fn, left, right):
    """
    Given two never decreasing iterators produce another iterator
    resulting from passing the value from left and right to fn.
    This iterator should also be never decreasing.
    """
    # Imagine an infinite 2D-grid.
    # Each column corresponds to an entry from right
    # Each row corresponds to an entry from left
    # Each cell correspond to apply fn to those two values

    # If the number of columns were finite, then we could easily solve
    # this problem by keeping track of our current position in each column
    # in each iteration, we'd take the smallest value report it, and then
    # move down in that column. This works because the values must increase
    # as we move down the column. That means the current set of values
    # under consideration must include the lowest value not yet reported

    # To extend this to infinite columns, at any point we always track a finite
    # number of columns. The last column current tracked is always in the top row
    # if it moves down from the top row, we add a new column which starts at the top row
    # because the values are increasing as we move to the right, we know that
    # this last column is always lower then any columns that come after it





    # Due to infinities, we need to keep track of all
    # items we've ever seen. So we put them in this list
    # The list contains the first part of the incoming iterators that
    # we have explored
    left_items = [next(left)]
    right_items = [next(right)]

    # we use a heap data structure, it allows us to efficiently
    # find the lowest of all value under consideration
    heap = []

    def add_value(left_index, right_index):
        """
        Add the value result from combining the indexed attributes
        from the two iterators. Assumes that the values have already
        been copied into the lists
        """
        value = fn( left_items[left_index], right_items[right_index] )
        # the value on the heap has the index and value.
        # since the value is first, low values will be "first" on the heap
        heapq.heappush( heap, (value, left_index, right_index) )

    # we know that every other value must be larger then 
    # this one. 
    add_value(0,0)

    # I assume the incoming iterators are infinite
    while True:
        # fetch the lowest of all values under consideration
        value, left_index, right_index = heapq.heappop(heap)

        # produce it
        yield value

        # add moving down the column
        if left_index + 1 == len(left_items):
            left_items.append(next(left))

        add_value(left_index+1, right_index)

        # if this was the first row in this column, add another column
        if left_index == 0:
            right_items.append( next(right) )
            add_value(0, right_index+1)






def fib():
    a = 1
    b = 1
    while True:
        yield a
        a,b = b,a+b



r = increasing(operator.add, fib(), itertools.count() )
for x in range(100):
    print next(r)

Answer 2

Определите последовательности как:

a1 <= a2 <= a3 ...
b1 <= b2 <= b3 ...

Позвольте a1b1 означать op(a1,b1) для краткости.

Исходя из ваших допустимых предположений (очень важно), вы знаете следующее:

max(a1, b1) <= a1b1 <= a1b2 <= a1b3 ...
   <=
max(a2, b1) <= a2b1 <= a2b2 <= a2b3 ...
   <=
max(a3, b1) <= a3b1 <= a3b2 <= a3b3 ...
    .     .
    .      .
    .       .

Вам нужно будет сделать что-то вроде:

Generate a1b1.Вы знаете, что если вы продолжите увеличивать переменные b, вы получите только более высокие значения.Теперь возникает вопрос: есть ли меньшее значение путем увеличения переменных a?Ваша нижняя граница равна min(a1, b1), поэтому вам придется увеличивать значения a до min(ax,b1) >= a1b1.Как только вы достигнете этой точки, вы можете найти наименьшее значение из anb1, где 1 <= n <= x и получить его безопасно.

У вас будет несколько горизонтальных цепочек, которые вам придется отслеживать.Каждый раз, когда у вас есть значение, которое превышает min(ax,b1), вам придется увеличивать x (добавляя больше цепочек), пока min(ax,b1) не станет больше, чем оно, прежде чем безопасно его испустить.

Просто отправная точка ... У меня нет времени кодировать это в данный момент.

РЕДАКТИРОВАТЬ: О хе, это именно то, что вы уже имели.Ну, без дополнительной информации, это все, что вы можете сделать, так как я уверен, что математически, это то, что необходимо.

EDIT2: Что касается вашего «приемлемого» решения: вы можете просто дать a1bn в порядке возрастания n, возвращая min(a1,b1) как N = P.Вам нужно быть более конкретным.Вы говорите так, как будто у вас есть эвристика того, что вы обычно хотите видеть, общий способ, которым вы хотите пройти через обе итерации, но не говоря нам, что это такое, я не знаю, как можно добиться большего.

---

ОБНОВЛЕНИЕ: Уинстон хорош, но делает предположение, что автор не упомянул: что op(a,c)> op(b,c), если b>a.Тем не менее, мы знаем, что op(a,b)>=a и op(a,b)>=b.

Вот мое решение, которое принимает это второе предположение, но не то, которое взял Уинстон.Пропишет ему структуру кода, хотя:

def increasing(fn, left, right):
    left_items = [next(left)]
    right_items = [next(right)]

    #columns are (column value, right index)
    columns = [(fn(left_items[0],right_items[0]),0)]

    while True:
        #find the current smallest value
        min_col_index = min(xrange(len(columns)), key=lambda i:columns[i][0])

        #generate columns until it's impossible to get a smaller value
        while right_items[0] <= columns[min_col_index][0] and \
              left_items[-1] <= columns[min_col_index][0]:
            next_left = next(left)

            left_items.append(next_left)
            columns.append((fn(next_left, right_items[0]),0))

            if columns[-1][0] < columns[min_col_index][0]:
                min_col_index = len(columns)-1

        #yield the smallest value
        yield columns[min_col_index][0]

        #move down that column
        val, right_index = columns[min_col_index]

        #make sure that right value is generated:
        while right_index+1 >= len(right_items):
            right_items.append(next(right))

        columns[min_col_index] = (fn(left_items[min_col_index],right_items[right_index+1]),
                                  right_index+1)
        #repeat                

Для (патологического) ввода, демонстрирующего разницу, рассмотрим:

def pathological_one():
    cur = 0
    while True:
        yield cur
        cur += 100

def pathological_two():
    cur = 0
    while True:
        yield cur
        cur += 100

lookup = [
    [1,   666, 500],
    [666, 666, 666],
    [666, 666, 666],
    [666, 666, 666]]

def pathological_op(a, b):
    if a >= 300 or b >= 400: return 1005
    return lookup[b/100][a/100]

r = increasing(pathological_op, pathological_one(), pathological_two())
for x in range(15):
    print next(r)

Ответ Уинстона дает:

>>> 
1
666
666
666
666
500
666
666
666
666
666
666
1005
1005
1005

Пока мой дает:

>>> 
1
500
666
666
666
666
666
666
666
666
666
666
1005
1005
1005

Answer 3

Позвольте мне начать с примера того, как бы я решил это интуитивно.

Поскольку чтение встроенного кода немного утомительно, я введу некоторые обозначения:

Обозначение

• i1 будет представлять iter1. i1 ₀ будет представлять первый элемент iter1. То же самое для iter2.
• represent будет представлять op оператор

Интуитивно понятное решение

Используя упрощенное предположение 2, мы знаем, что i1 ₀ ※ i2 ₀ - самый маленький элемент, который когда-либо будет получен от вашего последнего итератора. Следующий элемент будет меньшим из i1 ₀ ※ i2 ₁ и i1 ₁ ※ i2 ₀ .

Предполагая, что i1 ₀ ※ i2 ₁ меньше, вы получите этот элемент. Далее вы получите меньшее из i1 ₁ ※ i2 ₀ , i1 ₁ ※ i2 ₀ и i1 ₁ ※ i2 ₁ .

Выражение как обход DAG

То, что у вас есть, является проблемой обхода графа. Сначала подумайте о проблеме как о дереве. Корень дерева: i1 ₀ ※ i2 ₀ . Этот узел и каждый узел под ним имеет двух дочерних элементов. Двое детей i1 _x ※ i2 _y являются следующими: Один ребенок i1 _{x + 1} ※ i2 _y , а другой ребенок - i1 _x ※ i2 _{у + 1} . Исходя из вашего второго предположения, мы знаем, что i1 _x ※ i2 _y меньше, чем оба его потомка.

(На самом деле, как упоминает Райан в комментарии, это направленный ациклический граф или DAG. Некоторые «родители» делят «детей» с другими «родительскими» узлами.)

Теперь нам нужно сохранить границу - набор узлов, которые могут быть рядом с возвращаемыми. После возврата узла мы добавляем обоих его потомков к границе. Чтобы выбрать следующий узел для посещения (и вернуться из вашего нового итератора), мы сравниваем значения всех узлов на границе. Мы берем узел с наименьшим значением и возвращаем его. Затем мы снова добавляем оба его дочерних узла к границе. Если дочерний элемент уже находится на границе (добавлен как дочерний элемент какого-либо другого родителя), просто игнорируйте его.

Хранение границы

Поскольку вас в первую очередь интересует значение узлов, имеет смысл хранить эти узлы, проиндексированные по значению. Таким образом, в ваших интересах использовать dict. Ключи в этом dict должны быть значениями узлов. Значения в этом dict должны быть списками, содержащими отдельные узлы. Поскольку единственной идентифицирующей информацией в узле является пара операндов, вы можете хранить отдельные узлы в виде двух кортежей операндов.

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

>>> frontier
{1: [(2, 3), (2, 4)], 2: [(3, 5), (5, 4)], 3: [(1, 6)], 4: [(6, 3)]}

Другие замечания по реализации

Поскольку итераторы не поддерживают произвольный доступ, вам нужно держаться за значения, которые создаются вашими первыми двумя итераторами, пока они больше не нужны. Вы будете знать, что значение по-прежнему необходимо, если на него ссылается какое-либо значение в вашей границе. Вы будете знать, что значение больше не нужно, если все узлы в граничных ссылочных значениях позже / больше, чем тот, который вы сохранили. Например, i1 ₂₀ больше не требуется, когда узлы в вашей границе ссылаются только на i1 ₂₁ , i1 ₂₅ , i1 ₃₃ , ...

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

Непрактично

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

Answer 4

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

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

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

Чтобы вычислить следующий элемент в вашем итераторе, вы должны сделать следующее:

• Для каждой строки, которую вы когда-либо использовали, вычислите «следующее» значение в этой строке.Например, если вы использовали 5 значений из строки 1, вычислите 6-е значение (i = 1, j = 6), взяв 1-е значение из первой последовательности и 6-е значение из второй последовательности (оба из которых у вас естькэшировать) и применять к ним операцию (умножение).Кроме того, вычислите первое значение в первой неиспользованной строке.
• Возьмите минимум всех вычисленных вами значений.Выведите это значение как следующий элемент в вашем итераторе
• Увеличьте счетчик для строки, из которой вы взяли элемент на предыдущем шаге.Если вы взяли элемент из новой неиспользуемой строки, вы должны увеличить счетчик количества использованных вами строк и создать новый счетчик для этой строки, инициализированной в 1. При необходимости вы также должны вычислить больше значенийодна или обе входные последовательности.

Этот процесс является довольно сложным, и, в частности, обратите внимание, что для вычисления значений N необходимо в худшем случае сохранить количество состояний, пропорциональное квадрату корень N. (Правка: sqrt (N) на самом деле лучший случай.) Это резко контрастирует с типичным генератором, которому требуется только постоянное пространство для перебора его элементов независимо от длины.

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

Answer 5

В обсуждении других ответов отмечается, что потенциально требуется неограниченное хранилище независимо от алгоритма, поскольку каждый a[n] должен оставаться доступным для каждого нового b[n].Если вы уберете ограничение, что input будет двумя итераторами и вместо этого потребует, чтобы они были только последовательностями (индексируемыми или просто чем-то, что может быть многократно восстановлено), то я полагаю, что все ваше состояние внезапно сворачивается в одно число:последнее значение, которое вы вернули.Зная последнее значение результата, вы можете искать выходное пространство в поисках следующего.(Если вы хотите правильно генерировать дубликаты, вам также может понадобиться отследить, сколько раз результат был возвращен)

С парой последовательностей у вас есть простое отношение повторения:

result(n) = f(seq1, seq1, result(n-1))

, где f(seq1, seq1, p) ищет минимальное значение в выходном пространстве q, такое что q > p.С практической точки зрения вы, вероятно, сделаете запоминаемые функции для последовательностей и выберете алгоритм поиска, чтобы не перегружать пул запомненных элементов.

Answer 6

Используйте огенераторы , которые являются просто итераторами, написанными как функции, которые дают результаты.В этом случае вы можете написать генераторы для iter1 и iter2 и другой генератор, чтобы обернуть их и вывести их результаты (или выполнить вычисления с ними, или историю их результатов) по ходу работы.

ОтВ моем чтении вопроса вы хотите что-то вроде этого, которое будет вычислять каждый элемент первого итератора с каждым элементом следующего, используя указанную операцию , вы также утверждаете, что хотите какой-то способ wrap-up "iter1", "iter2" и "op" в итерируемой переменной, которая сама дает значения в монотонно увеличивающемся выводе .Я предлагаю генераторам предложить простое решение такой проблемы.

import itertools

def prime_gen():
    D, q = {}, 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

def infinite_gen(op, iter1, iter2):
    while True:
        yield op(iter1.next(), iter2.next())

>>> gen = infinite_gen(operator.mul, prime_gen(), itertools.count())

>>> gen.next()
<<< 0

>>> gen.next()
<<< 3

>>> gen.next()
<<< 10

Генераторы предлагают большую гибкость, поэтому должно быть довольно легко написать iter1 и iter2 как генераторы, которые возвращают нужные значения взаказ, который вы хотите.Вы также можете использовать сопрограммы , которые позволяют отправлять значения в генератор.