希尔(Shell) 排序 - 增强版插入排序算法

前面讲过的几种排序多是以排序逻辑来命名的,例如冒泡,选择和插入排序,以及其他如归并排序,当然还有觉得自己足够牛 X 快速排序命名。而本文要学习的排序算法叫做希尔排序是以其设计者 Donlad Shell 命令的排序算法,该算法在 1959 年公布,能以作者来命名的算法应该是很不错的,令设计者引以为傲的。最初写出冒泡和选择排序的就没以作者来命名,可能不好意说,更可能是公共思维。

那么什么是希尔排序呢?它实际上是插入排序算法的增强版本,又称递减增量排序算法。它对待排序列表进行间隔式分段插入处理,从而总体上减少了元素的移动次数而达到性能的大大提升。那么理解希尔排序之前一定要先了解插入排序。那么为什么说希尔排序既是递减又是增量呢? 阅读全文 >>

类别: Algorithm. 标签: , . 阅读(48). 评论(0) »

插入排序算法解析

前面说过最原始的复杂度为 O(n2) 的冒泡和选择排序,也跳跃到了复杂度为  O(n log n) 的快速排序,现在又再看一个复杂度同样为 O(n2) 的插入排序。从排序名称结合代码我们理解了为什么叫做冒泡或是选择,快速排序自认高名,那么何以这又谓之插入排序呢?是怎么插入,从左边往右边插,还是从右边往左边插,这得搞清它的排序原理:

它在列表较低的一端维护一个有序的子列表(从最左端一个元素开始),并逐个将每个新元素(高端的)"插入"这个子列表。插入的时候遍历低端列表,找准位置插入便是,插入点后的元素需后移,当所有高端的元素插入完成了,整个列表就变得有序了。

整个排序操作示意图如下: 阅读全文 >>

类别: Algorithm. 标签: , , . 阅读(37). 评论(0) »

理解 Python 类的变量,方法与属性

熟悉了传统的 C++/Java 类定义的风格,来感受一下 Python 是如何定义类的。本篇是阅读 《The Quick Python Book》第二版关于类定义的笔记,由原书内容进一步引申,不过是依照本人的思考顺序来组织的。在理解 Python 类定义的同时头脑中应该闪现出 JavaScript/Java 如何定义类的情景。

最简单的类定义

class MyClass:
    pass

由于 class MyClass 后面要有个冒号,而冒号后总得有点东西才能表示该类定义结束了,于是放个 pass 当占位符。Python 也像 Java 一样,有一个根类,叫做 object,例如上面的定义

我们能看到它隐式的基类是 object, 而不用显式的声明为 class MyClass(object)。看到 __bases__ 属性是一个 Tuple, 意识到  Python 是支持多重继承的。 阅读全文 >>

类别: Python. 标签: , . 阅读(34). 评论(1) »

真正有些水准的排序算法 - 快速排序

冒泡和选择排序的简单粗暴也许在某些人眼里都不能称作算法,现在要进入一种更优雅的排序算法,快速排序。它使用分而治之(Divide and Conquer, D&G) 的策略,要应用到递归调用。快速排序敢说自己快速,也确实比选择排序快很多很多。冒泡和选择排序,尤其是选择排序是非常自然的排序算法,而快速排序就不是一般人会随意想出来的。

快速排序的演绎需要用递归来思考循环的问题,然而我之前总是在及力用循环来避免递归调用,有趣的是诸如 Haskell 等函数式编译语言根本没有循环,只能用递归来编写循环的效果。来看一个简单的例子,比如要从 1 加到 100,我们很自然会用循环从 1 累加到 100,如果换成递归,看下面的代码

递归有助于我们把大问题分解为小问题,上面代码的思维是数组的和总是很一个元素加上剩下元素列表的和,直到最后元素列表为空(和为 0)。 阅读全文 >>

类别: Algorithm. 标签: . 阅读(46). 评论(1) »

两种最基本的排序算法: 冒泡和选择

因 COVID-19 漫延各自居家,也更有闲时,便拣起一本关于算法的书籍来研究。本不是科班出身,算法方面自然是自己的薄弱环节。平时用各种 SDK,只大概听说了些算法,仅能就自己如何选择哪种实现而作为参考。

如今阅读的是一本入门的书籍,名为 《算法图解》,英文版书名是 《Grokking Algorithms》。 该书图文并茂,十分适合初学者,关于排序最基本莫过于冒泡与选择排序。该书并未提及冒泡,而是直接从选择排序切入,在阅读本书之前我就一直对这两咱排序方式傻傻不分。一直以为头脑中的选择排序就是冒泡排序,那就来看下什么是真正的冒泡排序。 阅读全文 >>

类别: Algorithm. 标签: . 阅读(41). 评论(2) »

Kubernetes 学习笔记(二) - 部署和访问应用

前边折腾了各种安装 Kubernetes 集群的操作,还跑到 AWS 上撸了一把 EKS,也在 Kubernetes 上部署过服务。继续更深一步的学习如何部署应用和怎么通过 Service 去访问 Pod 中的应用,顺带看看内部的网络是怎么流转的。

测试平台还是以本地启动的三个 Vagrant 虚拟机组成的 Kubernetes 集群,安装方法见 Kubernetes 学习笔记(一) - 初上手

  1. k8s-master  (172.28.128.14)
  2. k8s-node1    (172.28.128.10)
  3. k8s-node2   (172.28.128.11)

测试应用的镜像为 yanbin/python-web, 代码见 github 上的 yabqiu/python-web-docker/app.py, 一个默认启动在  80 端口上的 Flask Web 应用,输出为当前 hostname  和一个唯一标识符。

部署应用

《每天5分玩转Kubernetes》里用的 Kubernetes 是 1.7 版本,其中还在用 kubectl run 的方式来部署应用(它会产生一个隐式的 deployment 对象),该方式已在 Kubernetes 1.12 中不推荐使用了,建议用 kubectl create deployment...,而实际中更应该用 yaml 文件编排后再 kubectl apply -f <your-yaml-file>, 这样多种对象可以编写在一起,更方便日后同样的命令更新各种对象,或者用 kubectl delete -f <your-yam-file> 批量删除所创建的对象。 阅读全文 >>

类别: Kubernetes. 标签: . 阅读(19). 评论(0) »

Kubernetes 集群中节点的 INTERNAL-IP 问题

用自己 Kubernetes 学习笔记(一) - 初上手 一文中的方法用 Vagrant 虚拟机安装的 Kubernetes 集群,部署应用什么的都没问题,然而却在用

$ kubectl exec -it <pod-name> -- sh

试图登陆 docker 容器时出问题了,总是报错说

error: unable to upgrade connection: pod does not exist

kubectl 登陆不了 docker 容器,而且  kubectl logs 也会报一样的错,必须到具体的工作节点上用 docker exec 或 docker logs 才能访问到该节点上的容器信息。

这就不太对头,网上找了下原因,结果是因为节点间通信时选错了 IP 地址。

比如三个 Vagrant 虚拟机分别是

  1. k8s-master (172.28.128.14)
  2. k8s-node1 (172.28.128.10)
  3. k8s-node2 (172.28.128.11)

在 k8s-master 中初始集群时用的命令也是指定的 172.28.128.14 IP 地址 阅读全文 >>

类别: Kubernetes. 标签: , . 阅读(498). 评论(0) »

Java 普通线程池与 ForkJoinPool 的效果对比

Java 多线程编程常用的一个接口是 ExecutorService, 其实就一个线程池的接口,一般由两种方式创建线程池,一为 Executors 的工厂方法,二则创建 ForkJoinPool 实例,当然也有直接使用 ThreadPoolExecutor 的。

关于什么时候用 ForkJoinPool 或普通的线程池(如 Executors.newFixedThreadPool(2) 或 new ThreadPoolExecutor(...)) 不过多的述说。如果要运用到 ForkJoinTask 的话就要用 ForkJoinPool, 它是 Java7 新引入的线程池类型。

关于 Java7 的 fork-join 框架可参考很多年前的一篇 Java 的 fork-join 框架实例备忘。ForkJoinPool 的一个典型特征是能够进行 Work stealing。它也是 Akka actor 效率高效的一个有力保证。

本文只能某一种情形下在选择普通线程池与 ForkJoinPool 的区别,直接说吧,普通线程更容易造成死锁,而 ForkJoinPool 却能应对相同的状况。 阅读全文 >>

类别: Java/JEE. 标签: . 阅读(494). 评论(0) »

AWS EKS 执行 kubectl 时 error: You must be logged in to the server (Unauthorized)

在 AWS 上创建好 EKS 后,想要在本地用  kubectl 来管理 EKS,必须用 aws eks update-kubeconfig 来更新本地的 ~/.kube/config 文件或者 KUBECONFIG 环境变量指向的别的配置文件。

比如说你创建 EKS 的用户在本地 ~/.aws/credentials 中的 profile 是 my-aws-profile, 那么完整的 update-kubeconfig 命令就是

$ aws eks --profile my-aws-profile --region us-east-1 update-kubeconfig --name myeks-cluster
Updated context arn:aws:eks:us-east-1:069762108088:cluster/myeks-cluster in /Users/yanbin/.kube/config

再来执行 kubectl get pods 如果出现错误 error: You must be logged in to the server (Unauthorized),肯定是因为你使用的 awscli 命令比较老(到底有多老呢?在 github 上已经无法追溯了,大概是 1.16.266 之前的)。大约生成的 ~/.kube/config 文件末尾像下面那样 阅读全文 >>

类别: Kubernetes. 标签: . 阅读(747). 评论(0) »

搭建使用 AWS 的 Kubernetes EKS 服务

前面从无到有或是分别以 Docker Desktop, Minikube, kind 来搭建过 Kubernetes 集群。而如今各大云服务提供商基本都推出了各自的 Kubernetes 服务,例如:

  1. Google GKE - Google Kubernetes Engine
  2. Amazon EKS - Amazon Elastic Kubernetes Service
  3. Microsoft AKS - Azure Kubernetes Service
  4. IBM Cloud Kubernetes Service
  5. Alibaba Cloud Container Service

所以对 Kubernetes 的进一步学习过程中何不一跃而直上云霄,直接尝试 AWS 的 EKS 如何搭建。EKS 是在 2018 年 6 月份正式推出,见 Amazon Elastic Container Service for Kubernetes Now Generally Available。EKS 在 AWS 上是与 ECS 并列的服务,它们的功能也比较类似,都是伸缩性的容器服务,ECS 配置管理更分散,EKS 本身就是一个集群管理工具。它们也有些共同的东西,如 Auto Scaling Groups, Launch Templates。

现在用 Terraform 脚本来演示一下如何创建一个 EKS 集群,并启动三个 EC2 Worker 节点(EKS 也支持 Fargate Worker 节点),并部署一个应用。Terraform 脚本将会列出完成该任务的基本要素,也将会看看背后发生了什么。 阅读全文 >>

类别: AWS, Kubernetes. 标签: , . 阅读(298). 评论(0) »