0ms Branchless Leetcode 3069 | Py3 & C++ 高速解法

Py3 CPP 速解3069  Distribute Elements Into Two Arrays I

為什麼要寫branchless code?避免 CPU 的分支預測失敗!當代CPU 會預先猜測條件判斷（如 if-else）的結果並繼續往下執行。當預測成功時，猜對了效能極佳，猜錯了會造成時間上的懲罰。利用容器index的True or False達成Branchless code!

[C++ Python3 codes請進]

-------

Why write branchless code? Because CPU mispredictions incur a time penalty. Use boolean indexing (True or False) to achieve branchless code.

[codes on Leetcode]https://leetcode.com/problems/distribute-elements-into-two-arrays-i/solutions/8471181/branchless-loop-beats-100-by-anwendeng-h5c1/

#anwendeng 

----

Time stamps:

00:00 - Introduction to LeetCode 3069

00:17 - Problem simplification and logic breakdown

01:03 - Python 3 implementation (Branchless approach)

02:18 - Running Python test cases (0ms result)

02:39 - C++ solution overview (0ms result)

#LeetCode #Leetcode3069

#Branchless 

#Python

#CPP

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        A=([nums[0]], [nums[1]])
        for x in nums[2:]:
            A[A[0][-1]<=A[1][-1]].append(x)
        return A[0]+A[1]        

class Solution {
public:
    vector resultArray(vector& nums) {
        vector A[2]={{nums[0]}, {nums[1]}};
        const int n=nums.size();
        for(int i=2; i< n; i++){
            A[A[0].back()<=A[1].back()].push_back(nums[i]);
        }
        A[0].insert(A[0].end(), A[1].begin(), A[1].end());
        return A[0];
    }
};