2020年10月27日 星期二
Algorithm_Sort_Heap srot
Algorithm_Sort_Heap srot
tags: Algorithms Sort python
def heapify(input_array, index, bound):
"""將資料結構化為heap
parameters:
input_array: 輸入的未排序陣列
index: 要排序的root
bound: 比較邊界，如果某個root的左、右索引已超過陣列長度就不處理
假設，root的index=n，那其節點索引為
root: n
root_left_node: 2n + 1
root_right_node: 2n + 2
舉例來說，[0, 1, 2, 3, 4, 5, 6]
0
1 2
3 4 5 6
0為root，左邊節點為1，右邊則為2
1為root，左邊節點為3，右邊則為4
heap sort的一半是最後的節點，因此只會比較到陣列一半取上高斯
其餘皆會是最終節點，不需要再比較，所以3456本身是不需要比較的
我們會從2開始比，也就是7/2 = 3 - 1 = 2(因為python的索引初始值為0)
要記得，python的索引是由0開始
root永遠是三個節點中最大的(或最小的)，但節點不考慮大小
5 5
1 2 2 1 左邊兩種情況都可以
"""
# 先預設最大值為root index
largest_idx = index
# print(f'init_array: {input_array}')
# print(f'init_larget_idx: {largest_idx}, value: {input_array[largest_idx]}')
left_idx = index * 2 + 1
# print(f'left_idx: {left_idx}')
right_idx = index * 2 + 2
# print(f'right_idx: {right_idx}')
# 下面的比較，因為我們只關心root是最大的，因此不需要再比較左右兩邊
# 注意到與陣列長度的比較條件必需在前面，不然會引發索引異常
if left_idx < bound and input_array[largest_idx] < input_array[left_idx]:
largest_idx = left_idx
# print(f'l_larget_idx: {largest_idx}, value: {input_array[largest_idx]}')
if right_idx < bound and input_array[largest_idx] < input_array[right_idx]:
largest_idx = right_idx
# print(f'r_larget_idx: {largest_idx}, value: {input_array[largest_idx]}')
# 比較之後，如果最大值的異動，那就調整array的順序
if largest_idx != index:
input_array[index], input_array[largest_idx] = input_array[largest_idx], input_array[index]
# print(f'new array: {input_array}')
# 遞迴處理heapify
heapify(input_array, largest_idx, bound)
def heap_sort(input_array):
"""heap sort"""
array_size = len(input_array)
# heap sort會從底層開始排序上來
# 而且並不會所有的元素都排序，因為n//2 + 1之後的節點都是最終節點
# 只有n//2 + 1之前是root，因此只做這邊的迴圈比較
# 這邊只是做heap的結構
for i in range(array_size // 2 - 1, -1, -1):
heapify(input_array, i, array_size)
# 處理排序
# 我們知道，經過heap過的結構，最大的一定是在最上面(假設是max heap)
# 因此，實作上會將root的部份跟最後的結點做交換，再將n-1做一次heap
for i in range(array_size - 1, 0, -1):
# 每次heap之後都做頭尾的交換
# print(f'heap_sort: {input_array}')
input_array[0], input_array[i] = input_array[i], input_array[0]
# 特別注意到，每一次迭代都會減少一個，因此這邊給的是迴圈中的i，而不是array_size
heapify(input_array, 0, i)
return input_array
下面給出五個資料集在不同資料量下的結果，其中
- l1: 已經排序好的，由小到大
- l2: 已經排序好的，但是逆排序，由大到小
- l3: 亂數生成
- l4: 亂數生成
- l5: 亂數生成
| Heap Sort | 20000 | 40000 | 60000 | 80000 | 100000 |
|---|---|---|---|---|---|
| l1 | 416 ms | 606 ms | 864 ms | 1.23 s | 1.51 s |
| l2 | 255 ms | 721 ms | 876 ms | 1.15 s | 1.64 s |
| l3 | 265 ms | 603 ms | 923 ms | 1.23 s | 1.8 s |
| l4 | 297 ms | 562 ms | 946 m | 1.16 s | 1.59 s |
| l5 | 279 ms | 553 ms | 966 ms | 1.22 s | 1.66 s |
2020年10月26日 星期一
Algorithm_Sort_Merge sort
Algorithm_Sort_Merge sort
tags: Algorithms Sort python
def merge(left_a, right_a):
"""合併兩個陣列"""
def _merge():
while left_a and right_a:
# print('_merge:', left_a, right_a)
# 比較兩個陣列的第一個索引的值那一個比較小就優先回傳
yield (left_a if left_a[0] < right_a[0] else right_a).pop(0)
yield from left_a
yield from right_a
return list(_merge())
def divide(input_array):
"""分割陣列"""
# 取上高斯點做為中點切掉兩個陣列
divide_point = len(input_array) // 2
left_a = input_array[: divide_point]
right_a = input_array[divide_point: ]
return left_a, right_a
def merge_sort(input_array):
"""利用遞迴呼執行分割、合併、排序"""
# print('merge_sort_array:', input_array)
if len(input_array) == 1:
# print('return array:', input_array)
return input_array
left_a, right_a = divide(input_array)
return merge(merge_sort(left_a), merge_sort(right_a))
下面給出五個資料集在不同資料量下的結果，其中
- l1: 已經排序好的，由小到大
- l2: 已經排序好的，但是逆排序，由大到小
- l3: 亂數生成
- l4: 亂數生成
- l5: 亂數生成
| Merge Sort | 20000 | 40000 | 60000 | 80000 | 100000 |
|---|---|---|---|---|---|
| l1 | 261 ms | 585 ms | 805 ms | 1.35 s | 2.18 s |
| l2 | 199 ms | 528 ms | 880 ms | 1.47 s | 2.09 s |
| l3 | 294 ms | 844 ms | 1.52 s | 2.37 s | 3.64 s |
| l4 | 282 ms | 761 ms | 1.45 s | 2.39 s | 3.42 s |
| l5 | 331 ms | 735 ms | 1.5 s | 2.27 s | 3.48 s |
Algorithm_Sort_Insrtion sort
Algorithm_Sort_Insrtion sort
tags: Algorithms Sort python
def insertion_sort(input_array):
"""insertion sort
input_array: list
list內的元素需為數值
return
由小大到排序後的list
"""
if len(input_array) <= 1:
return
# 從第2個element開始處理
for idx, idx_value in enumerate(input_array[1: ]):
# 內圈迴圈使用
inner_idx = idx
while inner_idx >= 0 and idx_value < input_array[inner_idx]:
# 這邊的idx剛好就是j-1的索引
# 判斷兩值的大小，如果索引值(右)比前一個元素(左)小
# 那就將前一個元素複製到索引處
input_array[inner_idx + 1] = input_array[inner_idx]
inner_idx -= 1
# 當兩個索引不同代表異動排序過
if inner_idx != idx:
# 將原始索引值寫入最終停止的索引處
input_array[inner_idx + 1] = idx_value
return input_array
下面給出五個資料集在不同資料量下的結果，其中
- l1: 已經排序好的，由小到大
- l2: 已經排序好的，但是逆排序，由大到小
- l3: 亂數生成
- l4: 亂數生成
- l5: 亂數生成
| Insertion sort | 20000 | 40000 | 60000 | 80000 | 100000 |
|---|---|---|---|---|---|
| l1 | 7ms | 16ms | 25ms | 22ms | 37ms |
| l2 | 1min 31s | 5min 47s | 13min 27s | 24min 18s | 37min 34s |
| l3 | 43.4s | 2min 59s | 6min 52s | 12min 27s | 20min 6s |
| l4 | 43.1s | 3min 2s | 6min 50s | 13min 1s | 19min 52s |
| l5 | 42.9s | 2min 57s | 6min 51s | 12min 42s | 19min 47s |
2020年10月21日 星期三
SAP_ABAP_邊學邊記錄_取得internal table的資料筆數
在ABAP中，如果想要從interlnal table取得目前表內的資料筆數，只需要透過下面的語法就可以完成
DESCRIBE TABLE your_internal_table LINES your_variable.
訂閱：
文章 (Atom)
Algorithm_Sort_Quick sort
tags:
AlgorithmsSortpythonimport random def quick_sort(input_array, is_random=False): """Quick Sort parameters: input_array: 輸入的未排序陣列 is_random: 是否隨機取pivot point 預設情況下是取陣列最後一個元素做pivot point 在worst case的情況下(資料已排序過)，如果沒有亂數取pivot無法成功執行 """ # print(f'input array: {input_array}') array_size = len(input_array) if array_size < 2: # 不處理 return input_array # 取得pivot if is_random: pivot_point = random.randint(0, array_size - 1) else: pivot_point = array_size - 1 pivot = input_array.pop(pivot_point) # print(f'pivot: {pivot}, pivot_point: {pivot_point}') # 寫入比pivot大以及小的資料 greater_pivot = [element for element in input_array if element > pivot] # print(f'greater_pivot: {greater_pivot}') lesser_pivot = [element for element in input_array if element < pivot] # print(f'lesser_pivot: {lesser_pivot}') # print(f'total: {lesser_pivot} + {[pivot]} + {greater_pivot}') # 利用python list相加的特性做遞迴處理 return quick_sort(lesser_pivot, is_random) + [pivot] + quick_sort(greater_pivot, is_random)下面給出五個資料集在不同資料量下的結果，其中