深度优先

【Angular】同步异步处理

发表于 2019-07-19 分类于前端知识
本文字数： 4.4k 阅读时长 ≈ 4 分钟

转自：https://rxjs-cn.github.io/learn-rxjs-operators/operators/combination/forkjoin.html

遇到一个angular异步请求的问题，需要同时调用六七个接口，后面的操作是基于这六七个接口的返回结果的。

用forkJoin，正好可以解决，网上的一些例子都不适用。

函数签名: forkJoin(...args, selector : function): Observable

当所有 observables 完成时，发出每个 observable 的最新值。

如果你想要多个 observables 按发出顺序相对应的值的组合，试试 zip！

如果内部 observable 不完成的话， forkJoin 永远不会发出值！

为什么使用 `forkJoin` ？

当有一组 observables，但你只关心每个 observable 最后发出的值时，此操作符是最适合的。此操作符的一个常见用例是在页面加载(或其他事件)时你希望发起多个请求，并在所有请求都响应后再采取行动。它可能与 Promise.all 的使用方式类似。

注意，如果任意作用于 forkJoin 的内部 observable 报错的话，对于那些在内部 observable 上没有正确 catch 错误，从而导致完成的 observable，你将丢失它们的值 (参见示例 4)。如果你只关心所有内部 observables 是否成功完成的话，可以在外部捕获错误。

还需要注意的是如果 observable 发出的项多于一个的话，并且你只关心前一个发出的话，那么 forkJoin 并非正确的选择。在这种情况下，应该选择像 combineLatest 或 zip 这样的操作符。

示例

示例 1: Observables 再不同的时间间隔后完成

( StackBlitz | jsBin | jsFiddle )

// RxJS v6+
import { delay, take } from 'rxjs/operators';
import { forkJoin, of, interval } from 'rxjs';

const myPromise = val =>
  new Promise(resolve =>
    setTimeout(() => resolve(`Promise Resolved: ${val}`), 5000)
  );

/*
  当所有 observables 完成时，将每个 observable 
  的最新值作为数组发出
*/
const example = forkJoin(
  // 立即发出 'Hello'
  of('Hello'),
  // 1秒后发出 'World'
  of('World').pipe(delay(1000)),
  // 1秒后发出0
  interval(1000).pipe(take(1)),
  // 以1秒的时间间隔发出0和1
  interval(1000).pipe(take(2)),
  // 5秒后解析 'Promise Resolved' 的 promise
  myPromise('RESULT')
);
//输出: ["Hello", "World", 0, 1, "Promise Resolved: RESULT"]
const subscribe = example.subscribe(val => console.log(val));

示例 2: 发起任意多个请求

( StackBlitz | jsBin | jsFiddle )

// RxJS v6+
import { mergeMap } from 'rxjs/operators';
import { forkJoin, of } from 'rxjs';

const myPromise = val =>
  new Promise(resolve =>
    setTimeout(() => resolve(`Promise Resolved: ${val}`), 5000)
  );

const source = of([1, 2, 3, 4, 5]);
// 发出数组的全部5个结果
const example = source.pipe(mergeMap(q => forkJoin(...q.map(myPromise))));
/*
  输出:
  [
   "Promise Resolved: 1",
   "Promise Resolved: 2",
   "Promise Resolved: 3",
   "Promise Resolved: 4",
   "Promise Resolved: 5"
  ]
*/
const subscribe = example.subscribe(val => console.log(val));

示例 3: 在外部处理错误

( StackBlitz | jsBin | jsFiddle )

// RxJS v6+
import { delay, catchError } from 'rxjs/operators';
import { forkJoin, of, throwError } from 'rxjs';

/*
  当所有 observables 完成时，将每个 observable 
  的最新值作为数组发出
*/
const example = forkJoin(
  // 立即发出 'Hello'
  of('Hello'),
  // 1秒后发出 'World'
  of('World').pipe(delay(1000)),
  // 抛出错误
  _throw('This will error')
).pipe(catchError(error => of(error)));
// 输出: 'This will Error'
const subscribe = example.subscribe(val => console.log(val));

示例 4: 当某个内部 observable 报错时得到成功结果

( StackBlitz | jsBin | jsFiddle )

// RxJS v6+
import { delay, catchError } from 'rxjs/operators';
import { forkJoin, of, throwError } from 'rxjs';

/*
  当所有 observables 完成时，将每个 observable 
  的最新值作为数组发出
*/
const example = forkJoin(
  // 立即发出 'Hello'
  of('Hello'),
  // 1秒后发出 'World'
  of('World').pipe(delay(1000)),
  // 抛出错误
  _throw('This will error').pipe(catchError(error => of(error)))
);
// 输出: ["Hello", "World", "This will error"]
const subscribe = example.subscribe(val => console.log(val));

示例 5: Angular 中的 forkJoin
(plunker )

@Injectable()
export class MyService {
  makeRequest(value: string, delayDuration: number) {
    // 模拟 http 请求
    return of(`Complete: ${value}`).pipe(
      delay(delayDuration)
    );
  }
}

@Component({
  selector: 'my-app',
  template: `
    <div>
      <h2>forkJoin Example</h2>
      <ul>
        <li> {{propOne}} </li>
        <li> {{propTwo}} </li>
        <li> {{propThree}} </li>
      </ul>
    </div>
  `,
})
export class App {
  public propOne: string;
  public propTwo: string;
  public propThree: string;
  constructor(private _myService: MyService) {}

  ngOnInit() {
    // 使用不同的延迟模拟3个请求
    forkJoin(
      this._myService.makeRequest('Request One', 2000),
      this._myService.makeRequest('Request Two', 1000),
      this._myService.makeRequest('Request Three', 3000)
    )
    .subscribe(([res1, res2, res3]) => {
      this.propOne = res1;
      this.propTwo = res2;
      this.propThree = res3;
    });
  }
}

【算法】快速排序

发表于 2019-07-16 分类于算法竞赛
本文字数： 3k 阅读时长 ≈ 3 分钟

转自：https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了 O(N2)。假如我们的计算机每秒钟可以运行 10 亿次，那么对 1 亿个数进行排序，桶排序则只需要 0.1 秒，而冒泡排序则需要 1 千万秒，达到 115 天之久，是不是很吓人。那有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢。

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个 10 个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排列。

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字 6 在序列的第 1 位。我们的目标是将 6 挪到序列中间的某个位置，假设这个位置是 k。现在就需要寻找这个 k，并且以第 k 位为分界点，左边的数都小于等于 6，右边的数都大于等于 6。想一想，你有办法可以做到这点吗？

给你一个提示吧。请回忆一下冒泡排序，是如何通过“交换”，一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢？怎样交换才既方便又节省时间呢？先别急着往下看，拿出笔来，在纸上画画看。我高中时第一次学习冒泡排序算法的时候，就觉得冒泡排序很浪费时间，每次都只能对相邻的两个数进行比较，这显然太不合理了。于是我就想了一个办法，后来才知道原来这就是“快速排序”，请允许我小小的自恋一下(^o^)。

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换他们。这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i”和“哨兵 j”。刚开始的时候让哨兵 i 指向序列的最左边（即 i=1），指向数字 6。让哨兵 j 指向序列的最右边（即 j=10），指向数字 8。

首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先出动，这一点非常重要（请自己想一想为什么）。哨兵 j 一步一步地向左挪动（即 j–），直到找到一个小于 6 的数停下来。接下来哨兵 i 再一步一步向右挪动（即 i++），直到找到一个数大于 6 的数停下来。最后哨兵 j 停在了数字 5 面前，哨兵 i 停在了数字 7 面前。

现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列如下。

6 1 2 5 9 3 4 7 10 8

到此，第一次交换结束。接下来开始哨兵 j 继续向左挪动（再友情提醒，每次必须是哨兵 j 先出发）。他发现了 4（比基准数 6 要小，满足要求）之后停了下来。哨兵 i 也继续向右挪动的，他发现了 9（比基准数 6 要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下。

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵 j 继续向左挪动，他发现了 3（比基准数 6 要小，满足要求）之后又停了下来。哨兵 i 继续向右移动，糟啦！此时哨兵 i 和哨兵 j 相遇了，哨兵 i 和哨兵 j 都走到 3 面前。说明此时“探测”结束。我们将基准数 6 和 3 进行交换。交换之后的序列如下。

3 1 2 5 4 6 9 7 10 8

到此第一轮“探测”真正结束。此时以基准数 6 为分界点，6 左边的数都小于等于 6，6 右边的数都大于等于 6。回顾一下刚才的过程，其实哨兵 j 的使命就是要找小于基准数的数，而哨兵 i 的使命就是要找大于基准数的数，直到 i 和 j 碰头为止。

OK，解释完毕。现在基准数 6 已经归位，它正好处在序列的第 6 位。此时我们已经将原来的序列，以 6 为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“ 9 7 10 8 ”。接下来还需要分别处理这两个序列。因为 6 左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理 6 左边和右边的序列即可。现在先来处理 6 左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以 3 为基准数进行调整，使得 3 左边的数都小于等于 3，3 右边的数都大于等于 3。好了开始动笔吧。

如果你模拟的没有错，调整完毕之后的序列的顺序应该是。

2 1 3 5 4

OK，现在 3 已经归位。接下来需要处理 3 左边的序列“ 2 1 ”和右边的序列“5 4”。对序列“ 2 1 ”以 2 为基准数进行调整，处理完毕之后的序列为“1 2”，到此 2 已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“ 2 1 ”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下。

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下。

1 2 3 4 5 6 7 8 9 10

到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N2)，它的平均时间复杂度为 O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。

自己撸的代码：

public class QuickSort : ISort
{
    public int[] Sort(int[] numbers)
    {
        return Sort(numbers, 0, numbers.Length - 1);
    }

    private static int[] Sort(int[] numbers,int left,int right)
    {
        if (left<right)
        {
            int middle = numbers[(left + right) / 2];
            int i = left - 1;
            int j = right + 1;
            while (true)
            {
                while (numbers[++i] < middle) ;

                while (numbers[--j] > middle) ;

                if (i >= j)
                    break;

                Swap(numbers, i, j);
            }
            Sort(numbers, left, i - 1);
            Sort(numbers, j + 1, right);
        }
        return numbers;
    }

    private static void Swap(int[] numbers, int i, int j)
    {
        int temp = numbers[i];
        numbers[i]= numbers[j];
        numbers[j] = temp;
    }
}

【设计】单例模式

发表于 2019-07-08 分类于编程路上
本文字数： 2.6k 阅读时长 ≈ 2 分钟

来源：伯乐在线 - 熊绎
http://blog.jobbole.com/109449/

设计模式是老生常谈的问题，有人工作多年却对设计模式一窍不通，但是更多的人是懂一点点，但是不求甚解。其实这样不好，暂且不说在工作中的应用，即便是在面试时，被面试官问到设计模式时一脸懵逼，是非常尴尬的事情。本文不废话，不谈大篇理论教学，只针对面试，给出设计模式的关键点，从应试的角度，让大家认识和理解设计模式。

首先搞清楚一点，设计模式不是高深技术，不是奇淫技巧。设计模式只是一种设计思想，针对不同的业务场景，用不同的方式去设计代码结构，其最最本质的目的是为了解耦，延伸一点的话，还有为了可扩展性和健壮性，但是这都是建立在解耦的基础之上。

我们都知道大名鼎鼎的GoF的21种设计模式，看过head first的这本书的人应该不少。针对这21种设计模式，面试官问出的问题可能千变万化，让人莫名的忧(dan)伤(teng)，但是不要怕，只要你搞清楚了每种设计模式的关键点和精髓，就可以举一反三，迎刃而解了。

今天我们来看看最简单的单例模式。理论我就不介绍了，没听说过的可以去查一下。即便是最简单的单例，也有关键点。举个不太恰当地例子，看过修仙修道之类小说的同学都知道，一般阵法高手做阵都有一个或多个“阵眼”，同理，我们每种设计模式也有“阵眼”，那么单例的“阵眼”在哪里？各位莫慌，我们先来看看代码。根据单例模式的理论：保证系统中只有一个实例，于是我撸了以下代码

public class Singleton {  
    private Singleton() {}                     //关键点0：构造函数是私有的
    private static Singleton single = null;    //关键点1：声明单例对象是静态的
    public static Singleton GetInstance()      //通过静态方法来构造对象
    {                        
         if (single == null)
         {                                     //关键点2：判断单例对象是否已经被构造
             single = new Singleton();  
         }    
        return single;  
    }  
}

好了，如果我是面试官，你是候选人，我要你撸个单例给我，你撸以上代码问我资词不资词，我肯定是不资词的。为什么？真的不是因为我想搞个大新闻，而是这段单例的代码一般情况下还是可以勉强运行，但是，遇到多线程的并发条件下就大清药丸了。因为这段代码是线程不安全的，有可能给new出多个单例实例，都多个了，还是屁的“单例”啊。

好，废话不多说，继续撸代码，你可能会说：”不是说线程不安全吗？小爷我加上线程安全判断呗，度娘在手天下我有，来了您呐~“

public class Singleton {  
    private Singleton() {}                     //关键点0：构造函数是私有的
    private static Singleton single = null;    //关键点1：声明单例对象是静态的
    private static object obj= new object();
    public static Singleton GetInstance()      //通过静态方法来构造对象
    {                        
         if (single == null)                   //关键点2：判断单例对象是否已经被构造
         {                            
            lock(obj)                          //关键点3：加线程锁
            {
               single = new Singleton();  
             }
         }    
        return single;  
    }  
}

好了，这回该消停了吧，锁也加了，线程也安全了。But，你还是太连清。。。这样依然有问题。问题在哪里？就在关键点2，检测单例是否被构造。虽然这里判断了一次，但是由于某些情况下，可能有延迟加载或者缓存的原因，只有关键点2这一次判断，仍然不能保证系统是否只创建了一个单例，也可能出现多个实例的情况，那么怎么办呢？

public class Singleton {  
    private Singleton() {}                     //关键点0：构造函数是私有的
    private static Singleton single = null;    //关键点1：声明单例对象是静态的
    private static object obj= new object();
    public static Singleton GetInstance()      //通过静态方法来构造对象
    {                        
         if (single == null)                   //关键点2：判断单例对象是否已经被构造
         {                            
            lock(obj)                          //关键点3：加线程锁
            {
               if(single == null)              //关键点4：二次判断单例是否已经被构造
               {
                  single = new Singleton();  
                }
             }
         }    
        return single;  
    }  
}

所以，在判断单例实例是否被构造时，需要检测两次，在线程锁之前判断一次，在线程锁之后判断一次，再去构造实例，这样就万无一失了。是不是很简(Tu)单(Xue)呢？
最后，我们来归纳一下。下次面试别人再问你单例模式，你可以这样说：

单例是为了保证系统中只有一个实例，其关键点有5：

一.私有构造函数
二.声明静态单例对象
三.构造单例对象之前要加锁（lock一个静态的object对象）
四.需要两次检测单例实例是否已经被构造，分别在锁之前和锁之后
如果要你撸代码，你就撸最后这一段，完美~面试官要是个女的准想和你生猴子。。。

哦，别高兴太早了，面试官要是个男的，也可能会问你下列问题

0.为何要检测两次？
如上面所述，有可能延迟加载或者缓存原因，造成构造多个实例，违反了单例的初衷。

1.构造函数能否公有化？
不行，单例类的构造函数必须私有化，单例类不能被实例化，单例实例只能静态调用

2.lock住的对象为什么要是object对象，可以是int吗？
不行，锁住的必须是个引用类型。如果锁值类型，每个不同的线程在声明的时候值类型变量的地址都不一样，那么上个线程锁住的东西下个线程进来会认为根本没锁，相当于每次都锁了不同的门，没有任何卵用。而引用类型的变量地址是相同的，每个线程进来判断锁多想是否被锁的时候都是判断同一个地址，相当于是锁在通一扇门，起到了锁的作用。

好了，这下估计男的都想跟你生猴子了。。。

当所有 observables 完成时，发出每个 observable 的最新值。

为什么使用 forkJoin ？

示例

为什么使用 `forkJoin` ？