Linux迷+Python粉 - 技术https://blog.pythonwood.com/2021-12-14T23:46:00+08:00K8S运维总结之关于Kubernetes项目最佳实践的思考2021-12-14T23:46:00+08:002021-12-14T23:46:00+08:00pythonwoodtag:blog.pythonwood.com,2021-12-14:/2021/12/K8S运维总结之关于Kubernetes项目最佳实践的思考/<p>Kubernetes [kubə&rsquo;netis]简称<span class="caps">K8S</span>或Kube,平时使用<span class="caps">K8S</span>主力是Minikube,在几个项目生产实践中,则使用<span class="caps">GCP</span>/<span class="caps">AWS</span>/阿里云的对应的<span class="caps">K8S</span>实现,<span class="caps">GKE</span>/<span class="caps">EKS</span>/<span class="caps">ACK</span>。以下是作者在项目运维中获得和经反思提炼的知识总结 …</p><p>Kubernetes [kubə&rsquo;netis]简称<span class="caps">K8S</span>或Kube,平时使用<span class="caps">K8S</span>主力是Minikube,在几个项目生产实践中,则使用<span class="caps">GCP</span>/<span class="caps">AWS</span>/阿里云的对应的<span class="caps">K8S</span>实现,<span class="caps">GKE</span>/<span class="caps">EKS</span>/<span class="caps">ACK</span>。以下是作者在项目运维中获得和经反思提炼的知识总结,部分理解带有个人观点。</p> <hr> <h2 id="1kubernetes">1、Kubernetes 基础概念<a class="headerlink" href="#1kubernetes" title="Permanent link">&para;</a></h2> <p><img alt="Kubernetes集群基础概念.jpg" src="https://blog.pythonwood.com/uploads/2021/Kubernetes集群基础概念.jpg" title="Kubernetes集群基础概念.jpg"></p> <h3 id="pods">理解 Pods<a class="headerlink" href="#pods" title="Permanent link">&para;</a></h3> <p>Kubernetes 中最小计算单元,内含pause和一个或一组进程。深入pods技术细节见<a href="https://segmentfault.com/a/1190000021710436" title="pod">Kubernetes Pod 网络精髓:pause 容器详解</a>。</p> <h3 id="_1">理解网络<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>Kubernetes有2个网络地址池<span class="caps">CIDR</span>分别供Pod和Service。Service和Pod都是有<span class="caps">IP</span>的网络实体,会消耗ip池地址,且各<span class="caps">IP</span>互通(由<span class="caps">CNI</span>实现)。Pod还是个计算实体承载服务,Service则按一定规则转发流量到0个或多个pod。实现模型理解见<a href="https://morven.life/posts/networking-6-k8s-summary/" title="net">浅聊 Kubernetes&nbsp;网络模型</a></p> <h3 id="service">理解Service<a class="headerlink" href="#service" title="Permanent link">&para;</a></h3> <p>Service本质就是dns解析+proxy转发,通过Service名:port方式就能访问真正的实体pod,类似非<span class="caps">K8S</span>生态的consul,但<span class="caps">K8S</span>内部服务名字的dns解析都是高度自动化的,无感知的。</p> <h3 id="podvm">有状态下pod漂移与vm漂移<a class="headerlink" href="#podvm" title="Permanent link">&para;</a></h3> <p>ip在pod生命周期内不变,但pod会因销毁重建导致ip漂移。内存与未绑定文件在pod销毁期间就清空了。相比而言,vm漂移技术成熟,ip内存文件都是一起在线飘到新地方,不存在重启销毁问题。</p> <hr> <h2 id="2kubernetes">2、理解Kubernetes技术<a class="headerlink" href="#2kubernetes" title="Permanent link">&para;</a></h2> <h3 id="1">1. 社区角度:<a class="headerlink" href="#1" title="Permanent link">&para;</a></h3> <p>从2015年7月Kubernetes v1.0正式发布至今v1.22版本,基于Kubernetes的生态已经非常庞大,直接导致go的流行,运维云原生化趋势。 <img alt="kubernetes结合devops概念图.png" src="https://blog.pythonwood.com/uploads/2021/kubernetes结合devops概念图.png" title="kubernetes结合devops概念图.png"></p> <h3 id="2">2. 工程师角度:<a class="headerlink" href="#2" title="Permanent link">&para;</a></h3> <p>绝大部分编排k8s的中间产物都是yaml文件,所以k8s工程师被称为yaml工程师。但其实ansible/salt工程师才是最先全用yaml的。 <img alt="K8S工程师写yaml.png" src="https://blog.pythonwood.com/uploads/2021/K8S工程师写yaml.png" title="K8S工程师写yaml.png"></p> <h3 id="3">3. 技术角度:<a class="headerlink" href="#3" title="Permanent link">&para;</a></h3> <p>内核技术升级是上层技术革新的基础,当年nginx使用epoll网络<span class="caps">IO</span>模型率先实现10K并发,如今docker/Kube实际上是内核cgroup/namespace进程环境限制/隔离加内核netfilter网络模块的上层产物。——技术早已出现,只是换个地方而更被人熟知,这现象可称为【军用科技民用化】。</p> <h3 id="4">4. 运维效用角度:<a class="headerlink" href="#4" title="Permanent link">&para;</a></h3> <p>自动化套件ansible/salt也是非常成熟的,另一方面非容器或非linux机的自动化集群管理并非k8s强项,k8s仅在支持容器化的项目上高效,而大部分项目可以容器化(0.9*0.9依然接近1,但不是全部)。 <img alt="kubernetes对比ansible.png" src="https://blog.pythonwood.com/uploads/2021/kubernetes对比ansible.png" title="kubernetes对比ansible.png"></p> <h3 id="5">5. 基于作者理解:<a class="headerlink" href="#5" title="Permanent link">&para;</a></h3> <ul> <li>k8s是“定义即状态”的运维实现,对应软件代码“定义即实现”具体指发展到<span class="caps">IDL</span>层面(接口描述语言)。</li> <li>k8s内置电池,一个k8s集群相当于实现了一个跑在容器的逻辑机房(计算+网络+存储都是可扩展的),外加一个ansible/salt控制中心。</li> <li>k8s本身学习难度大,非初学者友好,需要较深的linux内核/网络基本做底,但k8s生态的文章,精品率更高,反过来能加速学习容器化与linux相关知识的过程。</li> </ul> <hr> <h2 id="3kube">3、Kube入门学习建议<a class="headerlink" href="#3kube" title="Permanent link">&para;</a></h2> <h3 id="_2">💡 理解上把容器对标物,从虚拟机转变到进程来。<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <ol> <li>容器是一个新概念,从字面上并不好理解其真本质:隔离</li> <li>容器更像一个进程,而不是一个轻量的虚拟机。</li> </ol> <h3 id="k8s">💡 个人学习k8s路径选型<a class="headerlink" href="#k8s" title="Permanent link">&para;</a></h3> <ol> <li>从单机上的容器(docker/containerd)出发,跳一步到单机的<span class="caps">K8S</span>(minikube),再到多节点<span class="caps">K8S</span>(minikube),再适应云商的改版<span class="caps">K8S</span>。</li> <li>Ingress也有很多种,建议如果熟悉nginx,先从ingress-nginx入手。</li> <li>服务治理Istio囊括范围非常大,k8s只是组件之一,容易找不着北。个人觉得不适合用来入门k8s。</li> <li>官方dashboard已经很好,配合<a href="https://github.com/derailed/k9s" title="k9s"><span class="caps">K9S</span></a>工具已经够用了。一个管<span class="caps">UI</span>,一个管console。k9s真是vi党的福音。</li> <li>lens也是好工具,管理国内集群无明显延迟感。国外可能会稍卡顿。</li> </ol> <h3 id="_3">💡 容器 ≈ 进程+网络。<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h3> <ol> <li>除了理解linux内核,也需要iptables/ipvs理解能力。</li> <li>网络理解更难啃些,建议不要跳过docker网络直接理解k8s网络cni。 <img alt="内核netfilter图标.png" src="https://blog.pythonwood.com/uploads/2021/内核netfilter图标.png" title="内核netfilter图标.png"></li> </ol> <h3 id="docker-compose">💡 使用docker-compose作为对照参考<a class="headerlink" href="#docker-compose" title="Permanent link">&para;</a></h3> <ol> <li>对比中理解docker编排/k8s编排各自的长短处。会对k8s理解得更加全面和立体。</li> <li>docker-compose也是一股容器编排方面的重要力量。有余力者学1得2。 </li> </ol> <h3 id="minikube">💡 个人经验最佳学习搭档<a href="https://kubernetes.io/" title="doc">官方文档书籍</a> + <a href="https://minikube.sigs.k8s.io/" title="minikube">minikube</a>实践 。<a class="headerlink" href="#minikube" title="Permanent link">&para;</a></h3> <ol> <li>官方文档要重复看,坚持看,一般看第三遍就懂了。</li> <li>minikube是官方首推的学习和测试k8s环境,只需单机docker环境即可启动一个完备的k8s集群,很轻量,最快支持最新k8s版本。</li> <li>推荐第三方书的话 <a href="https://item.jd.com/12724298.html" title="book">《kubernetes网络权威指南》</a></li> </ol> <hr> <h2 id="4kube">4、Kube最佳实践,经验建议<a class="headerlink" href="#4kube" title="Permanent link">&para;</a></h2> <h3 id="imagesk8sprojzz-projxx">💡 打包images兼容非<span class="caps">K8S</span>容器环境运行,更利运维部署,以及开发调试。【Projzz, Projxx】<a class="headerlink" href="#imagesk8sprojzz-projxx" title="Permanent link">&para;</a></h3> <ul> <li>Projzz的镜像兼容docker,并且cp内部某套集群就是用docker部署的,线上则全用<span class="caps">K8S</span>部署的。</li> <li>Projxx的Pod启动是准备3-4个部分容器,最终合并到最终容器的emptyDir来running,如果选这种模式确实只能k8s了。</li> </ul> <blockquote> <p>做一个通用的镜像,能独立运行。用好动态部分来让同一镜像变成不同的runtime容器,如volume挂载,配置,环境env变量都是动态的。</p> </blockquote> <h3 id="appprojyy">💡 相似微服务可以统一镜像,使用<span class="caps">APP</span>环境变量启动镜像的不同部分【Projyy】<a class="headerlink" href="#appprojyy" title="Permanent link">&para;</a></h3> <blockquote> <p>相对于各微服务独立打包镜像的分包模式,还有一种简单的全包模式。</p> </blockquote> <p>Projyy镜像都是java进程,启动脚本命令基本一样,只是目录和jar包不同,使用了轻量的全包模式。通过指定<span class="caps">APP</span>环境变量,启动对应微服务。兼容docker/k8s。</p> <p>全包镜像模式好处:</p> <ol> <li>统一的Dockerfile,entrypoint.sh不用维护多个文件。</li> <li>减少镜像总占用空间,版本管理起来更轻量简洁。(harbor界面也简洁了)</li> <li>更接近vm时代supervisor的管理整代码包的方式。更好理解。</li> </ol> <h3 id="externalnameendpointskubeprojxx">💡 用ExternalName型和EndPoints型的服务进行Kube内部服务名固定。【Projxx】<a class="headerlink" href="#externalnameendpointskubeprojxx" title="Permanent link">&para;</a></h3> <blockquote> <p>用Service映射内部/外部服务简化架构:</p> <ol> <li> <p>组件依赖以服务<span class="caps">SVC</span>出现供微服务调用。Projxx依赖为zoo-svr, mysql-svr, redis-svr 与 zoo-svr-out,&nbsp;mysql-svr-out。</p> </li> <li> <p><span class="caps">SVC</span>底层的EndPoints/ExternalName映射各集群不同。如正式va集群是中心,微服务调用mysql-svr-out/mysql-svr-out底层相同,sg集群则不同。</p> </li> <li> <p>如下图,屏蔽底层差异后,研发不用关心底层,mysql等服务的映射关系由运维定义和修改,容灾切换。</p> </li> </ol> </blockquote> <p>Projxx图解: <img alt="Kubernetes统一SVC名指向外部依赖.png" src="https://blog.pythonwood.com/uploads/2021/Kubernetes统一SVC名指向外部依赖.png" title="Kubernetes统一SVC名指向外部依赖.png"></p> <h3 id="namespace">💡 在namespace级别隔离业务环境,而非集群级别隔离。<a class="headerlink" href="#namespace" title="Permanent link">&para;</a></h3> <blockquote> <p>减少k8s集群,理想状态是一个测试集群(dev/qa/pre/time/audit服)+一个正式集群。【Projyy】</p> </blockquote> <p>为了让单集群支持多环境,需要以下条件:</p> <ol> <li>yaml/chart中不写死namespace,使用kubectl -n <ns> 和 helm -n <ns> 在运行时指定namespace。</li> <li>节点映射到pod中的目录或文件名,需要保证不同namespace间不不一样。注意hostpaht和local映射。</li> <li>ingress域名不能在多namespace里共用,不同namespace用不同域名。(一般已经天然满足的)</li> <li>daemonset组件处理好不同namespace里不同环境的情况。比如filebeat以daemonset部署时可以收集多namespace的日志。</li> </ol> <h3 id="hostpathpodsshnodeprojzz">💡 善用hostpath在pod层面实现节点的初始化,日志清理等,不建议ssh到node进行初始化。【Projzz】<a class="headerlink" href="#hostpathpodsshnodeprojzz" title="Permanent link">&para;</a></h3> <blockquote> <p>将node的东西暴露给pod,就可以从pod层面处理好node的事项。以下推荐度逐渐递减</p> </blockquote> <ul> <li>以crontab/job加hostpath挂载处理初始化,还能定时清理日志等。</li> <li>以daemonset加hostpath挂载</li> <li>使用initpod模式加hostpath挂载</li> </ul> <h3 id="deploymentstatefulsetro">💡 多用Deployment而不是多用StatefulSet【<span class="caps">RO</span>】<a class="headerlink" href="#deploymentstatefulsetro" title="Permanent link">&para;</a></h3> <blockquote> <p>如无必要,Deployment好于StatefulSet,尤其在大副本数滚动更新时StatefulSet慢</p> </blockquote> <ul> <li>默认情况,Deployments更新2批次完成,而StatefulSet逐个重启,虽然可优化,但不如Deployment快和便捷。</li> <li>需要hostname/dns固定时间,启动顺序(如mysql主从集群)有要求时才特别的需要StatefulSet。</li> <li>Ro的Account登陆校验,Bgame跨服,Global模块,用不到特殊情况,account更新比较慢,理论上改成Deployments会更优。</li> </ul> <h3 id="_4">💡 其他建议:<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h3> <ol> <li>kubectx/kubens实际上在交互shell时才比较好用图省敲键盘。在脚本或自动化流程中,多使用&ndash;kubeconfig和&ndash;context参数指定集群更好。</li> <li>Fairy使用kustomize跑着也很稳,其求同存异的patch思路,也是很好的,免去helm那样写go模版。</li> <li>pod/service/namespace的名字尽量精简,<a href="https://kubernetes.io/zh/docs/concepts/services-networking/dns-pod-service/#pod-sethostnameasfqdn-field" title="FQDN64c">Linux内核的主机名字段限定了<span class="caps">FQDN</span>最多 64 个字符</a>。</li> <li>ingress尽量合并以减少总量,像gcp的gke就存在多于15个ingress是重载非常慢的问题。</li> <li>珍惜两个cidr地址的使用,太大了网络ip使用量,即pods/svc太多,会导致集群内耗过多。&nbsp;这类比开发微服务太小散,会导致cpu内耗在(反)序列化中。某字节内部资料说有10%</li> <li>尽量减少总容器量,比如微服务较多时,daemonset的filebeat部署,比inject/sidecar类型的部署模式省容器。</li> <li>提升副本数不如提升配置,副本数20升级60,&nbsp;在业务代码支持情况下,不如保持20个,配置升3倍。</li> <li>总的来说,本质上就是微服务不是越多越好,目前业界有种不良趋势,服务拆得太小。把服务越拆越细,这事本身也像一个技术界内卷行为。</li> </ol> <hr> <h2 id="5kube">5、Kube带来的问题反思<a class="headerlink" href="#5kube" title="Permanent link">&para;</a></h2> <h3 id="1-kube">1. 云厂商各自实现部分,并不统一,造成割裂,在复杂(云)之上制造复杂(Kube)。<a class="headerlink" href="#1-kube" title="Permanent link">&para;</a></h3> <h4 id="_5">正例:<a class="headerlink" href="#_5" title="Permanent link">&para;</a></h4> <p>基于<span class="caps">LB</span>的证书解密实现,<a href="https://help.aliyun.com/document_detail/86531.html" title="aliyun">阿里云</a>/<a href="https://aws.amazon.com/cn/premiumsupport/knowledge-center/eks-cidr-ip-address-loadbalancer/" title="aws"><span class="caps">AWS</span></a>均是annotation注释指向某个cert证书对象的id。运维开发的效用在于屏蔽这些差异。参考【某_ingress_chart】代码。</p> <h4 id="_6">反例:<a class="headerlink" href="#_6" title="Permanent link">&para;</a></h4> <p>基于<span class="caps">LB</span>的whiteiplist实现,阿里云 / <span class="caps">AWS</span>不同。annotation注释指向一块acl对象id /&nbsp;使用spec中loadBalancerSourceRanges。兼容起来麻烦,也只能运维配置,最终可能还不如在游戏层实现【Projxx】</p> <h3 id="2-16lb">2. 产生大量不好识别的16进制名称的<span class="caps">LB</span><a class="headerlink" href="#2-16lb" title="Permanent link">&para;</a></h3> <p>LoadBalance型服务,产生的名字不规律。难识别。</p> <h3 id="3-ingress">3. ingress 与动静文件分离问题<a class="headerlink" href="#3-ingress" title="Permanent link">&para;</a></h3> <p>使用nginx&nbsp;ingress也无法做到动静分离,只能将静态文件另外部署,如cdn,ingress后配nginx服等等。</p> <p><a href="https://github.com/nginxinc/kubernetes-ingress/issues/323" title="#323">How to setup ingress to serve static content on kubernetes?&nbsp;#323</a></p>面试算法编程选记2题之二分法-寻找斜率为K的2点2020-06-22T00:00:00+08:002020-06-22T00:00:00+08:00pythonwoodtag:blog.pythonwood.com,2020-06-22:/2020/06/面试算法编程选记2题之二分查-寻找斜率为K的2点/<p>因为一直是用自学+坚持自学方法走过来的,折腾技术运用还可以,基础算法编程能力一直偏弱。</p> <p>1、二分法属于思维简单,细节弄人的典型。之前陷入过二分法脑风暴中不能通透,这次趁面试遇到好好再过一次,提高深度。</p> <p>2、输入数组A 例如&nbsp;[(x1,y1),(x2,y2)&hellip;],输出斜率为K的点对数目</p> <h3 id="_1">二分查找<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>二分查找要处理好中点 …</p><p>因为一直是用自学+坚持自学方法走过来的,折腾技术运用还可以,基础算法编程能力一直偏弱。</p> <p>1、二分法属于思维简单,细节弄人的典型。之前陷入过二分法脑风暴中不能通透,这次趁面试遇到好好再过一次,提高深度。</p> <p>2、输入数组A 例如&nbsp;[(x1,y1),(x2,y2)&hellip;],输出斜率为K的点对数目</p> <h3 id="_1">二分查找<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>二分查找要处理好中点,缩小方法,避免死循环。重在细节实现。&nbsp;Plus增强后支持最左最右查找</p> <p>已过 leetcode算法题:<a href="https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9">https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9</a></p> <div class="highlight"><pre><span></span><span class="s s-Atom">class</span> <span class="nv">BinarySearch</span><span class="s s-Atom">:</span> <span class="s s-Atom">def</span> <span class="nf">getPos</span><span class="p">(</span><span class="s s-Atom">self</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="s s-Atom">while</span> <span class="s s-Atom">a1</span> <span class="s s-Atom">&lt;=</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="s s-Atom">位置未检</span> <span class="s s-Atom">mid</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">a1</span><span class="o">+</span><span class="s s-Atom">a2</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span> <span class="s s-Atom">#</span> <span class="s s-Atom">中间索引赋值是关键,可等左,不等右</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">val</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">==</span> <span class="nn">val</span><span class="p">:</span> <span class="s s-Atom">return</span> <span class="s s-Atom">mid</span> <span class="s s-Atom">elif</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">&lt;</span> <span class="nn">val</span><span class="p">:</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="o">+</span> <span class="mi">1</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="o">-</span> <span class="mi">1</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">return</span> <span class="o">-</span><span class="mi">1</span> <span class="s s-Atom">def</span> <span class="nf">getPosPlus</span><span class="p">(</span><span class="s s-Atom">self</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">,</span> <span class="s s-Atom">searchtype</span><span class="o">=</span><span class="mi">0</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">&#39;&#39;&#39;支持最左,最右二分查找的修改Plus版本</span> <span class="s s-Atom"> &#39;left&#39;:-1, &#39;fast&#39;:0, &#39;right&#39;:1 其中0是默认版本,找到即返回。</span> <span class="s s-Atom"> &#39;&#39;&#39;</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span> <span class="s s-Atom">while</span> <span class="s s-Atom">a1</span> <span class="o">&lt;</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">直到重合时,单元素</span> <span class="s s-Atom">mid</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">a1</span><span class="o">+</span><span class="s s-Atom">a2</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span> <span class="s s-Atom">#</span> <span class="s s-Atom">中间索引赋值是关键,可等左,不等右</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">val</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">==</span> <span class="nn">val</span><span class="p">:</span> <span class="s s-Atom">if</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="mi">0</span><span class="s s-Atom">:</span> <span class="s s-Atom">return</span> <span class="s s-Atom">mid</span> <span class="s s-Atom">if</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="s s-Atom">elif</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="s s-Atom">elif</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">&lt;</span> <span class="nn">val</span><span class="p">:</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a1</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">==</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">避免剩余2个元素时,</span> <span class="s s-Atom">mid=左陷入死循环</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">a2</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">assert</span> <span class="s s-Atom">a1</span> <span class="o">==</span> <span class="s s-Atom">a2</span> <span class="s s-Atom">return</span> <span class="s s-Atom">a1</span> <span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">a1</span><span class="p">]</span> <span class="o">==</span> <span class="s s-Atom">val</span> <span class="s s-Atom">else</span> <span class="o">-</span><span class="mi">1</span> <span class="s s-Atom">if</span> <span class="k">__</span><span class="s s-Atom">name__</span> <span class="o">==</span> <span class="s s-Atom">&#39;__main__&#39;:</span> <span class="s s-Atom">rt</span> <span class="o">=</span> <span class="nv">BinarySearch</span><span class="p">()</span> <span class="s s-Atom">for</span> <span class="nv">A</span> <span class="nf">in</span> <span class="p">((</span><span class="mi">1</span><span class="p">,),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">5</span><span class="p">),</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">10</span><span class="p">,</span><span class="mi">21</span><span class="p">])</span><span class="s s-Atom">:</span> <span class="s s-Atom">n</span> <span class="o">=</span> <span class="nf">len</span><span class="p">(</span><span class="nv">A</span><span class="p">)</span> <span class="s s-Atom">for</span> <span class="s s-Atom">val</span> <span class="s s-Atom">in</span> <span class="nv">A</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPos</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span> <span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">&#39;find %3s in %10s: index=%s&#39;</span> <span class="c1">% (val, A, idx))</span> <span class="s s-Atom">#</span> <span class="s s-Atom">支持最左,最右二分查找的修改Plus版本</span> <span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPosPlus</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">&#39;find %3s in %10s: index=%s&#39;</span> <span class="c1">% (val, A, idx))</span> <span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPosPlus</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">&#39;find %3s in %10s: index=%s&#39;</span> <span class="c1">% (val, A, idx))</span> </pre></div> <h3 id="k">寻找斜率为K的点对<a class="headerlink" href="#k" title="Permanent link">&para;</a></h3> <p>算法题:</p> <p>有一个数组,数组每个元素是一个对象,每个对象有x和y两个值,这个数组记录 为A: A = [{x1, y1}, {x2, y2}, &hellip;];我们把数组A中任意两个满足以下关系的元素叫 做“点对”:(y2-y1)/(x2-x1) = K, K是一个常数。编写程序:给定A与K,返回A中点&nbsp;对的数目。</p> <div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">groupby</span> <span class="n">K</span> <span class="o">=</span> <span class="mi">1</span> <span class="c1"># 斜率</span> <span class="k">def</span> <span class="nf">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">k</span><span class="o">=</span><span class="n">K</span><span class="p">):</span> <span class="sd">&#39;&#39;&#39;</span> <span class="sd"> 分析:计算一遍点到直线y=kx距离 |Kx - y| / √(k*k+1),距离等两点的可能与y=kx平行。先验证y=kx上的,距离等不一定平行。</span> <span class="sd"> 技巧:结合题目实际,可不开平方pow运算,不取绝对值。</span> <span class="sd"> &#39;&#39;&#39;</span> <span class="k">print</span><span class="p">(</span><span class="s1">&#39;debug: kpairs(</span><span class="si">%s</span><span class="s1">, </span><span class="si">%s</span><span class="s1">)&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">A</span><span class="p">))</span> <span class="n">result</span> <span class="o">=</span> <span class="mi">0</span> <span class="n">distance</span> <span class="o">=</span> <span class="p">[</span> <span class="p">(</span><span class="n">k</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">y</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">k</span><span class="o">**</span><span class="mi">2</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="ow">in</span> <span class="n">A</span> <span class="p">]</span> <span class="n">point_distance</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">distance</span><span class="p">),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1"># 距离排序,取点</span> <span class="k">for</span> <span class="n">distance</span><span class="p">,</span> <span class="n">pointiter</span> <span class="ow">in</span> <span class="n">groupby</span><span class="p">(</span><span class="n">point_distance</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]):</span> <span class="n">points</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">pointiter</span><span class="p">)</span> <span class="n">count</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">points</span><span class="p">)</span> <span class="k">print</span><span class="p">(</span><span class="s1">&#39;debug: line:y=</span><span class="si">%3s</span><span class="s1">x, got </span><span class="si">%3s</span><span class="s1"> point distance=</span><span class="si">%7.3s</span><span class="s1">: </span><span class="si">%s</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">count</span><span class="p">,</span> <span class="n">distance</span><span class="p">,</span> <span class="n">points</span><span class="p">))</span> <span class="c1"># debug</span> <span class="k">if</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span> <span class="n">result</span> <span class="o">+=</span> <span class="n">count</span><span class="o">*</span><span class="p">(</span><span class="n">count</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span> <span class="c1"># 组合数 4 -&gt; 6</span> <span class="k">return</span> <span class="n">result</span> <span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="p">:</span> <span class="n">A</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">)]</span> <span class="c1"># 正方形</span> <span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> <span class="s1">&#39;check and debug kpairs(</span><span class="si">%s</span><span class="s1">)&#39;</span><span class="o">%</span><span class="n">A</span> <span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="s1">&#39;check and debug kpairs(</span><span class="si">%s</span><span class="s1">)&#39;</span><span class="o">%</span><span class="n">A</span> <span class="n">A</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">3</span><span class="p">,</span><span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">20</span><span class="p">,</span><span class="mi">20</span><span class="p">),</span> <span class="p">(</span><span class="mi">10</span><span class="p">,</span><span class="mi">16</span><span class="p">),</span> <span class="p">(</span><span class="mi">22</span><span class="p">,</span><span class="mi">28</span><span class="p">)]</span> <span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">)</span> <span class="o">==</span> <span class="mi">4</span><span class="p">,</span> <span class="s1">&#39;check and debug kpairs(</span><span class="si">%s</span><span class="s1">)&#39;</span><span class="o">%</span><span class="n">A</span> <span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> <span class="s1">&#39;check and debug kpairs(</span><span class="si">%s</span><span class="s1">)&#39;</span><span class="o">%</span><span class="n">A</span> </pre></div> <h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2> <ol> <li>点到直线距离公式的几种推导 <a href="https://zhuanlan.zhihu.com/p/26307123">https://zhuanlan.zhihu.com/p/26307123</a></li> </ol>面试高频题-LRU缓存的python实现2019-08-22T14:00:00+08:002019-08-22T14:00:00+08:00pythonwoodtag:blog.pythonwood.com,2019-08-22:/2019/08/面试高频题-LRU缓存的python实现/<p>过程简略:&nbsp;url去重的方法,数据库四种隔离级别,乐观锁悲观锁,算法题研讨。算法讨论占了很长时间,以下是把这个过程沉淀后的一遍随笔。</p> <h3 id="leetcode146-lru">leetcode算法题:146. <span class="caps">LRU</span>缓存机制<a class="headerlink" href="#leetcode146-lru" title="Permanent link">&para;</a></h3> <p><a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> <blockquote> <p>运用你所掌握的数据结构,设计和实现一个  <span class="caps">LRU</span> (最近最少使用 …</p></blockquote><p>过程简略:&nbsp;url去重的方法,数据库四种隔离级别,乐观锁悲观锁,算法题研讨。算法讨论占了很长时间,以下是把这个过程沉淀后的一遍随笔。</p> <h3 id="leetcode146-lru">leetcode算法题:146. <span class="caps">LRU</span>缓存机制<a class="headerlink" href="#leetcode146-lru" title="Permanent link">&para;</a></h3> <p><a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> <blockquote> <p>运用你所掌握的数据结构,设计和实现一个  <span class="caps">LRU</span> (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put&nbsp;。</p> <p>获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回&nbsp;-1。</p> <p>写入数据 put(key, value) -&nbsp;如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。</p> <p>进阶:</p> <p>你是否可以在 O(1)&nbsp;时间复杂度内完成这两种操作?</p> <p>示例:</p> </blockquote> <div class="highlight"><pre><span></span>LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 </pre></div> <h2 id="_1">思考过程简要<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h2> <p>第一次遇到,没有做好题。之后总结思考如下。面试完重新整理好代码,才通过。</p> <p>1、数据结构知识弱,链表随机增删复杂度O(1),&nbsp;数组复杂度O(n)。使用按时间排序的双向链表。头部总是最新访问或插入的,尾巴总是最老的。使用额外maxsize限制大小,nowsize记录目前大小。</p> <p>2、链表元素是key-val的进一步封装的Node类。链表是另一个类,类总head和tail表示头尾两个空的node。一直不删。</p> <p>3、开头想到最小堆,用得不对。二分法等比较查找下限O(lgN),与哈希法的O(1)差距意识不明显。而哈希函数用内置字典即可。</p> <p>4、拆分小函数复用代码。比如get = 出链 + 插入头部, put = 出链 + 插入头部(update) 或者&nbsp;插入头部(非update)</p> <p>5、之后发现python有functools.lru_cache的现成实现,值得学习。</p> <h2 id="leetcode">leetcode通过提交的代码<a class="headerlink" href="#leetcode" title="Permanent link">&para;</a></h2> <div class="highlight"><pre><span></span><span class="kr">class</span> <span class="nx">Node</span>: <span class="kt">def</span> <span class="nx">__init__</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="o">=</span><span class="nx">None</span><span class="p">,</span> <span class="nx">val</span><span class="o">=</span><span class="nx">None</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">key</span> <span class="o">=</span> <span class="nx">key</span> <span class="nx">self</span><span class="p">.</span><span class="nx">val</span> <span class="o">=</span> <span class="nx">val</span> <span class="nx">self</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">None</span> <span class="nx">self</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">None</span> <span class="kr">class</span> <span class="nx">LRUCache</span><span class="o">:</span> <span class="s1">&#39;&#39;&#39;</span> <span class="s1"> 小函数: 删node,入head</span> <span class="s1"> 注意:head和tail是空的node,不能删除</span> <span class="s1"> &#39;&#39;&#39;</span> <span class="nx">def</span> <span class="nx">__init__</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">maxsize</span><span class="o">=</span><span class="mi">10</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">maxsize</span> <span class="o">=</span> <span class="nx">maxsize</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">=</span> <span class="mi">0</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="o">=</span> <span class="nx">Node</span><span class="p">()</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="o">=</span> <span class="nx">Node</span><span class="p">()</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="err">#</span> <span class="nx">key</span> <span class="o">-&gt;</span> <span class="nx">nodes</span><span class="p">.</span><span class="nx">val</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span> <span class="o">=</span> <span class="p">{}</span> <span class="nx">def</span> <span class="nx">get</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span><span class="o">:</span> <span class="err">#</span> <span class="mi">2019</span><span class="o">-</span><span class="mi">08</span><span class="o">-</span><span class="mi">21</span><span class="err">面试时加的要求</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="nx">self</span><span class="p">.</span><span class="nx">addNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="k">return</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="k">else</span><span class="o">:</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span> <span class="nx">def</span> <span class="nx">put</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span> <span class="nx">def</span> <span class="nx">set</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span><span class="o">:</span> <span class="err">#</span> <span class="err">在链表中,</span><span class="nx">update</span><span class="err">操作</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">addNode</span><span class="p">(</span><span class="nx">Node</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">))</span> <span class="nx">def</span> <span class="k">delete</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span>: <span class="kt">self.popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="nx">def</span> <span class="nx">popNode</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">node</span><span class="p">)</span><span class="o">:</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">==</span> <span class="nx">None</span>: <span class="kt">return</span> <span class="err">#</span> <span class="err">使用</span><span class="nx">head</span><span class="err">和</span><span class="nx">tail</span><span class="err">为空</span><span class="nx">node</span><span class="err">时无需检查</span> <span class="err">#</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="o">:</span> <span class="err">#</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="err">#</span> <span class="k">else</span><span class="o">:</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="err">#</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="o">:</span> <span class="err">#</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="err">#</span> <span class="k">else</span><span class="o">:</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">-=</span> <span class="mi">1</span> <span class="err">#</span> <span class="err">字典更新</span> <span class="nx">del</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">[</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">]</span> <span class="k">return</span> <span class="nx">node</span> <span class="nx">def</span> <span class="nx">addNode</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">node</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="err">总在链表头加入</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">==</span> <span class="nx">None</span>: <span class="kt">return</span> <span class="k">if</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">&gt;=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">maxsize</span><span class="o">:</span> <span class="err">#</span> <span class="err">满了,就去掉尾巴再插入</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">self</span><span class="p">.</span><span class="nx">tail</span><span class="p">.</span><span class="nx">prev</span><span class="p">)</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span> <span class="err">#</span> <span class="err">费时的</span><span class="nx">debug</span><span class="err">错误:这句之后</span><span class="p">[[</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">]]</span> <span class="o">-&gt;</span> <span class="p">[]</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">+=</span> <span class="mi">1</span> <span class="err">#</span> <span class="err">字典增加</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">[</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">]</span> <span class="o">=</span> <span class="nx">node</span> <span class="kd">@property</span> <span class="nx">def</span> <span class="nx">vals</span><span class="p">(</span><span class="nx">self</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="nx">debug</span> <span class="err">#</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="err">#</span> <span class="err">错误:发现用时</span><span class="mi">15</span><span class="err">分钟</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="nx">_vals</span> <span class="o">=</span> <span class="p">[]</span> <span class="err">#</span> <span class="k">while</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span><span class="o">:</span> <span class="err">#</span> <span class="mi">2019</span><span class="o">-</span><span class="mi">08</span><span class="o">-</span><span class="mi">21</span><span class="err">大坑,</span><span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">=</span> <span class="mi">0</span><span class="err">时会失败!费了</span><span class="mi">1</span><span class="err">小时!!!</span> <span class="k">while</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span> <span class="nx">and</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">!=</span> <span class="nx">None</span>: <span class="kt">_vals.append</span><span class="p">([</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">,</span><span class="nx">node</span><span class="p">.</span><span class="nx">val</span><span class="p">])</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="k">return</span> <span class="nx">_vals</span> <span class="nx">def</span> <span class="nx">pprint</span><span class="p">(</span><span class="nx">self</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="nx">debug</span> <span class="nx">print</span><span class="p">(</span><span class="nx">self</span><span class="p">.</span><span class="nx">vals</span><span class="p">,</span> <span class="nx">flush</span><span class="o">=</span><span class="nx">True</span><span class="p">)</span> <span class="k">if</span> <span class="nx">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="o">:</span> <span class="nx">lru</span> <span class="o">=</span> <span class="nx">LRUCache</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">print</span><span class="p">(</span><span class="nx">lru</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">))</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="k">delete</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="err">#</span> <span class="nx">leetcode</span><span class="err">的测试用例</span> <span class="nx">cache</span> <span class="o">=</span> <span class="nx">LRUCache</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">);</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">1</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">);</span> <span class="err">#</span> <span class="err">该操作会使得密钥</span> <span class="mi">2</span> <span class="err">作废</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="o">-</span><span class="mi">1</span> <span class="p">(</span><span class="err">未找到</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">);</span> <span class="err">#</span> <span class="err">该操作会使得密钥</span> <span class="mi">1</span> <span class="err">作废</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="o">-</span><span class="mi">1</span> <span class="p">(</span><span class="err">未找到</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">3</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">4</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">4</span> </pre></div> <h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2> <ol> <li> <p>leetcode算法题:146. <span class="caps">LRU</span>缓存机制 <a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> </li> <li> <p>Python 缓存机制与 functools.lru_cache <a href="http://blog.konghy.cn/2016/04/20/python-cache/">http://blog.konghy.cn/2016/04/20/python-cache/</a></p> </li> </ol>Linux服务器安装轻量X环境xfce桌面和VNC服务2019-04-27T21:00:00+08:002019-04-27T21:00:00+08:00pythonwoodtag:blog.pythonwood.com,2019-04-27:/2019/04/Linux服务器安装轻量X环境xfce桌面和VNC服务/<p>有些任务需要Linux桌面环境,例如使用chrome/firefox浏览器进行测试或抓取数据。简要记录安装过程备需。任何时候,一个免key的<span class="caps">SSH</span>登录环境都能带来方便。</p> <p>以下环境是Ubuntu18.04,&nbsp;Ubuntu其他版本大同小异。其他linux发行版需修改。</p> <h3 id="xfce">安装必须的xfce桌面基础包。还有语言支持包<a class="headerlink" href="#xfce" title="Permanent link">&para;</a></h3> <p>桌面环境我选xfce。足够轻量体验也很好。vnc服务器我选tightvncserver,简单高效。</p> <div class="highlight"><pre><span></span># X环境,设置中文环境 …</pre></div><p>有些任务需要Linux桌面环境,例如使用chrome/firefox浏览器进行测试或抓取数据。简要记录安装过程备需。任何时候,一个免key的<span class="caps">SSH</span>登录环境都能带来方便。</p> <p>以下环境是Ubuntu18.04,&nbsp;Ubuntu其他版本大同小异。其他linux发行版需修改。</p> <h3 id="xfce">安装必须的xfce桌面基础包。还有语言支持包<a class="headerlink" href="#xfce" title="Permanent link">&para;</a></h3> <p>桌面环境我选xfce。足够轻量体验也很好。vnc服务器我选tightvncserver,简单高效。</p> <div class="highlight"><pre><span></span># X环境,设置中文环境 sudo apt install xfdesktop4 tightvncserver xfce4-terminal xfce4-panel ttf-wqy-zenhei ttf-wqy-microhei language-pack-zh-hans-base language-pack-zh-hans </pre></div> <h3 id="_1">设置桌面显示中文<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>英语普通4级的我,桌面环境还是用母语熟悉。</p> <div class="highlight"><pre><span></span># 设置中文环境 sudo dpkg-reconfigure locales # 时区 sudo dpkg-reconfigure tzdata </pre></div> <h3 id="vncxstartup">初始化vnc,设置密码和xstartup环境<a class="headerlink" href="#vncxstartup" title="Permanent link">&para;</a></h3> <p>完成后相关配置文件都在$<span class="caps">HOME</span>/.vnc文件夹内,复制文件夹设置权限归属即可,不须重新配置。</p> <h4 id="vnc">初始一个默认.vnc文件夹<a class="headerlink" href="#vnc" title="Permanent link">&para;</a></h4> <div class="highlight"><pre><span></span>vncserver -localhost :1 # 开启1号,只监听在127.0.0.1本地lo网卡 # 监听0.0.0.0可用 vncserver :1 vncserver -kill :1 # 关闭1号 </pre></div> <h4 id="vncxstartupvnc">修改~/.vnc/xstartup,登录vnc后的启动桌面命令<a class="headerlink" href="#vncxstartupvnc" title="Permanent link">&para;</a></h4> <p>文件最后一句内容</p> <div class="highlight"><pre><span></span>startxfce4 &amp; </pre></div> <h4 id="vncpasswdvnc">使用vncpasswd命令设置vnc密码<a class="headerlink" href="#vncpasswdvnc" title="Permanent link">&para;</a></h4> <div class="highlight"><pre><span></span>vncpasswd </pre></div> <h3 id="vnc_1">vnc启动与安全<a class="headerlink" href="#vnc_1" title="Permanent link">&para;</a></h3> <p>参考上面即可。如监听localhost地址,可用ssh本地转发功能建立ssh隧道再进行连接。</p> <div class="highlight"><pre><span></span>ssh -gfTNL 5901:localhost:5901 host # vnc的1号端口对应5901, 2、3等端口对应递增。 </pre></div> <h3 id="vnc_2">vnc服务要开机启动<a class="headerlink" href="#vnc_2" title="Permanent link">&para;</a></h3> <p>因版本不同差别较大,需要配置较多,vnc服务不是常用,不需开机自启。</p> <h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2> <p>How to Install and Configure <span class="caps">VNC</span> on Ubuntu <a href="https://www.digitalocean.com/community/tutorials/how-to-install-and-configure-vnc-on-ubuntu-16-04">https://www.digitalocean.com/community/tutorials/how-to-install-and-configure-vnc-on-ubuntu-16-04</a></p> <p>How to install <span class="caps">VNC</span> on Linux ( <span class="caps">GUI</span> for your Linux <span class="caps">VPS</span> ) <a href="https://www.interserver.net/tips/kb/install-vnc-linux-gui-linux-vps/">https://www.interserver.net/tips/kb/install-vnc-linux-gui-linux-vps/</a></p>Linux释放磁盘空间——系统日志systemd-journal清理2018-12-05T15:00:00+08:002018-12-05T15:00:00+08:00pythonwoodtag:blog.pythonwood.com,2018-12-05:/2018/12/Linux释放磁盘空间——系统日志systemd-journal清理/<h2 id="varlogjournal">/var/log/journal 目录占用空间很大<a class="headerlink" href="#varlogjournal" title="Permanent link">&para;</a></h2> <p>原因systemd系统通过systemd-journald.service记录日志.&nbsp;默认以二进制写入/var/log/journal/目录中的日志文件,系统安装久了发现磁盘空间逐渐变小。</p> <p>ubuntu18.04,&nbsp;centos7等新系统都使用新型系统systemd,就可能需要清理。</p> <div class="highlight"><pre><span></span>$ du -sh /var/log …</pre></div><h2 id="varlogjournal">/var/log/journal 目录占用空间很大<a class="headerlink" href="#varlogjournal" title="Permanent link">&para;</a></h2> <p>原因systemd系统通过systemd-journald.service记录日志.&nbsp;默认以二进制写入/var/log/journal/目录中的日志文件,系统安装久了发现磁盘空间逐渐变小。</p> <p>ubuntu18.04,&nbsp;centos7等新系统都使用新型系统systemd,就可能需要清理。</p> <div class="highlight"><pre><span></span>$ du -sh /var/log/journal/ <span class="m">2</span>.2G /var/log/journal/ </pre></div> <h2 id="_1">手动命令行清理 单次生效 可临时救急<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h2> <p>删除数天以前旧日志</p> <div class="highlight"><pre><span></span># journalctl --vacuum-time=7d Vacuuming done, freed 2.1G of archived journals from /var/log/journal/1095e22a7289463f9f4fdd6d10e3da34. </pre></div> <p>删除到只保留100M日志量的状态</p> <div class="highlight"><pre><span></span># journalctl --vacuum-size=100M Vacuuming done, freed 2.0G of archived journals from /var/log/journal/1095e22a7289463f9f4fdd6d10e3da34. </pre></div> <h2 id="systemd-journaldservice">配置systemd-journald.service 永久生效<a class="headerlink" href="#systemd-journaldservice" title="Permanent link">&para;</a></h2> <p>systemd-journald 的配置文件为 /etc/systemd/journald.conf&nbsp;中,将SystemMaxUse=这行去掉注释,修改为SystemMaxUse=1G,将日志总量限制在1G内。</p> <p>预计下次启动生效,但我测试暂没有效果,不知原因。</p> <h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2> <p>clear up systemd-journal <a href="https://ma.ttias.be/clear-systemd-journal/">https://ma.ttias.be/clear-systemd-journal/</a></p> <p>使用journalctl查看systemd日志 <a href="https://lujun9972.github.io/blog/2018/08/08/使用journalctl查看systemd日志/">https://lujun9972.github.io/blog/2018/08/08/使用journalctl查看systemd日志/</a></p>