单元测试

测试文件需要以xxx_test.go的方式命名。

go test默认会执行当前目录下的所有测试文件。对于执行某个特定测试文件下的特定测试函数,参见-file和-run参数。

测试文件模板:

package gotest

import (
    "testing"
)

func Test_Division_1(t *testing.T) {
    if i, e := Division(6, 2); i != 3 || e != nil { //try a unit test on function
        t.Error("除法函数测试没通过") // 如果不是如预期的那么就报错
    } else {
        t.Log("第一个测试通过了") //记录一些你期望记录的信息
    }
}

func Test_Division_2(t *testing.T) {
    t.Error("就是不通过")
}

测试函数是func TestXxx(t *testing.T) {}格式。

记录信息:t.Log("one test passed.", e)

产生错误信息:t.Error("Division did not work as expected.")

继续阅读

Xcode调试所需要的临时空间非常大,而且不会自动删除,长年累月积累,会造成严重的空间浪费。我的硬盘就白白耗费了22G。缓存的位置:

/Users/<用户名>/Library/Developer/Xcode/DerivedData/

里面包含了大量的缓存文件,都是在编译调试时使用的。很多都是历史遗留的不再使用的文件。直接删除相应文件夹即可。

对于当前工程来说,删除以上文件夹相当于做了一次clean。

问题描述

Sublime Text支持VIM模式,但是有个问题,就是Insert模式下,Esc键与自动完成冲突。当遇到自动完成窗口时,按下Esc键不是退出Insert模式,而是关闭自动完成窗口,这样非常不方便。

解决方法

原理参见文章。解决方法很简单,已经有人做好插件了。只需要用Package Control下载Vintage Escape插件即可。

Java中已经有for eachfor index的方法来遍历集合,为何还要存在迭代器这种东西呢?其实迭代器有其它方式无法实现的功能,那就是遍历/修改的模式。两种for循环在遍历集合的时候非常方便,但是在遍历过程中,如果存在修改集合的需求,就会出现效率问题了。

这里以一个经典的例子作为解释。情景是,有一个LinkedList,在遍历过程中需要删除当前遍历到的元素。这时无论是使用remote(int location)还是remote(Object object)方法,都存在效率问题。因为根据链表的特性,这两个方法都需要从头再遍历一遍。这样,相当于两个循环嵌套,导致时间复杂度变为(O^2)。用迭代器就能很好的解决这个问题。以下是一个用迭代器的示例代码:

mBokehPoints = new LinkedList<BokehPoint>();
for (Iterator<BokehPoint> iter = mBokehPoints.iterator(); iter.hasNext();) {
    BokehPoint e = iter.next();
    if (e.updatePoint()) {
        ......
    } else {
        iter.remove();
    }
}

以上代码在遍历时使用了迭代器的remove方法来删除特定的元素,这个方法不需要重新遍历链表,而是直接将当前位置的元素删除。

当然,迭代器还有其它的意义,比如迭代器是集合遍历的基础方法,迭代器统一了遍历接口,集合中许多功能的实现都与迭代器有关(remove方法底层就是迭代器实现)。

注意:网上有好多在链表遍历时使用remove方法的代码,这是很低效的做法,需要用迭代器修正。

Go语言中没有直接的大小端检测库,因此我写了个小程序用来检测机器的大小端。

检测的核心方法其实就是C语言里的检测方法,通过测试一个特定的int类型变量的头部字节,来确定机器的大小端。

核心代码:

const INT_SIZE int = int(unsafe.Sizeof(0))

//true = big endian, false = little endian
func getEndian() (ret bool) {
    var i int = 0x1
    bs := (*[INT_SIZE]byte)(unsafe.Pointer(&i))
    if bs[0] == 0 {
        return true
    } else {
        return false
    }
}

我写的检测代码的地址:

https://github.com/virtao/GoEndian

通过以下命令安装到gopath里:

go get github.com/virtao/GoEndian

库的使用方法在项目主页中有描述。

Go中可以使用“+”合并字符串,但是这种合并方式效率非常低,每合并一次,就必须遍历一次字符串。Java中提供StringBuilder类来解决这个问题。Go中也有类似的机制,那就是Buffer。以下是示例代码:

package main

import (
    \"bytes\"
    \"fmt\"
)

func main() {
    var buffer bytes.Buffer

    for i := 0; i < 1000; i++ {
        buffer.WriteString(\"a\")
    }

    fmt.Println(buffer.String())
}

使用bytes.Buffer来组装字符串,不需要遍历,只需要将添加的字符串放在缓存末尾即可。

那么这种效率差别有多大呢?我们做个测试,组装10万个“a”。

package main

import (
    \"bytes\"
    \"fmt\"
    \"time\"
)

func main() {

    _, t := testBuf()

    //fmt.Println(s)
    fmt.Println(\"string buffer : \", t, \"ns\")

    _, t = testPlus()

    //fmt.Println(ss)
    fmt.Println(\"string plus : \", t, \"ns\")
}

func testPlus() (s string, t int64) {
    start := time.Now().UnixNano()
    for i := 0; i < 100000; i++ {
        s += \"a\"
    }
    end := time.Now().UnixNano()

    return s, end - start
}

func testBuf() (s string, t int64) {
    var buf bytes.Buffer
    start := time.Now().UnixNano()
    for i := 0; i < 100000; i++ {
        buf.WriteString(\"a\")
    }
    s = buf.String()
    end := time.Now().UnixNano()

    return s, end - start
}

测试结果:

string buffer :  3001700 ns
string plus :  1414015200 ns

使用Buffer仅仅用了3ms,而加号则使用了1.4s,差距巨大。而且使用Buffer时,三分之二的时间用在了buf.String()上,也就是说,组装时间仅仅有1ms,其余2ms花在了转换为字符串上。

我本来是组装1万个“a”的,结果使用Buffer的方式测不出时间(时间为0ns),不得已采用的10万,这也说明Buffer效率非常高。

题目要求

出处:https://www.v2ex.com/t/94742

在一个整型数组里,所有的数都重复了两次,仅有两个数是不重复的,如何在时间O(n)和空间O(1)内找出这两个数?

思路分析

假设这组数字为:

23, 23, 19, 19, 1, 88, 88, 3, 3, 2, 56, 56

两个不重复的数字设为a1和a2。

将所有数字异或:

x = 23^23^19^19^1^88^88^3^3^2^56^56 = 1^2

经过这一步,我们找到了两个不重复数字a1和a2的异或后的结果x。我们还需要将这两个数字分开。下面就是一个比较重要的思路了,x是两个数异或的结果,也就是说,x保存了两个数字各比特位的差异。相同的位为0,不相同的位为1。我们找出不相同的位,便可以将整组数字分为两组。

例如:这里x = 3 = 00000011B,从这里看出,a1和a2在1~2比特位上是不一样的。我们随便选取其中一位,比如右起第一位为区分位,这样所有数字可以分为两组:

比特位末位为0:88, 88, 2, 56, 56
比特位末位为1:23, 23, 19, 19, 1, 3, 3

这样分完后,我们发现,a1和a2分到不同的组里了。将其中任意一组所有数字进行异或,便可以得出其中一个不重复的数字:

a1 = 88^88^2^56^56 = 2
a2 = a1^x = a1^a1^a2 = 1

这样,我们只需要遍历两遍数组,就可以找出这两个数。

代码实例(Go语言)

package main

import (
    \"fmt\"
)

func main() {
    nums := []int{23, 23, 19, 19, 1, 88, 88, 3, 3, 2, 56, 56}

    //设两个不重复的数为a1和a2,x = a1 ^ a2,bits为a1和a2某个不一致的位
    var a1, a2, x, bits int

    //将所有的数字异或,得到的结果就为x,因为重复的数经过异或后都为0
    for _, v := range nums {
        x = x ^ v
    }

    //找出a1和a2某个不一致的位,换句话说,就是找出x为1的位(当然,x为1的位有很多,我们这找的是x从右往左第一个为1的位)
    bits = 1
    for i := 31; i >= 0; i++ {
        if x&bits != 0 {
            break
        }
        bits = bits << 1
    }

    //舍去所有bits位为0的数字,将剩下的数字全部异或,这样就能得出两个不重复的数字其中的一个
    for _, v := range nums {
        if v&bits != 0 {
            a1 = a1 ^ v
        }
    }

    //根据x和a1可以很容易求出a2
    a2 = x ^ a1

    fmt.Println(\"Result : \", a1, a2)
}

异或的运算律

以上题目充分考察了异或的运算律以及异或后的结果所代表的含义。下面内容转自:http://longzxr.blog.sohu.com/190676432.html,内容稍作修改。

异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示。其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。

简单理解就是相同为0,不同为1。

  • 异或运算律

    1. 交换律:a^b == b^a
    2. 结合律:(a^b)^c == a^(b^c)
    3. 对于任何数x,都有x^x=0,x^0=x
    4. 自反性:a^b^b = a^0 = a

异或运算最常见于多项式除法,不过它最重要的性质还是自反性:a^b^b = a^0 = a,即对给定的数a,用同样的运算因子b作两次异或运算后仍得到a本身。这是一个神奇的性质,利用这个性质,可以获得许多有趣的应用。 例如,所有的程序教科书都会向初学者指出,要交换两个变量的值,必须要引入一个中间变量。但如果使用异或,就可以节约一个变量的存储空间: 设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值 表达式 (值) :

A = A ^ B (a ^ b)
B = B ^ A (b ^ a ^ b = a)
A = A ^ B (a ^ b ^ a = b)

类似地,该运算还可以应用在加密,数据传输,校验等等许多领域。

类似的题目

google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数?

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

Go的slice的实质是对数组的封装。slice在数组的基础上,扩展出了大小可变的功能,但是底层实现依赖于数组。而且其切片功能非常类似于指针:切片是一个slice对数组内容的指向,而不是对数组内容的复制。以下程序说明了这种不同。

例子

package main

import (
    \"fmt\"
)

func main() {
    arr1 := [5]int{1, 2, 3, 4, 5}
    fmt.Println(\"定义数组arr1:\", arr1)
    slice1 := arr1[1:2]
    fmt.Println(\"定义对数组arr1的切片slice1(arr1[1:2]):\", slice1)
    fmt.Println(\"slice1缓冲大小:\", cap(slice1))
    slice1 = append(slice1, 6, 7, 8)
    fmt.Println(\"对slice1进行append,添加6、7、8三个数字,这时slice1内容:\", slice1)
    fmt.Println(\"此时slice1缓冲大小:\", cap(slice1))
    fmt.Println(\"这时arr1的内容:\", arr1)
    fmt.Println(\"这说明slice1仅仅是指向arr1的指针,如果修改了slice1,会对之前的arr1造成影响,这也是为什么slice1非常轻量高效的原因。\")
    fmt.Println(\"=========\")

    arr2 := [5]int{1, 2, 3, 4, 5}
    fmt.Println(\"定义数组arr2:\", arr2)
    slice2 := arr2[1:2]
    fmt.Println(\"定义对数组arr2的切片slice2(arr2[1:2]):\", slice2)
    fmt.Println(\"slice2缓冲大小:\", cap(slice2))
    slice2 = append(slice2, 6, 7, 8, 9)
    fmt.Println(\"对slice2进行append,添加6、7、8、9四个数字,这时slice2内容:\", slice2)
    fmt.Println(\"此时slice2缓冲大小:\", cap(slice2))
    fmt.Println(\"这时arr2的内容:\", arr2)
    fmt.Println(\"这说明之前的结论部分正确,也就是说,如果slice2执行append操作时超过了原有缓冲区的大小,slice2会重新创建一个新的更大的缓冲区(新大小为原先缓冲区大小的两倍),并将原数据复制到新缓冲区。这也是为什么arr2内容没有变化的原因。\")
    fmt.Println(\"PS:这里所说slice的缓冲区,其实质是个数组,slice永远指向一个数组。\")
    fmt.Println(\"=========\")

    slice3 := []int{1, 2, 3, 4, 5}
    fmt.Println(\"创建切片slice3:\", slice3)
    fmt.Println(\"slice3缓冲大小:\", cap(slice3))
    slice3 = append(slice3, 6, 7, 8)
    fmt.Println(\"为slice3添加6、7、8三个数:\", slice3)
    fmt.Println(\"slice3缓冲大小:\", cap(slice3))
    fmt.Println(\"这说明slice是以原大小的倍数增长的。\")
    fmt.Println(\"=========\")

    fmt.Println(\"创建空的数组arr4和切片slice4。\")
    arr4 := [5]int{}
    slice4 := []int{}
    fmt.Println(\"数组arr4初始值:\", arr4)
    fmt.Println(\"切片slice4初始值:\", slice4)
    fmt.Println(\"切片slice4的缓冲区大小:\", cap(slice4))
    fmt.Println(\"以上展示了array与slice的区别。\")
}

运行结果:

定义数组arr1: [1 2 3 4 5]
定义对数组arr1的切片slice1(arr1[1:2]): [2]
slice1缓冲大小: 4
对slice1进行append,添加6、7、8三个数字,这时slice1内容: [2 6 7 8]
此时slice1缓冲大小: 4
这时arr1的内容: [1 2 6 7 8]
这说明slice1仅仅是指向arr1的指针,如果修改了slice1,会对之前的arr1造成影响,这也是为什么slice1非常轻量高效的原因。
=========
定义数组arr2: [1 2 3 4 5]
定义对数组arr2的切片slice2(arr2[1:2]): [2]
slice2缓冲大小: 4
对slice2进行append,添加6、7、8、9四个数字,这时slice2内容: [2 6 7 8 9]
此时slice2缓冲大小: 8
这时arr2的内容: [1 2 3 4 5]
这说明之前的结论部分正确,也就是说,如果slice2执行append操作时超过了原有缓冲区的大小,slice2会重新创建一个新的更大的缓冲区(新大小为原先缓冲区大小的两倍),并将原数据复制到新缓冲区。这也是为什么arr2内容没有变化的原因。
PS:这里所说slice的缓冲区,其实质是个数组,slice永远指向一个数组。
=========
创建切片slice3: [1 2 3 4 5]
slice3缓冲大小: 5
为slice3添加6、7、8三个数: [1 2 3 4 5 6 7 8]
slice3缓冲大小: 10
这说明slice是以原大小的倍数增长的。
=========
创建空的数组arr4和切片slice4。
数组arr4初始值: [0 0 0 0 0]
切片slice4初始值: []
切片slice4的缓冲区大小: 0
以上展示了array与slice的区别。

总结

  • slice类似于一个指向数组的指针,slice与数组的不同之处在于,slice可以改变大小。而slice改变大小的方式是重新创建一个更大的数组,并将数据复制到新数组。
  • slice的大小是以原大小的2倍来增长的。
  • 切片后的数据尽量用于读取而不是写入,时刻记住切出来的数据是对原数据的一个引用,而不是一个copy。
  • slice和array的定义方式区别很小,仅仅是是否指定了大小的区别。例如:

    array := [5]int{} //指定了大小,这是一个数组
    slice := []int{} //未指定大小,这是一个切片
    

    如何检验一个变量是否为数组,只需要对其进行append操作,对数组进行append操作会出错。array默认值为5个0元素,而slice默认为空。

  • 我猜测,对于同样多元素,slice要比array占用内存多,因为slice本身需要有个变量来记录其实际长度(slice缓冲大小和slice的有效长度可能不一致)。

Go中所有的文本都以UTF-8编码,因此使用GBK、EUC-KR等国家编码的文本需要进行编码转换才能使用。Go有个比较不错的编码转换库:mahonia(http://code.google.com/p/mahonia/),我们通过例子就可以很方便的了解它的使用方法。

从GBK与UTF-8互转的例子,代码如下:

package main

import (
    \"code.google.com/p/mahonia\"
    \"fmt\"
)

func main() {
    //\"你好,世界!\"的GBK编码
    testBytes := []byte{0xC4, 0xE3, 0xBA, 0xC3, 0xA3, 0xAC, 0xCA, 0xC0, 0xBD, 0xE7, 0xA3, 0xA1}
    var testStr string
    utfStr := \"你好,世界!\"
    var dec mahonia.Decoder
    var enc mahonia.Encoder

    testStr = string(testBytes)

    dec = mahonia.NewDecoder(\"gbk\")
    if ret, ok := dec.ConvertStringOK(testStr); ok {
        fmt.Println(\"GBK to UTF-8: \", ret, \" bytes:\", testBytes)
    }

    enc = mahonia.NewEncoder(\"gbk\")
    if ret, ok := enc.ConvertStringOK(utfStr); ok {
        fmt.Println(\"UTF-8 to GBK: \", ret, \" bytes: \", []byte(ret))
    }
    return
}

这里要注意,NewDecoder和NewEncoder在指定的编码集不存在的情况下,会返回nil,当然,如果你确定编码集是存在的,可以忽略。对于编码集对应的名称,可以查看mahonia的源码,分布在各个编码源文件的init方法里。比如,GBK编码在gbk.go文件里。

Go中的空接口可以代表任何类型,这时候我们就需要有一种方法,能够判断接口代表的具体类型,并且能够进行转换。Go中有两种方法可以实现这个目标。

if结构

if ret, ok := val.(string); ok {
    return ret
}
return def

val是空接口。我们通过这个结构,可以判断val里面是否保存了string类型。如果是,则ok = true,ret保存转换后的字符串;如果不是,则ok = false,ret为空。使用这种结构我们很容易判断并转换类型。

switch结构

有时候我们需要大量的类型判断,这时候用if就不是那么方便了(需要套好几层if语句),其实switch也是支持类型判断的,代码示例如下:

switch v := val.(type) {
case int:
    fmt.Println(\"type is int, value is \", v)
case string:
    fmt.Println(\"type is string, value is \", v)
default:
    fmt.Println(\"unknown type\")
}

case条件全部是类型,v是转换后的值。注意,“val.(type)”这种写法只能用在switch语句中。另外,这种switch结构不能使用fallthrough。

示例代码

package main

import (
    \"fmt\"
)

func main() {
    var test interface{}

    test1 := 20
    test2 := \"Hello World\"

    fmt.Println(\"test1 = \", test1)
    fmt.Println(\"test2 = \", test2)

    test = test1
    fmt.Println(\"MustInt: test1 = \", MustInt(test, 0))
    fmt.Println(\"MustString: test1 = \", MustString(test, \"not string\"))
    PrintType(test)

    fmt.Println()

    test = test2
    fmt.Println(\"MustInt: test2 = \", MustInt(test, 0))
    fmt.Println(\"MustString: test2 = \", MustString(test, \"not string\"))
    PrintType(test)
}

func MustString(val interface{}, def string) string {
    if ret, ok := val.(string); ok {
        return ret
    }
    return def
}

func MustInt(val interface{}, def int) int {
    if ret, ok := val.(int); ok {
        return ret
    }
    return def
}

func PrintType(val interface{}) {
    switch v := val.(type) {
    case int:
        fmt.Println(\"type is int, value is \", v)
    case string:
        fmt.Println(\"type is string, value is \", v)
    default:
        fmt.Println(\"unknown type\")
    }
}

运行结果:

test1 =  20
test2 =  Hello World
MustInt: test1 =  20
MustString: test1 =  not string
type is int, value is  20

MustInt: test2 =  0
MustString: test2 =  Hello World
type is string, value is  Hello World