tags: Binary Search,LeetCodeNJ YouTube: https://www.youtube.com/watch?v=LPFhl65R7ww The most difficult thing is doing binary search among two sorted arrays, in this video Tushar Roy given us a straightforward method of how to do binary search among tow sorted arrays. Assume we have two sorted arrays, X and Y, and cut them between at x2,x3 and y3,y4: If we meet the conditions: x2 <= y3 y2 <= x3 then we find the median postion, as the merged arrays of the four elements may be order by: ...

tags: Algorithm,Data Structures Make my best effort to move to Nanjing for my son. This is a successor of LeetCode101.

tags: Starcoin Web3 StarTrek,Blockchain Overview Block is the basic element in a blockchain system, as we known blockchain system is just a ledger, which means a bookkeeping1 that recording of financial transactions. In the blockchain system, those transactions are stored in the blocks. In each block, the data stored in may look like: TXN FROM TO VALUE #0 God Cale 100 #1 Cale Alice 10 #2 Alice Bob 1 #3 Bob Mike 0.5 Then what’s a blockchain? Just simply chain the blocks together, usually add a field to point to its parent: ...

tags: Merkle tree,Starcoin Web3 StarTrek

tags: Starcoin Web3 StarTrek,Sparse Merkle Tree,Merkle tree,LSM-Tree,Account-Model Blockchain Systems source: Gao, Zhenhuan, Yuxuan Hu, and Qinfan Wu. “Jellyfish Merkle Tree,” n.d., 12. JMT(Jellyfish Merkle Tree) a LSM-tree based Implementation of Sparse Merkle Tree Inspired by Patricia Merkle Tree and has been implemented in Rust, but it is language-independent. Merkel tree fits pretty well as an authenticated key-value store holding a huge amount of data in a tamper-proof way. Two major concerns where people have been trying to achieve some enhnacements: ...

tags: Starcoin Web3 StarTrek, Proof-of-work Generate nonce (random data) as salt to join to the data of block to be hash. The goal is to find a hash value that less than target. The target is influenced by difficulty. As the difficulty gets bigger and the target will be smaller, which means more difficult to find. pub fn difficult_to_target(difficulty: U256) -> U256 { U256::max_value() / difficulty }

tags: Starcoin Web3 StarTrek,Blockchain source: Wikipedia: Merkle tree Starcoin Cookbook What is a Merkle tree. Merkle tree is a hash tree, named after Ralph Merkle, who patented in 1979. Most implementations of them are binary, which means two child nodes under each node. Why the merkle tree is important to the peer-to-peer network? The main purpose of a merkle tree is to ensure the data we received from a peer-to-peer network are undamaged and unaltered, it’s important as the data were splitted into many blocks and stored in multiple nodes in the network. ...

tags: Starcoin Web3 StarTrek The documentation of Starcoin are written in multiple places: The Developers Documentation on the main site English Version Chinese Version The Starcoin Cookbook English Version Chinese Version

tags: Starcoin Web3 StarTrek Why compile starcoin from source? Why not download a released binary? Because I want to contribute code to it, maybe in the future. But the toolchain is awesome, the progress is very simple. Just two steps: Clone the code from GitHub git clone git@github.com:starcoinorg/starcoin.git Run scripts/dev_setup.sh: cd starcoin ./scripts/dev_setup.sh Then we are ready to compile: cargo build Wait? You haven’t install Rust yet? Please refer to Getting started. ...

tags: Web3 Learn journal of Starcoin Web3 StarTrek Program, check the follow “Links to this note”.

tags: ipfs source: https://blogchain.app/home

source: https://github.com/ipfs/ipfs site: https://ipfs.io/

Some words that I always forget util I wrote it down: discipline collapse phantom

tags: High Performance,SIMD source: Lemire, Author Daniel. “Fast Bitset Decoding Using Intel AVX-512.” Daniel Lemire’s Blog (blog). Accessed May 12, 2022. https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/.

tags: Degree source: evanprodromou. “Master’s Degree in Computer Science.” Evan Prodromou’s Blog (blog), May 4, 2022. https://evanp.me/2022/05/04/masters-degree-in-computer-science/.

tags: Degree source: “【01B0801】 计算机及应用（独立本科段）.” Accessed May 6, 2022. http://zkxcx.bjeea.cn/portal/kszylb.jsp?zydm=01B0801&amp;tab=2. Required Courses Code Name Credit Type Level1 Status2 Free Online Courses 03708 中国近现代史纲要 2 Political 5 pending 03708 马克思主义基本原理概论 4 Political 5 pending 00015 英语（二） 14 Basic 1 passed 00023 高等数学（工本） 10 Basic 7 pending 02197 概率论与数理统计（二） 3 Basic 7 pending 02324 离散数学 4 CS 7 pending 腾讯课堂 04737 C++程序设计 3 CS 1 pending 04738 C++程序设计（实践） 2 CS - pending 02326 操作系统 4 CS 2 pending 02327 操作系统（实践） 1 CS - pending 02331 数据结构 3 CS 2 pending 04734 数据结构（实践） 2 CS - pending 02325 计算机系统结构 4 CS 3 pending 04735 数据库系统原理 4 CS 1 pending 04736 数据库系统原理（实践） 2 CS - pending 02333 软件工程 3 CS 3 pending 02334 软件工程（实践） 1 CS - pending 04741 计算机网络原理 4 CS 2 pending 04747 Java语言程序设计（一） 3 CS 1 pending 04748 Java语言程序设计（一）（实践） 1 CS 1 pending 10027 计算机及应用专业毕业设计 0 CS 1 wait Summary: ...

tags: Degree, Career I haven’t got a CS degree, it wasn’t a big deal when I was yonger, as I was cheap and many employers could affort, and didn’t care too much about it. But now days, when I’m 30+ years old, and not cheap anymore. The employers who can affort me are much less. And most of them are required a CS degree, so the degree is important to me now. ...

tags: Degree source: Engineer, Lowly Midwestern. “My Experience Getting a Tech Job with No Degree or Relevant Work Experience.” Substack newsletter. Lowly Midwestern Engineers’ Newsletter (blog), May 2, 2022. https://lowlyswe.substack.com/p/my-experience-getting-a-tech-job.

tags: Degree source: “How I Got a Computer Science Degree in 3 Months for Less Than $5000 | Miguel Rochefort.” Accessed April 28, 2022. https://miguelrochefort.com/blog/cs-degree/.

tags: Career

tags: SIMD,High Performance source: “Luhn Algorithm Using SWAR and SIMD.” Accessed May 5, 2022. https://nullprogram.com/blog/2022/04/30/. 3x increase after used SIMD.

tags: SSE/AVX/AVX2/AVX512,High Performance source: Lemire, Author Daniel. “Removing Characters from Strings Faster with AVX-512.” Daniel Lemire’s Blog (blog). Accessed May 5, 2022. https://lemire.me/blog/2022/04/28/removing-characters-from-strings-faster-with-avx-512/. It’s 21.25 times faster with AVX-152: 0.4 GB/s to 8.5 GB/s.

tags: Emacs,GnuPG Pinentry,GnuPG,GnuPG Agent There is a little bit more background here: I’m using Windows Subsystem Linux(WSL) now, which means I was running Emacs in a virtual machine with Debian Linux distro. And also I ran Emacs in GUI mode with WSL, the pinentry for GnuPG Agent is: /usr/bin/pinentry-gtk2, everything was prefect. This morning I couldn’t commit with Magit in Emacs, when I was running my Emacs in Terminal Text Mode. The first thing I had done is change the pinentry: ...

tags: Unix,Tools

tags: GnuPG

tags: GnuPG,GnuPG Agent

tags: Data Structures,Algorithm

tags: Algorithm,Tree,Graph source: https://en.wikipedia.org/wiki/Minimum%5Fspanning%5Ftree

tags: High Performance source: https://en.wikipedia.org/wiki/Non-uniform_memory_access

tags: Linux,Network,Tools netstat -s: show network status(errors) # show udp status $ netstat -s --udp Udp: 437.0k/s packets received 0.0/s packets to unknown port received. 386.9k/s packet receive errors 0.0/s packets sent RcvbufErrors: 123.8k/s SndbufErrors: 0 InCsumErrors: 0

tags: Linux,Network,TCP,UDP,Tools ethtool -S: Reveal where the packets actuaaly went receiver$ watch 'sudo ethtool -S eth2 |grep rx' rx_nodesc_drop_cnt: 451.3k/s rx-0.rx_packets: 8.0/s rx-1.rx_packets: 0.0/s rx-2.rx_packets: 0.0/s rx-3.rx_packets: 0.5/s rx-4.rx_packets: 355.2k/s rx-5.rx_packets: 0.0/s rx-6.rx_packets: 0.0/s rx-7.rx_packets: 0.5/s rx-8.rx_packets: 0.0/s rx-9.rx_packets: 0.0/s rx-10.rx_packets: 0.0/s

tags: Linux,High Performance,Network,ethtool source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. What are Multi-queue NICs RX queue was used to pass packets between hardware and kernel. Now days NICs support multiple RX queues: Each RX queue is pinned to a separate CPU. Multi-queue hashing algorithms Use a hash from packet to decide the RX queue number. The hash is usually counted from a tuple (src IP, dst IP, src port, dst port). This guarantees that packets for a single flow will always end up on exactly the same RX queue, and reordering of packets within a single flow can’t happen. ...

tags: Network,Linux,Tools

tags: Network,UDP,High Performance,iptables,ethtool,netstat,NUMA source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. Keys: Make sure traffic won’t be interfered with by the iptables iptables -I INPUT 1 -p udp --dport 4321 -j ACCEPT iptables -t raw -I PREROUTING 1 -p udp --dport 4321 -j NOTRACK #+end_src[[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]] 2. The first bottleneck ​ + All packets are received by a signal RX queue, checked out with =ethtool -S=. ​ + How to solve: according to [[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]], change the hash algorithm with =ethtool=: #+begin_src bash ethtool -N eth2 rx-flow-hash udp4 sdfn Multiple threads with NUMA, and with multiple receiver ips to fit in multi-queue hash algorithm. Also note that there is a lock contention on the UDP receive buffer side, see Rivera, Diego, Eduardo Acha, Jose Piquer, and Javier Bustos-Jimenez. “Analysis of Linux UDP Sockets Concurrent Performance.” In 2014 33rd International Conference of the Chilean Computer Science Society (SCCC), 65–69. Talca: IEEE, 2014. https://doi.org/10.1109/SCCC.2014.8. ...

tags: Network

tags: Network

tags: Distributed Systems

tags: C/C++ Capture a map with reference If we capture a map by value, then we can’t use the operator []: unordered_map<int, int> freq; // Won't compile // auto comp_by_map = [freq](const int& a, const int& b) { return freq[a] < freq[b];}; auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b];};

tags: Hash Table,Heap (data structure),LeetCode101,Priority Queue,C++ Lambda class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> freq; // Note that: we need caputre a map by reference, // otherwise we can't use the operator[]. // See also: https://stackoverflow.com/a/6281071 auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b]; }; // Note that: here we need pass our lambda /comp_by_map/ to the // constructor of std::priority_queue. priority_queue<int, vector<int>, decltype(comp_by_map)> pq(comp_by_map); for (auto n: nums) { freq[n] = freq.find(n) == freq.end() ? 1 : freq[n] + 1; } for (auto iter: freq) { pq.push(iter.first); } while (k > 0) { res.push_back(pq.top()); pq.pop(); k--; } return res; } };

tags: LeetCode101,In-place Travel array in reverse order, and record how many times need to swap, which is how many elements not equal val. class Solution { public: int removeElement(vector<int>& nums, int val) { int k = 0; for (int j = nums.size() - 1; j >= 0; --j) { if (nums[j] == val) { for (int i = 0; i < k; ++i) { swap(nums[i + j], nums[j + i + 1]); } } else { k++; } } return k; } };

tags: Two Pointers,Three Pointers,LeetCode101,Sorting Based on: LeetCode101: 167. Two Sum II - Input Array Is Sorted LeetCode101: 15. 3Sum We create a new loop: class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int T, S, r, l; for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.size(); ++j) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } l = j + 1; r = nums.size() - 1; T = target - nums[i] - nums[j]; while (l < r) { S = nums[l] + nums[r]; if (S == T) { res.push_back({nums[i], nums[j], nums[l], nums[r]}); while (l < r && nums[l] == nums[l + 1]) { l++; } while (l < r && nums[r] == nums[r - 1]) { r--; } l++; r--; } else if (S < T) { l++; } else { r--; } } } } return res; } };

tags: Priority Queue,LeetCode101 Using a min heap to keep k elements, top is the Kth largest element. class KthLargest { private: // min heap priority_queue<int, vector<int>, std::greater<int>> pq; int K; public: KthLargest(int k, vector<int>& nums) { K = k; for (auto n: nums) { add(n); } } int add(int val) { pq.push(val); while (pq.size() > K) { pq.pop(); } return pq.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

tags: Heap (data structure),LeetCode101 Find top k values, classical heap problems. Here we need find top 2 values, and pop them from heap, then we will meet two cases: If they are not same, put back the differ between them, continue. Otherwise, continue directly.

tags: LeetCode101,Sorting,Two Pointers Key ideas: Move both sides to inwards. If the sum value less than target, move left pointer. Otherwise move right poinger. class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int S, l = 0, r = numbers.size() - 1; vector<int> res(2, 0); while (l < r) { S = numbers[l] + numbers[r]; if (S == target) { break; } if (S < target) { l++; } else { r--; } } res[0] = l + 1; res[1] = r + 1; return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas see LeetCode101: 15. 3Sum class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = INT_MAX, l, r, sum, T, res; for (int i = 0; i < nums.size(); i++) { l = i + 1; r = nums.size() - 1; T = target - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (abs(sum - T) < closest) { res = sum + nums[i]; closest = abs(sum - T); } if (sum == T) { return target; } if (sum < T) { l++; } else { r--; } } } return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas: Sort the nums first. Then, we travel the nums, pick current element as nums[i], and apply LeetCode101: 167. Two Sum II - Input Array Is Sorted to the remains. We skip the same numbers to avoid duplicate. class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int l, r, sum, T; vector<vector<int>> res; for (int i = 0; i < nums.size(); i++) { // Skip same numbers to avoid duplicate if(i > 0 && nums[i] == nums[i-1]) { continue; } l = i + 1; r = nums.size() - 1; T = 0 - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (sum == T) { res.push_back({nums[i], nums[l], nums[r]}); // Skip same numbers in each side to avoid duplicate while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum < T) { l++; } else { r--; } } } return res; } };