Go Reflect

Solana 101: 5. Escrow dApp

Solana 101: 3. Create a SPL Token

Solana 101: 4. Create a SPL NFT

Solana 101: 2. Anchor

Solana 101: 1. Develop Model

Solana 101: 0. Prelude

tags: Solana 101: Create an Escrow dApp 聊聊区块链 一个完整的区块链系统生态: 主币:进行 gas 费结算:BitCoin / ETH / TRX 等等 节点服务(JSONRPC 2.0):提供数据查询、广播交易,交易广播(P2P -> 挖矿节点); 交易验证:挣取 gas 费,出块奖励(挖矿); PoW(Proof of Work):通过算力证明提供交易验证(出块);sha256(nonce + body) -> sha256 import hashlib from typing import Tuple raw_block = b'block data' dificulty = 5 def proof_my_work(dificulty, raw_block) -> Tuple[int, str]: nonce = 1 while True: body = bytes(nonce) + raw_block h = hashlib.sha256(body) hex_value = h.hexdigest() if hex_value[:dificulty] == '0' * dificulty: return nonce, hex_value nonce += 1 proof_my_work(dificulty, raw_block) PoS(Proof of Stake):通过质押主币提供交易验证,一旦被发现作弊则扣除质押的主币; 链浏览器:通过 Web UI 进行链上数据查询; 钱包 == 私钥:资产证明,交易授权,公钥导出地址,私钥则是证明拥有该地址; 智能合约(Smart Contract):对资产进行编程; 代币(Tokens):基于智能合约实现,Fungible Tokens(ERC20 / TRC20) 和 Non-Fungible Tokens (ERC721) dApp:通过桥接钱包和链上智能合约实现一定的链上操作; 从智能合约来看各个区块链生态之间的区别 主要是虚拟机的区别,为了执行智能合约,区块链系统需要虚拟机来执行代码,目前主流的虚拟机包括:

Solana 101: Create an Escrow dApp

Python lambda generate bitmap

GTK Debug Mode

macOS Cheatsheet

Cheatsheet

PostgresQL

PostgresQL Cheatsheet

GnuPG Agent Cheatsheet

DeFi from Scratch

tags: DeFi, Blockchain, Uniswap, Uniswap V3 I need derive price from decentralized exchanges, and I have finished some research about Uniswap v3. It’s brand new for me, and after that I want to share some ideas about DeFi, and I think it would be helpful for you to understand Uniswap and some other decentralized exchanges. DeFi from Scratch We exchange stuffs very often, and we can exchange tokens in a centralized exchange.

Uniswap V3 Tick

Uniswap V3

DeFi

Uniswap

Non-Fungible Tokens vs. Fungible Tokens

tags: Blockchain,Ethereum source: “Graphical Guide to Understanding Uniswap - EthHub.” Accessed August 23, 2022. https://docs.ethhub.io/guides/graphical-guide-for-understanding-uniswap/. ERC20 tokens are the most common type of token built on top of Ethereum. They are fungible in nature, meaning that there isn’t a distinction between individual tokens. For example, if I have 100 metal marbles in my hand that are all the same size and color, it doesn’t matter which one I give you.

Your Makefiles are wrong

tags: Makefile source: Davis-Hansson, Jacob. “Your Makefiles Are Wrong.” Jacob Davis-Hansson on Tech, December 15, 2019. https://tech.davis-hansson.com/p/make/. Best Makefile Defaults # Always use bash as the shell. SHELL := bash # Enable bash strict mode. .SHELLFLAGS := -eu -o pipefail -c ## Change some Defaults of Make. # Ensures each Make recipe is ran as one single shell session, # rather than one new shell per line. .ONESHELL: # Delete it's target file if a Make rule fails.

Podcasts RSS Feed Validator

Solana Account

tags: Solana, Solana 101: Prelude Account: a Memory region The solana term for a memory region is “account”. Some programs own thousands of independent accounts. Programs own accounts, aka the owner of accounts. Transactions and Accounts You can make a program read and write data by sending transactions. Programs provide endpoints that can be called via transactions (In reality it’s a bit more complex than that but frameworks like Anchor abstract away this complexity).

Solana Program

Rust Opaque Types: Static Dispatch vs. Dynamic Dispatch

error: is only available in macOS 10.15 or newer

tags: Flutter,GUI,macOS souce: https://github.com/flutter/flutter/issues/73122 To solve this problem we should specify MACOSX_DEPLOYMENT_TARGET: I would imagine that there is Apple documentation on managing build settings in Xcode, but I don’t have a link offhand. There’s no Flutter-specific documentation of the process, if that’s what you mean; it isn’t any different in a Flutter macOS application as it would be any other macOS application. If you don’t want to use Xcode, you can change MACOSX_DEPLOYMENT_TARGET directly in Runner.

Wecom Debug Mode

Flutter

iOS

Flutter FFI didn’t be Invoked in Release Mode

tags: Rust,Flutter,iOS source: “Using Dummy Headers - Flutter_rust_bridge.” Accessed July 25, 2022. http://cjycode.com/flutter_rust_bridge/integrate/ios_headers.html. Recently, I met a problem that the iOS app didn’t work properly in release mode. After a little searching, I found it’s a Flutter app and invoked a Rust function by FFI. The inital call were not invoked during app startup, and it should be. I finally resolved the problem by following: https://github.com/fzyzcjy/flutter_rust_bridge/issues/496 http://cjycode.com/flutter_rust_bridge/integrate/ios_headers.html In short:

openssl

openssl unknown ca

Move Resources Permissions

tags: Move,Starcoin Web3 StarTrek Bedrock – Object-capability model In my words, Move is kind of a Resource-Oriented Programming language. The resource is represented by struct in Move, aka object in other programming language. By the way, the resource in Move is the struct which cannot be copied and cannot be dropped1. Distinct from other programming language, objects are stored in memory, resource in Move can store to the chain’s global storage.

Brevity 500: 500 mini-games to help you learn powerful writing skills

GitHub: hackclub/some-assembly-required

How is a Block be Executed

tags: Starcoin Web3 StarTrek,Move When I start learning Move and looking at the stdlib starcoin-framework and starcoin-framework-commons. Then I realized there are must some magic during the block execution in runtime. To roll the world, the runtime should provide some built in types and call some function in the stdlib. How does StarcoinVM Validate Transactions? As a miner, it’s responsible for executing block, it follows: Received some transactions from P2P network: EventHandler of PeerTransactionsMessage.

Starcoin Node Debug

Move: A Language With Programmable Resources

Move

How is an Account be Created

tags: Starcoin Web3 StarTrek,Account-Model Blockchain Systems We can create an account by wallet like MetaMask or StarMask, but I’m curious about how an account is created on the blockchain system. As a wallet has been embedded in the starcoin node, we can use it to create an account as follow: $ ./target/debug/starcoin -d ~/.starcoin -n dev account create -p my-pass { "ok": { "address": "0x2f1aeb63bd30d8eb841d6a941c5d6df3", "is_default": false, "is_readonly": false, "public_key": "0x91f79bdd9ced49332bf85b751d02339e05aff047c386d0c14b380d8519d2fb4b", "receipt_identifier": "stc1p9udwkcaaxrvwhpqad22pchtd7vy2276p" } } As above we can see our account has been created, and the address is: 0x2f1aeb63bd30d8eb841d6a941c5d6df3.

Luck Surface Area: How to Get Lucky In Life(a Note of “How to Get Rich”)

Rust libp2p

tags: libp2p,Starcoin Web3 StarTrek source: https://docs.rs/libp2p/0.45.1/libp2p/tutorials/index.html Ping: Four necessary traits Identity: PeerId and corresponding Keypair Transport: send and receive bytes on the network. NetworkBehaviour: decode or encode the bytes from the Transport. Swarm: drives both a Transport and a NetworkBehaviour forward. use futures::StreamExt; use libp2p::ping::{Ping, PingConfig}; use libp2p::{identity, Multiaddr, PeerId, Swarm}; use std::error::Error; #[async_std::main] async fn main() -> Result<(), Box<dyn Error>> { // First we need to create a network identity.

Distributed Hash Table

libp2p

tags: P2P,Starcoin Web3 StarTrek,Network source: https://docs.libp2p.io/ A set of protocols for peer identity, discover, routing, transport and more. Peer-to-peer network Peers or nodes communicate with oen another directly, it’s different from the client-server architecture. libp2p Solved Transport abstract data transmission and receipt to adapte many protocols, include the future protocols. Identity use public key cryptography as the basis of peer identity, with this: It gives each peer a globally unique “name”, in the form of a PeerId.

P2P

starcoin#3450

tags: Starcoin Web3 StarTrek,starcoin issue solving Today I saw this issue: starcoin#3450 at GitHub, I decide to give it a try. The corresponding type VMStatus is defined out of starcoin’s reposiotry, here. The work need to be done seems are: convert function from u16 to a readable string. convert status_code from StatusCode to a readable string. Let’s take a look at StatusCode first, StatusCode is a enum that contains lot of variants, WOW!

starcoin issue solving

Addressable Merkle Tree(AMT)

tags: Merkle tree,Blockchain,Starcoin Web3 StarTrek source: Gao, Zhenhuan, Yuxuan Hu, and Qinfan Wu. “Jellyfish Merkle Tree,” n.d., 12. What is Addressable mean? It means the leaf node in the tree can be found by an address. The address encoded the path to the leaf node, for example, a leaf node in a binary tree, which has 3 level. Its address may be encoded to 010, the corresponding path is: left->right->left:

UTXO VS. ACCOUNT MODEL

Account-Model Blockchain Systems

Patricia Merkle Tree

Seal is a verifiable timestamp mechanism for cryptographically proving that a note is created before a specific time.

Binary Search : Median of two sorted arrays of different sizes.

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:

LeetCodeNJ

Starcoin Blockchain from Scartch

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.

Sparse Merkle Tree

Jellyfish Merkle Tree

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:

Starcoin PoW

Merkle tree

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.

Starcoin Learn Resource

Compile Starcoin from Source And Setup a Dev Node

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.

Starcoin Web3 StarTrek

Blogchain

ipfs

IPFS

Words that I always forgot

Fast bitset decoding using Intel AVX-512

Master’s Degree in Computer Science

Master’s Degree in Computer Science

【01B0801】 计算机及应用(独立本科段)

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:

Carr

Why I Decide to Get A Computer Science Degree in 2022

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.

My experience getting a tech job with no degree or relevant work experience

How I Got a Computer Science Degree in 3 Months for Less Than $5000 | Miguel Rochefort

Degree

Luhn algorithm using SWAR and SIMD

Removing characters from strings faster with AVX-512

GnuPG Can not Sign Commit with Magit in Terminal Text Mode

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.

GnuPG

GnuPG Agent

GnuPG Pinentry

Graph

Minimum spanning tree

NUMA

netstat

ethtool

Multi-queue NICs

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).

iptables

Assembly

How to receive a million packets per second

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=.

UDP

Multicast

Clock Synchronization

C++ Lambda

LeetCode101: 347. Top K Frequent Elements

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.

LeetCode101: 27. Remove Element

LeetCode101: 18. 4Sum

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.

LeetCode101: 703. Kth Largest Element in a Stream

LeetCode101: 1046. Last Stone Weight

LeetCode101: 167. Two Sum II - Input Array Is Sorted

LeetCode101: 16. 3Sum Closest

LeetCode101: 15. 3Sum

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.

Three Pointers

LeetCode101: 680. Valid Palindrome II

tags: String,Two Pointers,LeetCode101 Two pointers move inwards, when we meet two different characters: Remove left character to see if the remains string still satisfied a valid palindrome. Remove right character to see if the remains string still satisfied a valid palindrome. Returns true if either one above two is true. class Solution { public: bool validPalindrome(string s) { for (int i = 0, j = s.size() -1; i < j; i++,j--) { if (s[i] !

In-place Reverse

tags: In-place WikiPedia: https://en.wikipedia.org/wiki/In-place%5Falgorithm Let see two examples before we go further: As above we can see, to reverse a array in-place, we just need swap each two elements in the array from both side to middle. The pseudo code from WikiPedia: function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp The loop travels the array to the middle and swap each other in the list, two points we must be noticed:

In-place

LeetCode101: 344. Reverse String

LeetCode101: 35. Search Insert Position

tags: Binary Search,LeetCode101 There is three corner cases must be handled if we don’t find target in nums: Return r + 1 if target is greater than right. Or return mid + 1 if target is greater than mid. Otherwise return mid. class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = r / 2; while (l !

LeetCode101: 74. Search a 2D Matrix

Divide-and-Conquer

LeetCode101: 136. Single Number

tags: Bit Manipulation,Bitwise Operator: XOR According to bitwise operator XOR: x ^ x = 0 y ^ 0 = y We apply the XOR operator to all the nums, all the same numbers will apply x ^ x = 0, and then y ^ 0 = y will result the single number. class Solution { public: int singleNumber(vector<int>& nums) { int xorN = 0; for (auto iter = nums.begin(); iter !

Bit Manipulation

Bitwise Operator: XOR

LeetCode101: 287. Find the Duplicate Number

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 Treat as A Linked List with circle According to the length of nums is n + 1, and integer range is [1, n], so we can treat each element as a index that point to some next value. For example: [1,3,4,2,2] It can be treated as(format is element(index)): 1(0) -> 3(1) -> 2(3) -> 4(3) -> 2(4) -> 4(3) We can see there is a circle in it, so:

LeetCode101: 142. Linked List Cycle II

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return nullptr; } // tortoise move 1 step auto slow = head->next; // hare move 2 steps auto fast = head->next->next; while (slow !

Fast & Slow Pointers

Cycle detection

tags: Algorithm,Linked List,Fast & Slow Pointers source: https://en.wikipedia.org/wiki/Cycle%5Fdetection Floyd’s tortoise and hare With two pointers: tortoise move slow: move 1 step in each loop. hare move fast: move 2 steps in each loop. If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle? We put tortoise back to the beginning they both started.

Tree

Binary Tree

Complete Binary Tree

Binary heap

tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree source: https://en.wikipedia.org/wiki/Binary%5Fheap Binary tree with two additional constraints: Shape property: complete binary tree. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order. Heap operations Insert Steps to add an element to a heap: Add element to the bottom level of the heap at the leftmost open space.

LeetCode101: 215. Kth Largest Element in an Array

LeetCode101: 1337. The K Weakest Rows in a Matrix

tags: Priority Queue,LeetCode101 The key ideas: Use a std::pair to hold {count, index}, so it can compare count first then the index. Use a min heap priority queue to get the K weakest rows. class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { // min heap priority_queue< std::pair<int, int>, vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; for (auto iter = mat.begin(); iter != mat.end(); ++iter) { int c = count((*iter).

Priority Queue

How to Speak and Write Correctly

tags: Learning English,读书笔记 source: Joseph Devlin. How to Speak and Write Correctly, 2007. http://archive.org/details/how_to_speak_and_write_correctly_librivox. I found this book in my Kindle on the subway to work this morning. And remembered that I downloaded it free from the Kindle store years ago. For some reasons, maybe my English was not good enough to read it, I haven’t read it yet. After read a little, I think it’s prefect for me for now.

Heapsort

Heap (data structure)

tags: Data Structures,Tree WHAT is a heap? Tree-based data structure which is essentially an almost complete tree that statifies the heap property. Max heap For any given node C, if P is a parent node of C, then the key(the value) of P is greater than or equal to the key of C. Min heap The P is less than or equal to the key C. When to use a heap?

Sorting

LeetCode101: 881. Boats to Save People

tags: Hash Table,LeetCode101,Sorting,Two Pointers Intuition with HashMap class Solution { public: int numRescueBoats(vector<int>& people, int limit) { unordered_map<int, int> cntOfWeights; for (auto iter = people.begin(); iter != people.end(); ++iter) { cntOfWeights[*iter]++; } int r = 0; for (int i = 0; i < people.size(); i++) { if (cntOfWeights[people[i]] == 0) { continue; } cntOfWeights[people[i]]--; for (int j = (limit - people[i]); j > 0; --j) { if (cntOfWeights.find(j) != cntOfWeights.

LeetCode101: 991. Broken Calculator

tags: Math,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited.

LeetCode101: 1663. Smallest String With A Given Numeric Value

tags: String,LeetCode101,Tricky Initialize a string that fills 'a' in it. Then we turn it to the expected string from end to start. The maximal value of each position in the string is 26. If we start from all elements is 'a' in the string. Then the represent value of the string is n. If it’s not equal to k. Then we need turn the last character of string to r = k - n.

LeetCode101: 12. Integer to Roman

tags: Math,Hash Table,LeetCode101 class Solution { public: string intToRoman(int num) { vector<string> roman {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; vector<int> integers {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; string r; int times = 0; for (int i = 0; i < integers.size(); ++i) { if (num >= integers[i]) { times = num / integers[i]; num -= times * integers[i]; for (int j = times; j > 0; --j) { r.

LeetCode101: 11. Container With Most Water

LeetCode101: 316. Remove Duplicate Letters

tags: String,LeetCode101,Stack,Hash Table,Hash Set I have solved this problem years before, LeetCode: 316.Remove Duplicate Letters, but still stuck on it. The key idea is not only about stack, but also required a map to record how many same letters behind current one. Which helps us to decide if drop current letter or not, when the new letter is less than the top of stack, which means smaller in lexicographical order.

LeetCode101: 763. Partition Labels

tags: String,LeetCode101,Hash Set,Hash Table,Stack The key idea is similar to LeetCode101: 316. Remove Duplicate Letters, we use a HashMap to track how many letters which is same in the string. Then we use a HashSet to store appeared letters. When there is no more letters appeared in the HashSet, it’s time to partition. class Solution { public: vector<int> partitionLabels(string s) { unordered_map<char, int> cntOfLetters; unordered_set<char> appearedLetters; vector<int> r; int count = 0; for (auto iter = s.

String

LeetCode101: 9. Palindrome Number

tags: LeetCode101,Math The key idea is: To use \(log10(10^n) = n\) to get how many digits in the number. Then we need iterate \(n + 1\) times to compare each side. The digit in the left is \(\frac{x}{10^{n-i}} \mod 10\). The digit in the right is \(\frac{x}{10^i} \mod 10\). class Solution { public: bool isPalindrome(int x) { if (x < 0) { return false; } // failed at here if (x < 10) { return true; } int n = log10(x); int ld = pow(10, n); // left div int rd = 1; // right div for (int i = 0; i < (n + 1) / 2; i++) { // left right if (x / ld % 10 !

Math

Integer Overflow

tags: C/C++ In some problems, we need to detect is our result overflow in a 32-bit integer. The key ideas is check our value before it becomes bigger. For example: // INT_MAX 2147483647 // INT_MIN -2147483648 // INT_MAX's suffix is 7 if (res > INT_MAX / 10 || (res == INT_MAX / 10 && pop > 7)) { return 0; } // INT_MIN's suffix is -8 if (res < INT_MIN / 10 || (res == INT_MIN / 10 && pop < -8)) { return 0; } res = res * 10 + pop; Our final result need a 10 times current value and plus a value, then we check:

LeetCode101: 8. String to Integer (atoi)

tags: Tricky,LeetCode101,Integer Overflow The key idea is how to detect integer overflow, it’s same to: LeetCode101: 7. Reverse Integer. class Solution { public: int myAtoi(string s) { auto iter = s.begin(); int base = 1, r = 0, p = 0; // Skip whitespace for (; iter != s.end() && *iter == ' '; ++iter) { } // negative or positive if (*iter == '-' || *iter == '+') { if (*iter == '-') { base = -1; } ++iter; } for (; iter !

LeetCode101: 6. Zigzag Conversion

tags: Tricky,LeetCode101 Make R = total required rows d = R - 2 2 is contains head line and tail line that not need insert a character between two columns. r = current row offset, which starts from 0. c = current column offset, which starts from 0. We can use a formula to make columns, which is \(c(R+d)+r\). For example, "PAYPALISHIRING", numRows=3: P A H N A P L S I I G Y I R The columns only the head and tail rows is correct should be:

LeetCode101: 7. Reverse Integer

tags: Tricky,Stack,LeetCode101,Integer Overflow The key is how to detect integer overflow without store to a larger size integer. For this purpose, we could detect integer overflow before carry: The maximal of INT_MAX before carry is \(\frac{INT\_MAX}{10}\). We continue compare pop with the suffix of INT_MAX, 7, if maximal before carry is equal to \(\frac{INT\_MAX}{10}\). The minimal of INT_MIN before carry is \(\frac{INT\_MIN}{10}\) too. We continue compare pop with the suffix of INT_MIN, -8, if minimal before carry is equal to \(\frac{INT\_MIN}{10}\).

LeetCode101: 946. Validate Stack Sequences

tags: Stack Intuition for (int i = 0; i < pushed.size(); i++) { if (pushed[i] != popped[pushed.size() - 1 - i]) { return false; } } But the pop/push operations can happend in any sequence. Stack Using a stack. Returns false, IF the next value neither the popped nor pushed. In each sequence we must do a operation: push or pop. When to push: stack is empty, or top of stack is not current popped value When to pop:

LeetCode101: 1249. Minimum Remove to Make Valid Parentheses

tags: Stack,LeetCode101 Stack class Solution { public: string minRemoveToMakeValid(string s) { stack<char> st; char open = '(', close = ')'; int open_count = 0; string res; // forward to remove unnecessary close parentheses for (auto iter = s.begin(); iter != s.end(); ++iter) { if (*iter == open) { open_count++; } if (open_count == 0 && *iter == close) { continue; } if (*iter == close) { open_count--; } st.push(*iter); } int close_count = 0; // backward to remove unnecessary open parentheses while (!

LeetCode101: 769. Max Chunks To Make Sorted

tags: Tricky,LeetCode101 original: 0, 2, 1, 4, 3, 5, 7, 6 max: 0, 2, 2, 4, 4, 5, 7, 7 sorted: 0, 1, 2, 3, 4, 5, 6, 7 index: 0, 1, 2, 3, 4, 5, 6, 7 As shown above, the position of break point is same to the position of max value of chunks. So here: We track chunks’s max value. Break at the position of max value lives in sorted array, which means the index in this case.

Tricky

LeetCode101: 739. Daily Temperatures

LeetCode101: 654. Maximum Binary Tree

tags: Monotonic Stack,LeetCode101,Binary Search Tree Mono-descreasing stack Key: The largest number is the root, that we can observe in by iteration. We must clear the stack to fill the right side of BST after loop. The last popped element is the left of current node. From top to bottom, the top element is the right side of the element that under the top. class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { vector<TreeNode*> res(nums.

LeetCode101: 581. Shortest Unsorted Continuous Subarray

tags: Monotonic Stack,LeetCode101 Mono-increasing stack Key: Some case should move backward as the new value we meeted is larger than it. When we meet 2 in the stack, and here we need move backward. Some case we need move forward, as the following values are the mono-increaing stack: [1, 2, 5, 3, 4] class Solution { public: int findUnsortedSubarray(vector<int>& nums) { stack<int> st; // mono-increasing int left = -1, right = -2; for (int i = 0; i < nums.

LeetCode101: 503. Next Greater Element II

tags: Monotonic Stack,LeetCode101 related: LeetCode101: 496. Next Greater Element I Mono-descreasing stack / normal order loop twice Loop twice to solve circular interger array Mono-descreasing stack to store index, avoid HashMap in Next Greater Element I, as there is a cicular array. class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { vector<int> res(nums.size(), -1); stack<int> st; for (int j = 0, i = 0; j < nums.size() * 2; ++j) { i = j >= nums.

LeetCode101: 496. Next Greater Element I

tags: Monotonic Stack,Hash Table,LeetCode101 Mono-descreasing and reverse order travel class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // Mono-descreasing and reverse order travel. // The next greater of the popped value is the top of the stack, if it has any. // // For example: [1,3,4,2] // the stack goes: // [2] // [4] -> 2 // [4, 3, 1] stack<int> st; vector<int> res; unordered_map<int, int> m; for (int i = nums2.

LeetCode101: 402. Remove K Digits

tags: Monotonic Stack,LeetCode101 Mono-increasing stack and reverse order travel (Not Work) Notes: We attempt to remove the most large numbers in the left, first, we use the right n numbers to meet the requirements, which is num.length - k and then, using a monotonic increasing stack to keep the result as samller as we can. (A monotonic increasing stack will remove larger elements before pushing.) Also note that: the result’s length is not actually equal num.

LeetCode101: 456. 132 Pattern

tags: Monotonic Stack,LeetCode101,Tricky We travel the numbers in the reverse order: Use a mono-increasing stack to find the largest number(3 in the 132 pattern), the value popped from stack is the second large number(2 in the 132 pattern), if any value less than the second large number, returns true. // Note: // // - subsequence is not contiguous, is i < j < k, not i + 1 = j, j + 1 = k // class Solution { public: bool find132pattern(vector<int>& nums) { int K = INT_MIN; stack<int> mst; // mono-increasing stack for (int i = nums.

Monotonic Stack

tags: Data Structures,Stack source: “Monotonic Stack.” Accessed March 13, 2022. https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack. A monotonic stack is a stack whose elements are monotonically increasing or descreasing. It’s not only about the order in the stack, it’s also about remove larger/smaller elements before pushing. Monotonically descreasing we need to pop smaller elements from the stack before pushing a new element: vector<int> nums; // fill nums stack<int> st; for (auto i = nums.size() - 1; i >= 0; i--) { while (!

AVL Tree

Binary Search Tree

Red-Black Tree

set vs unordered_set in C++ STL

tags: C/C++ source: GeeksforGeeks. “Set vs Unordered_set in C++ STL,” May 28, 2018. https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/. set Ordered set that implemented by a “Self balancing BST” like Red-Black Tree. Extra find operations equal_range returns range of elements matching a specific key lower_bound returns an iterator to the first element not less than the given key upper_bound returns an iterator to the first element greater than the given key #include <iostream> #include <set> #include <assert.

OrderedSet

LeetCode101: 220. Contains Duplicate III

tags: Sliding Window,OrderedSet Use HashSet to attempt to meet the requirements in the window class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { auto left = 0; auto K = 0; set<long> hset; // set in cpp is an sorted set for (auto right = 0; right < nums.size(); right++) { K = right - left; if (K > k) { hset.erase(nums[left]); left++; } hset.insert(nums[right]); // some numbers are the same.

LeetCode101: 219. Contains Duplicate II

tags: Sliding Window,Hash Table,LeetCode101 This is an “near by” problem that can be solved by Sliding Window. The k in the problem is somehow means contiguous. And using a HashTable to indicate that two values in the different position are equal. The steps is following: Find two values at each side of window are equal. Return true if the offset between their indices is less than or equal k. Otherwise set left to the new position and continue.

Hash Table

LeetCode101: 209. Minimum Size Subarray Sum

tags: Sliding Window,LeetCode101 Key: sum is greater than or equal to target Compute minimal must above slide left window, as decrease may cause sum less than target. See also 1695. Maximum Erasure Value class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0; int sum = 0; int minimal = INT_MAX; for (auto right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { minimal = min(minimal, right - left + 1); sum -= nums[left++]; } } return minimal == INT_MAX ?

  1. Repeated DNA Sequences

LeetCode101: 187. Repeated DNA Sequences

Hash Set

LeetCode101: 1695. Maximum Erasure Value

tags: Sliding Window,LeetCode101,Hash Set Use HashMap to store indices See also: 3. Longest Substring Without Repeating Characters class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { int maximum = 0; int left = 0, right = 0; unordered_map<int, int> indices; for (; right < nums.size(); right++) { int n = nums[right]; if (indices.find(n) != indices.end() && indices[n] + 1 > left) { left = indices[n] + 1; } maximum = max(maximum, std::accumulate(nums.

An Introduction to Sliding Window Algorithms

tags: Sliding Window source: Moore, Jordan. “An Introduction to Sliding Window Algorithms.” Medium, July 26, 2020. https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7. Efficientive algorithm: Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. – Antoine de Saint-Exupéry The following return values can use a sliding window: Minimum value Maximum value Longest value Shortest value K-sized value And contiguous is one of the biggest clues.

Window Sliding Technique

Brute Force Approach

Two Pointers

Differences between Sliding Window and Two Pointers

LeetCode101: 3. Longest Substring Without Repeating Characters

tags: Sliding Window,LeetCode101,Hash Table Use HashMap to store counts of letters Two points we should be noticed: The length of substring should be (right - left) + 1, as one side must be counted. We must decrese the number in the counts first, and then slide the left window, or we must decrese the wrong one, please compare between Wrong and Correct. Wrong left++; counts[s[left]]--; Correct counts[s[left]]--; left++; The full code see:

Sliding Window

  1. Add Two Numbers II

LeetCode101: 445. Add Two Numbers II

Stack

Linked List

LeetCode101: 2. Add Two Numbers

Linked List

LeetCode101

fork() is evil; vfork() is goodness; afork() would be better; clone() is stupid

Podcast/YouTube: Lex Fridman

English Listening Practice

的地得

Wealth

How To Get Rich (without getting lucky)

Material Design

Material Design: Tools for picking colors

Design

Material Design: The color system

tags: Design,Material Design: Tools for picking colorsMaterial Design source: Material Design. “Material Design.” Accessed February 12, 2022. https://material.io/design/color/the-color-system.html#color-usage-and-palettes. Principles Hierarchical Color indicates which elements are interactive, how they relate to other elements, and their level of prominence. Important elements should stand out the most. Legible Text and import elements, like icons, should meet legibility standards when appearing on colored backgrounds. Expressive Show brand colors at memorable moments that reinforce your brand’s style.

GTK

GUI

GTK+ 3 Text Widget Overview

GitHub: antoyo/relm – Idiomatic, GTK+-based, GUI library, inspired by Elm, written in Rust

Elm

GitHub: iced-rs/iced – A cross-platform GUI library for Rust, inspired by Elm

Are we GUI Yet?

tags: Rust GUI source: “Are We GUI Yet?” Accessed February 8, 2022. https://www.areweguiyet.com/. The answer is no, it seems the most popular GUI libraries are beta and not production ready. GitHub: antoyo/relm – Idiomatic, GTK+-based, GUI library, inspired by Elm, written in Rust GitHub: iced-rs/iced – A cross-platform GUI library for Rust, inspired by Elm GitHub: linebender/druid – A data-first Rust-native UI design toolkit. GitHub: redox-os/orbtk – The Rust UI-Toolkit.

GitHub: linebender/druid – A data-first Rust-native UI design toolkit.

GitHub: redox-os/orbtk – The Rust UI-Toolkit.

Rust GUI

The Dark Side Of Smart Contracts

tags: Smart contracts source: Business Tech Guides. “The Dark Side Of Smart Contracts.” Accessed February 7, 2022. https://businesstechguides.co/smart-contracts. WHAT are Smart Contracts? Blockchain-based programmes that execute agreements once certain criteria are fulfilled by all parties involved. A self-executing piece of code. When it’s deployed on blockchain, meaning nobody controls it. Analog a contract in the real world, for example, the contract you are signed with your landloard to lease an apartment.

YouTube: 250. My Zettelkasten: An Author’s Digital Slip-Box Method Example (Using Plain-Text Software)

为什么要定期回顾:避免「我学会了」的假象

记笔记就像编相声

The Four Underlying Principles of Taking Smart Notes

tags: How to Take Smart Notes,slip-box,PKM source: Part 2: “THE FOUR UNDERLYING PRINCIPLES” from Ahrens, Sönke. How to Take Smart Notes: One Simple Technique to Boost Writing, Learning and Thinking: For Students, Academics and Nonfiction Book Writers. North Charleston, SC: CreateSpace, 2017. Writing Is the Only Thing That Matters Don’t be afraid to writing ideas down and push them public, as there is no private knowledge in the academia area, and there is no such thing as a history of unwritten ideas.

Personal Knowledge Management

Zettelkasten 卡片盒筆記法,建立知識連結網路來活用筆記

GTD

slip-box

Why Rust strings seem hard

Thread Safety

如何理解 Sync 和 Send?

The Little Book of Rust Macros

A half-hour to learn Rust

Rust Macro

GitHub: dtolnay/proc-macro-workshop - Learn to write Rust procedural macros

GitHub: pingcap/talent-plan - open source training courses about distributed database and distributed systemes

GitHub: rust-lang/rustlings – Small exercises to get you used to reading and writing Rust code!

Blockchain: It’s not still the early days

tags: Blockchain,Web3 source: White, Molly. “It’s Not Still the Early Days.” Molly White, January 14, 2022. https://blog.mollywhite.net/its-not-still-the-early-days/. For blockchains, some thoughts are false, like: “It’s the early days.” “Give it a chance.” The reason is long time have passed, but no bright changes happened, the long time means Bitcoin began to be used in 2009, and Ethereum lanched in 2015. To compare: Smartphones from 2009 to 2015: Nokia -> iPhone/Android.

AQM

Message Queue

Bufferbloat Dark Buffers in the Internet

Bufferbloat

5W1H

TCP Fast Open

tags: TCP,Network,5W1H TCP Fast Open(TFO): WHY TFO is proposed? TCP Three-Way Handshake for every new TCP connection is too expensive. WHAT is the TFO? TCP Fast Open (TFO) is a mechanism that aims to reduce the latency penalty imposed on new TCP connections. HOW the TFO reduce the latency on new TCP connections? TFO allows data transfer within the SYN packet. WHEN the TFO is avaiable. TFO support is now avaiable in Linux 3.

Controlling Queue Delay

tags: CoDel,Network source: “Controlling Queue Delay - ACM Queue.” Accessed January 11, 2022. https://queue.acm.org/detail.cfm?id=2209336. Bufferbloat What is the bufferbloat? In the internet, large buffer is used everywhere: PC Router/Swtich/ISP Server The large may cause delay. Why the bufferbloat still with us and made increaingly critical by two trends? Cheap memory. Complicate network paths. How to sloves the problem? AQM(active queue management) is the known solution, but it’s difficult to implement, so even it has been known two decades but still not been widely deployed.

CoDel

Fun Bugs

Fun Story

Speed of Light: We can’t send mail more than 500 miles

Networking 101: Primer on Latency and Bandwidth

Reproducible Research Papers using Org-mode and R: A Guide

How to Take Smart Notes

HTTP

GitHub: duckwork/titlecase.el - Titlecase things in Emacs

Chicago Manual of Style: Chapter 8 Names, Terms, and Titles of Works

Online: Title Case

Title Case

The Programmer’s Way to Write in Title Case Using Emacs Lisp

tags: Learning English,Title Case source: “The Programmer’s Way to Write in Title Case Using Emacs Lisp.” Accessed January 10, 2022. https://hungyi.net/posts/programmers-way-to-title-case. Genernal correct title cased phrase: Uppercase the first letter of most words e.g. “There Is No Spoon” Not capitalize ‘small’ and ‘unimportant’ words e.g. “Long Live the King” Always capitalize the first and the last words, even if they’re small e.g. “The Land and Save We Live On”

Patterns of Distributed Systems: Quorum

Patterns of Distributed Systems: Paxos

Career

How to quit like a boss

tags: Career source: “How to Quit like a Boss.” Accessed January 7, 2022. https://jmsbrdy.com/blog/leaving-spring/. HN: https://news.ycombinator.com/item?id=29830296 From the article: Avoid communication failures: your manager should not be surprised by your leaving. Do have regular, clear, frank conversations about your career with your direct manager. Do tell your manager clearly if there’s something you’re looking for in your career which your current role isn’t providing. Don’t withhold concerns or aspirations from your manager.

Crypto: the good, the bad and the ugly

tags: Blockchain,Smart contracts,Web3 source: “Crypto: The Good, the Bad and the Ugly.” Accessed January 7, 2022. https://seldo.com/posts/crypto-the-good-the-bad-and-the-ugly. The good: Smart contracts allows anybody to execute arbitrary code in the network. And use money to avoid abuse, as every action in the smart contract cost money(computing resource). Finaacial engineering: new money. Entertainment: NFT, a big dream(culture) for everybody who loves crypto. True cloud computing: Smart contracts again. Web3 The bad:

Ethereum development

Set up your local development environment

tags: Smart contracts,Ethereum,Ethereum development source: ethereum.org. “Ethereum Local Development Setup.” Accessed January 7, 2022. https://ethereum.org. Local development node: Use Hardhat to build the ethereum development environment. And also there are some tools that based on Hardhat: scaffold-eth: forkable Ethereum dev stack focused on fast product iterations Ganache: A tool for creating a local blockchain for fast Ethereum development. Tools that based on Ganache: Python based: brownie Testing tools: Waffle: ethers.

Ethereum: Deploying your first smart contract

PoA

Wikipedia: Proof of authority

Comparison of Classical Test Theory and Item Response Theory and Their Applications to Test Development

CTT

Educational

Educational Measurement

A Simple Guide to the Item Response Theory (IRT)

tags: IRT,读书笔记 source: Yu, Chong Ho. “A Simple Guide to the Item Response Theory ( IRT ) and Rasch Modeling.” Accessed January 6, 2022. https://www.semanticscholar.org/paper/A-Simple-Guide-to-the-Item-Response-Theory-(-IRT-)-Yu/f42efb1bcf38f6650a8b16650e2811e8803cd4ec. IRT is about fitness or simplicity for test. There are two versions of IRT: IRT - three parameters. Rasch modeling - one parameter only. Three parameters: A - discrimination, how effectively this item can discriminate students’s proficient between highly and less. B - difficulty, or the threshold, tells us how easy or how difficult an item is.

IRT

How I took my SaaS from idea to sold in 14 months

Problems once solved by a metaclass can be solved by init_subclass

Rust Language Cheat Sheet

Streaming

Why local state is a fundamental primitive in stream processing

Streaming 102: The world beyond batch

tags: Bigdata,Flink,Dataflow Model,Streaming source: “Streaming 102: The World beyond Batch – O’Reilly.” Accessed January 5, 2022. https://www.oreilly.com/radar/the-world-beyond-batch-streaming-102/. Three more concepts: Watermarks: Useful for event time windowing. All input data with event times less than watermark have been observed. Triggers: Signal for a window to produce output. Accumulation: The way to handle multiple results that are observed for the same window. Streaming 101 Redux What: Transformations Where: windowing Make a temporal boundary for a unbounded data source.

Dataflow Model

Streaming 101: The world beyond batch

tags: Bigdata,Flink,Streaming source: Akidau, Tyler. “Streaming 101: The World beyond Batch.” O’Reilly Media, August 5, 2015. https://www.oreilly.com/radar/the-world-beyond-batch-streaming-101/. Streaming: a type of data processing engine that is designed with infinite data sets in mind. Other common uses of “streaming” that will be avoid in the rest of the post: Unbounded data: A type of ever-growing, essentially infinite data set. Unbounded data processing: An ongoing mode of data processing, applied to the aforementioned type of unbounded data.

DAOs, DACs, DAs and More: An Incomplete Terminology Guide

Online Tutorial

DAO Education: Level Up Your Knowledge of DAOs

My writing finances, 2021

HN: I make $3K/mo from a browser extension!

Web3/Crypto: Why Bother?

Skiff x Ethereum Naming Service

MetaMask

Real Problems That Web3 Solves, Part 1

tags: Web3,Smart contracts source: Bill Prin’s Personal Page. “Real Problems That Web3 Solves, Part 1,” January 3, 2022. https://billprin.com/2022/01/03/real-problems-web3-solves.html. What exactly is the difference between Web3, blockchain, and cryptocurrency You can think of blockchain and cryptocurrency as technological implementation details, and Web3 as the communities, businesses, and social relationships that form on top of that technology. A similar analogy would be the original World Wide Web, which could have been construed as a rebrand of the underlying technologies of HTML over HTTP over TCP/IP.

Smart contracts

Decentralized autonomous organizations (DAOs)

Neural Network From Scratch

my personal note taking journey

Zotero zotxt’s api 500 as the specify style is not installed

tags: Zotero,Emacs I got an error when I’m inserting Zotero ref to Emacs by M-x org-zotxt-insert-reference-link RET [error] request--callback: peculiar error: 500 I got the error of zotxt by follow the instruction Debug Output Logging: (5)(+0000003): HTTP/1.0 500 Internal Server Error X-Zotero-Version: 5.0.96.3 X-Zotero-Connector-API-Version: 2 Content-Type: text/plain; charset=UTF-8 csl is nullTypeError: csl is null buildBibliographyResponse/responseData<@resource://gre/modules/addons/XPIProvider.jsm -> jar:file:///Users/wanghui/Library/Application%20Support/Zotero/Profiles/34hkbjfm.default/extensions/zotxt@e6h.org.xpi!/bootstrap.js:220:9 buildBibliographyResponse@resource://gre/modules/addons/XPIProvider.jsm -> jar:file:///Users/wanghui/Library/Application%20Support/Zotero/Profiles/34hkbjfm.default/extensions/zotxt@e6h.org.xpi!/bootstrap.js:219:24 buildResponse/<@resource://gre/modules/addons/XPIProvider.jsm -> jar:file:///Users/wanghui/Library/Application%20Support/Zotero/Profiles/34hkbjfm.default/extensions/zotxt@e6h.org.xpi!/bootstrap.js:156:20 tryCatcher@resource://zotero/loader.jsm -> resource://zotero/bluebird/util.js:16:16 module.exports/Promise.prototype._settlePromiseFromHandler@resource://zotero/loader.jsm -> resource://zotero/bluebird/promise.js:547:13 module.

Scientific Writing with Zotero and Org Mode

Research

A research workflow with Zotero and Org mode

tags: Org Mode,Taking Notes,Zotero,Research,Emacs source: “A Research Workflow with Zotero and Org Mode | Mkbehr.Com.” Accessed January 5, 2022. http://www.mkbehr.com/posts/a-research-workflow-with-zotero-and-org-mode/. Gluing zotero and Org mode together with zotxt(zotxt-emacs). Workflow: Store papers into zotero by its browser plugin, that may also download the PDF. Create a page in Emacs and link to zotero via zotxt-emacs C-c " ". When I want to read the paper. Go to the page in Emacs and type C-c " a.

Zotero

Deserializing JSON really fast

Database

[译] RFC 1180:朴素 TCP/IP 教程(1991)

Assembly Nights

web3 is Centralized

An Algorithm for Passing Programming Interviews

A not so gentle intro to web3

Web3

Go Fuzzing

Bonsai offers freelance contracts, proposals, invoices

Assembly

NASM Assembly Language Tutorials

Microstartup

HN: My Microstartups make $500/day while I’m sleeping

tags: Freelance,Microstartup source: https://news.ycombinator.com/item?id=29790964 Comments: Related: “Tell HN: My Microstartups make $500/day while I’m sleeping” (this): https://news.ycombinator.com/item?id=29790964 “AMA: I make $100K+ ARR from my microstartups” (3 months ago): https://news.ycombinator.com/item?id=28561132 “Show HN: I passed up an opportunity to make $200K from my microstartup” (2020): https://twitter.com/1HaKr/status/1301142901510995969 “Show HN: My Indie Hacker goal - Earn $100 a day to keep your desk job away” (2020): https://news.ycombinator.com/item?id=24304674 “Show HN: I made $9000 posting on Hacker News about my microstartup” (2020): https://news.

Ledger, the first peer-reviewed journal dedicated to the study of blockchains and cryptocurrencies!

Privoxy socks5 to HTTP

Privoxy

Tools

HTTPs

Beam

Flink: Keyed State

Flink: Exactly Once Guarantees

tags: Flink State Snapshots,Fault Tolerance via State Snapshots source: https://nightlies.apache.org/flink/flink-docs-release-1.14/docs/learn-flink/fault%5Ftolerance/#exactly-once-guarantees Depending on the choices you make, Flink possiable outcomes: Flink makes no effort to recover from failures (at most once) Nothing is lost, but you may experience duplicated results (at least once) Nothing is lost or duplicated (exactly once) Given that Flink recovers from faults by rewinding and replaying the source data streams, when the ideal situation is described as exactly once this does not mean that every event will be processed exactly once.

Wikipedia: Chandy–Lamport algorithm

Flink: How does State Snapshotting Work?

tags: Fault Tolerance via State Snapshots,Flink State Snapshots,Wikipedia: Chandy–Lamport algorithm source: https://nightlies.apache.org/flink/flink-docs-release-1.14/docs/learn-flink/fault%5Ftolerance/#how-does-state-snapshotting-work Workflow: Checkpoint coordinator (part of the job manager) instructs a task manager to begin a checkpoint. Insert numbered checkpoint barriers into their streams of all the sources record their offsets. checkpoint barriers flow through the job graph, indicating the part of the stream before and after each checkpoint. Checkpoint n will contain the state of each operator that resulted from having consumed every event before checkpoint barrier n, and none of the events after it.

Flink Checkpoint

Flink Savepoint

Flink Checkpoint Storage

State Backends

tags: Flink State Snapshots,Fault Tolerance via State Snapshots,Stateful Stream Processing Two implementations of state backends are available: RocksDB An embedded key/value store keeps its working state on disk. Overhead Accesses and updates involve serialization and deserialization. Java heap-based state backend Keeps its working state in memory, on the Java heap. Risk Large amount state will cause OOM. Conclusion Both of these state backends are able to do asynchronous snapshotting, meaning that they can take a snapshot without impeding the ongoing stream processing.

Fault Tolerance via State Snapshots

Flink State Snapshots

Stateful Stream Processing

tags: Stream processing,Flink source: https://nightlies.apache.org/flink/flink-docs-release-1.14/docs/learn-flink/overview/#stateful-stream-processing https://nightlies.apache.org/flink/flink-docs-release-1.14/docs/concepts/stateful-stream-processing/ This means that how one event is handled can depend on the accumulated effect of all the events that came before it. How the stateful streaming processing works on a distributed cluster? The set of parallel instances of a stateful operator is effectively a sharded key-value store. Each parallel instance is responsible for handling events for a specific group of keys, and the state for those keys is kept locally.

Timely Stream Processing

Flink Redistributing

tags: Flink Parallel Dataflows Redistributing streams (as between map() and keyBy/window above, as well as between keyBy/window and Sink) change the partitioning of streams. Each operator subtask sends data to different target subtasks, depending on the selected transformation. Examples are keyBy() (which re-partitions by hashing the key), broadcast(), or rebalance() (which re-partitions randomly). In a redistributing exchange the ordering among the elements is only preserved within each pair of sending and receiving subtasks (for example, subtask[1] of map() and subtask[2] of keyBy/window).

One-to-one

Flink Parallel Dataflows

Stream processing

Batch processing

Flink实时计算-深入理解 Checkpoint和Savepoint

知乎:Flink实时计算-深入理解 Checkpoint和Savepoint

GitHub: 像小说一样品读 Linux 0.11 核心代码

Audio: The lost talks from Linus Torvalds at DECUS'94

Linux

Ethereum: Shard chains

Ethereum: The Beacon Chain

How does Ethereum’s proof-of-stake work?

tags: Ethereum,Proof-of-stake source: https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/#how-does-pos-work When you submit a transaction on a shard, a validator will be responsible for adding your transaction to a shard block. Validators are algorithmically chosen by Ethereum: The Beacon Chain to propose new blocks. Attestation If a validator isn’t chosen to propose a new shard block, they’ll have to attest to another validator’s proposal and confirm that everything looks as it should. It’s the attestation that is recorded in the beacon chain rather than the transaction itself.

ETH

Proof-of-history

Proof-of-stake

tags: Blockchain,Blockchain Proof,Ethereum,Solana source: https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/ Proof workflow: Users stake money(ETH) to become a validator. Validators are chosen at random to create blocks and are responsible for checking and confirming blocks they don’t create. user’s stake is also used as a way to incentivise good validator behavior. For example, a user can lose a portion of their stake for things like going offline (failing to validate) or their entire stake for deliberate collusion.

Proof-of-work

tags: Blockchain Proof,Blockchain,Ethereum source: https://ethereum.org/en/developers/docs/consensus-mechanisms/pow/ Wikipedia: https://en.wikipedia.org/wiki/Proof%5Fof%5Fwork A key feature of proof-of-work schemes is their asymmetry: the work – the computation – must be moderately hard (yet feasible) on the prover or requester side but easy to check for the verifier or service provider. With a hash function, let’s say SHA-1. For example, to do PoW, we need to generate a SHA-1 hash of the given data that must begins 52 binary zeros, that is 13 hexadecimal zeros:

Blockchain Proof

Shinobi Systems’ Solana Proof of Stake + Proof of History Primer

Blockchain Demo

Video: Blockchain 101 - A Visual Demo

C/C++ 多态

JavaScript

Swift

《深入理解计算机系统》读书笔记

SO: What is the difference between iter and into_iter?

GitHub: Rust Memory Container Cheat-sheet

Wrapper Types in Rust: Choosing Your Guarantees

GitHub: Internal details of Tokio from code to designs

PAPER: Raft

PAPER: Time, Clocks, and the Ordering of Events in a Distributed System

CSDN: 理解这两点,也就理解了paxos协议的精髓

GitHub: raft-rs

Raft Understandable Distributed Consensus

Distributed consensus (blockchain) simulation and visualization

Org-roam export backlinks on Hugo

tags: org-roam, Org Mode source: https://seds.nl/notes/org%5Froam%5Fexport%5Fbacklinks%5Fon%5Fhugo/ https://seds.nl/notes/export%5Forg%5Froam%5Fbacklinks%5Fwith%5Fgohugo/ 利用 hugo 的 partial template layouts/partials/backlinks.html {{ $re := $.File.BaseFileName }} {{ $backlinks := slice }} {{ range .Site.AllPages }} {{ if and (findRE $re .RawContent) (not (eq $re .File.BaseFileName)) }} {{ $backlinks = $backlinks | append . }} {{ end }} {{ end }} <hr> {{ if gt (len $backlinks) 0 }} <div class="bl-section"> <h4>Links to this note</h4> <div class="backlinks"> <ul> {{ range $backlinks }} <li><a href="{{ .

Online Tools

RoamResearch

Roam: Why I Love It and How I Use It

How To Take Smart Notes: 10 Principles to Revolutionize Your Note-Taking and Writing

tags: Learning,Taking Notes,RoamResearch source: https://fortelabs.co/blog/how-to-take-smart-notes/ Luhmann’s slip-box: build second brain context – its network of associations, relationships, and connections to other information. But Luhmann often remarked that he never forced himself to do anything he didn’t feel like doing: “I only do what is easy. I only write when I immediately know how to do it. If I falter for a moment, I put the matter aside and do something else” (Luhmann et al.

How To Take Smart Notes With Org-mode

tags: Learning,Taking Notes,org-roam,Org Mode source: https://blog.jethro.dev/posts/how%5Fto%5Ftake%5Fsmart%5Fnotes%5Forg/ Notes aren’t a record of my thinking process. They are my thinking process. – Richard Feynman The primary purpose of note-taking should not be for storing ideas, but for developing them. When we take notes, we should ask: “In what context do I want to see this note again?” Note-taking for writing: Find topic/research question Research/find literature Read and take notes Draw conclusions / outline text Write Two types of notes:

Learning

读书笔记

加解密

英语读音规则

英语词法

tags: Learning English 比较级 形容词/副词比较级 常规单音节词 -er fast -> faster small -> smaller nice -> nicer large -> larger(删除词尾不发音的 e) -y -> -ier busy -> busier pretty -> prettier 短元音 + 辅音:重写辅音 -er big -> bigger hot -> hotter 多音节: more + diffcult -> more difficult interesting -> more interesting careful /kɛəful/ -> more careful -y 二音节词(-ly副词除外):常不加 more busy -> busier pretty -> prettier quickly -> more quickly 特殊 much/many -> more little -> less good/well -> better bad -> worse 代词比较级 more less 比较级修饰 a little/ a bit + 比较级 更…一点 much / a lot / far + 比较级 更…得多 英语常见词用法 open/close 静态和动态 open When do you open(v.

流利英语

tags: Learning English 连读 变音 /d/ + /j/ = /dʒj/ Woul~d y~ou like to try int on? /t/ + /j/ = /tʃj/ What abou~t you~? 词尾辅音 + 词首元音 I~t i~s A glas~s o~f water 还原 r RP he~r i~deas Whe~re is i~t? 语块切割 Chunking 语块(Chunk) 能表达实际含义且语义不割裂的词串。 语块切割(Chunking) 根据说话节奏将句子自然切割为若干语块。 语块语连读 同一语块内能连则连。 吞音 基本原则 同一语块内,音同则吞。 示例 Excuse me, Coul~d you~ tell me how I can get to Pret A Monger? get to -> geto

英语习语

tags: Learning English Give me a hand come in 有 come in all/different colors/size come on 「随意」鼓动、鼓励、催促 come to 总计 Excuse me 抱歉/引起注意 by the way/BTW 顺便说一下 shame on sb.! sb. 可耻 make it 成功达成 do/try one’s best (to do sth.) 尽最大努力做某事 sure thing no problem. 礼貌请求 礼貌程度 please > please 疑问句 > 肯定句 could > would > can 示例: Show me (please) Can you show me? Can you show me please?

英语语法结构

tags: Learning English 双宾语 例句:I want to buy a birthday gift for my sister. 结构:buy sth. for sb. 双宾语:by sb. sth. buy my sister a birthday gift. Can I buy a drink for you? Can I buy you a drink? 双宾语限制 第二个宾语必须为名词,不能是人称代词(pron.)。 下面语句不能使用双宾语 I want to buy you it.(X) 双宾语动词 bring/give/tell/sell/ask/show Bring it to me Bring me a present. Give it to me Give me the pen. tell the story to me tell me the story email the photo to me email me the photo sell the handbag to her sell her the handbag ask sb.

英语常用词

英语短语

tags: Learning English shape ʃeip be in great/good shape stay/keep in (good) shape 英语表示次数范围 five times a month once two weeks 英语表示尺码 loose /luːs/ 松的 tight /tait/ 紧的 what/how about 提议 What/How about some coffee? What/How about you? 穿衣:try on/take off/put on n.: try on sth I’d like to try on the shoes. pron.: try sth. on I’d like to try them on. think of 认为 sth. 怎么样 What do you think of my new shirt?

英语词性

tags: Learning English 副词 adv/adverb 是指在句子中表示行为或状态特征的词,用以修饰动词、形容词、其他副词或全句,表示时间、地点、程度、方式等概念。 副词可分为:时间副词、频率副词、地点副词、方式副词、程度副词、疑问副词、连接副词、关系副词、表顺序的副词以及表完成的副词。 频率副词 always usually often sometimes about 表示大约大约修饰数量。 形容词 adj 形容词后缀 -ful helpful useful thankful 形容词后缀 -ed interested excited 形容词后缀 -ing interesting exciting 动词 verb 情态动词 modal verb. can(could)/may(might)/must/need/to/shall(should)/will(would). 动名词 形式 v.-ing 动词的名词化。 语法:名词 语意:动词 形变规则 特殊 1 -e:去 e 加 ing live -> living give -> giving 特殊 2 短元音 + 一辅音:重复最后一个字母加 ing jog -> jogging swim -> swimming 常规:直接加 ing do -> doing study -> studying 词性 I usually go swimming.

英语时态

tags: Learning English 通过动词变化来区分时间 通过动词变化来区分时间。 I am walking in the rain. 正在 I will walk in the rain. 将要 I walk in the rain sometings. 一般状态、重复、常态 一般现在时 表示: 当前的一般状态 重复或习惯动作 am/is/are(be 动词):是,处于某状态 do/does(实意动词):具体动作 (X): am/is/are + do/des 一般现在时不能 am/is/are 跟动词实意动词 一般现在时第三人称单音形规则 tags: 英语读音规则 一般现在时第三人称单数动词需要变形,需要注意变形后的读音 清对清 /s/ works helps 非清则浊 /z/ lives sees goes does /dʌz/ 组合 /dz/ /ts/ meets needs 近似音 -es /iz/ introduces fishes 现在进行时 当前正在发生的事情或动作,表示当前正在发生或者近将来。 I’m looking for a shirt.

Linux kernel

tags: Linux Linux I/O Linux I/O 演进 阻塞式:read()/write() 非阻塞式:select()/poll()/epoll(),不支持文件 I/O Thread Pool Direct I/O(数据软件):绕过 page cache 异步 IO(Linux AIO):早起进支持文件 I/O,近期支持了 epoll 支持非文件 I/O Linux io_uring [译] Linux 异步 I/O 框架 io_uring:基本原理、程序示例与性能压测 对比 Linux AIO: 重新设计实现真正的是不。 支持任何类型的 I/O:cached files、direct-access files 甚至 blocking sockets。 灵活、可扩展:基于 io_uring 能够重写 Linux 的每个系统调用。 原理及核心数据结构:SQ/CQ/SQE/CQE 每个 io_uring 实例都有两个环形队列,在内核和应用程序之间共享: 提交队列:submission queue(SQ) 完成队列:completion queue(CQ) 这两个队列: 都是单生产者、单消费者,size 是 2 的幂次; 提供无锁接口(lock-less access interface),内部使用内存屏障做同步(coordinated with memory barrers)。 使用方式: 请求 应用创建 SQ entries(SQE),更新 SQ tail; 内核消费 SQE,更新 SQ head 完成 内核为完成一个或多个请求创建 CQ enries(CQE),更新 CQ tail; 应用消费 CQE,更新 CQ head 完成事件(completion events)可能以任意顺序到达,到总是与特定的 SQE 相关联的。 消费 CQE 过程无需切换到内核态 带来的好处 支持批处理 支持文件 I/O 系统调用:read、write、send、recv、accept、opentat、stat、专用的一些系统调用,如 fallocate 不再局限于数据库应用 应对现在硬件架构:将硬件架构本身作为一个网络(多核多 CPU 是一个基础网络、CPU 之间是一个网络、CPU 和磁盘 I/O 之间又是一个网络) 三种工作模式 中断驱动模式(interrupt driven):默认模式。可通过 io_uring_enter() 提交 I/O 请求,然后直接检查 CQ 状态判断是否完成。

Scala lsp-metals

领域模式

tags: DDD,《领域驱动设计》读书笔记 领域基础模式 模式:UBIQUITOUS LANGUAGE 在同领域专家、开发人员和项目管理沟通的过程中建立并使用 UBIQUITOUS LANGUAGE,,并在模型实现时依然使用 UBIQUITOUS LANGUAGE 来让设计与沟通相一致(中文语境下稍显困难),UBIQUITOUS LANGUAGE 让知识消化后直接驱动变更模型。 应用 UBIQUITOUS LANGUAGE 需要大声的建模。 模式:MODEL-DRIVEN DESIGN 严格按照模型来编写代码,让模型与实际系统相结合。 不再分离「分析模型」和程序设计,而是寻求一种能够满足这两方面需求的单一模型。 工具:面向对象编程语言、UML等。 更好的支持 UBIQUITOUS LANGUAGE. 模式:HANDS-ON MODELER 开发设计和模型设计紧密合作,避免模型设计者不参与编写和程序设计者不参与模型设计。 每一个开发人员都必须不同程度的参与模型讨论并且与领域专家保持联系,模型设计者及时通过 UBIQUITOUS LANGUAGE 与接触代码的人及时交换关于模型的想法。 领域模式构造块 模式:LAYERED ARCHITECTURE 分层架构是实现 DDD 的基础,分层架构将不同的层次的实现分开,自上倒下应分为: 用户界面层 应用层 领域层(模型的精髓) 基础设施层 核心在于要将领域层单独出来实现 MODEL-DRIVEN DESIGN,对业务进行建模封装业务规则。调用规则也只能自上而下的调用,不能反向调用。 领域层(或模型层)分离出来之后使得模型足够丰富,结构足够清晰,可以捕捉到基本的业务知识,并有效的使用这些知识。 模式:ENTITY 用于跟踪对象的状态,有唯一标识符,在系统中是可变的,两个对象是否一个通过唯一标识来判断,不是靠它们的属性定义。 模式:VALUE OBJECT 区别与 ENTITY ,没有唯一标识,仅记录状态,一般设计为不可变用于共享 VALUE OBJECT,两个对象是否一个通过对象属性的值来判断。 模式:SERVICE 没有状态,但又需要建模的对象,只包含动作。用于一些不适合建模为对象的领域概念。 与领域概念相关的操作不是 ENTITY 或 VALUE OBJECT 的一个自然组成部署 接口是根据领域模型的其他元素定义的。 操作是无状态的 模式:MODULE(或 PACKAGE) 根据对象的意义划分领域模型,低耦合高内聚。按照模式或者对象生命周期或者其他方式划分都是错误的。 模式:AGGREGATE 划分模型边界,统一对关联模型的创建、修改、复制和销毁。一般选定一个 ENTITY 对象作为 AGGREGATE 的「根」,同时对事务应用一组规则:

Airflow

案例 Airflow powers AI。 Airflow SSO 接入 公司 SSO 系统不是基于开源标准,而是一套自定义的方式,目前网上没有成熟的解决方案,通过查看 Flask-AppBuilder 和 Airflow 的代码发现可以扩展 flask_appbuilder.security.views.AuthRemoteUserView 并通过自定义的 SecurityManager 指定 authremoteuserview 来实现,去掉具体 SSO 逻辑后的代码如下: from urllib.parse import urlencode from urllib.parse import urljoin import requests from flask import flash from flask import redirect from flask import request from flask_appbuilder.baseviews import expose from flask_appbuilder.security.views import AuthRemoteUserView try: from airflow.www.security import AirflowSecurityManager except ImportError: AirflowSecurityManager = None __version__ = "0.1.0" AUTHORIZE_URL = "https://example.com/sso/login" ACCESS_TOKEN_URL = "https://example.

Spark

tags: Bigdata Spark 编程语言选择 毋庸置疑,Python 应该是最简单也是大部分的选择,但是如果有依赖那么将要付出额外的心智负担(Spark 管理 Python 依赖)。 JVM 语言的依赖组织方式则具有天然的优势,可以将依赖(排除 Spark 生态之后)都 bundle 进 Jar 包里。 其中 Scala 兼具简单和 JVM 的优势,但是它「不流行」。 Spark Driver & Executor Driver 执行 spark-commit 客户端,创建 SparkContext 执行 main 函数。 Executor Spark Worker 上的线程 See also: Understanding the working of Spark Driver and Executor Cluster Mode Overview Spark 代码执行 我在配置 Spark 的时候就在好奇,从观察上看部分代码应该是执行在 Driver 上部分代码会执行在 Executer,这让我很好奇。 但是我通过学习 Spark RDD 学习到了一些知识。 以下代码是在 Executor 上执行的: Transformations 和 Actions 是执行在 Spark 集群的。 传递给 Transformations 和 Actions 的闭包函数也是执行在 Spark 集群上的。 其他额外的代码都是执行在 Driver 上的,所以想要在 Driver 打印日志需要上使用 collect:

Scala

tags: Programming Language Scala 学习资源 Scala Book Scala 这么好的语言为什么不流行 HN:Scala 为什么不流行 Reddit:Scala 为什么不流行 结论:Java 人才更多且成本更低。 Scala 工具 sbt sbt new 无法处理替换过的 SSH 会导致 Auth fail,一个 workaround 就是手动 clone 项目然后: sbt new file:///path/to/template.g8 sbt 国内加速 ~/.sbt/repositories: [repositories] local nexus-aliyun:https://maven.aliyun.com/nexus/content/groups/public nexus-aliyun-ivy:https://maven.aliyun.com/nexus/content/groups/public/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext] typesafe: https://repo.typesafe.com/typesafe/ivy-releases/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext], bootOnly Unique Scala Rust from Scala Rust 和 Scala 有很多想通的地方,Rust 应该从 Scala 借鉴了很多: 可变量和不可变量 模式匹配 Trait 内置类型 val b: Byte = 1 val x: Int = 1 val l: Long = 1 val s: Short = 1 val d: Double = 2.

SVG 绘制工具

设计

Graphviz

LeetCode: 98. Validate Binary Search Tree

tags: LeetCode https://leetcode.com/problems/validate-binary-search-tree/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr || (root->left == nullptr && root->right == nullptr)) { return true; } if (root->left !

LeetCode: 113. Path Sum II

tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left !

LeetCode: 112. Path Sum

tags: LeetCode https://leetcode.com/problems/path-sum/ 递归版 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) { return false; } return pathSum(root, 0, targetSum); } bool pathSum(TreeNode* node, int sum, int targetSum) { sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { return true; } } if (node->left !

LeetCode: 79. Word Search

tags: LeetCode 79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board.

Event Store

领域驱动设计

High Performance Browser Networking

预写日志

RabbitMQ

Twitter DistributedLog

Amazon Kinesis Streams

消息队列

Networking 101: Building Blocks of TCP

tags: TCP,High Performance Browser Networking 原文链接:https://hpbn.co/building-blocks-of-tcp/。 Overview The 4th version of RFC 675, and final two seperate RFCs: RFC 791 - Internet Protocol(IPv4) RFC 793 - Transmission Control Protocol TCP provides: Effective abstraction. A reliable network running over unreliable channel. Hiding most the complexity of network communication: retransmission of lost data, in-order delivery, congestion control and avoidance, data integrity, and more. Three-Way Handhsake Sequence numbers are important for keep in-order delivery, and they are picked randomly from both sides for security reasons.

TCP

背压

流处理系统

发送事件流 消息系统 生产者速度比消费者快:丢弃消息、将消息缓存在队列、激活背压。 节点崩溃或者暂时历险,是否会有消息丢失? 生产者与消息系统之间的直接消息传递 UDP 组播:广泛应用于金融股票 无代理消息库:ZerroMQ 和 nanomsg StatsD 和 Brubeck 使用 UDP 传递消息 HTTP、RPC 接口 消息代理 参见:AMQP/JMS 风格的消息代理。 也称消息队列。 消息对比与数据库对比 多个消费者 确认和重传机制 分区日志 参见: 基于日志的消息代理。 数据库与流 保持系统同步 变更数据捕获 变更数据捕获(Change Data Capture,CDC)记录了写入数据库的所有更改,并以可复制到其他系统的形式来提取数据。 如果在写入时立即将更改作为一种流来发布,那么 CDC 就更有趣来。 实现变更数据捕获 解析复制日志,并将解析的内容发送到事件流中进行 replay。 初始快照 replay 日志占用空间过大,需要进行截断,截断之前的进行初始快照保存。 日志压缩 参考哈希索引。 对变更流的 API 支持 数据库开始支持将变更流作为标准接口。 事件溯源 一种在领域驱动设计社区中开发的技术,与 CDC 最大的区别在于事件溯源在不同抽象层次上应用了将所有对应用程序状态的更改保存为更改事件日志: CDC 中:应用程序以数据可变方式来操纵数据库,从数据库中提取较低级的变更日志,从而确保从数据库提取写入顺序与实际写入顺序相匹配。写入数据库的程序不需要知道 CDC 正在发生。 事件溯源中:应用程序的写入逻辑是基于写入事件日志的不可变事件构建的。事件存储仅支持追加,不鼓励甚至禁止更新或删除操作。事件旨在反映在应用程序级别所发生的事情,而不是低级别的状态改变。 专门的数据库 Event Store 来支持使用事件溯源的应用程序。 从事件中导出当前状态:真正对用户有意义 命令和事件 命令经过校验后转化为事件。 状态,流与不可变性 流处理 事件中的数据写入数据库、缓存、搜索索引或类似的存储系统,提供给客户端查询。 通过某种方式将事件推送给用户,如电子邮件、短信等。 处理一个或多个输入流产生过一个或多个输出流。 流处理适用场景 复杂事件处理 复杂事件处理(Complex Event Processing,CEP)尤其适用需要搜索特定的事件模式。 实现:Esper、IBM Info Sphere Streams、Apama、TIBCO StreamBase 和 SQLstream。

Why MapReduce is making a comeback

When Zero Cost Abstractions Aren’t Zero Cost

弹性分布式数据集

HBase

大规模并行处理

Clock Synchronization with Chris Perl

tags: 分布式,一致性,Clock Synchronization,Multicast source: https://signalsandthreads.com/clock-synchronization/ Electronic Oscillator: Computer itself to Dervie its Notion of Time Computer’s clock are based on a 1 MHz electronic oscillator circuit, that is oscillating at some frequency, and driving an interrupt. So the operating system can use it to derive its notion of time. It helps computer to keep the time correct. But a bad oscillator could be influenced by the heat of CPU, like compiling Linux kernel, etc.

Hive

Hadoop

tags: Bigdata Hadoop Distributed File System MapReduce MapReduce shuffle 按照 reducer 分区,排序和将数据分区从 mapper 复制到 reducer。(令人困惑的术语,并不完全与洗牌一样,在 MapReduce 中其实没有随机性)。 MapReduce 的分布式执行 Hadoop MapReduce 并行化基于数据分区实现: 输入:通常是 HDFS 中的一个目录。 分区:每个文件或文件块都被视为一个单独的分区。 处理:每个分区由单独的 map 任务来处理。 每个 mapper 都会尽量实现计算靠近数据。 代码复制:JAR 文件。 Reduce 任务的计算也被分隔成块,可以不必与 mapper 任务数量相同,MapReduce 框架使用关键字的哈希值来确保具有相同关键字的键值对都在相同的 reduce 任务中处理。 键值对必须进行排序,排序是分阶段进行的: 每个 map 任务都基于关键字哈希值,按照 reducer 对输出进行分块。 每个分区都被写入 mapper 程序所在的本地磁盘上的已排序文件,参见 SSTables 和 LSM-Tree。 reducer 与每个 mapper 相连接:MapReduce 调度器会在 mapper 写入经过排序的输出文件后,通知 reducer 开始从 mapper 中获取输出文件,框架进行 MapReduce shuffle。 reducer 任务从 mapper 中获取文件并将它们合并在一起,同时保持数据的排序。不同 mapper 使用相同的关键字生成记录,会在合并后的 reducer 输入中位于相邻的位置。 reducer 可以使用任意逻辑来处理这些记录,并且生成任意数量的输出记录。记录被写入分布式文件系统中的文件。 MapReduce 工作流调度器 Oozie Azkaban Luigi Airflow Pinball 对比分布式数据库 MapReduce 中的并行处理和并行 join 算法已经在十多年前所谓的大规模并行处理(MPP)数据库中实现了。

Tokio

分布式文件系统

网络连接存储

Hadoop Distributed File System

Emacs Easter egg

数据库

批处理系统

MapReduce MapReduce 与分布式文件系统 MapReduce 就像分布在上千台机器上的 Unix 工具。 MapReduce 作业通常不会修改输入,除了输出外没有任何副作用。 MapReduce 作业在分布式文件系统上读写。(Unix 工具 stdin、stdout),如 HDFS(Hadoop Distributed File System)等(GlusterFS、QFS、Amazon S3、Azure Blob 和 OpenStack Swift)。 MapReduce 作业执行 MapReduce 是一个编程框架,可以使用它编写代码处理 HDFS 等分布式文件系统中的大型数据集。 要创建 MapReduce 作业需要实现两个回调函数: mapper 和 reducer (另请参阅 MapReduce 查询): Mapper: 每个输入记录都会调用一次,从输入记录提取任意数量的关键字和值(可以为空),不保留任何状态,可以独立处理。 Reducer: MapReduce 框架使用 Mapper 生成的键值对,收集同一个关键字的所有值,并使用迭代器调用 reducer 以使用该值的集合。 Reducer 可以生成输出记录。 MapReduce 分布式执行 参见 Hadoop 的 MapReduce 的分布式执行。 MapReduce 工作流 将 MapReduce 作业链接到工作流是非常普遍的,作业的输出作为下一个作业的输入。通过目录名隐式的完成: 第一个作业必须配置将其输出写入 HDFS 中指定目录; 第二个作业必须配置读取相同的目录名作为输入。 目前已经开发了处理依赖管理的 MapReduce 工作流调度器。 Reduce 端的 join 与分组 批处理的背景下讨论 join,主要解决数据集内存在关联的所有事件。 假设 join 两张表:用户和活动事件。

LeetCode: 37. Sudoku Solver

LeetCode: 36. Valid Sudoku

tags: LeetCode https://leetcode.com/problems/valid-sudoku/ <- high -- low -> +------------------- wow(row(i):0,col(j):0) 0 -> [ 0010, 0010 ] | 1 -> [ 0000, 0000 ] | 2 -> [ 0000, 0000 ] | | +--------------- wow(row(i):0,col(j):1) 0 -> [ 0010 | 1 = 0011, 0010 ] | | 1 -> [ 0000, 0000 | 1 = 0001 ] | | 2 -> [ 0000, 0000 ] | | | | +----------- wow(row(i):0,col(j):2) 0 -> [ 0011 | 3 = 0100, 0010 ] | | | 1 -> [ 0000, 0001 ] | | | 2 -> [ 0000, 0000 | 3 = 0100 ] +---+---+---+ | 2 | 1 | 3 | +---+---+---+ ----| 3 | 2 | 1 | | +---+---+---+ | | 1 | 3 | 2 | | +---+---+---+ |- wow(row(i):1,col(j):0) 0 -> [0010 | 3 = 0110, 0010] +---------------------+ 1 -> [0000, 0001 | 3 = 0101] 2 -> [0000, 0100] class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> wow(9,0); int mux1; int mux2; int mux3; int box_index; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j] == '.

区块链

LeetCode: 40. Combination Sum II

tags: LeetCode source: https://leetcode.com/problems/combination-sum-ii/ LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重: class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, 0, 0, target); vector<vector<int>> r; for (auto t : res) { r.push_back(t); } return r; } private: set<vector<int>> res; vector<int> track; map<int, bool> visited; void backtracking(vector<int>& condidates, int start, int n, int target) { if (n == target) { res.insert(track); return; } if (n > target) { return; } int c = 0; int sz = condidates.

LeetCode: 39. Combination Sum

tags: LeetCode source: https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题:会有不同顺序但是元素相同的数组,如何快速高效的进行过滤?

LeetCode: 52. N-Queens II

回溯算法

工业云

云原生

云计算

技术概念

边缘计算

LeetCode: 51. N-Queens

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置,那么横轴、纵轴、对角线都不再允许放置。我们按行进行遍历,所以我们需要跟踪以下位置是否已经放置 Queue: 纵轴(Column):cols 主对角线(Positive Diagonal):posDiag 次对角线(Negative Diagonal):negDiag 纵轴很好记录,但是对角线比较困难,我们先来看一下对角线的特征,假设横轴为 r 纵轴为 c , r - c 在正对角线是一致的: 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res.

Multi-Paxios

Zab

Paxos

Raft

VSR

链式复制

比较-设置

全序

macOS 签名 GDB

偏序

CAP 理论

一致性与共识

tags: 分布式共识,一致性 一致性保证 分布式一致性主要针对延迟和故障等问题来协调副本之间的状态。 线性化:最强一致性模型 顺序保证:保证时间顺序,特别是因果关系和全局顺序 最终一致性:一种非常弱的保证,参见最终一致性效应 可线性化 分布式语义下对寄存器(单个对象)顺序的读写。应区别与可串行化。 可串行化针对不同事务的隔离,用来确保事务执行的结果与串形执行的结果相同 可线性化是读写寄存器(单个对象)的最新值的保证。 线性化依赖的条件 加锁与主节点选举 每个启动节点都试图获得锁,其中只有一个可以成功成为主节点。通过加锁来保证主节点选举「线性化」。 约束与唯一性保证 同一个用户名、电子邮件或系统中文件名需要唯一性的保证,也应该进行「线性化」。 跨通道的时间依赖 系统中存在其他通信渠道也需要「线性化」。 实现线性化系统 主从复制(部分支持可线性化) 共识算法(可线性化) 多主复制(不可线性化) 无主复制(可能不可线性化) 线性化与Quorum 一致性 Dynamo 风格的复制模型,读写遵从严格的 quorum 是无法支持可线性化的。 线性化的代价 多主复制和主从复制,网络中断都会导致同步暂停,从而无法保证客户端要求的线性化读写。 CAP 理论 可线性化与网络延迟 很少有系统真正满足线性化,现代多个 CPU 对同一个内存地址的读写都不能满足(参见硬件内存模型),如果需要强一致则需要内存屏障(栅栏)指令。 之所以放弃线性化的原因就是性能,而不是为了容错。由于网络延迟的不确定性,无论是否发生网络故障,线性化对性能的影响都是巨大的。 顺序保证 顺序与因果关系 顺序有助于保持因果关系。 因果顺序并非全序:因果关系是小范围集合的偏序,可线性化是一个全序操作。 可线性化强于因果一致性 捕获因果依赖关系:检测并发写 序列号排序 非因果序列发生器 适用于系统不存在唯一主节点。 每个节点都独立产生自己的一组序列号:一个奇数一个偶数,或者切入节点唯一标识符。 用足够高的分辨率的墙上时间戳附加到每个操作上。 预先分配区间范围,并及时扩容。 Lamport 时间戳 可以产生因果关系一致的序列号。Lamport 时间戳是一个值对 (计数器,节点 ID) : 节点 ID:每个节点都有一个唯一标志符。 计数器:每个节点都有一个计数器记录各自处理的请求总数。 优点: 两个节点可能存在相同的计数器,但是时间戳中的节点 ID 可以确保每个时间戳都是唯一的。 保证全序:比较两个 Lamport 时间戳,计数器较大的时间戳越大,计数器相同则节点 ID 大的那个时间戳越大。 通过节点排序保证了全局因果关系。Lamport 不同于版本矢量:

拜占庭故障

Fencing 令牌

单调时钟与墙上时钟

LeetCode: 47. Permutations II

tags: LeetCode,backtracking 视频解析:https://www.youtube.com/watch?v=s7AvT7cGdSo 在 LeetCode: 46. Permutations 的基础上增加重复的元素。感觉不能依赖于 track + map 的去重逻辑回溯。 class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; } }; 数据特征: Value: 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, Index: 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> ret; int n, i; vector<vector<int>> perms; if (nums.

分布式系统挑战

tags: 分布式 故障与部分失效 单节点一般是要么工作要么失效,但是分布式系统多节点面临部分失效,大大提高了分布式系统的复杂性。 单节点软件特性: 硬件正常工作时,相同的操作通常总会产生相同的结果,即确定性。 如果发生了某种内部错误,我们宁愿使计算机全部崩溃,而不是返回一个错误的结果。 云计算和超算 超算:垂直扩展的极端,设置检查点,一点节点故障则全部失效从上一个检查点重新开始(离线批处理),类似单机上内核崩溃。 云计算:水平扩展的极端 传统企业位于两个极端的中间 分布式可靠必然面临部分失效,需要依赖软件系统来提供容错机制。我们需要在不可靠的组件上构建可靠的系统。 不可靠网络 分布式无共享系统:成本低廉。 互联网以及大多数 IDC 内部网络都是异步网络:不保证发送一定到达(排队),等待响应时可能出现任何错误。 现实中的网络故障非常普遍 故障检测:HA、主从切换、保活机制(ICMP,SYN) 超时与无限期的延迟 网络拥塞与排队 网络负载过高会出现拥塞。 数据在发送的过程中分别会在发送端和接收端进行排队:等待发送和等待处理。 TCP 的拥塞控制机制。 虚拟化 CPU 核切换虚拟机 同步与异步网络 同步网络:固定电话网络,一路电话分配固定的电路、有带宽保证,规定延迟内保证完成数据包发送,不会丢弃数据包,成本高,利用率低 异步网络:数据中心网络,共享带宽,无法保证延迟和数据包发送,成本低廉,利用率高 不可靠时钟 单调时钟与墙上时钟 时间同步与准确性 计算机中的石英钟不够精确 NTP 服务器不稳定(网络、防火墙或服务本身) 虚拟机中时钟是虚拟化的。 终端设备不可控:休眠、故意设置 依赖同步的时钟 时钟陷阱: 一天可能不总是 86400 秒 回拨 多个节点上的时间完全不相同 需要精确同步的时钟: 自己监控所有节点上的时钟偏差 某个节点时钟漂移超出上限则将其宣告失效 时间戳与时间顺序 最后写入者获胜 时钟的置信区间 通过直接安装 GPS 接收器或原子(铯)时钟,它的误差范围通常可以查询制造商手册。 全局快照的同步时钟 Google Spanner 根据部署了 GPS 接收器或者原子时钟的 TrueTime API 返回的时钟置信区间。确保读事务足够晚发生,避免与先前事务的置信区间产生重叠。 进程暂停 垃圾回收 虚拟化暂停虚拟机 磁盘 I/O 内存交换分区 手动暂停进程(SIGSTOP/SIGCONT) 响应时间保证 RTOS 系统 调整垃圾回收的影响 知识,真相与谎言 真相由多数决定:Quorum 一致性 主节点与锁 Fencing 令牌 拜占庭故障 理论系统模型与现实 计时方面

LeetCode: 46. Permutations

tags: LeetCode,backtracking Keywords backtrack 回溯算法 图解 举例: [1, 2, 3] ,顺着叶子节点和删除的节点就可以还原成全排列。 从上面图可以看出来,叶子节点加上回溯路径上被移除的节点就是结果的一项,从左到右依次是: [3,R:2,R:1] -> [3,2,1] [2,R:3,R:1] -> [2,3,1] … class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> track; backtrack(res, track, nums); return res; } void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); i++) { if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) { continue; } track.

JavaScript 内存模型 (2017)

C、Rust 和 Swift 的内存模型

C++ 弱同步原子(acquire/release atomic)

tags: C++11 内存模型,C/C++ C++ 还添加了较弱的原子,可以使用 atomic_store_explicit 和 atomic_load_explicit 以及附加的n内存排序参数来访问这些原子。使用 memory_order_seq_cst 使显式调用等效于C++ 同步原子(atomic)较短的调用。 较弱的原子称为 acquire/release 原子,一个 release 如果被后来的 acquire 观察到,那么就创建了一个 happen-before 的关系(从 release 到 acquire)。这个术语意在唤起 mutex:release 就像 unlock mutex , acquire 就像锁定同一个 mutex 。release 之前执行的写入必须对后续 acquire 之后执行的读取可见,就像解锁 mutex 之前执行的写入必须对后解锁 mutex 之后执行的读取可见一样。 atomic<int> done; // Thread 1 // Thread 2 atomic_store(&done, 1, memory_order_release); while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ } acquire/release 原子只对单个内存位置的操作进行顺序一致的交替执行,所以属于内存一致性(coherence)而非顺序一致性。 来看下面 litmus test: Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0?

C++ 非同步原子(Relaxed atomic)

C++ 同步原子(atomic)

DRF-SC 还是着火(Catch Fire)

C++11 内存模型

Java 同步原子(volatile)

线程的创建前置于(happens bofere)线程的第一个动作。 互斥体 m 的解锁前置于(happens before)任何 后续(subsequent) 对互斥体 m 的锁定。 volatile 变量 v 的写入前置于(happens bofere)任何 后续(subsequent) 对变量 v 的读取。 “后续(subsequent)” 意味着什么?Java 定义了所有锁定、解锁和 volatile 变量访问的行为,给出了整个程序中所有这些操作的总顺序,就像它们发生在某个顺序一致的交错中一样。“后续(subsequent)”指在总顺序中较晚执行。也就是说:锁定、解锁和 volatile 变量的访问的“总顺序”定义了“后续”的含义,“后续”定义了由特定执行创建的“前置于(happens before)”关系,最终“前置于(happens before)”关系定义了该特定执行是否存在数据竞争。如果没有数据竞争,那么执行就会以顺序一致的方式进行。 事实上, volatile 访问必须表现得像在某种总排序一样,意味这在下面 litmus test 中,不能出现 r1=0 和 r2=0 的结果: Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no.

Java 决定竞争读写的具体规则

内存顺序一致性(sequential consistency)

内存一致性(coherence)

Memory coherence vs consistency

Coherence deals with maintaining a global order in which writes to a single location or single variable are seen by all processors. Consistency deals with the ordering of operations to multiple locations with respect to all processors. Memory coherence: a memory system is coherent if any read of a data item returns the most recently written value of that data item (what values can be returned by a read).

悲观与乐观并发控制

可串形化的快照隔离

两阶段加锁

串行化

写倾斜

写倾斜与幻读

防止更新丢失

更新 Go 内存模型

LeetCode: 25. Reverse Nodes in k-Group

tags: LeetCode source: https://leetcode.com/problems/reverse-nodes-in-k-group/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { deque<ListNode*> dq; ListNode* cur = head; ListNode* top = nullptr; ListNode* tail = nullptr; bool first_k = true; while (cur !

事务隔离级别

ACID

事务

LeetCode: 92. Reverse Linked List II

tags: LeetCode source: https://leetcode.com/problems/reverse-linked-list-ii/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { stack<int> st; ListNode* cur = head; ListNode* prev_start = nullptr; if (left == 1) { prev_start = new ListNode(0, head); // dummy prev_start point to head } int i = 1; while(cur !

Emacs Projectile 优化

Java 内存模型

新的 Java 内存模型(2004)

Java 编译器公共子表达式消除(common subexpression elimination)

原始 Java 内存模型(1996)

DRF-SC 系统同步指令

同步原子(synchronizing atomic)

原子变量(atomic variable)或原子操作(tomic operation)

现代语言以原子变量(atomic variable)或原子操作(atomic operation)的形式提供特殊能力,允许程序同步其线程(参见硬件内存一致性模型)。 代码示例 // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); 如果使用原子变量实现 done 会产生很多效果: Thread 1 的编译代码必须确保对 x 的写入完成,并且对 done 的写入可见之前对 x 的写入对其他线程可见。 Thread 2 的编译代码必须在循环的每次迭代中(重新)读取 done 。 Thread 2 的编译代码必须在读取 done 之后才读取 x 。 编译后的代码必须做任何必要的事情来禁用可能会重新引入这些问题的硬件优化。 使 done 原子化的最终结果是程序按照我们想要的方式运行,成功地将 x 的值从 Thread 1 传递到 Thread 2 。 上面代码如果不使用原子变量会出现 Thread 1 和 Thread 2 读取 x 的同时写 x ,从而导致数据竞争(data race)。 done 使用原子变量实现后,用于同步对 x 的访问: Thread 1 现在不可能在 Thread 2 读取 x 的同时写 x,从而避免数据竞争。 这是硬件内存模型弱有序和无数据竞争(DRF)在编程语言环境的应用。

弱有序和无数据竞争(DRF)

ARM/POWER Relaxed Memory Model

ARM和POWER系统的概念模型是,每个处理器从其自己的完整内存副本中读取和向其写入,每个写入独立地传播到其他处理器,随着写入的传播,允许重新排序。 在这个宽松的(relaxed)模型中,我们迄今为止所看到的每一个litmus test的答案都是“yes,这真的可能发生。” Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. On ARM/POWER: yes! Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no.

内存屏障

x86 总存储有序(x86-TSO)

x86 总存储有序(x86 Total Store Order, x86-TSO):所有处理器仍然连接到一个共享内存,但是每个处理器都将对该内存的写入(write)放入到本地写入队列中。处理器继续执行新指令,同时写操作(write)会更新到这个共享内存。一个处理器上的内存读取在查询主内存之前会查询本地写队列,但它看不到其他处理器上的写队列。其效果就是当前处理器比其他处理器会先看到自己的写操作。 重要的是: 所有处理器都保证写入(存储 store)到共享内存的(总)顺序,所以给这个模型起了个名字:总存储有序(Total Store Order,TSO)。 写队列是一个标准的先进先出队列:内存写操作总是以与处理器执行相同顺序的应用于共享内存。 基于以上下面 litmus test 的答案依然是 no ,这种情况与顺序一致性模型结果一致: Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. 但其他测试则并不一致区分与顺序一致性的常用例子: Litmus Test: Write Queue (also called Store Buffer) Can this program see r1 = 0, r2 = 0?

litmus test

顺序一致性

Leslie Lamport 1979 年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 定义: The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

内存一致性模型

硬件内存模型

Emacs 优化启动速度

动态再平衡策略

基于词条的二级索引分区

基于文档分区的二级索引

基于关键字哈希值分区

基于关键字区间分区

系统热点

负载倾斜

数据分区

syn

quote

Rust 属性宏解析

准备 解析宏通过两个 crate 进行: quote = “1.0” syn = “1.0” Derive 属性宏 探讨 Rust 宏系统中带属性(Attributes)的 Derive 宏的几种变体,以及如何进行解析。 属性宏的变体 函数调用 #[derive(Custom)] struct Demo { #[attr(arg)] a: i8, } 关键字参数调用 #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 直接赋值 #[derive(Custom)] struct Demo { #[meta = "val"] c: i8, } 函数调用 关键字参数调用 可以从 Struct 解析出各个字段,通过解析各个字段的 attrs 属性,并对 attrs 进行遍历,使用 attr.parse_args()? 即可解析出对应的关键字参数,咱们以前面的代码为例: #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 对应的解析代码为:

Happens-before 关系和并发

检测并发写

sloppy quorum

Quorum 一致性

无主节点复制

全部-至-全部型拓扑

星型拓扑

环形拓扑

最后写入者获胜

收敛于一致的状态

避免冲突

前缀一致读

单调读一致性

强一致性

读写一致性

最终一致性效应

复制滞后问题

复制日志实现

主从复制

数据复制

认同的话

Actor

Avro

Thrift 与 Protocol Buffers

数据编码与演化

OLAP

OLTP

B-trees

哈希索引

排序字符串表:SSTables

LSM-Tree

数据存储与检索

数据模型与查询语言

可靠、可扩展与可维护的应用系统

《数据密集型应用系统设计》读书笔记

项目代号

macOS 问题解决三板斧

macOS TimeMachine 日志

English IPA

tags: Learning English 一些通用的规则: 音标后面的 ː 提示拖长音。 元音 大而圆 音标 中文 发音技巧 常见单词 拼读规则 /​æ​/ 爱 张大嘴发中文的「爱」,发音短促有力。 bag map dad sad a /​e​/ 爱 音同 /​æ​/ 但是嘴形要小一些。 get let pen yes e /​ɔː​/ 哦 嘴巴轮圆了发音,并拖长音 floor door store sport oor,ore,or /​ɔ​/ 哦 /​ɔː​/ 的短音 lot dog hot shop o 扁扁扁 音标 中文 发音技巧 常见单词 拼读规则 /iː​/ 一 相比一嘴要扁一些,稍稍更用力一些 see meet he she ee, e /​i​/ 一 /iː​/ 短音 happy daddy honey 词尾的 y 或 ey /​I​/ 一 用 /​e​/ 的嘴形发 /​i​/ this give it city i /əː​/ 呃 相比中文嘴要扁一些,稍稍更用力一些 work girl dirt sir or, ir /​ə​/ 呃 /əː​/ 的短音 again a father weather 单独的 a 及词尾的 er 需要额外注意的:

二叉树的遍历

tags: Algorithm,Data Structures,Binary Search Tree 分为三种:前序、后序和中序,其中最容易用栈改写的是后序。 前序(Preorder):Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector.

OX-HUGO 批量导出 Markdown

中间件

技术随想

C/C++ thread-local storage

macOS max open files

GDB 打出所有线程的 Backtrace

C++ LSP

Python behind the scenes #2: how the CPython compiler works

tags: Translate,Incomplete,Python Python 幕后 #2: CPython 编译器如何工作 今天的主题(Today’s subject) 在本系列的第一篇文章中我们研究了 Python 虚拟机。我们学了解到它通过执行一系列叫做字节码(bytecode)的指令。 我们也看到 Python 字节码没有完全描述代码片段的行为。这也是为什么存在一个代码对象(code object)的概念。 执行诸如函数或模块的代码块也就是执行对应的代码对象。代码对象包含了代码块的字节码,包含代码中使用的常量和变量名, 还有代码块的一些属性。 通常,一个 Python 程序员不用编写字节码,并且也不用创建代码对象,而是编写正常的 Python 代码。所有 CPython 必须 能够将源代码转换成代码对象。CPython 编译器就负责这部分工作。我们将通过这部分内容探索它是如何工作的。 Note: 本文参考 CPython 3.9。一些实现细节将必然会随着 CPython 的演进而改变。 我将会尝试关注一些重要的改变并添加更新备注。 什么是 CPython 编译器(What CPython compiler is) 我们已经了解了 CPython 编译器的职责,但是在我们进入到它是如何实现的之前,让我们首先来搞清楚为什么我们称之为编译器? 在通常情况加,编译器是一个将一个程序语言翻译到另一个与之等价的程序语言的程序。编译器有许多种类,但是通常情况下我们 讨论的都是静态编译:将一个高级语言的程序翻译成机器码。CPython 编译器也是这样吗?要回答这个问题,我们先看一下静态编 译器的传统三阶段设计(three-stage design)。 编译器前端(frontend)将源代码转换成一种中间语言(IR,intermediate representation)。然后优化器(optimzer)拿到中间语言 对其进行优化并把优化过的中间语言传递给编译器后端生成机器码。如果我们选择一种源语言和目标机器无关的中间语言,我们就 得到了三阶段设计的关键益处:对于一个编译器来说,支持一种新的源语言仅仅需要新增一个对应的编译器前端,支持一种新的目标机器 仅仅需要新增一个对应的编译器后端。 LLVM 工具集(toolchain)就是这个模型的一个很好的成功的例子。有很多编译器前端如 C、Rust、Swift 等其他很多编程语言基于 LLVM 提供给编译器更加复杂的部分。LLVM 的创建者 Chris Latter 提供了一个很好的 LLVM 架构概览。 CPython 尽管不需要支持多个源语言和目标机器,尔仅仅需要支持 Python 代码和 CPython 虚拟机。不过,CPython 同样实现了三阶段设计。 如果想知道为什么,我们需要更加详细的解释编译器的三阶段的每个阶段。

straight.el 命令

straight.el 更新所有已安装的包

Emacs Buffer 名字去重

范数(norm)

MAE(平均绝对误差)

RMSE(均方根误差)

机器学习涉及数学概念

Python behind the scenes #1: how the CPython VM works

tags: Translate,Python 原文链接:Python behind the scenes #1: how the CPython VM works。 Python 幕后 #1: CPython 虚拟机如何工作 介绍(Introduction) 你是否曾经好奇过当你运行 Python 代码时 python 做了些什么? $ python script.py 这篇文章将开启一个系列来尝试解答这个问题。我们将深入 Python 最流行的实现 CPython 的内部。 通过深入 CPython 的内部我们将更深一层的去理解这门编程语言本身。这也是我们这个系列的最主要的目标。 如果你熟悉 Python 并且可以阅读 C 代码,但是对 CPython 源码本身没有太多的经验, 那么你可能非常适合本系列,并且对本系列感兴趣。 什么是 CPython 并且为什么有人想学习它(What CPython is and why anyone would want to study it) 我们首先来说明一些众所周知的事情。CPython 是用 C 编写的 Python 解析器。他是 Python 语言的众多实现 的一种,其他还有诸如 PyPy、Jython、IronPython 等。CPython 的独特之处在于它是 Python 的起源、维护时间最长也是最受欢迎的。

机器学习测试与验证

机器学习的主要挑战

机器学习系统的种类

《机器学习实战》读书笔记

Machine Learning

Rust Obscure Words for non-native English speakers

Rust Asynchronous Programming

tags: Rust Future async fn 将一个代码块转换为一个 Future 对象, Future 对象维护一个状态机 Future 对象必须运行在一个 Executor 上 Executor futures::executor::block_on 阻塞当前线程直到 future 完成 // `block_on` blocks the current thread until the provided future has run to // completion. Other executors provide more complex behavior, like scheduling // multiple futures onto the same thread. use futures::executor::block_on; async fn hello_world() { println!("hello, world!"); } fn main() { let future = hello_world(); // Nothing is printed block_on(future); // `future` is run and "hello, world!

Go Swagger 实现代码即文档

tags: Go 目标 当跟随这篇文章完成后将产出如下内容: 代码 http://gitlab.17zuoye.net/vgo/go-swagger-example 文档 http://swagger.17zuoye.net/?url=http%3A%2F%2F10.200.242.61%3A9090%2Fswagger.json 准备 Go1.14 及以上版本 安装 go-swagger :参见 官方文档。 接下来使用 gin 框架作为示例,如果之前没接触过可以先了解下该框架 创建一个项目 $ mkdir go-swagger-example $ cd go-swagger-example/ $ go mod init gitlab.17zuoye.net/vgo/go-swagger-example 开始使用 首先在你的 `main.go` 定义 go generate 像下面这样: //go:generate swagger generate spec -o ./swagger.yml package main func main() { println("Hello world!"); } 此时如果运行 go generate 在项目目录下就会生成一个 swagger.yml 文件: paths: {} swagger: "2.0" 使用单独的包托管 swagger 相关定义 在之前实践的过程中发现,如果在多个包中定义了相同名称的结构体会到只一个结构体覆盖另外一个结构体的定义。 所以为了解决这个问题,我把所有 swagger 相关的定义都放在同一个包下来避免相同名字的结构体。 创建 swagger/swagger.

MySQL forget password

MVCC

MySQL grant subnet

Network

逻辑右移

算数右移

汇编

tags: Computer Systems,《深入理解计算机系统》读书笔记 程序编码 $ gcc -Og -S mstore.c # outputs mstore.s $ gcc -Og -c mstore.c # outptus mstore.o $ objdump -d mstore.o 所有以 ‘.’ 开头额行都是指导汇编器和链接器工作额伪指令。 数据格式 C 声明 Intel 数据类型 汇编代码后缀 大小(字节) char 字节 b 1 short 字 w 2 int 双字 l 4 long 四字 q 8 char* 四字 q 8 float 单精度 l 4 double 双精度 q 8 访问信息 寄存器 一个 x86-64 的中央处理单元(CPU)包含一组 16 个存储 64 位值的 通用目的寄存器 。

IEEE 浮点数

tags: Computer Systems,《深入理解计算机系统》读书笔记 浮点数小数表示形式 .0111 = \(0x2^{-1}+2^{-2}+2^{-3}+2^{-4}\) IEEE 浮点数表示形式 \[ V=(-1)^s X M X 2^E \] s = 0 表示负数, s = 1 表示正数 M 是二进制表示的小数 E 是阶码 浮点数二进制组成 一个单独符号位 s 表吗符合 k 位阶码字段 exp 编码阶码 E n 位小数字段 frac 编码尾数 M 两种常见的格式 float s = 1 k = 8 n = 23 double s = 1 k = 11 n = 52 三种计算方式 前置的一些值 e 是 exp 位表示的无符号数 f 是 frac 位表示的小数 \(Bias = 2^{k-1} -1\) 规格化的值 规则:阶码字段 exp 的位模式即不全为 0,也不全为 1(单精度 255,双精度 2047) 计算方式 \(E = e - Bias\) $M = 1 + f $ 非规格化的值 规则:阶码字段 exp 全是 0(用于表示 0) 计算方式 \(E = 1 - Bias\) \(M = f\) 可以表示 +0 和 -0。

Choosing a Rust web framework, 2020 edition

SSH

Fearless Concurrency with Rust

Rust Means Never Having to Close a Socket

tags: Translate,Rust,Rust Wrapper Types 原文链接:Rust Means Never Having to Close a Socket Rust 最酷的特性之一就是它可以自动地帮助你管理资源,同时在仍能保持安全(没有段错误)和高性能。 这是因为 Rust 是一门与众不同地编程语言,要理解我说的可能有点困难,让我来更近一步说明: Rust 就像带垃圾回收的编程语言,你无需手动释放内存 Rust 不同于其他带垃圾回收的编程语言,你无需1手动关闭或者释放像文件、套接字和锁这样的资源 Rust 达到以上这些特性不附带任何运行时开销(垃圾回收或者引用计数),并且不牺牲安全性。 如果你曾经造成过一个套接字或者文件泄漏,或者使用过一些抽象方法造成了这些资源的泄漏,那么你就会知道这有多重要。 你可能已经期望通过“使用后释放”来避免内存问题,而与此同时你并没有考虑到没有明确地关闭套接字可能出现类似的错误。我在这里告诉你,还有更好地办法。 如果你使用的是带垃圾回收的编程语言,则应密切关注本文提到的资源管理方面的内容。如果你使用的是像 C/C++ 这样底层编程语言,你可能会对安全方面更加感兴趣。 Rust 的许多特性都是从其他语言借鉴而来。Rust 之所以变得有趣是因为它把所有的这些特性放在了一起,并且在编程语言层面实现了更严格地保证。 实际上,这种编程语言层面的保证让这些特性更加实用。 所有权系统(The Ownership System) 让这种保证工作的方式是通过 Rust 的「所有权(ownership)」系统。不管任何时候你创建一个新的对象,都被创建它的「作用域(scope)」所拥有。 让我们通过一个例子来进一步说明:我们定义一个函数,函数拷贝输入文件到临时文件去处理它,然后拷贝输入文件到输出文件。 fn process(from: &Path, to: &Path) -> IoResult<()> { // creates a new tempdir with the specified suffix let tempdir = try!(TempDir::new("skylight")); // open the input file let mut from_file = try!

Rust 并发

Rust 宏

智能指针

智能指针 表现的像一个指针,拥有数据并允许在对数据进行维护。 通常通过 struct 实现并实现两个特性 Deref 和 Drop Deref 允许智能指针实例行为像一个引用,让代码可以同时处理引用和智能指针 Drop 允许自定义智能指针超出作用域的行为。 标准库常见的智能指针 Box<T> 用于在堆分配值 Rc<T> 引用计数类型,允许多个拥有者 Ref<T> 和 RefMut<T> 和通过 RefCell<T> 访问,运行时取代编译期强制检查借用规则 Box<T> 场景: 编译期未知大小的类型(递归类型(自己包含自己类型的类型,如链表)编译期无法确定大小) // 递归类型 enum List { Cons(i32, Box<List>), Nil, } fn main() { let b = Box::new(5); println!("b = {}", b); let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))); } 避免大量数据转移所有权时发生拷贝 拥有一个实现特定特性的值(不关心具体类型)的所有权 Deref 用于自定义解引用操作符( * ) 的行为,智能指针通过实现该特性来模拟普通引用的行为。 对比 fn main() { let x = 5; let y = &x; assert_eq!

迭代器

生命周期

生命周期 Rust 中的每一个引用都有其生命周期:引用有效的作用域。 大部分情况下生命周期都是隐式和自举的,在无法完成的情况下就需要我们通过生命周期泛型参数帮助编译器进行注解。 生命周期的主要目标是避免悬空指针。 生命周期泛型参数定义各个引用之间(参数和参数、参数和返回值)的关系,并不改变(延长)变量原本的生命周期 &i32 // a reference &'a i32 // a reference with an explicit lifetime &'a mut i32 // a mutable reference with an explicit lifetime 参考以下代码 fn longest<'a>(x: &'a str, y: &'a str) -> &'a str { if x.len() > y.len() { x } else { y } } 以上代码 标注生命周期 'a 函数有两个引用参数,都使用生命周期 'a 表示两个参数的生命周期必须一致(存活的周期一样长) 函数返回一个引用,并且存活的时间和生命周期 'a 一致 以上指定不改变任何传入的引用的生命周期,我们只是要求借用检查器(borrow checker)检查这些约束。 也就是说借用检查器要检查传入的两个引用的生命周期必须一致,返回的引用的存活周期不能超过传入的引用的存活周期 思考 当函数返回一个引用时,返回值的生命周期注解要和参数的其中之一相匹配,否则那么引用就是指向里函数内创建的值(不能返回)。 也就是说返回引用时,引用的声明周期必须和参数(其一)相关。如果想要返回函数内创建的值最好返回一个有所有权的值类型。 结构体生命周期 如果结构体需要持有引用,需要在定义结构体时给每一个引用都加上生命周期注解。

闭包

let add_one = | num | { num + 1 }; 由于闭包和当前上下文相关联,所以 Rust 可以进行类型推导,类型注解也就不是必要的,但是依然可以自己添加: let add_one = | num: i32 | { num + 1 }; fn add_one_v1 (x: u32) -> u32 { x + 1 } let add_one_v2 = |x: u32| -> u32 { x + 1 }; let add_one_v3 = |x| { x + 1 }; let add_one_v4 = |x| x + 1 ; 使用 Fn 存储闭包类型 struct Cacher<T> where T: Fn(u32) -> u32 { calculation: T, value: Option<u32>, } impl Cacher<T> where T: Fn(u32) -> u32 { fn new(calculation: T) -> Cacher<T> { Cacher { calculation, value: None, } } fn value(&mut self, arg: u32) -> u32 { if let Some(value) = self.

Traits

Traits 定义行为在多个类型中共享。 可以定义默认行为在实现者中间共享。 可以用于定义参数的行为,同样可以定义返回值行为,当用 trait 限定返回值类型时,不能同时(if/else)返回多种实现了该 trait 的类型。 pub trait Summary { fn summarize(&self) -> String; } pub struct Article{ pub title: String, } impl Summary for Article { fn summarize(&self) -> String { format!("{}", self.title) } } pub fn notify(item: impl Summary) { println!("{}", item.summarize()); } // trait bound 语法糖版本 pub fn notify<T: Summary>(item: T) { println!("{}", item.summarize()); } 定义参数行为 通过 impl : fn notify(item: impl TraitName) ,用于简单明了的场景,比如一个参数 通过 trait bound : fn notify<T: TraitName> (item: T) ,用于更复杂的场景,比如多个参数用于减少代码 可以通过 + 连接: fn notify(T: TraitName + Display) (item: T)

错误处理

enum Result<T, E> { Ok(T), Err(E), } ? 操作符 对比 use std::io; use std::io::Read; use std::fs::File; fn read_username_from_file() -> Result<String, io::Error> { let f = File::open("hello.txt"); let mut f = match f { Ok(file) => file, Err(e) => return Err(e), }; let mut s = String::new(); match f.read_to_string(&mut s) { Ok(_) => Ok(s), Err(e) => Err(e), } } 和 use std::io; use std::io::Read; use std::fs::File; fn read_username_from_file() -> Result<String, io::Error> { let mut f = File::open("hello.

if let

模块化

模式匹配

枚举

多种类型的集合体,一个类型的变量可以存储多种类型的值,枚举的每一项都是该枚举类型的变体: enum IpAddrKind { V4, V6, } fn main() { route(IpAddrKind::V4); route(IpAddrkind::V6); } fn route(kind: IpAddrKind) { // ... } 枚举的每一个变体都可以直接包含数据,并且每一个变体可以包含不同的数据类型和不同的数量,甚至可以直接放结构体(也可以是匿名的)。 struct Ipv4Addr { // --snip-- } enum IpAddr { V4(Ipv4Addr), V6(String), } let home = IpAddr::V4(127, 0, 0, 1); let loopback = IpAddr::V6(String::from("::1")); struct Message { Quit, Move{ x: i32, y: i32 }, // anonymous struct Write(String), ChangeColor(i32, i32, i32), // three i32 values } 枚举也可以通过 impl 实现方法

结构体

引用和借用

类型前置 & 表示引用,引用允许变量指向一个值但是不发生所有权转移。 引用不占有所有权,所以变量超出作用域之后不会触发 drop 调用。 引用作为函数形参被成为借用(borrowing) 可变引用 针对特定作用域下的特定数据只能创建一个可变引用。如果要创建多个可变引用可以通过大括号创建新的作用域 let mut s = String::from("hello"); { let s1 = mut &s; } let s2 = mut &s; 当已经存在不可变引用时,则无法再创建可变引用,下面代码无法编译通过 let mut s = String::from("hello"); let s1 = &s; // OK let s2 = &s; // OK let s3 = mut &s; // BIG PROBLEM 悬空引用 以下代码是不允许的,无法编译通过 fn main() { let s = dangling_string(); } fn dangling_string() -> &String { let s = String::from("hello"); &s } 上面代码 s 在函数内部分配,那么在函数执行完成后 s 将被释放,所以返回 s 的引用会造成悬空引用。

所有权

规则 每个值都有一个变量叫做所有者(owner) 同一时间只能有一个所有者 当所有者超出作用域则值被销毁 变量作用域 作用域是一个变量有效的范围 当变量超出作用域范围自动调用对象的 drop 方法进行内存归还操作 变量相互作用:所有权转移(Move) 对于所有在栈上分配的值(固定大小),在进行赋值操作时都对值进行拷贝: let x = 5; ley y = x; // copy 5 to y 但是对于在堆上分配的,变量保存的是指向内存的指针,所以在赋值时拷贝的也是指向该内存的指针: let s1 = String::from("hello"); let s2 = s1; 为了保证内存安全,防止 s1 和 s2 超出作用域范围调用两次 drop 造成重复的内存回收,Rust 会让 s1 不再有效,来避免对 s1 进行回收。继续使用 s1 会导致编译错误。这种情况叫做所有权转移(move)。 变量相互作用:克隆(Clone) 克隆用于深度拷贝变量: let s1 = String::from("hello"); let s2 = s1.clone(); println!(s1); 变量项目作用:拷贝(Copy) 如果数据类型的大小在编译期能够确定都将存储在栈上,这种情况下能够进行快速的拷贝。 Copy 特性(trait)注解用于将值存贮在栈栈上 Copy 特性注解不能和 Drop 特性注解混用 Copy 特性注解使用规则如下 所有的数字类型 所有的布尔型 所有的浮点型 字符类型 所有元素都实现了 Copy 特性注解的元祖 所有权和函数 函数传递实参的规则和变量类似,传递变量到一个函数将为发生所有权转移或者拷贝。

语句和表达式

Member initialize

Iterator class

SSE/AVX/AVX2/AVX512

优化

CMake

Build System

Emacs Tmux 256 colors

Rust Trait Object

Rust Wrapper Types

《架构整洁之道》读书笔记

SOLID

SRP: Single Responsibility Principle 浅显的解释是软件模块只提供单一功能 更进一步任何一个软件模块都应该有且只有一个被修改的原因 再更进一步这个原则是关于人(Actor)的 任何一个软件模块都应该只对一个用户或系统利益相关者负责。 最终就是任何一个软件模块都应该只对某一类行为负责 OCP:Open/Closed Principle 设计良好的软件应该易于扩展,同时抗拒修改。也就是说一个软件模块应该允许在不修改源码的情况下扩展它的行为。 可以通过组合 SRP(代码分组)和调整依赖关系实现(DIP)。如果 A 组件不想被 B 组件上发生的修改所影响,那么就应该让 B 组件依赖于 A 组件。 LSP:Liskov Substitution Principle 里氏替换原则:多态。 每个类型是 S 的对象 o1 都存在一个类型为 T 的对象 o2,能使操作 T 类型的程序 P 在用 o2 替换 o1 时行为保持不变,我们就可以将 S 称为 T 的子类型。 public class LiskovSub { public static main(String[] args) { T o1 = new S(); T o2 = new T(); P(o1); // ok P(o2); // ok } public static P(T o) { o.

系统架构

《百箭穿杨》读书笔记

需要熟悉股市相关概念进行扫盲。 粗读要点 树立安全边际,跟随格雷厄姆 寻找好的困难股,降低触底难度,加大触底区间,预测底部区间,分 5 档抄底,最好在 1-3 档就能完成抄底 每次只买总资产的 1% 盈利后可以将本金提出,只留底仓等待顶峰信号后抛出赚取高额利润的前提下保障本金 总是留 25%-40% 的现金 做长线 分析财报看毛利、营收增长率、负债率可以确定一个好股,然后就等一些情况下这只股遇到困难触底 看行业处于哪个周期:萌发、成长啥的 不做重仓 复读要点完善 安全边际 跟随格雷厄姆 偏离:更保守或更激进 大赚小赔不如小赚不赔:不亏钱 困境好企 做有把握的事,不啃硬骨头,广撒网,多捞鱼,选取一批困境好企来实现从小盘大稳定增长股 行业中的好企业标准 行业很关键 需求无限,供给有限 关注行业周期 大周期:新生->成长->成熟->衰落->消亡 小周期:大周期各个过程中的景气与萧条(一两年、三五年甚至一二十年) 消亡之前会有死灰复燃,大周期中成长阶段会有萧条,注意区分。 门槛高,竞争少 只有少数寡头,估值会高 唯一或第一 成熟行业比较简单,成长行业比较困难。 通过企业原则、经营原则、财务原则和市场原则衡量。- P28 生活经验活常识也很重要。 落难好企 行业顺境,某些原因导致的猜疑导致股价下跌 行业遭遇整体困境:偶然事件,反转时间比好把握 个股困境,主打产品破灭:有无法度过的风险 财务数据衡量困境好企能否度过难关 - P32 负债率越低越好:不能超过 50% 资产中的现金越多越好:高于股东权益的 1/3,刚上市的好过上市很久的老企业(把钱折腾光了) 产品的毛利率越高越好:市场有需求 应收账款越少越好:钱可能收不回来 通过季报发现反转时机 季报时间长,抗短期干扰,一季度定调、二季度(半年)纠偏或修正、三季度出结果(更好或更差)、四季度(年报)成果汇报和新的起点用于比较第一季度。 一季度和半年狠重要。 通过 营业收入 发现转机。困境表现为净利润增速下滑,之前是好企可能会市盈率过高。 容错寻底 不亏钱的情况下寻找极限底部,保障安全、带来最大利润、带来良好心态 变种“不破买价”:买入的价格很难再跌回原来的位置 变成左侧交易者,不追涨 大盘底与个股底的关系 同步性:大盘筑底个股也在筑底,大盘达到最低位时,个股也先后到达最低位 差异性 大盘下跌蓝筹股先跌到位,大盘下跌过程中小盘成长股与稳定增长股少许跟跌或逆市上扬。 市场反弹小盘成长股与稳定增长股开始杀跌。 耦合性:大盘底出现时次新股出现底部的概率大,老股形成底部可能需要好几年 – P56

Kafka

tags: Bigdata 相关知识点 概念组成 Producer 消息产生者,往指定 Topic 的指定 Partition 发送消息 Consumer Group 消费指定 Topic 的消息 Consumer 消费指定 Topic 下某一分区的消息 Topic 区分不同消息主题 Partition 保证同一分区的有序性 Connector 消息可被不同的 Consumer Group 重复消费(广播或订阅)。同一 Consumer Group 下的不同 Consumer 分别消费不同的 Partition,Consumer 数量不能超过 Partition 数量。 数据被持久化并分片成功后发送 ACK 保证里数据不被丢失。 设计 持久化 基于文件系统 基于队列是顺序的和磁盘的顺序访问要比内存的随机访问要快(参见 The Pathologies of Big Data), Kafka 采用在磁盘文件系统上尾部写头部读的方式。 Kafka 没有采用 BTree 存储数据因为 BTree 的操作是 O(log N) ,而且对磁盘的 seek 操作要慢,且同时只能进行一次限制了并行,所以实际操作比 O(log N) 要慢 基于磁盘的顺序访问进行在尾部写和头部读,可以实现读写都是 O(1) 的时间复杂度,并且读写互不干扰 基于以上实现,Kafka 可以不必在消息一经消费就删除,而是可以保留消息一段相对较长的时间(比如一周) 高效

LeetCode

LeetCode: Trapping Tain Water

Linux Virtual Memory Management

tags: Linux 原文连接:Linux Virtual Memory Management Chapter 2 Describing Physical Memory:描述物理内存 独立于平台架构的方式描述内存 — 更好的支持多平台 本章包含描述存储器、内存页的结构体(structures)和一些影响 VM 行为的标识位(flags) VM 中普遍(prevlent)认为第一重要(principal)的概念是 NUMA。 大型机器中内存访问速度取决于 CPU 到内存的距离。比如一组(bank)内存分配给每一个处理器或者一组内存非常适合靠近的 DMA 设备卡。 这里的每组(bank)内存被称为节点(node)并且这个概念在 Linux 中通过 struct pglist_data(typedef pg_data_t) 表示,即使在 UMA 架构下也是如此。每一个节点是一个由 NULL 结尾的链表,通过 pg_data_t->next_node 指向下一个节点。 每一个节点都被分割成多个块(block)称为分区(zone)用于表示内存中的范围。分区使用 struct zone_struct(typedef zone_t) 结构体描述,每一个分区都是以下三种类型的一种 ZONE_DMA 开始 16MB 内存,供 ISA 设备使用 ZONE_NORMAL 16MB - 896MB,由内核直接映射到线性地址空间的上部区域(将在第四章讨论) ZONE_HIGHMEM 896MB - END,剩余不由内核直接映射的系统可用内存, 大部分内核操作都只能使用这种类型的分区,所以这里也是这里也是最关键的性能区域(most performance critical zone) 每一个物理页帧(physical page frame)都使用结构体 struct page 表示,所有的结构体都保存在全局数组 mem_map 中,mem_map 通常存储在 ZONE_NORMAL 的开始处;

动态规划

tags: Algorithm 状态转移方程 无后效性 如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。 一旦 \(f(n)\) 确定,“我们如何凑出 \(f(n)\) ”就再也用不着了: 要求出 \(f(15)\),只需要知道 \(f(14)\),\(f(10)\),\(f(4)\) 的值, 而 \(f(14)\),\(f(10)\),\(f(4)\) 是如何算出来的,对之后的问题没有影响。 “未来与过去无关”,这就是无后效性。 最优子结构 大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”: \(f(n)\) 的定义需要蕴含“最优”,利用 \(f(14)\),\(f(10)\),\(f(4)\) 的最优解,我们即可算出 \(f(15)\) 的最优解。 能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。 DP 思路 参见 LeetCode 讨论: 先写出穷举的方法 找出不必要的重复计算 写出 DP 练习 0x00 硬币找零 描述 假设有几种硬币,如1、3、5,并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 状态转移公式 公式 \(f(n)=min\{f(n-1),f(n-3),f(n-5)\} + 1\) 检查是否满足上面提到的两个特性: 无后效性:对于 \(n\),一旦 \(f(n)\) 确定,以后只关心 \(f(n)\) 的值,不关心怎么计算的; 最优子结构:对于 \(n\),只要 \(n - 1\) \(n - 3\) \(n - 5\) 能是最优解,那么就能计算出 n; 推导过程 假设找零 15:

归并排序

算法

Let’s Encrypt

tags: Over the Wall,HTTPs 这里以新增 vd.linuxzen.com 为例。 新增 DNS 解析 通过 DNSPOD 新增 DNS 解析 A 记录 调整 Nginx 新增 HTTP 站点 Nginx 参考配置 server { listen 80; server_name vd.linuxzen.com; include /etc/nginx/snippets/letsencrypt-acme-challenge.conf; } 新增签发证书 $ acme.sh --force --issue -d linuxzen.com -d www.linuxzen.com -d cwiki.linuxzen.com -d monitor.linuxzen.com -d v.linuxzen.com -d vd.linuxzen.com -d d.linuxzen.com -d piwik.linuxzen.com -d t.linuxzen.com -d wiki.linuxzen.com -d note.linuxzen.com -w /var/www/letsencrypt/ 安装证书 $ acme.sh --install-cert -d linuxzen.com --cert-file /etc/nginx/certs/linuxzen.

Over the Wall

V2Ray

tags: Over the Wall,Tools 架构 Client -> DIDIYun(HAProxy) -> HK 滴滴云 HAPorxy 配置 117.51.146.119 frontend v_linuxzen_com bind *:6697 option tcplog mode tcp default_backend v_linuxzen_com_nodes backend v_linuxzen_com_nodes mode tcp balance roundrobin option ssl-hello-chk server webserver1 45.115.36.35:443 check 客户端改动 需要调整 hosts $ echo '117.51.146.119 v.linuxzen.com' | sudo tee -a /etc/hosts HK V2Ray Docker 启动 $ docker run -d -p 127.0.0.1:25001:25001 --name v2ray --restart always -v /etc/v2ray:/etc/v2ray v2ray/official HK Let’s Encrypt 证书 $ acme.

xinetd

tags: Over the Wall,Network xinetd 代理 SMTP 和 IMAP 通过 xinetd 代理 SMTP 和 IMAP 实现 gmail 翻墙。 配置服务端 service imap { type = UNLISTED port = 993 bind = 0.0.0.0 socket_type = stream wait = no user = nobody redirect = imap.gmail.com 993 per_source = UNLIMITED cps = 100 2 } service smtp-465 { type = UNLISTED port = 465 bind = 0.0.0.0 socket_type = stream wait = no user = nobody redirect = smtp.

股市相关概念

基金定投

Deep Learning

AI

《巴比伦富翁新解》读书笔记

CPI

ELisp

Financial Management

Go

Go Channel

Helm

Makefile

Unix

基金

复利

夏普比率

标准差(Standard Deviation)

CPI

《领域驱动设计》读书笔记

tags: 正在读的书,读书笔记,DDD 前言和目录 好的软件需要控制复杂性,好的领域模型可以帮助控制复杂性。 什么样的项目需要 DDD?尝试型的小型项目应该不需要 DDD,但是一旦上了规模考虑后续迭代则需要 DDD。 本书组织方式: 领域建模 领域建模的过程就是消化知识的过程,这个过程应该贯穿整个开发过程,需要持续学习。 模型用来描绘人们所关注的实现或想法的某个方面,比如地图就是模型。 模型是一种简化,是对实现的解释:把与解决问题密切相关的方面抽象出来,而忽略无关的细节。 软件问题建模的区域就是软件的领域 物质世界的领域:机票预订程序涉及的飞机乘客。 无形的领域:会计程序的金融领域。 领域涉及知识信息超载的问题,模型这种知识对知识进行了选择性的简化和有意的结构化。 领域模型将领域专家头脑中的支持严格的组织且有选择的抽象,并不是尽可能建立一个符合“现实”的模型。 模型表示 关联 规定一个遍历方向:存在双向联结时(地址 -> 人 或 人 -> 地址)尽量只用一种,并避免互相关联 添加一个限定符,以便有效减少多重关联 消除不必要的关联 表示方式 领域模式 实践 MODEL-DRIVEN DESIGN 隔离领域:引入应用层 应用 LAYERED ARCHITECTURE 把领域层划分出来,通过应用层类来处理应用程序功能。应用层类是协调者,负责提问,领域层负责回答。 将 ENTITY 和 VALUE OBJECT 区分开 依次考虑对象是必须跟踪的 ENTITY 还是表示一个 VALUE OBJECT。 AGGREGATE 边界 识别模型中的 AGGREGATE 根和对应的边界。 选择 REPOSITORY 为 AGGREGATE 根对象建立 REPOSITORY。 场景走查 根据应用程序特性复核建模,进行场景走查,确保能够有效地解决应用问题。可以走查一些正常和异常业务场景进行复核。 对象创建 如果对象复杂则创建单独的 FACTORY 类进行对象创建,简单对象可以直接在 AGGREGATE 根上通过 FACTORY METHOD 进行创建。

LeetCode: 316.Remove Duplicate Letters

tags: LeetCode 移除小写字母中重复的字母,让所有字母都只出现一次,并且结果是所有结果中按照字典序排序最小的那个。 Example 1 Input: “bcabc” Output: “abc” Example 2 Input: “cbacdcbc” Output: “acdb” 解法之一: 通过一个数组对每一个出现的字母进行计数 遍历每一个字母放入栈,并将该字母的计数减 1 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的(有比当前更小的字典序),从栈底弹出该字母 func removeDuplicateLetters(s string) string { var countOfEachLetter [26]int var visited [26]bool stack := make([]byte, 0) stackBottom := 0 bytesArr := []byte(s) for _, c := range bytesArr { countOfEachLetter[getIndex(c)]++ } for _, c := range bytesArr { index := getIndex(c) countOfEachLetter[index]-- if visited[index] { continue } // countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符 for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 { // 标记为未访问用于后面的字符加入结果 visited[getIndex(stack[stackBottom])] = false // 移动栈底 stackBottom++ } // 加入到结果栈 stack = append(stack, c) visited[index] = true } return string(stack[stackBottom:]) } func getIndex(b byte) int { return int(b - 'a') } 通过上面解法遇到如下错误:

LeetCode: 153.Find Minimum in Rotated Sorted Array

tags: LeetCode 解法 1 找到中间节点依次往左右扩散: 向左边扩散,如果左边的大于当前元素,那么当前元素即为最小值 向右边扩散,如果右边的小于当前元素,那么右边元素即为最小值 如果以上不成立则第一个元素为最小元素(未旋转),以下是代码 func findMin(nums []int) int { length := len(nums) if length == 1 { return nums[0] } // 从中间开始确定方向 mid := length / 2 - 1 left, right := mid, mid for left - 1 >= 0 || right + 1 < length { if left - 1 >= 0 { if nums[left - 1] > nums[left] { return nums[left]; } left-- } if right + 1 < length { if nums[right] > nums[right + 1] { return nums[right + 1] } right++ } } return nums[0] } 优化 参考答案后可通过二分查找做如下优化,首先判断是否被旋转:

LeetCode: 154.Find Minimum in Rotated Sorted Array II

LeetCode: 3.Longest Substring Without Repeating Characters

tags: LeetCode 准备 动态规划 实践 字符串 “abcabcbb” 根据索引有如下关系 a b c a b c b b 0 1 2 3 4 5 6 7 \(f(0,1)=f(0,0) + 1\) \(f(0,2)=f(0,1) + 2\) 在所有字符都不重复的情况下有如下公式 \(f(s,e)=f(s,e-1) + e\) 若遇到重复的情况则,3 索引于当前字串 的 0 重复则表明当前字串已经到头,需要记录并偏移 s,s=1: \(f(1,3)=f(1,2)+3\) 假设: s - 开始字符索引 e - 结束字符索引 若遇到当前字符于前面 r 字符重复则: \[ f(r,e)=f(s,e - 1) + e; s=r \] 解法 func lengthOfLongestSubstring(s string) int { if len(s) == 0 { return 0 } appearedIndexes := [256]int{} for i := 0; i < 256; i++{ appearedIndexes[i] = -1 } longest, start, end := 0, 0, 0 b := []byte(s) for cIndex, c := range b { index := int(c) appearedIndex := appearedIndexes[index] end = cIndex // 出现过需要截断 if appearedIndex !

LeetCode: 4.Median of Two Sorted Arrays

tags: LeetCode 思路 归并排序 代码 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { nums := mergeSort(nums1, nums2) length := len(nums) if length % 2 != 0 { return float64(nums[(length - 1) / 2]) } i := length / 2 return (float64(nums[i]) + float64(nums[i - 1])) / 2 } func mergeSort(nums1 []int, nums2 []int) []int { l1 := len(nums1) l2 := len(nums2) result := make([]int, 0, l1 + l2) i, j := 0, 0 for i < l1 && j < l2 { if nums1[i] < nums2[j] { result = append(result, nums1[i]) i++ } else { result = append(result, nums2[j]) j++ } } result = append(result, nums1[i:].

LeetCode: 5.Longest Palindromic Substring

tags: LeetCode > https://leetcode.com/problems/longest-palindromic-substring/description/ 思路 直接暴力往两边搜索 func longestPalindrome(s string) string { buf := []byte(s) length := len(buf) if length == 0 { return s } start, end := 0, 0 for ci, _ := range buf { i, j := ci, ci // 无法处理 "aaaa" 和 "noon" 这种情况 for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] { i-- j++ } // 考虑 "bba" 这种情况 if i == j && ci > 0 && buf[ci] == buf[ci - 1] { i, j = ci-1, ci } // 考虑 "abb" 这种情况 if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] { i, j = ci, ci + 1 } if i !

LeetCode: 6.ZigZag Conversion

MySQL

《The Rust Programming Language》读书笔记