Algorithm

参考文献 Gossip协议

参考文献 一文读懂11个主流共识算法, 彻底搞懂PoS,PoW,dPoW,PBFT,dBFT这些究竟是什么鬼 分布式一致性与共识算法 Raft user study Paxos 共识简介 所谓共识，简单理解就是指大家都达成一致的意思. 拜占庭容错算法 工作量证明(PoW,Proof of Work) 简单理解就是一份用来确认你做过一定量的工作的证明。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，则是一种非常高效的方式。比如现实生活中的毕业证、驾驶证等等，也是通过检验结果的方式(通过相关的考试)所取得的证明。 工作量证明系统(或者说协议、函数)，是一种应对拒绝服务攻击和其他服务滥用的经济对策。它要求发起者进行一定量的运算，也就意味着需要消耗计算机一定的时间。 实用拜占庭容错算法(PBFT：Practical Byzantine Fault Tolerance) 非拜占庭容错算法/故障容错算法（Crash Fault Tolerance，CFT） CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。 也就是说， ...

参考文献 https://en.wikipedia.org/wiki/Exponential_backoff 指数退避算法设计与原理 指数退避算法 实例 spring-retry org.springframework.retry.interceptor.RetryInterceptorBuilder 示例 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106package cn.holelin.ct.pacs.manager;import cn.hutool.json.JSONUtil;import cn.holelin.ct.pacs.config.DefaultPacsServerProperties;i ...

参考文献 内存分配算法 常用的内存分配算法: 动态内存分配(Dynamic memory allocation DMA) 伙伴算法 Slab算法 动态内存分配(Dynamic memory allocation DMA) 动态内存分配,又称堆内存分配.操作系统根据程序运行过程中需求及时分配内存,且分配的内存大小就是程序需求的大小.在大部分场景下,只有程序运行的时候才知道所需要分配的内存大小,如果提前分配可能分配的大小无法把控,分配太大会浪费空间,分配太小会无法使用. DMA是从一整块内存中按需分配,对于分配的内存会记录元数据,同时还会使用空闲分区链维护空闲内存,便于在内存分配时查找可用的空闲分区.常用的有三种查找策略: 首次适应算法(first fit) 循环适应算法(next fit) 最佳适应算法(best fit) 首次适应算法(first fit) 空闲分区链以地址递增的顺序,将空闲分区以双向链表的形式连接在一起,从空闲分区链中找到第一个满足分配条件的空闲分区,然后从空闲分区中划分一块可用内存给请求进程,剩余的空闲分区仍然保留在空闲分区链中. 如下图 ...

参考文献 Graph 基础概念 顶点 边 未加权图 加权图 顶点矩阵 邻接表

参考文献 CSP问题 CSP问题是指约束满足问题（Constraint Satisfaction Problem），是一类重要的人工智能问题。在CSP问题中，变量的取值受到一定的约束条件限制，目标是找到满足所有约束条件的变量取值。常见的CSP问题有地图着色、八皇后、数独等。解决CSP问题的方法包括回溯算法、约束传播、启发式搜索等。CSP问题在人工智能领域有着广泛的应用，如排课、时间表安排、资源分配等。通过有效的算法和技术，可以高效地解决各种实际问题。 澳大利亚地图着色问题 The Australian map-coloring problem 八皇后问题 The eight queens problem Word search 现有框架 choco-solver https://github.com/chocoteam/choco-solver

搜索 Classic Computer Science Problems in Java 线性搜索 二分搜索(Binary search) 深度优先搜索(DFS Depth-first search) 12345678910111213141516171819202122232425262728public static <T> Node<T> dfs(T initial, Predicate<T> goalTest, Function<T, List<T>> successors) { // frontier is where we've yet to go Stack<Node<T>> frontier = new Stack<>(); frontier.push(new Node<>(initial, null)); // explored is where we've been Set<T> explored = new H ...

参考文献 随机算法 随机算法,顾名思义就是从可用的服务节点中,随机挑选一个节点来访问. 在实现时,随机算法通常是通过生成一个随机数来实现,比如服务有 10 个节点,那么就每一次生成一个 1～10 之间的随机数,假设生成的是 2,那么就访问编号为 2 的节点. 采用随机算法,在节点数量足够多,并且访问量比较大的情况下,各个节点被访问的概率是基本相同的. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/* * Copyright 2009-2016 Weibo, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obta ...

参考文献 算法第四版 算法分析中常见函数 描述 记号 定义 调和级数 HNH_{N}HN​ 1+1/2+1/3+1/4+...+1/N1+1/2+1/3+1/4+...+1/N1+1/2+1/3+1/4+...+1/N 阶乘 N!N!N! 1∗2∗3∗4∗...∗N1*2*3*4*...*N1∗2∗3∗4∗...∗N 算法分析中常用的近似函数 描述 近似函数 调和级数求和 HN=1+1/2+1/3+1/4+...+1/N∼lnNH_{N}=1+1/2+1/3+1/4+...+1/N \sim lnNHN​=1+1/2+1/3+1/4+...+1/N∼lnN 等差数列求和 1+2+3+4+...+N∼N2/21+2+3+4+...+N \sim N^{2}/21+2+3+4+...+N∼N2/2 等比数列求和 1+2+4+8+...+N=2N−1∼2N1+2+4+8+...+N=2N-1 \sim 2N1+2+4+8+...+N=2N−1∼2N,其中N=2nN=2^{n}N=2n 斯特灵公式 lg⁡N!=lg⁡1+lg⁡2+lg⁡3+ ...

参考文献 数据结构与算法之美 递归 去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示 递归需要满足的三个条件 一个问题的解可以分解为几个子问题的解 子问题就是数据规模更小的问题。 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。 递归代码编写 写递归代码最关键的是写出递推公式，找到终止条件. 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码 编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤 拆任务，找递推，定边界 如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问 ...