微笑的周末

本文由 简悦 SimpRead 转码， 原文地址 https://new.qq.com/omn/20180827/20180827A0NEVH.html 作者小灰 如需转载，请联系原作者授权。 时间复杂度的意义 究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司…… 一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花 100 毫秒，内存占用 5MB。小灰的代码运行一次要花 100 秒，内存占用 500MB。于是…… 由此可见，衡量代码的好坏，包括两个非常重要的指标： 1. 运行时间； 2. 占用空间。 基本操作执行次数 关于代码的基本操作执行次数，我们用四个生活中的场景，来做一下比喻： 场景 1：给小灰一条长 10 寸的面包，小灰每 3 天吃掉 1 寸，那么吃掉整个面包需要几天？ 答案自然是 3 X 10 = 30 天。 如果面包的长度是 N 寸呢？ 此时吃掉整个面包，需要 3 X n ...

本文由 简悦 SimpRead 转码， 原文地址 https://juejin.im/post/5bbfeace6fb9a05d1117a644?utm_source=gold_browser_extension 原子性在研究 JDK 中 AQS 时，会发现这个类很多地方都使用了 CAS 操作，在并发实现中 CAS 操作必须具备原子性，而且是硬件级别的原子性，java 被隔离在硬件之上，明显力不从心，这时为了能直接操作操作系统层面，肯定要通过用 C++ 编写的 native 本地方法来扩展实现。JDK 提供了一个类来满足 CAS 的要求，sun.misc.Unsafe，从名字上可以大概知道它用于执行低级别、不安全的操作，AQS 就是使用此类完成硬件级别的原子操作。 Unsafe 类Unsafe 是一个很强大的类，它可以分配内存、释放内存、可以定位对象某字段的位置、可以修改对象的字段值、可以使线程挂起、使线程恢复、可进行硬件级别原子的 CAS 操作等等。 但平时我们没有这么特殊的需求去 ...

本文由 简悦 SimpRead 转码， 原文地址 https://juejin.im/post/5bbc7c6de51d450e5c47a26c ————— 当天上午 ————— 什么是冒泡排序？ 冒泡排序的英文 Bubble Sort，是一种最基础的交换排序。 大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。 而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。 具体如何来移动呢？让我们来看一个栗子： 有 8 个数组成一个无序数列：5，8，6，3，9，2，1，7，希望从小到大排序。 按照冒泡排序的思想，我们要把相邻的元素两两比较，根据大小来交换元素的位置，过程如下： 首先让 5 和 8 比较，发现 5 比 8 要小，因此元素位置不变。 接下来让 8 和 6 比较，发现 8 比 6 要大，所以 8 和 ...

本文由 简悦 SimpRead 转码， 原文地址 https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190073&idx=1&sn=c20c002127e2ce3fe0c71a00aee70806&chksm=8c990563bbee8c75521c54ea8eb44b009ad07266b1e5fbf22926baf9a7b7302c7e4f7657dbb8&scene=21#wechat_redirect 小灰回忆起当时的情景…… 题目：实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都是 O（1）。 小灰的想法： 1. 创建一个整型变量 min，初始值 - 1 2. 当第一个元素进栈时，让 min=0，即把唯一的元素当做最小值。 3. 之后每当一个新元素近栈，让新元素和 min 指向 ...

本文由 简悦 SimpRead 转码， 原文地址 https://juejin.im/post/5b95da8a5188255c775d8124?utm_source=gold_browser_extension 1. 概述排序算法分为内部排序和外部排序，内部排序把数据记录放在内存中进行排序，而外部排序因排序的数据量大，内存不能一次容纳全部的排序记录，所以在排序过程中需要访问外存。 经常提及的八大排序算法指的就是内部排序的八种算法，分别是冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序，如果按原理划分，冒泡排序和快速排序都属于交换排序，直接插入排序和希尔排序属于插入排序，而简单选择排序和堆排序属于选择排序，如上图所示。 2. 冒泡排序2.1 基本思想冒泡排序（Bubble Sort）是一种简单的排序算法。它重复访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换的数据，也就是说该数列 ...

本文由 简悦 SimpRead 转码， 原文地址 https://liuzhengyang.github.io/2017/05/12/javamemorymodel/ JMM 简介Java Memory Model 简称 JMM, 是一系列的 Java 虚拟机平台对开发者提供的多线程环境下的内存可见性、是否可以重排序等问题的无关具体平台的统一的保证。(可能在术语上与 Java 运行时内存分布有歧义，后者指堆、方法区、线程栈等内存区域)。并发编程有多种风格，除了 CSP(通信顺序进程)、Actor 等模型外，大家最熟悉的应该是基于线程和锁的共享内存模型了。在多线程编程中，需要注意三类并发问题: 原子性 可见性 重排序原子性涉及到，一个线程执行一个复合操作的时候，其他线程是否能够看到中间的状态、或进行干扰。典型的就是 i++ 的问题了，两个线程同时对共享的堆内存执行 ++ 操作，而 ++ 操作在 JVM、运行时、CPU 中的实现都可能是一个复合操作, 例如在 JVM 指令的角度来看是将 ...

本文由 简悦 SimpRead 转码， 原文地址 http://ifeve.com/redis-lock-2/ 1 介绍这篇博文讲介绍如何一步步构建一个基于 Redis 的分布式锁。会从最原始的版本开始，然后根据问题进行调整，最后完成一个较为合理的分布式锁。 本篇文章会将分布式锁的实现分为两部分，一个是单机环境，另一个是集群环境下的 Redis 锁实现。在介绍分布式锁的实现之前，先来了解下分布式锁的一些信息。 2 分布式锁2.1 什么是分布式锁？分布式锁是控制分布式系统或不同系统之间共同访问共享资源的一种锁实现，如果不同的系统或同一个系统的不同主机之间共享了某个资源时，往往需要互斥来防止彼此干扰来保证一致性。 2.2 分布式锁需要具备哪些条件 互斥性：在任意一个时刻，只有一个客户端持有锁。 无死锁：即便持有锁的客户端崩溃或者其他意外事件，锁仍然可以被获取。 容错：只要大部分 Redis 节点都活着，客户端就可以获取和释放锁 2.4 分布式锁的实现有哪些？ 数据库 Memcached ...

本文由 简悦 SimpRead 转码， 原文地址 https://www.cnblogs.com/20145221GQ/p/5407824.html Java 实现：数据结构之排序0. 概述 形式化定义：假设有 n 个记录的序列（待排序列）为 {R1, R2 , …, Rn}，其相应的关键字序列为 { K1, K2, …, Kn }。找到{1,2, …, n} 的一个排列 p1,p2, …, pn，使得 Kp1≤Kp2≤ …≤ Kpn （升序），按此排列将 n 个记录重新排列为 { Rp1, Rp2, …，Rpn }的操作称作排序。 排序方法分类 基于比较的排序： 比较两个关键字大小 移动关键字到合适位置（交换或复制） 不基于比较的排序 排序有内部排序和外部排序之分，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 本篇博客所要介绍的是内部排序中的八大排序方法（参考博客地址为 C 语言实现）： 1. 插 ...

本文由 简悦 SimpRead 转码， 原文地址 https://tech.meituan.com/dianping_order_db_sharding.html 大众点评订单系统分库分表实践背景原大众点评的订单单表早就已经突破两百 G，由于查询维度较多，即使加了两个从库，优化索引，仍然存在很多查询不理想的情况。去年大量抢购活动的开展，使数据库达到瓶颈，应用只能通过限速、异步队列等对其进行保护；业务需求层出不穷，原有的订单模型很难满足业务需求，但是基于原订单表的 DDL 又非常吃力，无法达到业务要求。随着这些问题越来越突出，订单数据库的切分就愈发急迫了。 这次切分，我们的目标是未来十年内不需要担心订单容量的问题。 垂直切分先对订单库进行垂直切分，将原有的订单库分为基础订单库、订单流程库等，本文就不展开讲了。 水平切分垂直切分缓解了原来单集群的压力，但是在抢购时依然捉襟见肘。原有的订单模型已经无法满足业务需求，于是我们设计了一套新的统一订单模型，为同时满足 C 端用户、B 端商户、客服 ...

本文由 简悦 SimpRead 转码， 原文地址 https://www.jianshu.com/p/f4cca5ce055a 我们假设计算机运行一行基础代码需要执行一次运算。 1234int aFunc(void) { printf("Hello, World!\n"); // 需要执行 1 次 return 0; // 需要执行 1 次} 那么上面这个方法需要执行 2 次运算 123456int aFunc(int n) { for(int i = 0; i<n; i++) { // 需要执行 (n + 1) 次 printf("Hello, World!\n"); // 需要执行 n 次 } return 0; // 需要执行 1 次} 这个方法需要 (n + 1 + ...