ARTS Week13



Algorithm

字符串的最大公因子



字符串的最大公因子必然可以将字符串整除，也就是说，字符串都是由相同的子串组成的

那么两个字符串相互拼接结果应该是相同的

str1 + str2 = str2 + str1

如果这个等式不成立，说明两个字符串不存在公因子

将下来，就要看这两个字符串的公因子长度。

例如 “ABCABC” 和 “ABC” 长度是6 和 3，所以必须存在一个数能整除6和3，那么这个是3.

这是数学的求数字的最大公因子的问题了。



Review

How to think like a programmer — lessons in problem solving

像程序员一样思考到底意味着什么？以及你如何做到的？本质上， 这是解决问题的更有效方法。解决问题是最重要的，几乎所有的雇主都将解决问题的技能放在首位，可是如何去解决问题呢？

1. 了解。确切知道要问什么。大多数棘手的问题之所以棘手，是因为您不理解它们

2. 计划。不要没有计划就直接投入解决方案（以某种方式希望您能摸索到底）。规划您的解决方案！否则就像是无头苍蝇一样乱飞，能不能到达目的地纯粹靠运气

3. 划分。是最重要的一步。不要试图解决一个大问题。那会使你崩溃。而是将其分解为多个子问题。这些子问题更容易解决

4. 实践。实践。实践。实践。认识到“使用“在此处插入概念”可以轻松解决此问题”只是时间问题。



每个程序员都会遇到无法解决的难题，他使你卡在某个地方，请不要担心。这发生在每个人身上。

• 调试：逐步解决您的解决方案，以查找错误的地方。程序员将其称为调试

• 重新评估： 退后一步。从另一个角度看问题。有什么可以抽象为更通用的方法的吗

• 研究： 啊，Google不错。您没看错。无论您遇到什么问题，都可能有人解决了。



Tip

负载均衡器的实现。

我们需要有n个进程同时去处理我们程序，我们需要实现的功能，同一个客户端的请求只能由一个进程去处理。也就是我们需要实现一致性哈希。



定义一个 LoadBalance 类



首先定义进程的数量和每个进程有多少个虚拟节点，为什么需要虚拟节点这里就不多说了，可以看看

Share的 负载均衡策略之一致性哈希 这篇文章。

const NUM_PROCESSES = 3; // 处理进程数
const VIRTUAL_NODE = 20; // 虚拟节点

初始化进程和虚拟节点

/**
* 初始化进程名称
*/
private function initProcesses()
{
	for ($i = 0; $i < self::NUM_PROCESSES; $i++) {
      array_push($this->services, 'process_' . $i);
  }
}
/**
 * 初始化虚拟节点
 */
private function initVirtualNodes()
{
    for ($i = 0; $i < self::VIRTUAL_NODE; $i++) {
        foreach ($this->services as $service) {
            $key = $this->getHashCode($service . '_' . $i);
            $this->treeMap[$key] = $service;
        }
    }
}

关于是一致性问题，我们通过实现 hashCode 方法来确定客户端应当落在哪个进程。

/**
 * 获取字符串的hashCode
 *
 * @param string $text
 * @return int|float
 */
public function getHashCode(string $text)
{
    $mdv = hash('md5', $text);
    $mdv1 = substr($mdv,0,16);
    $mdv2 = substr($mdv,16,16);
    $crc1 = abs(crc32($mdv1));
    $crc2 = abs(crc32($mdv2));
    return $crc1 * $crc2;
}

接下来，当有客户端请求的时候，我们对客户端的唯一标识进行 hashCode， 然后与之前生成的 treeMap 的key的hashCode进行比较，剔除掉比客户端的唯一标识的hashCode小的项，然后获取数组第一个，就是当前

Share



负载均衡策略之一致性哈希

负载均衡策略之最少连接

最少连接策略指的是从已有的后端列表中选择正在处理的连接数/请求数最少的节点出来提供服务。我们可以通过负载均衡的算法，去实现类似负载均衡。