邢栋博客

邢栋博客,Action博客,记录工作和生活中的点点滴滴

关于栈内存和堆内存
数据结构中的栈和堆:
栈:是一种连续储存的数据结构,具有先进先出的性质。通常的操作有入栈(压栈)、出栈和栈顶元素,就要将之前的所有元素出栈才能完成。类比现实中的箱子一样。
堆:是一种非连续的树形储存结构,每个节点有一个值,整棵树是经过排序的。特点是根节点的值最小(或最大),且根节点的两个子树也是一个堆。常用来实现优先队列,存取随意。

内存中的栈区和堆区:
一般说的内存,指的是计算机的随机储存器(RAM),程序都在这里面运行。
栈内存:由程序自动向操作系统申请分配以及回收,速度快,使用方便,但程序员无法控制。若分配失败,则提示栈溢出错误。注意,const局部变量也存储在栈区内,栈区向地址减小的方向增长。
堆内存:程序员向操作系统申请一块内存,当系统收到程序的申请时,会遍历一个记录空闲内存地址的链表,寻找第一个空间大于所申请空间的堆栈点,然后将该结点从空间结点链表中删除,并将该节点的空间分配给程序。分配的速度较慢,地址不连续,容易碎片化。此外,由程序员申请,同时也必须由程序员负责销毁,否则会导致内存泄漏。

关于堆和栈区别的比喻:
堆和栈的区别可以引用一位前辈的比喻来看出:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大
golang声明通道struct{}
sign := make(chan struct{}, 3)
sign <- struct{}{}
<-sign
声明通道sign的时候以chan struct{}作为其类型的。其中的类型字面量struct{}有些类似于空接口类型interface{},它代表了既不包含任何字段也不拥有任何方法的空结构体类型。
struct{}类型值的表示方法只有一个,即:struct{}{}。并且,它占用的内存空间是0字节。确切的说,这个值在整个go程序中永远都只会存一份。虽然我们无数次的使用这个值的字面量,但是用到的却都是同一个值。
当我们仅仅把通道当做传递某种简单信号的介质的时候,用struct{}作为其元素类型是再好不过的了。
go语句及其执行规则(goroutine)
go语言不但有着独特的并发编程模型,以及用户级线程goroutine,还拥有强大的用于调度goroutine、对接系统线程的调度器。
这个调度器是go语言运行时系统的重要组成部分,它主要负责统筹调配go并发编程模型中的三个元素,即:G(gotoutine的缩写),P(process的缩写)和M(machine的缩写)。
其中M指代的是系统级线程。而P指的是一种可以承诺若干个G,而且能够使这些G适时地与M进行对接,并得到真正运行的中介。


//demo1:
package main
import (
	"fmt"
	//"time"
)
func main() {
	num := 10
	sign := make(chan struct{}, num)
	for i := 0; i < num; i++ {
		go func() {
			fmt.Println(i)
			sign <- struct{}{}
		}()
	}
	// 办法1。
	//time.Sleep(time.Millisecond * 500)

	// 办法2。
	for j := 0; j < num; j++ {
		<-sign
	}
}

golang让多个goroutine按照既定的顺序运行

//demo1:
package main
import (
	"fmt"
	"sync/atomic"
	"time"
)
func main() {
	var count uint32
	trigger := func(i uint32, fn func()) {
		for {
			if n := atomic.LoadUint32(&count); n == i {
				fn()
				atomic.AddUint32(&count, 1) //count++
				break
			}
			time.Sleep(time.Nanosecond)
		}
	}

	for i := uint32(0); i < 10; i++ {
		go func(i uint32) {
			fn := func() {
				fmt.Println(i)
			}
			trigger(i, fn)
		}(i)
	}
	trigger(10, func() {})
}


关于golang值的内存寻址

go语言哪些值不可以寻址
1.常量的值。 
2.基本类型值的字面量。 
3.算术操作的结果值。
4.对各种字面量的索引表达式和切片表达式的结果值。不过有一个例外,对切片字面量的索引结果值却是可寻址的。
5.对字符串变量的索引表达式和切片表达式的结果值
6.对字典变量的索引表达式的结果值。
7.函数字面量和方法字面量,以及对它们的调用表达式的结果值。
8.结构体字面量的字段值,也就是对结构体字面量的选择表达式的结果值。
9.类型转换表达式的结果值。
10.类型断言表达式的结果值。
11.接收表达式的结果值。

总结:不可变的、临时结果和不安全的
1.不可变的值不可寻址。常量、基本类型的值字面量、字符串变量的值、函数以及方法的字面量都是如此。其实这样规定也有安全性方面的考虑。
2.绝大多数被视为临时结果的值都是不可寻址的。算术操作的结果值属于临时结果,针对值字面量的表达式结果值也属于临时结果。但有一个例外,对切片字面量的索引结果值虽然也属于临时结果,但却是可寻址的。
3.若拿到某值的指针可能会破坏程序的一致性,那么就是不安全的,该值就不可寻址。由于字典的内部机制,对字典的索引结果值的取址操作都是不安全的。另外,获取由字面量或标识符代表的函数或方法的地址显然也是不安全的。

package main

type Named interface {
	// Name 用于获取名字。
	Name() string
}

type Dog struct {
	name string
}

func (dog *Dog) SetName(name string) {
	dog.name = name
}

func (dog Dog) Name() string {
	return dog.name
}

func main() {
	// 示例1。
	const num = 123
	//_ = &num // 常量不可寻址。
	//_ = &(123) // 基本类型值的字面量不可寻址。

	var str = "abc"
	_ = str
	//_ = &(str[0]) // 对字符串变量的索引结果值不可寻址。
	//_ = &(str[0:2]) // 对字符串变量的切片结果值不可寻址。
	str2 := str[0]
	_ = &str2 // 但这样的寻址就是合法的。

	//_ = &(123 + 456) // 算术操作的结果值不可寻址。
	num2 := 456
	_ = num2
	//_ = &(num + num2) // 算术操作的结果值不可寻址。

	//_ = &([3]int{1, 2, 3}[0]) // 对数组字面量的索引结果值不可寻址。
	//_ = &([3]int{1, 2, 3}[0:2]) // 对数组字面量的切片结果值不可寻址。
	_ = &([]int{1, 2, 3}[0]) // 对切片字面量的索引结果值却是可寻址的。
	//_ = &([]int{1, 2, 3}[0:2]) // 对切片字面量的切片结果值不可寻址。


	//_ = &(map[int]string{1: "a"}[0]) // 对字典字面量的索引结果值不可寻址。
	var map1 = map[int]string{1: "a", 2: "b", 3: "c"}
	_ = map1
	//_ = &(map1[2]) // 对字典变量的索引结果值不可寻址。

	//_ = &(func(x, y int) int {
	//	return x + y
	//}) // 字面量代表的函数不可寻址。
	//_ = &(fmt.Sprintf) // 标识符代表的函数不可寻址。
	//_ = &(fmt.Sprintln("abc")) // 对函数的调用结果值不可寻址。

	dog := Dog{"little pig"}
	_ = dog
	//_ = &(dog.Name) // 标识符代表的函数不可寻址。
	//_ = &(dog.Name()) // 对方法的调用结果值不可寻址。

	//_ = &(Dog{"little pig"}.name) // 结构体字面量的字段不可寻址。

	//_ = &(interface{}(dog)) // 类型转换表达式的结果值不可寻址。
	dogI := interface{}(dog)
	_ = dogI
	//_ = &(dogI.(Named)) // 类型断言表达式的结果值不可寻址。
	named := dogI.(Named)
	_ = named
	//_ = &(named.(Dog)) // 类型断言表达式的结果值不可寻址。

	var chan1 = make(chan int, 1)
	chan1 <- 1
	//_ = &(<-chan1) // 接收表达式的结果值不可寻址。

}

golang笔记之Printf函数
package main
import "fmt"
import "os"
type point struct {
	x, y int
}
func main() {
	//Go 为常规 Go 值的格式化设计提供了多种打印方式。例如,这里打印了 point 结构体的一个实例。
	p := point{1, 2}

	fmt.Printf("%v\n", p) // {1 2}
	// 如果值是一个结构体,%+v 的格式化输出内容将包括结构体的字段名。
	fmt.Printf("%+v\n", p) // {x:1 y:2}
	// %#v 形式则输出这个值的 Go 语法表示。例如,值的运行源代码片段。
	fmt.Printf("%#v\n", p) // main.point{x:1, y:2}
	//需要打印值的类型,使用 %T。
	fmt.Printf("%T\n", p) // main.point
	//格式化布尔值是简单的。
	fmt.Printf("%t\n", true)

	//格式化整形数有多种方式,使用 %d进行标准的十进制格式化。
	fmt.Printf("%d\n", 123)
	//这个输出二进制表示形式。
	fmt.Printf("%b\n", 14)
	//这个输出给定整数的对应字符。
	fmt.Printf("%c\n", 33)
	//%x 提供十六进制编码。
	fmt.Printf("%x\n", 456)
	//对于浮点型同样有很多的格式化选项。使用 %f 进行最基本的十进制格式化。
	fmt.Printf("%f\n", 78.9)
	//%e 和 %E 将浮点型格式化为(稍微有一点不同的)科学技科学记数法表示形式。
	fmt.Printf("%e\n", 123400000.0)
	fmt.Printf("%E\n", 123400000.0)

	//使用 %s 进行基本的字符串输出。
	fmt.Printf("%s\n", "\"string\"")
	//像 Go 源代码中那样带有双引号的输出,使用 %q。
	fmt.Printf("%q\n", "\"string\"")
	//和上面的整形数一样,%x 输出使用 base-16 编码的字符串,每个字节使用 2 个字符表示。
	fmt.Printf("%x\n", "hex this")
	//要输出一个指针的值,使用 %p。
	fmt.Printf("%p\n", &p)
	//当输出数字的时候,你将经常想要控制输出结果的宽度和精度,可以使用在 % 后面使用数字来控制输出宽度。默认结果使用右对齐并且通过空格来填充空白部分。
	fmt.Printf("|%6d|%6d|\n", 12, 345)
	//你也可以指定浮点型的输出宽度,同时也可以通过 宽度.精度 的语法来指定输出的精度。
	fmt.Printf("|%6.2f|%6.2f|\n", 1.2, 3.45)
	//要最对齐,使用 - 标志。
	fmt.Printf("|%-6.2f|%-6.2f|\n", 1.2, 3.45)
	//你也许也想控制字符串输出时的宽度,特别是要确保他们在类表格输出时的对齐。这是基本的右对齐宽度表示。
	fmt.Printf("|%6s|%6s|\n", "foo", "b")
	//要左对齐,和数字一样,使用 - 标志。
	fmt.Printf("|%-6s|%-6s|\n", "foo", "b")
	//到目前为止,我们已经看过 Printf了,它通过 os.Stdout输出格式化的字符串。Sprintf 则格式化并返回一个字符串而不带任何输出。
	s := fmt.Sprintf("a %s", "string")
	fmt.Println(s)
	//你可以使用 Fprintf 来格式化并输出到 io.Writers而不是 os.Stdout。
	fmt.Fprintf(os.Stderr, "an %s\n", "error")
}
golang笔记之值类型和引用类型
值类型:所有像int、float、bool和string这些类型都属于值类型,使用这些类型的变量直接指向存在内存中的值,值类型的变量的值存储在栈中。当使用等号=将一个变量的值赋给另一个变量时,如 j = i ,实际上是在内存中将 i 的值进行了拷贝。可以通过 &i 获取变量 i 的内存地址

引用类型:复杂的数据通常会需要使用多个字,这些数据一般使用引用类型保存。一个引用类型的变量r1存储的是r1的值所在的内存地址(数字),或内存地址中第一个字所在的位置,这个内存地址被称之为指针,这个指针实际上也被存在另外的某一个字中。

局部变量被声明后必须在相同的代码块中使用它,否则会得到编译错误,全局变量允许声明但不使用.如果要交换两个变量(已声明且赋值)的值,可以简单地使用a,b = b,a,这被称为并行或同时赋值; _实际上是一个只写变量,我们无法得到它的值,这样做是因为Go语言中必须使用所有被声明的局部变量,但有时我们并不需要使用从一个函数中得到的所有返回值;并行赋值也被用于当一个函数返回多个返回值时,比如这里的val和错误err是通过调用func1函数同时得到:val,err = func1()

iota:特殊常量,可以认为是一个可以被编译器修改的常量。在每一个const关键字出现时,被重置为0,然后在下一个const出现之前,每出现一次iota,值自动加1.
php的IteratorAggregate简单事例
<?php
    //IteratorAggregate Generators

    //事例(一)
    class Language implements IteratorAggregate{
        private $names;
        public function __construct(){
            $this->names = explode(',','PHP,JS,JAVA,GO');
        }
        public function getIterator(){
            return new ArrayIterator($this->names);
        }

    }

    $langs = new Language();

    foreach($langs as $lang){
        echo $lang.PHP_EOL;
    }

    //事例(二) 返回一个外部迭代器,可以对数据本身及相关逻辑做更统一的封装
    class Test implements IteratorAggregate{
        private $data;
        public function __construct(array $data){
            $this->data = $data;
        }
        public function getIterator(){
            foreach($this->data as $key=>$value){
                yield $key=>$value;
            }
        }
    }

    $testArr = array(
        'xd'=>100,
        'action'=>123,
        'xingd'=>126
    );
    $test = new Test($testArr);

    foreach($test as $key=>$value){
        echo $key.'-'.$value.PHP_EOL;
    }
数据结构以及常用数据结构的定义

数据:描述客观事物的符号,如文本、图片、视频
数据元素:组成数据的,有一定意义的基本单位
数据项:一个数据元素可以由若干个数据项组成
数据对象:性质相同的数据元素的组合
数据结构:数据结构是计算机用来组织和存储数据的方式。具体定义:数据结构是指相互之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素的关系组成

数据结构:
逻辑结构 
1.线性结构 (线性表、栈、队、串、数组)
2.非线性结构  树结构和图结构
物理(存储)结构
1.顺序结构
2.链式结构
3.索引结构
4.散列结构
数据运算
1.插入运算
2.删除运算
3.修改运算
4.查找运算
5.排序运算

时间复杂度
1.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数T(n)
注:如果一个循环次数n次的for语句,如果里面有3条赋值语句,那么总执行次数就是3n,所以这个函数T(n)就是循环次数,T(n)=3n,语句的执行次数(频度)*单位执行时间 就是总执行时间

2.从T(n)中找到同数量级(同阶)函数记作f(n),例如T(n)= 3n的同数量级的函数f(n)=n
注:如果T(n)=n^3+n^2+n,则 f(n)=n^3

3.这个时候我们能够计算出时间复杂度了 T(n)=O(f(n))
用T(n)/f(n),然后求极限值--------  (n^3+n^2+n)/n^3 = 1+1/n+1/n^2  ,求极限值 是一个常数,那么时间复杂度就是 O(f(n)),也就是O(n^3)

简单推导时间复杂度
1.用常数1取代执行时间中的所有加法常数
2.在修改后的执行次数函数中,只保留最高阶项
3.如果最高阶存在且不是1,则去掉他的系数
4.得到的结果就是大O阶
简单说就是 最高阶的执行次数


线性表的特点
定义:零个或多个数据元素的有限序列
除首尾外,均只有一个直接前驱和直接后继

一个数组元素可以有若干数据项组成
线性表有顺序存储和链式存储两种数据结构 
堆栈、队列、串、数组等都是线性表

单链表
head -> A -> B -> C -> D -> E
data-next 
节点包括 1、data数据域,存放节点的值 2、next指针域,存放节点的直接后继的地址
插入节点:头插/尾插,也叫前插和后插,其实就是head所指向节点不一样,当然他们的时间复杂度也不一样
删除节点:先找到要删除的节点位置,将父节点的next指向其子节点,然后删除该节点
查询节点:从head开始一级一级往下找
编辑节点:从head开始一级一级往下找,找到后编辑内容
节点排序:。


双链表
head <-> A <-> B <-> C <-> D <-> E
pre-data-next 
节点包括 1、data数据域,存放节点的值 2、pre指针域,存放节点的直接前驱的地址 3、next指针域,存放节点的直接后继的地址

队列QUEUE
队列是只允许在一端进行插入,则在另外一端进行删除的运算受限的线性表
1.允许删除的一端成为队头(Front)
2.允许插入的一端为队尾(Rear)
3.队列中没有元素成为空队列
4.队列亦称作先进先出的线性表,简称FIFO表

堆栈
先进后出



它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做树是是因为它看起来像一颗倒挂的树
特点
1.每个节点有零个或者多个子节点
2.没有父节点的节点成为根节点
3.每一个非根节点有且只有一个父节点
4.除了根节点外,每个子节点可以分为多个不相符的子树

无序树:树中任意节点的子节点之间没有顺序关系,这种树叫做无序树,也叫做自由树
有序数: 树中任意节点的子节点之间有顺序关系,成为有序树
二叉树:每个节点最多包含两个子树的树称为二叉树 完全二叉树:对于一颗二叉树,假设其深度d(d>1).除了第d层外,其他各层的节点,数目均已达最大值,且第d层所有节点从左向右连续的紧密排列,这样的二叉树称为完全二叉树
满二叉树:对于上述的完全二叉树,如果去掉其第d层的所有节点,那么剩下的部分就构成一个满二叉树(此时该满二叉树的深度为d-1)
霍夫曼树:带全路径最短的二叉树称为霍夫曼树或者最优二叉树



遍历二叉树
    A
  B    C
D E   F
  G H  I
1.先序遍历 ABCDEFGHI  首先访问根结点,然后遍历左子树,然后遍历右子树。简称 根-左-右
2.中序遍历 DBAGECHFI  首先遍历左子树,然后访问根节点,然后遍历右子树。简称 左-根- 右
3.后序遍历 DBGEHIFCA   首先遍历左子树,然后遍历右子树,最后访问根节点。简称 左-右-根

二叉排序数
二叉排序树又称二叉查找数,也成二叉搜索树,它或者是一颗空树;或者是具有下列性质的二叉树:
1.若左子树不空,则左子树上所有节点的值均小于它的根节点的值
2.若右子树不空,则右子树上所有节点的值均小于他的根节点的值
3.左、右子树也分别为二叉排序树



快速排序
通过一趟排序,将待排序部分记录分隔成独立的两部分,其中一部分记录的关键字均比另外一部分记录的关键值小,在分别对这两部分记录进行下一趟排序,以达到整个序列有序。
快速排序就是比较适合用递归来处理的。


简单选择排序
排序思想:设所排序序列的记录个数为n。i取1,2,。。。。n-1,从所有n-i+1个记录中找到排序码最小的记录,与第i个记录交换。执行n-1趟后完成了记录序列的排序。

直接插入排序
每次从无序表中取出第一个元素,把他插入到有序表的合适位置,使有序表依然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描,第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后完成了整个排序过程。







优惠券
广告位-淘宝
最新微语