Week_five_assignment

base64

解法一

暴力求解法：1、字元串每3步一切，得到目标字元串target，将其放入清單

2、周遊清單，按個将target轉為位元組序列

2、正常情況：位元組序列前補零得到24個位元組序列，6步一切得到4個子節序列b_character

3、尾部特殊情況：位元組序列target不足3個字元，位元組序列前補零，每缺一個字元，後面補8個零，最多補16個零，然後6補一切，得到位元組序列b_character

4、循環處理b_character，正常4次循環；尾部特殊情況，target長度為2，切3次，避開補的零；target長度為2，切2次，避開補的零。

5、’=‘号追加，target=2，補一個’=’，target=1，補兩個’=‘

缺點：

多次周遊、多個清單和字元串，效率極低

import string
base64 = string.ascii_uppercase + string.ascii_lowercase + string.digits + '+' + '/'   
# 得到base64字元串

word = '''Man is distinguished, not only by his reason, but by this singular passion 
from other animals, which is a lust of the mind, that by a perseverance of delight in 
the continued and indefatigable generation of knowledge, exceeds the short vehemence 
of any carnal pleasure'''

start = 0
step = 3
stop = start + step
target_lst = []

while True:
    target = word[start:stop]  # 每三位切割字元串
    if len(target) == 0:  # 如果沒切到，直接終止
        break
    target_lst.append(target)  # 将得到的字元串依次放入清單，
    start += step    
    stop = start + step
    if len(target) < 3:   # 如果切割的字元串長度小于3，得到全部字元串，終止循環
        break
    
# print(target_lst,'1111')
str_target = ''   # 連結整個base64解碼後的字元串

for i in target_lst: # 周遊清單，按個對字元串進行處理
    int_target = int.from_bytes(i.encode(),'big') # 得到字元串的十進制
    length = len(i)   # 取字元串長度，判斷長度，小于三進行特殊處理
    
#     print(int_target,"22222")

    if length == 3:  # 字元串長度等于3，前補零，得到目标二進制
        b_character = '{:024b}'.format(int_target)
        # print(b_character,"33333") 

    elif length == 2: # 字元串長度等于2，前後補零，得到目标二進制
        b_character = '{:016b}'.format(int_target) + 8 * '0'

    elif length == 1:  # 同上
        b_character = '{:08b}'.format(int_target) + 16 * '0'
        
    start = 0
    step = 6
    stop = start + step
    
    # print(length,'4444')
    for _ in range(length+1):  # 計數，24為轉為4個6位,如果length<3，隻能切2次或者3次
    						   # 正好避免切補零的部分
        index = int(b_character[start:stop],2)  # int函數，将二進制字元串轉為十進制
        str_target += base64[index]  # base64中，索引查找求得的十進制，即為base解碼
        start += step
        stop = start + step
    else:   # 最後判斷，如果目标字元串的長度小于3，補’=‘
        if length < 3:    
            while length:  # 長度2，補1個’=‘，長度1，補2個'='
                str_target += '='    # 目标字元串補'='
                length += 1

                if length == 3:   length等于3，循環終止
                    break

print(str_target)
           

解法二

1、判斷字元串能否被3整除，整除不處理，未整除，餘數為1，補2個null，餘數為2，補1個null,因為null在記憶體中是0

2、null不可見字元，使用十六進制的位元組表示方式’\x00’

3、3步一切，放入目标字典（優化點，步需要放入字典，而是取一個字元串，處理一次）

4、位與63(二進制111111），技巧：n位數字位與n位的二進制1，得到的還是原數字。位與0，得0.

5、将目标位元組序列右移6位，得到下一次的目标位元組序列

6、從後往前且，先切的往後方

7、用切片将補的位置全部換成’='号（優化點，碰見特殊字元串單獨處理，最後再連在一起）

優點:

1、直接補齊字元串，不用特殊補零

2、位與、右移，不用轉二進制，提高切割效率

缺點：

1、将切好的字元串放入清單，周遊處理

2、字元串拼好之後，特殊情況：切片生成新的字元串

3、3個大容器，記憶體開辟空間過大，效率低

import string
base64 = string.ascii_uppercase + string.ascii_lowercase + string.digits + '+' + '/'

word = '''Man is distinguished, not only by his reason, but by this singular passion 
from other animals, which is a lust of the mind, that by a perseverance of delight in 
the continued and indefatigable generation of knowledge, exceeds the short vehemence 
of any carnal pleasure'''

target_lst = []  # 存放目标字元串
length = len(word)  

div,mod = divmod(length,3)  # div為循環次數，mod用來判斷字元串不足3個，做特殊處理
# print(div,mod)

for i in range(div):  # 通過步長，得到目标字元串，并且追加到目标清單中
    target_lst.append(word[3 * i:3 * (i + 1)]) # 此處可優化，不需要放入清單，隻需要每三位轉一下，可以提高運作效率
    
if mod != 0:  # 特殊情況，mod=1，字元串一個，需要補兩個null,mod=2,需要補一個null
    target_lst.append(word[-mod:] + (3 - mod) * '\x00') # null不可見，'\x00'十六進制得到
    
# print(target_lst)

word_base64 = '' # 用于連結解碼後的字元串

for val in target_lst: # 周遊目标清單，按個處理
    code = val.encode()  
    num = int.from_bytes(code,'big')  # 得到字元串的十進制表達
    word = ''  # 連結每次解碼後的字元
    
    while num:  # num不為零進入，為零退出       
        index = num & 63   # 核心：63的二進制為111111,位與得到後六位（技巧：與1位與得到原數）
        word = base64[index] + word  # 從後向前切，切到的值向後追加
        num = num >> 6 # 向右位移6位，得到下一次目标位元組序列，依次循環

    word_base64 += word  # 得到目标解碼字元串

if mod != 0:  # 尾部特殊情況處理
    miss = 3 - mod    # 補一個null，0~-1 + ’=‘，補兩個null,0~-2 + 2個"="
    word_base64 = word_base64[:-miss] + miss * '=' # 此處可優化，再次生成一個字元串，占用過多記憶體
#     lst = list(word_base64)
#     lst[-miss:] = miss *'='
    
#     word_base64 = ''.join(lst)

print(word_base64) 
           

cache過期清除

解法一

1、模仿源代碼：make_key函數專門用來生成key，連接配接args和kwargs，以及裡面元素的資料類型

2、得到被裝飾函數的運作時間，使用二進制組儲存在value中，value[0]為值，value[1]為時間對象

3、如果delta時間超過10，清單中追加k。之後周遊清單，删除cache中的key

3、設定哨兵sentiel，get字典key，傳回值不為哨兵，直接傳回value。傳回值為哨兵，說明cache中無此kv對，傳回被裝飾函數的傳回值，得到時間對象，封裝成二進制組作為value，建立kv對

4、最後傳回value[0]

5、設定哨兵sentinel，解決函數傳回值為0，cache_get的值為0無法進入條件的問題。

缺點：

1、時間設定死了，無法更改

2、每次調用都要周遊字典，時間複雜度O(n)，效率極低

import datetime,functools,time  

def make_key(key_tup,kwargs,typed=False):
    key = ()
    kw_key = ()

    if args:  # 周遊args元組,連接配接指派給key
        key += key_tup

    if kwargs: # 字典不為空
        kw_key += tuple(kwargs) # 周遊字典的keys,轉為tuple
        kw_key += tuple(kwargs.values())  # 周遊字典的values,轉為tuple
        print(kw_key) # 列印檢視kw_key
        if key == kw_key:  # 兩者有可能相等？
            pass
        else:
            key += kw_key  # 連接配接指派給key
                    
    if typed:  # 類型不為False
        key += tuple(type(i) for i in args)  # （新技巧：生成器得資料類型，tuple疊代）
		# 将args中的元素周遊，type()得到資料類型并連接配接。
        if kwargs: # 字典不為空
            key += (type(i) for v in kwargs.values()) # 周遊字典，得到資料類型

    elif len(key) == 1 :  # 特殊情況，key長度位1，直接傳回元組裡面的第一個值
        return key[0]

    return key

def cache(fn):
    cache = {} # 緩存字典，閉包不消亡
    cache_get = cache.get  # 将字典get方法指派（源代碼習得新技巧）
    sentienl = object()   # 哨兵，object(),祖宗對象（源代碼習得新技巧）
    @functools.wraps(fn)
    def wrapper(*args,**kwargs):
        key = make_key(args,kwargs,typed=False) # 生成字典key
              
        lst = []   # 每次進入需要空清單，放删除的key，字典視圖對象，周遊中不能改變size
        for k,v in cache.items(): # 循環需要放在此處，調用函數就周遊，發現超過時間的就删除（缺點：每次調用都周遊，時間複雜度O(n),效率極低）
            delta = (datetime.datetime.now() - v[1]).total_seconds()
            # 得到時間差timedelta對象
            if delta > 10: # 固定死，內插補點大于10秒，将删除的k追加到lst中
                lst.append(k)
                print(lst)

        for key in lst: # 周遊清單，删除cache中的key                                     
                del cache[key]  # 集合、字典在周遊的時候不能改變size
                
        result = cache_get(key,sentinel)  # 通過key取值          
        if result is not sentinel: # 如果不為哨兵，說明cache字典有key,有value
            return result[0]  # result二進制組，0為值，1為datetime.datetime對象
        else: # 為哨兵，說明cache中無key
            start = datetime.datetime.now() # 生成時間
            result = fn(*args,**kwargs)  # fn函數調用
            cache[key] = (result,start)    # cache建立kv對

        return result,cache  # 檢視cache結果
    return wrapper
           

解法二

1、函數的形參個數、位置都是固定的，得到函數的參數，組成前置的key（元組）

2、如果函數參數全有預設值，則将預設值按照形參順序依次連接配接成key

3、進入make_key函數，判斷實參是否在key中，在則不處理，不在則連接配接成key

4、此時的key元素為形參名、預設值和實參，解決傳入實參和預設值一樣的問題。

5、實參關鍵字傳參位置打亂，但是形參順序是固定的，隻需要判斷值在不在key裡面即可

6、将duration柯裡化，可以設定duration的時長，決定删除時間

缺點：

1、每次進入周遊字典，效率低下

2、可以将前置key的生成放在make_key中

3、沒有實作(4,5) 和(5,4)一樣的功能

優化：

給cache一個時間，調用之後再定點清空cache

import datetime,functools,time,inspect

def make_key(key_tup,kwargs,typed=False):

#     if key_tup:
#         key += key_tup

    if kwargs:  # 如果字典不為空
        lst = []   
        for _,v in kwargs.items(): # 周遊字典的value
            if v not in key_tup:   # 判斷其是否在key_tup中，不在，則與key_tup連結，解決傳入一個位置參數
                key_tup += (v,)    # 修正，可以直接和（v,)相連，（v,)為單個元組的表達方式，
#                 lst.append(v)      # 和一個關鍵字傳參的問題
                                    # 因為v不能直接和tuple連結，所有使用了一個lst               
#         key_tup += tuple(lst)                
                    
    if typed:
        key_tup += tuple(type(i) for i in key_tup)
            
    key = key_tup
    print(key)

    if len(key) == 1 :
        return key[0]

    return key

def cache1(duration=100):
    def cache_inner(fn):
        cache = {}
        cache_get = cache.get
        sentinel = object()

        @functools.wraps(fn)
        def wrapper(*args,**kwargs):
            nonlocal hits,misses
            key_tup = ()   
            key_tup += tuple(inspect.signature(wrapper).parameters.keys())
            # 獲得函數簽名的parameters中的key，即形參的變量名，與空元組連結，組成前置的key
            # 優化點：可以将其移到make_key函數中
            if fn.__defaults__:   # 判斷fn的預設值是否為非空，非空則将預設值與key_tup連結，組成key
                key_tup += fn.__defaults__
            else:                 # 如果為空，則将傳入的實參與key_tup連結，組成key
                key_tup += args               
 
            key = make_key(key_tup,kwargs,typed=False)          
			# 解決kwargs的問題
            lst = []   # 每次進入就周遊，是以是空清單就可以
            for k,v in cache.items():      # 這個循環需要放在前面，進入字典就周遊，發現超過時間的就删除
                delta = (datetime.datetime.now() - v[1]).total_seconds()
                if delta > duration: # 周遊字典，查詢v裡面時間，并得到delta對象
                    lst.append(k)    # duration柯裡化成函數的參數，可以設定删除時間
#                     print(lst)

            result = cache_get(key,sentinel)
            for key in lst:                                      
                    del cache[key]  # 集合在周遊的時候也不能改變size

            if result is not sentinel: 
                return result[0]   # result是一個二進制組，索引0為值，索引1為時間
            else:
                start = datetime.datetime.now()
                result = fn(*args,**kwargs)
                cache[key] = (result,start)    

            return result,cache
        return wrapper
    return cache_inner