• 为什么要使用各种前端框架

    引言

    在学习前端的过程中,我开始接触到许多开发框架或开发工具,这些工具让我开始眼花缭乱。使用常规的html/css/js就已经能够开发出这种网页了,所以我问自己,为什么要学习这些框架或工具,这些库是用来解决什么问题的。想明白这个问题,我学习的目的就更加明确,在遇到一些开发情景时,也能够快速准确地挑选出应该使用的框架。

    下面按照我目前的理解,对目前的主流的前端开发库进行一些分析和比较。由于我还是一个初学着,所以我的观点可能还不是很成熟。

    为什么要使用jQuery

    jQuery是一个轻量级js库,它有如下特性:

    • 简化了HTML/DOM操作
    • CSS选择器
    • 动画特效支持
    • 解决跨浏览器的兼容行问题
    • 完善的Ajax支持

    在查阅资料的过程中,我还听到一些主张停用jQuery的声音。原因就在于随着前端开发生态不断的完善,现代浏览器原生API已经足够好用。

    为什么要使用SASS

    SASS是一种CSS预编译格式,它最终会编译成CSS。
    SASS提供了CSS语法的拓展,它支持变量,算数运算符,循环操作,函数操作,样式模板(mixin)等强大的特性。它能够让开发人员更方便地编写CSS。SASS支持 import 关键字,这样就能够很方便地对样式进行模块化设计。

    加一句题外话,在使用SASS时,需要考虑的另一个问题就是代码物理结构的安排(直白的说就是目录的划分,源文件的存放位置等),这也是所有代码开发中需要注意的问题。

    与SASS相似的工具还有LESS。

    为什么要使用Bootstrap

    Bootstrap是一个用于快速开发网页的前端框架。以我目前的理解来看,它更像是一个网页样式框架。

    • 丰富的基础样式和资源
    • 响应式(responsive),良好的移动端支持
    • 强大的网格(grid)系统
    • 一致性,保证跨浏览器的样式一致

    为什么要使用React

    DOM操作对性能的影响很大,频繁的DOM操作会使网页渲染的速度变慢,React主要解决了这个问题。
    React.js允许在js中编写html,形成Virtual DOM,只在变化进行重新渲染。

    下面的一段文字摘自参考资料中的第5篇文章。

    • Am I building an app which has lots of DOM interactions, or is it a relatively simple app with relatively few interactions?
    • Does my app require a very high browser performance, that any user interactions must immediately be reflected in the UI? Is my data going to change over time, at a high rate?
    • Is one user interaction going to affect many other areas/components in the UI?
    • Is there a possibility that my app could grow big in the future, and so I would want to write extremely neat, modular front-end JavaScript that is easy to maintain? Would I want to use lots of native JavaScript or would I prefer using a lot of abstractions/methods provided in a framework?
    • Would I prefer a framework/library which does not have a high learning curve and which is pretty easy to get started with development?

    在使用React之前,问自己这样几个问题,就能够帮助你决定是否需要使用React。

    • 所开发的网页应用涉及到很多DOM操作么?
    • 开发的网页应用需要很高的性能么,这意味着任何用于的操作都要立刻反应在界面上?我的数据变更会很频繁么?
    • 我开发的应用会在未来逐渐变得复杂么,这样我就需要将前端的js代码模块化?我是否会使用许多原生js特性,是否虚幻使用框架提供的抽象方法
    • 是否需要一个学习曲线比较平缓的框架,能够方便地上手进行开发?
  • javscript中的OOP特性

    1 引言

    js也是具有OOP(object oriented programming)特性的,OOP在构建一些大型应用程序还是有一套成熟理论的。作为C++的使用者在学习js中的OOP特性的过程中,能够较快地理解其中的各种术语和概念,也能比较两种语言的异同,深化知识理解。通过js的OOP特性的学习也让我开始从语言层面考虑程序设计问题。
    本篇文章主要介绍了js中的一些OOP特性,并且比较了js与C++的语言特性。如果你能熟练掌握C++的OOP特性,本文能帮助你快速地对js中的OOP特性建立整体的认识。

    2 写给C++使用者的js中的OOP特性介绍

    2.1 创建对象(object)

    js中创建object的代码,示例如下:

    let duck = {
      name: "Aflac",
      numLegs: 2,
      sayName: function() {
        return "The name of this duck is " + this.name + ".";
      }
    };
    

    js直接通过 {} 就可以创建出对象示例来,不需要对该对象(object)的类(class)进行声明。这点和C++不是很相同,C++需要先声明一个class再创建object。
    这个object有两个成员变量和一个成员函数,需要注意的是这两个成员变量都是公有(public)的,他们是可以直接用 . 符号访问的。
    js中也有 this 关键字,与C++相同, this 关键字用于表示当前实例。

    2.2 类(class)的声明

    js中声明一个类的操作实际上就是声明一个构造函数。

    let Bird = function(name, color) {
      this.name = name;
      this.color = color;
      this.numLegs = 2;
    }
    
    let crow = new Bird("Alexis", "black");
    
    crow instanceof Bird; // => true
    

    上面的代码声明了Bird类,在js中通常类的名字都是由首字母大写的单词表示的。类的构造函数也能接受参数用于对实例的初始化,这点与C++非常相似,使用 new 关键字就能够创建该类的实例。
    使用 instanceof 关键字用于检查对象是否属于某个类,也可通过验证 constructor 属性来判断一个对象是否属于一个类 crow.constructor == Bird

    2.3 类的共有成员

    js中通过 prototype 这一属性(把它叫做关键字好像还不太合适)能够实现C++中静态成员变量和静态成员函数的特性。

    Bird.prototype.numLegs = 2;
    

    上面的代码就给Bird类增加了一个静态成员变量。这个 prototype 可以是一个对象,这样类的共有成员就能方便地承载更多的属性了,示例代码如下。

    Bird.prototype = {
      constructor: Bird,
      numLegs: 2,
      eat: function() {
        console.log("nom nom nom");
      },
      describe: function() {
        console.log("My name is " + this.name);
      }
    };
    

    需要注意的是需要设置好 constructor 属性,这样是为了保证代码逻辑的一致性。
    对象会获得类的 prototype 属性,可以通过 isPrototypeof 方法来验证。

    Bird.prototype.isPrototypeOf(duck);
    

    2.4 类的私有成员

    js与C++一样,也可以有私有成员变量,代码如下所示。 hatchedEgg 就相当与是Bird的私有成员变量,并且提供了修改这个成员变量的方法 getHatchedEggCount

    function Bird() {
      let hatchedEgg = 10; // private property
    
      this.getHatchedEggCount = function() {
        // publicly available method that a bird object can use
        return hatchedEgg;
      };
    }
    let ducky = new Bird();
    ducky.getHatchedEggCount(); // returns 10
    

    这种形式在js中被称作闭包(closure),函数能够访问到与他处在同一个作用域(context)中的变量。

    2.5 类的继承和派生

    js中的派生主要通过 prototype 体现,下面的代码表示Bird派生自Object。同样,需要注意将 constructor 属性设置好。

    Bird.prototype = Object.create(Animal.prototype);
    Bird.prototype.constructor = Bird;
    

    2.6 类的覆盖

    js中可以重写基类中的方法,代码如下所示,这点与C++中的 override 相同。

    function Animal() { }
    Animal.prototype.eat = function() {
      return "nom nom nom";
    };
    function Bird() { }
    
    // Inherit all methods from Animal
    Bird.prototype = Object.create(Animal.prototype);
    
    // Bird.eat() overrides Animal.eat()
    Bird.prototype.eat = function() {
      return "peck peck peck";
    };
    
    Bird.prototype.fly = function() {
      console.log("I'm flying!");
    };
    

    通样也在派生之后也可以通过修改派生类的 prototype 以达到特化派生类的作用,上面的 fly 方法就是在Bird完成派生之后新增的方法。现在Bird有两个方法,它们分别是 eatfly

  • js正则表达式备忘

    引言

    近在FreeCodeCamp(FCC)学习前端的课程,其中有一节就是讲的 regexp ,也就是正则表达式。我之前零星地了解过一些正则表达式的相关知识,但不足以对正则表达式得出一个完整的认识。FCC的教程循序渐进,由简到繁,在教学中结合练习,非常适合初学者的学习过程。如何你的英文能够达到阅读技术类文献的水平,又正好想学习一下正则表达式,我推荐你试一下FCC的正则表达式教程,花3~4个小时就能够对正则表达式有个完整的理解。

    教程使用的编程语言是javascript,需要注意的是不同语言之间的正则表达式在某些细节上还是略有区别的。

    本篇文章主要是对学习过程中的知识点进行总结,方便以后进行查阅。

    要点总结(js版)

    FCC的教程使用javascript作为开发语言,本节所有的代码都是js代码。

    js中内置了正则表达式模块,下面是正则表达式在js中的使用示例

    let myString = "Hello World";
    let myRegex = /Hello/;
    let result = myRegex.test(myString);
    

    使用 | 进行or匹配

    let regex2 = /cat|bird/;
    

    使用 i 标识符在匹配时忽略大小写

    let regex3 = /case/i;
    

    使用正则表达式进行字符串过滤,使用 match 方法

    let extractStr = "Extract the word 'coding' from this string.";
    let codingRegex = /coding/; // Change this line
    let result = extractStr.match(codingRegex); // Change this line
    

    使用 g 进行返回满足规则的多次结果, g 为global的缩写

    let twinkleStar = "Twinkle, twinkle, little star";
    let starRegex = /twinkle/gi; // Change this line
    let result = twinkleStar; // Change this line
    

    使用 . 匹配所有的字符,使用 [] 匹配指定的字符

    let quoteSample = "Beware of bugs in the above code; I have only proved it correct, not tried it.";
    let vowelRegex = /[aeiou]/gi; // Change this line
    let result = quoteSample.match(vowelRegex); // Change this line
    

    [] 中可以使用 - 代表一个范围

    let quoteSample2 = "The quick brown fox jumps over the lazy dog.";
    let alphabetRegex = /[a-z]/gi; // Change this line
    let result = quoteSample2.match(alphabetRegex); // Change this line
    

    这个范围还可以是多个,并且允许包含数字

    let quoteSample3 = "Blueberry 3.141592653s are delicious.";
    let myRegex = /[h-s2-6]/gi; // Change this line
    let result = quoteSample3.match(myRegex); // Change this line
    

    使用 ^ 符号能够匹配不包含某些字符

    let quoteSample4 = "3 blind mice.";
    let myRegex2 = /[^0-9aeiou]/gi; // Change this line
    let  result = quoteSample4.match(myRegex2); // Change this line
    

    使用 + 对出现连续出现的字符进行匹配

    let difficultSpelling = "Mississippi";
    let  myRegex3 = /s+/g; // Change this line
    let result = difficultSpelling.match(myRegex3);
    

    使用 * 星号匹配可能没有出现的次数(出现次数为 0~n 次)

    let chewieQuote = "Aaaaaaaaaaaaaaaarrrgh!";
    let chewieRegex = /Aa*/; // Change this line
    let result = chewieQuote.match(chewieRegex);
    

    使用 ? 进行较短匹配 (lazy match, 与greedy match 对应)

    let text = "<h1>Winter is coming</h1>";
    let myRegex = /<.*?>/; // Change this line
    let result = text.match(myRegex);
    

    使用 ^ 对出现在字符串开始位置进行匹配
    注意上边也用到这个符号表示取反,是在 [] 中表示取反

    let rickyAndCal = "Cal and Ricky both like racing.";
    let calRegex = /^Cal/; // Change this line
    let result = calRegex.test(rickyAndCal);
    

    使用 $ 对出现在字符串结束位置进行匹配

    let caboose = "The last car on a train is the caboose";
    let lastRegex = /caboose$/; // Change this line
    let result = lastRegex.test(caboose);
    

    使用 \w 代替 [A-Za-z0-9_] ,包含所有的数字、字母和下划线

    let quoteSample = "The five boxing wizards jump quickly.";
    let alphabetRegexV2 = /\w/g; // Change this line
    let result = quoteSample.match(alphabetRegexV2).length;
    

    使用 \W 代替 [^A-Za-z0-9_] ,相当于上边的逆向匹配

    let quoteSample = "The five boxing wizards jump quickly.";
    let nonAlphabetRegex = /\W/g; // Change this line
    let result = quoteSample.match(nonAlphabetRegex).length;
    

    使用 \d 代替 [0-9] ,所有数字匹配

    let numString = "Your sandwich will be $5.00";
    let numRegex = /\d/g; // Change this line
    let result = numString.match(numRegex).length;
    

    使用 \D 代替 [^0-9] ,所有非数字匹配

    let numString = "Your sandwich will be $5.00";
    let noNumRegex = /\D/g; // Change this line
    let result = numString.match(noNumRegex).length;
    

    使用 \s 代替 [ \r\t\f\n\v] ,与空格和换行相关

    let sample = "Whitespace is important in separating words";
    let countWhiteSpace = /\s/g; // Change this line
    let result = sample.match(countWhiteSpace);
    

    使用 \S=,代替 =[^ \r\t\f\n\v] ,不包含空格和换行

    let sample = "Whitespace is important in separating words";
    let countNonWhiteSpace = /\S/g; // Change this line
    let result = sample.match(countNonWhiteSpace);
    

    使用 {min, max} 对字符出现的次数进行限定
    回想起使用 + 限制次数为 {0,} ,使用 - 限制次数为 {1,}

    let ohStr = "Ohhh no";
    let ohRegex = /Oh{3,6} no/; // Change this line
    let result = ohRegex.test(ohStr);
    

    仅限制出现次数的下限 {min,}

    let haStr = "Hazzzzah";
    let haRegex = /Haz{4,}ah/; // Change this line
    let result = haRegex.test(haStr);
    

    指定出现的次数 {count}

    let timStr = "Timmmmber";
    let timRegex = /Tim{4}ber/; // Change this line
    let result = timRegex.test(timStr);
    

    使用 ? 匹配可能出现的字母
    问号用于声明lazy match,如何判断是lazy match还是匹配可能出现的东西呢

    let favWord = "favorite";
    let favRegex = /favou?rite/; // Change this line
    let result = favRegex.test(favWord);
    

    lookahead 的概念, (?=...)(?!...)

    下面的正则表达式用于检查密码,由3~6个字母和至少1个数字组成

    let password = "abc123";
    let checkPass = /(?=\w{3,6})(?=\D*\d)/;
    let result = checkPass.test(password); // Returns true
    

    下面的正则表达式用于检查密码,有5个以上的字符和至少2个数字组成

    let sampleWord = "astronaut";
    let pwRegex = /(?=\w{5,})(?=\D*\d{2,})/; // Change this line
    let result = pwRegex.test(sampleWord);
    

    截取字符串中的重复部分,使用括号 () 对内容进行补充,是用 \1 表示第一个捕捉到的字符

    let repeatNum = "42 42 42";
    let reRegex = /^(\d*)\s\1\s\1$/; // Change this line
    let result = reRegex.test(repeatNum);
    

    通过截取字符串,可以对截取的字符串进行修改或替换操作,需要使用 replace 方法

    "Code Camp".replace(/(\w+)\s(\w+)/, '$2 $1'); // Returns "Camp Code"
    

    下面的正则表达式就是用于将 good 替换为 okey-dokey

    let huhText = "This sandwich is good.";
    let fixRegex = /good/; // Change this line
    let replaceText = "okey-dokey"; // Change this line
    let result = huhText.replace(fixRegex, replaceText);
    

    使用正则表达式实现类似 .trim() 的功能

    let hello = "   Hello, World!  ";
    let wsRegex = /^\s+|\s+$/g; // Change this line
    let result = hello.replace(wsRegex, ''); // Change this line
    

    elisp和python中的正则表达式

    在emacs中内置了 string-match 函数进行正则表达式匹配,其函数原型为 (string-match REGEXP STRING &optional START) ,下面就是在emacs中使用regexp的示例。

    (setq str-regexp "\.[h|cpp]$")
    (setq str-sample-1 "sample1.h")
    (string-match str-regexp str-sample-1)
    

    python中内置了 re 模块用于正则表达式匹配,下面就是在python中的regexp示例。

    import re
    pattern = r"Cookie"
    sequence = "Cookie"
    if re.match(pattern, sequence):
        print("Match!")
    else:
        print("Not a match!")
    
  • 每周算法:字符串转整数

    Description

    Implement atoi which converts a string to an integer.

    The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

    The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

    If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

    If no valid conversion could be performed, a zero value is returned.

    Note:
    Only the space character ' ' is considered as whitespace character.
    Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

    Example 1:
    Input: "42"
    Output: 42

    Example 2:
    Input: " -42"
    Output: -42
    Explanation: The first non-whitespace character is '-', which is the minus sign.
    Then take as many numerical digits as possible, which gets 42.

    Example 3:
    Input: "4193 with words"
    Output: 4193
    Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

    Example 4:
    Input: "words and 987"
    Output: 0
    Explanation: The first non-whitespace character is 'w', which is not a numerical
    digit or a +/- sign. Therefore no valid conversion could be performed.

    Example 5:
    Input: "-91283472332"
    Output: -2147483648
    Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
    Thefore INT_MIN (−231) is returned.

    来源 leetcode 8 string to integer

    Solution

    Approach 1

    这道题并不难,思路也比较容易想出来,下面就是我想到的解法。
    可能需要注意的问题是:

    1. 字符到数字的转换,这个涉及到ascii码表的记忆,如果记不住了可以直接使用'0' 'a' 'A'
    2. 对于溢出的判断,我一开始只想到了使用 int temp=num*10; if (temp/10!=num) 进行判断,实际上却忽略了 2147483648(0x80000000) 的边界情况,这个是需要特别注意的。
    int parseChar(char ch) {
        int num = ch - '0';
        if (num > 9 || num < 0) {
    	return -1;
        }
        return num;
    }
    
    int myAtoi (string str) {
        bool isNegative = false;
        bool isOverflow = false;
        int num = 0;
    
        // 从前向后进行转换
        size_t pos = 0;
    
        // 去除多余的空格
        while (str[pos] == ' ') {
    	++pos;
        }
    
        // 首先判断是否有符号位
        if (str.length() > 0) {
    	if (str[pos] == '-') {
    	    isNegative = true;
    	    ++pos;
    	}
    	else if (str[pos] == '+') {
    	    ++pos;
    	}
        }
    
        // 是否以数字进行开头
        // 从左向右读取数字,每次读取需要判断是否溢出
        for ( ; pos < str.length(); ++pos) {
    	int digit = parseChar(str[pos]);
    	if (digit < 0) {
    	    // 负数说明该位不是数字了
    	    break;
    	}
    
    	// 如何判断是否溢出
    	int temp = num*10;
    	if (temp/10 != num) {
    	    isOverflow = true;
    	    break;
    	}
    
    	num = temp + digit;
        }
    
        // 如果num变成负数,也是溢出了,相当于对最后一位检查溢出
        if (isOverflow || num < 0) {
    	return isNegative ? INT_MIN : INT_MAX;
        }
    
        return isNegative ? -num : num;
    }
    

    Approach 2

    下面这段代码目前是leetcode上运行速度最快的solution sample,仅仅耗时了4ms。作者使用了很多让程序跑得更快的方法,其中的技巧值得我学习。

    static int fast = []() {
    	ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        return 0;
    }();
    
    class Solution {
    public:
    int myAtoi(string str) {
    	long long sum = 0;
    	int base=10;
    	int n = str.size();
    	bool flag = true;
    	int sign = 1;
    	for(int i = 0; i < n; i++) {
    	    if(isalpha(str[i])) {
    		return sum;
    	    }
    	    else if(str[i]==' '&&flag) {
    		continue;
    	    }
    	    else if(str[i]>='0' && str[i]<='9') {
    		sum = 10*sum + sign*(str[i] - '0');
    		flag = false;
    	    }
    	    else if(str[i] == '-' &&flag) {
    		sign = -1;
    		flag = false;
    	    }
    	    else if(str[i] == '+' && flag) {
    		flag = false;
    	    }
    	    else {
    		return sum;
    	    }
    
    	    if(sum > INT_MAX) {
    		return INT_MAX;
    	    }
    	    else if(sum < INT_MIN) {
    		return INT_MIN;
    	    }
    	    return sum;
    	}
        };
    
    • C++标准库中提供了判断是否是数字的接口 isdigit 和判断是否是字母的接口 isalpha
    • 使用以下代码能加速代码的运行速度,这段代码会停止C++和C输入输出流的同步,并且解除 cincout 的捆绑,这里 有更详细的解释。效果很明显,将其添加到我的代码中,将我的代码的运行时间从20ms提升至8ms。
    static int fast = []() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
      return 0;
    }();
    
  • MapReduce模型

    序言

    对于mapreduce的兴趣起源于我最近在学习javascript时遇到了map和reduce函数。使用这两个函数进行数据处理时,总感觉思路有一点奇特,理解起来需要绕一个弯子。之前在学python时,也看到过这两个函数,但是当时没有在意,现在我觉得我有必要对这两个函数做一个深入的研究了。

    什么是MapReduce

    MapReduce的深层概念远比两个函数来得复杂,它是一个编程模型,主要用于解决大数据处理问题。使用这种模式编写的程序是可并行的(parallelized)并适用于大型计算机集群。运行时由系统自动对输入数据进行分割、协调多机器间的计算任务、进行异常处理、管理机器间的内部通信。这样,没有并行计算和分布式系统相关经验的开发人员也能够借助大型分布式系统进行数据处理了。

    百度百科中给出的定义比较全面,而且很准确。

    MapReduce是面向大数据并行处理的计算模型、框架和平台,它隐含了以下三层含义:
    1)MapReduce是一个基于集群的高性能并行计算平台(Cluster Infrastructure)。它允许用市场上普通的商用服务器构成一个包含数十、数百至数千个节点的分布和并行计算集群。
    2)MapReduce是一个并行计算与运行软件框架(Software Framework)。它提供了一个庞大但设计精良的并行计算软件框架,能自动完成计算任务的并行化处理,自动划分计算数据和计算任务,在集群节点上自动分配和执行任务以及收集计算结果,将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的复杂细节交由系统负责处理,大大减少了软件开发人员的负担。
    3)MapReduce是一个并行程序设计模型与方法(Programming Model & Methodology)。它借助于函数式程序设计语言Lisp的设计思想,提供了一种简便的并行程序设计方法,用Map和Reduce两个函数编程实现基本的并行计算任务,提供了抽象的操作和并行编程接口,以简单方便地完成大规模数据的编程和计算处理。

    map和reduce

    从编程语言的角度上来说
    map操作会接收到两个参数,一个列表和一个变换过程,其功能是将这个变换过程映射到每一个列表成员上,从而得到一个新的列表。
    reduce操作也会接收到两个参数,一个列表和一个变换过程,其功能是将这个变换过程从前向后作用在列表成员上,最终得到一个列表中条目。

    从分布式系统的角度上来说 (以下内容摘自百度百科)

    简单说来,一个映射函数就是对一些独立元素组成的概念上的列表(例如,一个测试成绩的列表)的每一个元素进行指定的操作(比如前面的例子里,有人发现所有学生的成绩都被高估了一分,它可以定义一个“减一”的映射函数,用来修正这个错误。)。事实上,每个元素都是被独立操作的,而原始列表没有被更改,因为这里创建了一个新的列表来保存新的答案。这就是说,Map操作是可以高度并行的,这对高性能要求的应用以及并行计算领域的需求非常有用。
    而化简操作指的是对一个列表的元素进行适当的合并(继续看前面的例子,如果有人想知道班级的平均分该怎么做?它可以定义一个化简函数,通过让列表中的元素跟自己的相邻的元素相加的方式把列表减半,如此递归运算直到列表只剩下一个元素,然后用这个元素除以人数,就得到了平均分。)。虽然他不如映射函数那么并行,但是因为化简总是有一个简单的答案,大规模的运算相对独立,所以化简函数在高度并行环境下也很有用。

    我之前在学习语言层面的map和reduce时,很难理解其用途,结合分布式计算的背景知识,就能够较形象地理解map和reduce操作的过程和作用。

    并行计算与大数据

    mapreduce模型给并行计算带来了革命性的影响,它是目前为止最成功、最广为接受和最易于使用的大数据并行处理技术。

    mapreduce最初由google提出,并开发出了如下产品

    • Google File System(大规模分散文件系统)
    • MapReduce (大规模分散FrameWork)
    • BigTable(大规模分散数据库)
    • Chubby(分散锁服务)

    随后就有其对应的开源实现,也就是Hadoop。Hadoop是Apache软件基金会发起的一个项目,它是一种分布式数据和计算的框架,它包含许如下子项目。

    • HDFS,hadoop distributed file system,是Google File System的开源实现
    • MapReduce,是Google MapReduce的开源实现
    • HBASE,类似Google BigTable的分布式NoSQL数据库
    • Zookeeper,分布式锁服务,类似Google Chubby
  • 每周算法:字符串锯齿变换

    Description

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

    P   A   H   N
    A P L S I I G
    Y   I   R
    

    And then read line by line: "PAHNAPLSIIGYIR"
    Write the code that will take a string and make this conversion given a number of rows:
    string convert(string s, int numRows);

    Example 1:
    Input: s = "PAYPALISHIRING", numRows = 3
    Output: "PAHNAPLSIIGYIR"

    Example 2:
    Input: s = "PAYPALISHIRING", numRows = 4
    Output: "PINALSIGYAHRPI"
    Explanation:

    P     I    N
    A   L S  I G
    Y A   H R
    P     I
    

    来源: LeetCode 06 ZigZag Conversion

    Solution

    Approach 1 找规律

    我想到的第一个方法就是找规律,通过寻找每一行的变化规律,编写相应的计算逻辑。
    需要注意:

    • 有符号数和无符号数的比较,这个是非常容易出错的,不要在有符号和无符号数之间进行比较。
    • 特殊情况,也就是只有一行的情况,这个情况不需要进行转换,直接返回原字符串就好。
    string convert(string s, int numRows) {
    
        int len = s.length();
        assert(numRows > 0);
        int base = 2*numRows - 2;
        if (base == 0) {
    	return s;
        }
    
        string ans;
    
        // 第一行和最后一行需要进行特殊处理
    
        // 第一行
        int i = 0;
        while (base*i < len) {
    	ans += s[base*i];
    	++i;
        }
    
        // 中间行
        for (int j=1; j<numRows-1; ++j) {
    	i = 0;
    	while (base*i - j < len) {
    
    	    if (base*i - j >=0 ) {
    		ans += s[base*i-j];
    	    }
    
    	    if (base*i + j < len) {
    		ans += s[base*i+j];                
    	    }
    
    	    ++i;
    	}
        }
    
        // 最后一行
        int lastStart = numRows - 1;
        i = 0;
        while (lastStart + base*i < len) {
    	ans += s[lastStart + base*i];
    	++i;
        }
    
        return ans;
    }
    

    Approach 2 Sort by Row

    这个方法是leetcode提供的一个方法,主要思路是使用一个二维矩阵将字符串按照顺序存储起来,时间复杂度为 O(n) ,空间复杂度为 O(n)

    string convert(string s, int numRows) {
        if (numRows == 1) return s;
    
        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;
    
        for (char c : s) {
    	rows[curRow] += c;
    	if (curRow == 0 || curRow == numRows - 1) {
    	    goingDown = !goingDown;
    	}
    
    	curRow += goingDown ? 1 : -1;
        }
    
        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
    

    Approach 3 Visit by Row

    这个方法是leetcode提供的另一个方法,通过计算下标完成字符串的转换,实际上也是对转换的规律进行了总结,时间复杂度为 O(n) ,空间复杂度为 O(1)
    对于空间复杂度,实际上需要额外的空间存储结果字符串,如果忽略函数所返回的结果字符串,则空间复杂度为 O(1)

    string convert(string s, int numRows) {
        if (numRows == 1) return s;
    
        string ret;
        int n = s.size();
        int cycleLen = 2 * numRows - 2;
    
        for (int i = 0; i < numRows; i++) {
    	for (int j = 0; j + i < n; j += cycleLen) {
    	    ret += s[j + i];
    	    if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
    		ret += s[j + cycleLen - i];
    	}
        }
        return ret;
    }