从有序的指数序列生成一个项目

Question

我正在为以下问题编写解决方案。

A is a list containing all elements 2^I * 3^Q where I and Q are integers in an ascending order.

Write a function f such that:

f(N) returns A[N]

前几个元素是：

A[0] = 1

A[1] = 2

A[2] = 3

A[3] = 4

A[4] = 6

A[5] = 8

A[6] = 9

A[7] = 12

我的解决方案是通过双循环每次 15 次生成一个包含前 225 个元素的列表，然后对这个列表进行排序和 return A[N]

有没有办法在不先创建和排序列表的情况下生成这个序列的第 N 个元素？

Answer 1

这里有两种方法可以在不创建如此大的列表的情况下解决您的问题。每种方法都有其缺点。

首先，你可以设置一个计数器为0。然后从1开始扫描所有整数。对于每个整数，在其因式分解中除以 2 和 3 的所有倍数。如果剩余 1，则递增计数器；否则，保持计数器不变。当计数器达到 N 时，您已找到 A[N] 的值。例如，您增加整数 1、2、3 和 4 的计数器，但不增加 5 的计数器。这种方法使用的内存很少，但会花费很多时间。

second 方法使用最小优先级队列，例如 Python 的 heapq。同样，将计数器设置为零，但也将优先级队列初始化为仅包含数字 1，并注意到目前为止看到的 3 的最高次幂也是 1。增加计数器然后查看队列中的最小数字。如果计数器是 N，那么您就得到了 A[N] 的值。否则，弹出该最小值并立即将其值加倍。（pop 和 push 可以在许多优先级队列中通过一次操作完成。）如果该值是迄今为止看到的 3 的最高次方，也推入其值的三倍并注意这个新值现在是 3 的最高次方.

第二种方法使用一个优先级队列，它占用一些内存，但最大的大小只会在 N 的平方根的数量级。我希望时间大致等于您对大列表进行排序的时间，但我不确定。这种方法的代码最复杂，需要你有一个最小优先级队列。

你的算法优点是简单，缺点是列表大。事实上，给定 N 2 和 3 的最大幂是一点也不明显，因此您需要使列表比需要的大得多。例如，您计算 "the first 225 elements by double looping in 15 times each" 的情况实际上只适用于 N=82.

下面我有所有三种方法的 Python 代码。使用 timeit 作为 N=200 我得到了这些时间：

1.19 ms  for sorting a long list (your approach) (powerof2=powerof3=30)
8.44 s   for factoring increasing integers
88 µs    for the min priority queue (maximum size of the queue was 17)

优先队列以很大的优势获胜——比我预期的大得多。这是所有三种方法的 Python 3.6.4 代码：

"""A is a list containing all elements 2^I * 3^Q where I and Q are
integers in an ascending order. Write a function f such that
f(N) returns A[N].

Do this without actually building the list A.

Based on the question <
generating-an-item-from-an-ordered-sequence-of-exponentials>
"""
import heapq  # min priority queue

def ordered_exponential_0(N, powerof2, powerof3):
    """Return the Nth (zero-based) product of powers of 2 and 3.
    This uses the questioner's algorithm
    """
    A = [2**p2 * 3**p3 for p2 in range(powerof2) for p3 in range(powerof3)]
    A.sort()
    return A[N]

def ordered_exponential_1(N):
    """Return the Nth (zero-based) product of powers of 2 and 3.
    This uses the algorithm of factoring increasing integers.
    """
    i = 0
    result = 1
    while i < N:
        result += 1
        num = result
        while num % 2 == 0:
            num //= 2
        while num % 3 == 0:
            num //= 3
        if num == 1:
            i += 1
    return result

def ordered_exponential_2(N):
    """Return the Nth (zero-based) product of powers of 2 and 3.
    This uses the algorithm using a priority queue.
    """
    i = 0
    powerproducts = [1]  # initialize min priority queue to only 1
    highestpowerof3 = 1
    while i < N:
        powerproduct = powerproducts[0]  # next product of powers of 2 & 3
        heapq.heapreplace(powerproducts, 2 * powerproduct)
        if powerproduct == highestpowerof3:
            highestpowerof3 *= 3
            heapq.heappush(powerproducts, highestpowerof3)
        i += 1
    return powerproducts[0]

从有序的指数序列生成一个项目

Generating an item from an ordered sequence of exponentials

math

sequences