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

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

Cygwin下的iconv工具(在libiconv包里)不支持-o参数,只能输出到屏幕,因此网上好多方法并不能达到效果,以下是经过测试的使用方法:

for i in `find ./ -type f` ; do iconv -f GBK -t UTF-8 $i > ${i}.tmp && mv ${i}.tmp $i ; done

使用tmp文件是为了在转换失败的时候不要继续覆盖原文件。

故障现象

我移动硬盘有300G空间为ext4分区格式,而我的Ubuntu一直装在VMware的虚拟机里。这样我使用VMware的挂载物理磁盘的功能来使用移动硬盘上的300G空间。以前一直好好的,最近突然出现挂载错误的情况。具体表现就是,当我启动虚拟机的时候,VMware会弹出对话框:

\"VMware错误提示\"

如果我点“重试”,则一直弹出这个错误。如果点“继续”,大概点十来次就不见了,但是300G空间的数据变为只读。如果点“取消”,那么整个虚拟机就会崩溃。

问题所在

刚开始我以为磁盘损坏了,用LinuxReader工具读取分区,发现没什么问题。然后我就去网上搜,最终找到一篇:《Setting a disk to offline in order to make physical disk access work in [Windows 7] on [VMware]》。文章的整体的意思是,Windows7在磁盘在线状态下是无法使用VMware的物理磁盘挂载功能的,将磁盘脱机就可以了。经过我实验,发现文章的说法是错误的,但是歪打正着,还是解决了我的问题。

其实我碰到这个问题,是因为我的分区对应的卷脱机了。Windows下有磁盘脱机和卷脱机两种脱机状态。至于我的卷怎么脱机的我也不太清楚,估计是因为,我的ext4分区被Windows分配盘符后,我害怕不小心被格式化了,将盘符删除了,结果Windows顺便把我的卷标记为了脱机状态。关于卷和分区的关系,平时我们的普通分区仅仅是卷的一种,叫做基本卷。卷可以实现比分区更多的功能,比如跨磁盘、组建RAID等。类似于Linux下的LVM。

解决方法

以管理员方式运行cmd,然后运行diskpart,用list volume列出所有卷的状态,对于脱机的卷,找到其编号,然后用select volume <编号>命令选择这个卷,再使用online volume将选择的卷联机。

以下是操作的详细步骤:

C:>diskpart

Microsoft DiskPart 版本 6.3.9600

Copyright (C) 1999-2013 Microsoft Corporation.
在计算机上: VIRTAO-PC

DISKPART> list volume

  卷 ###      LTR  标签          FS      类型        大小     状态       信息
  ----------  ---  -----------  -----  ----------  -------  ---------  --------
  卷     0     Z                       DVD-ROM         0 B  无介质

  卷     1     E   系统         NTFS   磁盘分区         131 GB  正常     页面文件

  卷     2     F   软件         NTFS   磁盘分区         800 GB  正常

  卷     3     C               NTFS   磁盘分区          80 GB  正常     系统

  卷     4     D               NTFS   磁盘分区          31 GB  正常

  卷     5     G   我的SD卡     exFAT  可移动           29 GB  正常

  卷     6     K   虚拟机       NTFS   磁盘分区          85 GB  正常

  卷     7     J   移动存储     NTFS   磁盘分区         380 GB  正常

  卷     8     H                       可移动             0 B  无介质

  卷     9     I                       可移动             0 B  无介质


DISKPART> select volume 8

卷 8 是所选卷。

DISKPART> online volume

DiskPart 成功使所选卷联机。

DISKPART> exit

退出 DiskPart...

C:>

DiskPart

这个工具是Windows下的专业命令行磁盘管理工具,类似Linux下的fdisk。这里只介绍有关卷和磁盘状态修改的命令。

首先是list命令,可以列出系统中的磁盘、分区或者卷的各类信息,包括后文要用到的编号:

list disk
list partition
list volume

然后是select命令,这个命令用来选择当前要操作的磁盘或者卷。只有使用这个命令选择目标磁盘或者卷后,才能进行进一步的操作。

select disk <编号>
select partition <编号>
select volume <编号>

第三个是控制联机和脱机的命令。

online disk
online volume
offline disk
offline volume

使用之前要先选择分区。

其它命令的详细用法,可以输入命令后查看帮助,也可以用help命令。

Linux下如果/boot是独立分区,经常更新内核容易导致/boot分区空间满了。解决方法就是删除旧的内核,这里以CentOS为例。

1. 查看/boot空间

# df -h /boot

2. 查看系统正在使用的内核版本,防止删错了导致无法启动

# uname -a

3. 删除旧的内核

# rm -rf /boot/*2.6.32-279*

如果多次升级,则可能有多个版本的旧内核,注意区分,别删错了。

也可以将这些文件先转移到别的地方,防止改错后系统无法启动。

4. 修改/boot/grub/grub.conf文件,将和2.6.32-279相关的条目删除

这一步注意备份grub.conf,一旦改错了还能有后悔药。

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