在快速求解2的幂次方中寻找数字

Question

任务是搜索所有小于 2^10000 的二的幂，返回第一个包含给定字符串的幂的索引。例如，如果要搜索的字符串是 "7"，那么程序将输出 15，因为 2^15 是第一个包含 7 的幂。

我尝试过暴力方法，但在大约 70% 的测试用例上超时。

for i in range(1,9999):
    if search in str(2**i):
        print i
        break

如果限制时间为5秒钟，该如何处理这个问题？

- user1411838

---

你输入的搜索字符串有限制吗？ - Save

@Save，对了，我忘记提到了。搜索字符串将少于200个字符。 - user1411838

Answer 1

尽量不要在每个步骤中计算2^i。

pow = 1
for i in xrange(1,9999):
    if search in str(pow):
        print i
        break
    pow *= 2

你可以边计算边进行。这应该能节省很多计算时间。

使用xrange会防止列表的生成，但在这里可能不会有太大的区别。 in可能被实现为二次字符串搜索算法。使用类似于KMP的字符串搜索可能（或可能不）更有效率。

- IVlad

---

此外，应使用xrange而非range。 - TerryA

使用KMP算法进行字符串搜索，我能看到什么样的性能提升？ - user1411838

@user1411838 - 很难说。虽然KMP算法在两个字符串的大小上是线性的，但编程语言中实现的二次算法通常经过了很大的优化，因此差异可能不会很大。您需要进行测试以确保。 - IVlad

@user1411838 - 我不确定。仅通过避免使用 ** 并使用 xrange，您能获得多少增益？您可以进行多线程处理吗？ - IVlad

你可能需要利用一些模式或数学事实来解决这些幂的问题。我会再考虑一下，目前我看不出你还能做什么。如果这个问题来自于一个在线评测网站，你能否提供链接？ - IVlad

Answer 2

更快的方法可能是直接在十进制中计算数字。

def double(x):
    carry = 0
    for i, v in enumerate(x):
        d = v*2 + carry
        if d > 99999999:
            x[i] = d - 100000000
            carry = 1
        else:
            x[i] = d
            carry = 0
    if carry:
        x.append(carry)

然后搜索功能可以变成：

def p2find(s):
    x = [1]
    for y in xrange(10000):
        if s in str(x[-1])+"".join(("00000000"+str(y))[-8:]
                                   for y in x[::-1][1:]):
            return y
        double(x)
    return None

同时请注意，所有2的幂次方的数字直到2的10000次方之前只有1500万个数字，并且搜索静态数据会更快。如果程序不必每次都重新启动，则...

def p2find(s, digits = []):
    if len(digits) == 0:
        # This precomputation happens only ONCE
        p = 1
        for k in xrange(10000):
            digits.append(str(p))
            p *= 2
    for i, v in enumerate(digits):
        if s in v: return i
    return None

使用这种方法，第一次检查需要一些时间，接下来的检查将非常快。

- 6502

---

后缀树比搜索这个巨大的字符串更快，因为查找与这个巨大的字符串的大小无关 - 它只取决于搜索字符串。 - Neil G

Answer 3

只有1万个数字，不需要任何复杂的算法。预先计算好它们并进行搜索即可。这应该只需要1或2秒钟。

powers_of_2 = [str(1<<i) for i in range(10000)]

def search(s):
    for i in range(len(powers_of_2)):
        if s in powers_of_2[i]:
            return i

- Kabie

Answer 4

计算每个2的幂，并使用每个字符串构建后缀树。这样做的时间复杂度是所有字符串大小的线性时间。现在，查找基本上是查询字符串长度的线性时间。

我认为你无法打败这种计算复杂性。

- Neil G

---

这听起来很有趣，如何在Python中编写基本的后缀树？计算幂次方是否相同？ - user1411838

@user1411838，是的，这是相同的代码；只是使用适当的数据结构，以便重复搜索更快。 - Neil G

Answer 5

试试这个

twos = []
twoslen = []
two = 1
for i in xrange(10000):
    twos.append(two)
    twoslen.append(len(str(two)))
    two *= 2

tens = []
ten = 1
for i in xrange(len(str(two))):
    tens.append(ten)
    ten *= 10

s = raw_input()
l = len(s)
n = int(s)

for i in xrange(len(twos)):
    for j in xrange(twoslen[i]):
        k = twos[i] / tens[j]
        if k < n: continue
        if (k - n) % tens[l] == 0:
            print i
            exit()

这个想法是预先计算2的每个幂次、10的每个幂次以及每个2的幂次所需的数字数量。这样问题就被简化为找到最小的i，使得存在一个j，使得从2 ** i中删除最后j个数字后得到一个以n结尾的数字，或者用公式表示为(2 ** i / 10 ** j - n) % 10 ** len(str(n)) == 0。

- sve

---

如果遇到一个不是数字的输入，比如31415926535897932，这个会发生什么？ - user1411838

Answer 6

这里的一个大问题是将二进制整数转换为十进制表示需要时间，其复杂度与位数成二次关系（至少在Python直接进行转换的方式中是如此）。实际上，像@6502在他的回答中所做的那样，伪造自己的十进制算术运算速度更快。

但是，让Python的decimal模块来处理它要快得多——至少在Python 3.3.2下是这样（我不知道Python decimal版本之前有多少C加速内置）。以下是代码：

class S:
    def __init__(self):
        import decimal
        decimal.getcontext().prec = 4000  # way more than enough for 2**10000
        p2 = decimal.Decimal(1)
        full = []
        for i in range(10000):
            s = "%s<%s>" % (p2, i)
            ##assert s == "%s<%s>" % (str(2**i), i)
            full.append(s)
            p2 *= 2
        self.full = "".join(full)

    def find(self, s):
        import re
        pat = s + "[^<>]*<(\d+)>"
        m = re.search(pat, self.full)
        if m:
            return int(m.group(1))
        else:
            print(s, "not found!")

以及示例用法：

>>> s = S()
>>> s.find("1")
0
>>> s.find("2")
1
>>> s.find("3")
5
>>> s.find("65")
16
>>> s.find("7")
15
>>> s.find("00000")
1491
>>> s.find("666")
157
>>> s.find("666666")
2269
>>> s.find("66666666")
66666666 not found!

s.full 是一个具有超过1500万个字符的字符串。它看起来像这样：

>>> print(s.full[:20], "...", s.full[-20:])
1<0>2<1>4<2>8<3>16<4 ... 52396298354688<9999>

因此，该字符串包含每个2的幂，指数跟随在尖括号中的幂后面。 find() 方法构造一个正则表达式来搜索所需的子字符串，然后向前查找幂。

通过试验，我相信几乎任何搜索方式都足够快。获取大幂的十进制表示占用了绝大部分时间。而decimal模块解决了这个问题。

- Tim Peters