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

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

linear-algebra containers data-structures performance python

ep84 · 技术社区 · 2 年前

我有以下条件:

数字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 回复 | 直到 2 年前

no comment Pratyush Goutam 2 年前

生成并合并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!

-1

Suramuthu R 2 年前

# 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