代码之家  ›  专栏  ›  技术社区  ›  ep84

Python中处理扩展线性序列的快速(最快)方法

  •  0
  • ep84  · 技术社区  · 10 月前

    我有以下条件:

    • 数字u(0)=1是u中的第一个。
    • 对于u中的每个x,则y=2*x+1和z=3*x+1也必须在u中。
    • 在u中没有其他数字。
    • 不应出现重复项。
    • 数字必须按升序排列

    例如:u=[1,3,4,7,9,10,13,15,19,21,22,27,…]

    程序希望我给出给定索引下成员的值。

    我已经找到了使用insort解决这个问题的方法,我还将一个最小的二叉搜索树组合在一起。不幸的是,这个过程需要比我现有的更快,我不知道下一步该怎么办。我以为BST能做到,但速度还不够快。

    这是我的BST代码:

    class BSTNode:
        def __init__(self, val=None):
            self.left = None
            self.right = None
            self.val = val
    
        def insert(self, val):
            if not self.val:
                self.val = val
                return
    
            if self.val == val:
                return
    
            if val < self.val:
                if self.left:
                    self.left.insert(val)
                    return
                self.left = BSTNode(val)
                return
    
            if self.right:
                self.right.insert(val)
                return
            self.right = BSTNode(val)
    
        def inorder(self, vals):
            if self.left is not None:
                self.left.inorder(vals)
            if self.val is not None:
                vals.append(self.val)
            if self.right is not None:
                self.right.inorder(vals)
            return vals
    

    这是我的功能:

    from sys import setrecursionlimit
    
    def twotimeslinear(n):
        #setrecursionlimit(2000)
        i = 0
        u = [1]
        ended = False
    
        bst = BSTNode()
        bst.insert(1)
        while i < n and not ended:
            
            for j in range(2, 4):
                k = 1
                cur = j * bst.inorder([])[i] + 1
                bst.insert(cur)
                
                if len(u) == n:
                    ended = True
                    break
            i+= 1
        return bst.inorder([])[n]
    

    我只需要指示我可以做些什么来加快这个过程。只要我知道我错过了什么,我就能解决这个问题。我可能忽略了一些更好的数据结构,但我甚至不知道该找什么。谢谢你的帮助。

    2 回复  |  直到 10 月前
        1
  •  3
  •   no comment Pratyush Goutam    10 月前

    生成并合并ys和zs:

    from heapq import merge
    from itertools import groupby
    
    def twotimeslinear(n):
        u = [1]
        ys = (2*x+1 for x in u)
        zs = (3*x+1 for x in u)
        for x, _ in groupby(merge(ys, zs)):
            u.append(x)
            if n < len(u):
                return u[n]
    
    print(*map(twotimeslinear, range(20)))
    

    Attempt This Online!

    您的限额指数60000需要~0.05秒,指数1000000需要~0.7秒。

    备选基本实施方案:

    def twotimeslinear(n):
        u = [1]
        i = j = 0
        while n >= len(u):
            y = 2*u[i] + 1
            z = 3*u[j] + 1
            m = min(y, z)
            u.append(m)
            if y == m:
                i += 1
            if z == m:
                j += 1
        return u[n]
    
    print(*map(twotimeslinear, range(20)))
    

    Attempt This Online!

    还有另一个版本,向它投掷了大量电池:-)

    from heapq import merge
    from itertools import groupby, tee, chain, islice, repeat
    from operator import itemgetter, mul, add
    
    def twotimeslinear(n):
        parts = [[1]]
        whole = chain.from_iterable(parts)
        output, feedback1, feedback2 = tee(whole, 3)
        ys = map(1 .__add__, map(2 .__mul__, feedback1))
        zs = map(add, map(mul, repeat(3), feedback2), repeat(1))  # different way just for fun
        merged = map(itemgetter(0), groupby(merge(ys, zs)))
        parts.append(merged)
        return next(islice(output, n, None))
    
    print(*map(twotimeslinear, range(20)))
    

    用Python代码设置后 完全用C代码编写。这是我的一个愚蠢的爱好。

    Attempt This Online!

        2
  •  -1
  •   Suramuthu R    10 月前
    # argument N the index 
    
    
    def get_my_seq(u,N):
    
        ls = [u]
        i = 0   
        while i >= 0 and len(ls) <= N:
            val_1 = (ls[i]*2) + 1
            val_2 = (ls[i]*3) + 1
            if val_1 not in ls:
                ls.append(val_1)
            if val_2 not in ls:
                ls.append(val_2)
                i = i -1
            i += 1
        ls = sorted(ls)
        print(ls)
        return ls[N]
        
    r = get_my_seq(3,30)
    print(r) 
    

    输出:

    # Seq for confirmation
    [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 64, 67, 81, 82, 85, 93, 94, 121, 139]
    
    # Value of the given index
    121