通过插入一个数字获得最大可能数的高效算法

Question

我刚刚编写了下面的算法，通过插入任何特定的数字来获得最大可能的数字

getLargestPossible接收两个参数，其目的是通过将numInsertion插入num中的任何位置来查找最大可能数。例如：

getLargestPossible(623, 5)和getLargestPossible(-482, 5)分别返回6523和-4582

如何以最有效的方式编写此算法

def attachRest(list_int, str_num, index):
    '''
    Converts list_int to list of strings, merges it with str_num 
    (splitted from index) and returns the result as an integer
    '''
    s = [str(i) for i in list_int]
    str_num = str_num[index:]
    s = s + list(str_num)
    num = int("".join(s))
    return num

def getLargestPossible(num, numInsertion):
    '''
    Returns a largest possible number by inserting numInsertion into num
    e.g.: getLargestPossible(623, 5)  returns 6523
          getLargestPossible(-482, 5) returns -4582
    '''
    new_num = []
    isNumberInserted = False
    
    if num > 0:
        str_num = str(num)
        for index, digit in enumerate(str_num):
            if numInsertion > int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
            
        if isNumberInserted is False: #e.g. if num==666 and numInsertion==5, return 6665
            num = num * 10 + numInsertion
            
        print(num)
    else:
        str_num = str(-1 * num)
        for index, digit in enumerate(str_num):
            if numInsertion < int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
    
        if isNumberInserted is False:
            num = num*10 - numInsertion
            print(num)
        else:
            print(-1 * num)

Answer 1

难道你不能简化成这样：

def get_largest_insertion(long_n,n):
    sn=str(abs(long_n))
    n=str(n)
    sign='-' if long_n<0 else '+'
    return(max(int(sign+sn[0:i]+n+sn[i:]) for i in range(len(sn)+1)))


>>> get_largest_insertion(623, 5)
6523
>>> get_largest_insertion(-482,5)
-4582
>>> get_largest_insertion(666,5)
6665

好的，让我们让它更快

通过简单的检查，我相信如果数字为负数，插入将始终是以下之一：

1. 字符串的结尾（例如f(-524242, 8): -5242428)；或
2. 第一个较大数字的左边（例如f(-3251342,2): -23251342或f(-1251342,2): -12251342

对于正数：

1. 字符串的结尾（例如f(345342,2): 3453422)；或
2. 第一个较小数字的左边（例如f(3251342,2): 32521342

您可以修改我的函数，以便它可以一次找到插入点，方法是：

def f3(long_n, n):
    sn=str(abs(long_n))
    sign='-' if long_n<0 else '+'
    n=str(n)
    if sign=='-':
        i=next((i for i,c in enumerate(sn) if c>n), len(sn))
    else:
        i=next((i for i,c in enumerate(sn) if c<n), len(sn))

    return int(sign+sn[0:i]+n+sn[i:])   

现在，让我们以以下内容为基准：

# your original function is f1
# my original is f2
# new one is f3

import time

# ====================
def attachRest(list_int, str_num, index):
    s = [str(i) for i in list_int]
    str_num = str_num[index:]
    s = s + list(str_num)
    num = int("".join(s))
    return num

def f1(num, numInsertion):
    new_num = []
    isNumberInserted = False
    
    if num > 0:
        str_num = str(num)
        for index, digit in enumerate(str_num):
            if numInsertion > int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
                
        if isNumberInserted is False:
            num = num * 10 + numInsertion
            
        return num
    else:
        str_num = str(-1 * num)
        for index, digit in enumerate(str_num):
            if numInsertion < int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
                
        if isNumberInserted is False:
            num = num*10 - numInsertion
            return num
        else:
            return -1 * num

# ===============
        

def f2(long_n,n):
    sn=str(abs(long_n))
    n=str(n)
    sign='-' if long_n<0 else '+'
    return(max([int(sign+sn[0:i]+n+sn[i:]) for i in range(len(sn)+1)]))

def f3(long_n, n):
    sn=str(abs(long_n))
    sign='-' if long_n<0 else '+'
    n=str(n)
    if sign=='-':
        i=next((i for i,c in enumerate(sn) if c>n), len(sn))
    else:
        i=next((i for i,c in enumerate(sn) if c<n), len(sn))

    return int(sign+sn[0:i]+n+sn[i:])       
            
# =====
def cmpthese(funcs, args=(), cnt=100, rate=True, micro=True, deepcopy=True):
    from copy import deepcopy 
    """Generate a Perl style function benchmark"""                   
    def pprint_table(table):
        """Perl style table output"""
        def format_field(field, fmt='{:,.0f}'):
            if type(field) is str: return field
            if type(field) is tuple: return field[1].format(field[0])
            return fmt.format(field)     
        
        def get_max_col_w(table, index):
            return max([len(format_field(row[index])) for row in table])         
        
        col_paddings=[get_max_col_w(table, i) for i in range(len(table[0]))]
        for i,row in enumerate(table):
            # left col
            row_tab=[row[0].ljust(col_paddings[0])]
            # rest of the cols
            row_tab+=[format_field(row[j]).rjust(col_paddings[j]) for j in range(1,len(row))]
            print(' '.join(row_tab))                
            
    results={}
    for i in range(cnt):
        for f in funcs:
            if args:
                local_args=deepcopy(args)
                start=time.perf_counter_ns()
                f(*local_args)
                stop=time.perf_counter_ns()
            results.setdefault(f.__name__, []).append(stop-start)
    results={k:float(sum(v))/len(v) for k,v in results.items()}     
    fastest=sorted(results,key=results.get, reverse=True)
    table=[['']]
    if rate: table[0].append('rate/sec')
    if micro: table[0].append('\u03bcsec/pass')
    table[0].extend(fastest)
    for e in fastest:
        tmp=[e]
        if rate:
            tmp.append('{:,}'.format(int(round(float(cnt)*1000000.0/results[e]))))
            
        if micro:
            tmp.append('{:,.1f}'.format(results[e]/float(cnt)))
            
        for x in fastest:
            if x==e: tmp.append(' ')
            else: tmp.append('{:.1%}'.format((results[x]-results[e])/results[e]))
        table.append(tmp) 
    
    pprint_table(table)  


if __name__=='__main__':
    import sys
    import time 
    print(sys.version)

    funcs=[f1, f2, f3]
    
    cases=(
        (-524242,8),
        (345342,2),
        (-34734573524242,8),
        (71347345345342, 2)
    )
    for ln, n in cases:
        for f in funcs:
            print(f'{f.__name__}{ln, n}: {f(ln,n)}')
        args=(ln, n)
        cmpthese(funcs,args)    
        print()

该基准打印：

3.9.0 (default, Nov 21 2020, 14:55:42) 
[Clang 12.0.0 (clang-1200.0.32.27)]
f1(-524242, 8): -5242428
f2(-524242, 8): -5242428
f3(-524242, 8): -5242428
   rate/sec μsec/pass     f2     f1     f3
f2   19,777      50.6       -37.0% -57.1%
f1   31,402      31.8  58.8%       -32.0%
f3   46,148      21.7 133.3%  47.0%      

f1(345342, 2): 3453422
f2(345342, 2): 3453422
f3(345342, 2): 3453422
   rate/sec μsec/pass     f2     f1     f3
f2   19,671      50.8       -38.4% -56.5%
f1   31,916      31.3  62.2%       -29.5%
f3   45,260      22.1 130.1%  41.8%      

f1(-34734573524242, 8): -347345735242428
f2(-34734573524242, 8): -347345735242428
f3(-34734573524242, 8): -347345735242428
   rate/sec μsec/pass     f2     f1     f3
f2   10,331      96.8       -38.1% -72.6%
f1   16,689      59.9  61.5%       -55.7%
f3   37,679      26.5 264.7% 125.8%      

f1(71347345345342, 2): 721347345345342
f2(71347345345342, 2): 721347345345342
f3(71347345345342, 2): 721347345345342
   rate/sec μsec/pass     f2     f1     f3
f2   10,579      94.5       -67.7% -77.4%
f1   32,779      30.5 209.8%       -29.9%
f3   46,743      21.4 341.8%  42.6%      

所以，同样的方法，但检查与蛮力使其速度提高了2到3倍