Leo_SHEN

Leo_SHEN 查看完整档案

北京编辑北京邮电大学  |  物理 编辑  |  填写所在公司/组织 guozi149.me 编辑
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

Leo_SHEN 回答了问题 · 5月19日

解决rust引用问题?

因为你标记3的那里还在使用b,导致mutable borrow的作用域是你标记的1 2 3三行,在此期间,你不能再次有任何borrow行为了。

至于你不理解的地方,官方描述就是操作你借走的资源。
A ‘mutable reference’ allows you to mutate the resource you’re borrowing.
https://doc.rust-lang.org/1.8...

其实很好理解,如果引用不算borrow的话,那么rust真个borrow机制就不可能工作了。

关注 1 回答 1

Leo_SHEN 发布了文章 · 5月19日

C++中vector的增长因子

我们都知道C++的vector的容量会随着添加的元素而自动增长,但是每次增长多少呢?原来的两倍?三倍?还是多少?下面,让我们来研究下增长因子是如何确定的。

首先,要阐述一个vector实现相关的事实:
vector使用allocator,而不是realloc,所以,不管你增长因子是多少,必然需要重新copy-cons(或move-cons)一遍。

废话不多讲了,下面进入正题。
假设,我们用了一个vector,其占用内存为M,内存布局如下图所示:

FreeMFree

我们一直使用这个vector,当元素太多导致内存不够的时候,要重新给这个vector分配内存,新分配的内存大小为f * M。
首先,要先分配f * M的空间,注意,这个时候M那块内存还没有释放掉:

FreeMf * MFree

然后把之前的M空间释放掉:

FreeFree(M)f * MFree

我们继续使用这个vector,内存又不够了,再次分配的内存大小为f * f * M。
和上面类似,分配内存时:

FreeFree(M)f Mf f * MFree

然后释放掉前一块地址:

FreeFree(M)Free(f M)f f * MFree

以此类推,第n次重新分配内存时,需要新分配f ^ n * M大小的内存,内存分布如下所示(带括号说明已经释放了):

Free(M)(f M)(...)f ^ (n-1) Mf ^ n * MFree

然后再把之前的f ^ (n-1) * M大小的内存回收:

Free(M)(f M)(...)(f^(n-1) M)f ^ n * MFree

我们思考这样一个问题:如果当第n次进行内存扩展时,前面n-2次操作释放的内存(包括第n-2次的内存和最开始占用的内存M)之和大于第n次所需要的内存,那么内存分配器就可以用之前留下来的内存而不用再往后去寻找Free的块。按照这个想法得到的内存分布如下:

Freef ^ n M(GAP)(f ^ (n-1) M)Free

这样做的好处有两个,一是可以提高内存分配器的效率,更重要的是,内存的使用更加紧凑,局部性更好,能够更好的利用缓存机制

上述想法包含一个约束条件,即下面的不等式(两边已同除了M):
f^n <= 1 + f + f^2 + ... + f^(n-2)
当f=1.5时,n最小为5,也就是说,第五次进行内存扩展的时候,可以利用前面释放的内存。
当f=2时,2^n <= 2^(n-1) -1,不等式永假,也就是说,vector再也不能利用之前释放的内存。

从不等式可以得到,f越小,能满足不等式的n也会随之减小,但是如果f很小,会频繁的遇到内存不足进行扩展的情况,也就是说,会经常性的copy-cons或者move-consvector里面的元素,得不偿失。而且5也足够小了,所以1.5是一个不错的选择。

读到这里,可能很多人会说,内存分配器是按照First-Fit来进行内存分配的吗?你怎么能假设“内存管理器就可以用之前留下来的内存而不用再往后去寻找Free的块”呢?而且,你这示例图都是连续的内存,实际情况未必如此啊。其实现代内存分配器很复杂,可能会把内存先分成若干块,每一块接受不同大小的内存分配,比如第一块都是内存需求量小于64B的,第二块都是内存需求量64B至128B,第三块都是需求量128B-1KB的等等;同时每一块又可能有不同的分配回收机制。所以实际情况远比我们想象的复杂,想要真实性能,做性能测试才是靠谱的途径。

排除这些外界因素,仅从本文分析的角度看来,增长因子1.5是个不错的选择,比2要好,因为使用2永远不会利用到之前释放的内存。

Facebook利用上述分析的原理(增长因子是1.5),配合jemalloc,开发了一套fbVector(已开源),性能比GCC的要好。
Microsoft的VC++ STL中的vector实现,增长因子也是1.5以获取更好的性能。
而GCC和CLang还停留在古老的增长因子为2的阶段。

下面这段小程序,能够帮你测试出当前实现的增长因子:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> arr;

    for (int i = 1; i < 10; i++)
    {
        arr.push_back(i \* i);
        std::cout <<
            "Size: " << arr.size() << "; " <<
            "Capacity: " << arr.capacity() << "\n";
    }

    return 0;
}

原文于2015-08发布在我的小站

查看原文

赞 0 收藏 0 评论 0

Leo_SHEN 回答了问题 · 5月11日

n升级node相关问题

$ npm prefix --global
$ sudo npm install -g n

如果不行的话,用echo $PATHcommand -v n看看环境变量是否正确。

BTW,提问的时候如果能带上命令行执行的结果,这样能帮助其他人来帮助你解决问题。

关注 1 回答 1

Leo_SHEN 回答了问题 · 5月11日

BFS/DFS 算法在实际场景中有什么作用

举个实际例子,你有若干个项目相互依赖,编译工具就要判断是否存在循环依赖,没有的话进行偏序排序,以此来按序编译.

关注 6 回答 6

Leo_SHEN 回答了问题 · 5月11日

算法解题思想:分而治之和归纳证明的区别?

递归,分而治之,归纳是三个维度的事情.
递归只是一种重复的方式;
分而治之是一种处理问题的思想,子问题可以完全不相交,也可以有部分相交;
归纳证明,这个是数学概念,基本无争议.

回到你的问题
快排是完全不相交的分而治之,我们往往使用递归的方式来解决子问题.
选择排序的证明是归纳证明,子问题和原问题只差一个元素,我们也可以用递归的方式来解决子问题.

关注 2 回答 1

Leo_SHEN 回答了问题 · 5月11日

解决"2013/9/30"字符串怎么用python转换为统一的"2013-09-30"?

关注 2 回答 1

Leo_SHEN 发布了文章 · 5月11日

C Style『泛型』(下):通用的Stack

内容简介:定义Stack头文件,实现Stack;引出为什么会内存泄漏;修复这个问题。

首先,我们定义头文件。

struct Stack {
    void *elements;
    int eleSize;
    int logicalLength;
    int allocLength;
};

void StackNew(Stack *s, int eleSize);

void StackDispose(Stack *s);

void StackPush(Stack *s, void *eleAddr);

void StackPop(Stack *s, void *eleAddr);

我们需要用void*来保存内容;由于void*不包含其他信息,所以需要eleSize来指定要进出栈的对象的大小;内部两个量,用于记录有多少个元素在栈里面,分配了多少空间来存放这些对象。
接下来定义的几个函数很容易理解,新初始化一个栈,销毁处理栈,进栈、出栈操作,eleAddr有着不同的含义,进栈操作指的是待进栈对象的地址,出栈操作指的是会把待出栈对象拷贝到的地址。
<!-- more -->
下面我们来实现New这个操作,初始化各个变量,为elements分配默认大小的空间。

void StackNew(Stack *s, int eleSize)
{
    assert(s->eleSize > 0);
    s->eleSize = eleSize;
    s->logicalLength = 0;
    s->allocLength = 4;
    s->elements = malloc(s->allocLength * eleSize);
    assert(s->elements);
}

Dispose这个函数很简单,释放elements占用的内存。

void StackDispose(Stack *s)
{
    free(s->elements);
}

Push函数稍微复杂一点,把要进栈的对象拷贝到栈空间里面,同时,要考虑到分配的空间可能已经不够大了,要动态增加。

void StackPush(Stack *s, void *eleAddr)
{
    if (s->logicalLength == s->allocLength)
    {
        StackGrow(s);
    }

    void *target = (char*)s->elements + s->eleSize * s->logicalLength;
    memcpy(target, eleAddr, s->eleSize);
    s->logicalLength++;
}

其中,Grow函数如下:

static void StackGrow(Stack *s)
{
    s->allocLength *= 2;
    s->elements = realloc(s->elements, s->allocLength * s->eleSize);
    assert(s->elements);
}

这里,使用了realloc函数重新分配内存,它的基本实现是如果当前内存后面有足够的空间,直接扩大内存,修改这块内存前的四字节或者八字节的标记块,返回与传入指针相同的地址;如果不够,开辟另一块内存,拷贝内容过去,释放前一块内存,返回新内存地址。

最后是Pop函数,要先判断栈里面是不是有东西,如果有,把最上面的对象拷贝到给定的地址去。

void StackPop(Stack *s, void *eleAddr)
{
    assert(s->logicalLength > 0);
    s->logicalLength--;
    void *source = (char*)s->elements + s->eleSize * s->logicalLength;
    memcpy(eleAddr, source, s->eleSize);
}

目前为止,这个Stack实现像模像样,我们写个简单的函数来测试一下:

    Stack s;
    StackNew(&s, 4);
    
    int x = 12;
    int y = 1;
    int z = 15;

    StackPush(&s, &x);
    StackPush(&s, &z);

    int output;

    StackPop(&s, &output);
    std::cout << output << std::endl;

    StackPush(&s, &y);

    StackPop(&s, &output);
    std::cout << output << std::endl;
    StackPop(&s, &output);
    std::cout << output << std::endl;

    StackDispose(&s);

输出就是15 1 12,符合预期。

但是这有一个严重的问题,比如传入的是char*,指针对应的是在Stack外malloc的内存,绝大多数情况,当时指向的指针早就过了生命周期或者指向了其他地方,那么,栈里面这个指针副本是唯一指向当初被分配的那块内存的指针。如果外部没有把所有指针对象都Pop出来并且释放(外部调用程序往往也没有这个义务做这些事情),那么,内存泄露就此产生了。所以,我们Stack实现要负责这个事情。

我们给Stack增加一个字段,同时修改以下New接口,让外界传入释放内存的函数,然后保存起来。

void (*freeFn)(void*);

void StackNew(Stack *s, int eleSize, void (*freeFn)(void*));

重新实现Dispose函数,如果Stack里面还有对象,且freeFn不是NULL的话,释放内存,以防内存泄漏。

void StackDispose(Stack *s)
{
    if (s->freeFn != NULL)
    {
        for (int i = 0; i < s->logicalLength; ++i)
        {
            s->freeFn((char*)s->elements + i * s->eleSize);
        }
    }

    free(s->elements);
}

原文写于2015年6月,发布在自己的小站

查看原文

赞 0 收藏 0 评论 0

Leo_SHEN 发布了文章 · 5月11日

C Style『泛型』(上):函数swap lsearch

在C语言中,没有提供任何泛型能力,但是,有神奇void*,只要运用恰当,能写出通用的『泛型』函数。在这里,『泛型』打了引号,表示并非真的是C#这种支持泛型语言中的含义,而是表示一种通用的意思。

关于这个主题,打算写上下两篇。上篇有关函数本身,写两个函数swap和lsearch来说明如何利用void*来写出通用的程序。下篇写一个通用的Stack来说明在C语言里面也能写出通用的数据结构。

首先来看第一个例子,swap函数不难写,很多人在刚开始学习C语言时候就写过。
比如想要交换两个int,可以写一个函数,函数声明大致如下:

void swap(int*, int*)

现在你又想交换两个double,交换两个自定义的结构体,怎么办呢?再写两个类似的函数,显然是不合适的。

我们可以写一个通用的函数来做这个事情。
我们传入两个要交换对象的地址。对于int版本的swap函数,编译器知道拿4个字节做交换,double版本的swap函数是8个字节,但是void*不包含类似的信息,所以我们要传入一个int来表示要交换对象的大小。
下面是通用版的swap函数

void swap(void *p1, void *p2, int size)
{
    char buffer[size];
    memcpy(buffer, p1, size);
    memcpy(p1, p2, size);
    memcpy(p2, buffer, size);
}

我们先开辟一个大小和对象大小一致的空间用来缓存数据。
然后就是经典的三步:把对象1放到buffer里面,对象2放到对象1里面,最后把buffer里面的放到对象2里面。
这里需要注意一下,函数第一句需要编译器的支持,幸好,现代编译器基本都支持了。
可以写几行代码简单的测试一下:

int x = 17;
int y = 27;
swap(&x, &y, sizeof(int));
std::cout << x << "\t" << y <<std::endl;

下面来写个线性搜索函数。
搜索,要有关键字,所以我们要传入待比较对象的地址,还要传入一个数组和它的大小,和前面说的一样,void*几乎不包含什么信息,所以要传入待搜索对象的大小,最后,要能比较两个对象,需要传入一个比较函数。对于线性搜索来说,可以不传,因为用memcmp比较就能知道两个对象是否一样,但是对于二分搜索就不行了。虽然只是一个简单的示例,还是要充分的考虑通用性的。

void* lsearch(void *key, void *base, int n, int eleSize, int(*cmp)(void*, void*))
{
    for (int i = 0; i < n; ++i)
    {
        void *eleAddr = (char*)base + i * eleSize;
        if (cmp(key, eleAddr) == 0)
        {
            return eleAddr;
        }
    }

    return NULL;
}

首先遍历数据,每一个对象都要和key进行比较。void*是不能做指针的加减运算的,我们转成char*,然后根据当前遍历的i和对象大小,向后移动若干个字节,获得待比较对象的地址。
然后就是比较啦,调用传入的比较函数比较,如果一致,就返回该地址。最后,遍历完成还没有找到则返回NULL。

这次写一个稍微复杂的代码来测试:找相同的字符串。
我们需要一个比较函数:

int strCmp(void *p1, void *p2)
{
    char *s1 = *(char**)p1;
    char *s2 = *(char**)p2;

    return strcmp(s1, s2);
}

需要注意一下,字符串本来就是char*,对于搜索函数而言,要比较的就是char*,lsearch需要的对象的地址,那么传入的就是char*的地址,也就是说,key的类型是char**,base数组里面是char*。所以我们的比较函数的p1 p2是char**,先强转再解引用。
如果写成char *s1 = (char*)p1;,那么s1的含义就和预期的不一致,把p1当做char*,解析地址,跳转到对应的地方,鬼知道那里是什么,很可能压根你就没权访问,假定能访问,从那里开始一直找到0结束,没人知道s1是个什么鬼字符串。
简单地说,这里需要理解指针,要理解跳一次和跳两次的区别。

char *notes[] = {"Ab", "F#", "B", "Gb", "D"};
char *favoriteNote = "Eb";
char **found = (char**)lsearch(&favoriteNote, notes, 5, sizeof(char*), strCmp);
std::cout << (found == NULL) << std::endl;
favoriteNote = "Gb";
found = (char**)lsearch(&favoriteNote, notes, 5, sizeof(char*), strCmp);
std::cout << *found << std::endl;

从测试代码就更容易理解char**了,倒数第二参数是char*的大小,说明要比较的对象类型是char*。
如前所述,第一个参数是对象的地址,favoriteNote是char*,我们要比较它(char*),所以再取地址传进去。

『泛型』函数就写到这里,回头有时间继续写『泛型』数据结构 - Stack。


原文写于2015年6月,发布在自己的小站

查看原文

赞 0 收藏 0 评论 0

Leo_SHEN 关注了专栏 · 5月9日

SegmentFault 思否观察

SegmentFault 思否对开发者行业的洞见、观察与报道

关注 17899

Leo_SHEN 关注了标签 · 5月9日

程序员

一种近几十年来出现的新物种,是工业革命的产物。英文(Programmer Monkey)是一种非常特殊的、可以从事程序开发、维护的动物。一般分为程序设计猿和程序编码猿,但两者的界限并不非常清楚,都可以进行开发、维护工作,特别是在中国,而且最重要的一点,二者都是一种非常悲剧的存在。

国外的程序员节

国外的程序员节,(英语:Programmer Day,俄语:День программи́ста)是一个俄罗斯官方节日,日期是每年的第 256(0x100) 天,也就是平年的 9 月 13 日和闰年的 9 月 12 日,选择 256 是因为它是 2 的 8 次方,比 365 少的 2 的最大幂。

1024程序员节,中国程序员节

1024是2的十次方,二进制计数的基本计量单位之一。程序员(英文Programmer)是从事程序开发、维护的专业人员。程序员就像是一个个1024,以最低调、踏实、核心的功能模块搭建起这个科技世界。1GB=1024M,而1GB与1级谐音,也有一级棒的意思。

从2012年,SegmentFault 创办开始我们就从网络上引导社区的开发者,发展成中国程序员的节日 :) 计划以后每年10月24日定义为程序员节。以一个节日的形式,向通过Coding 改变世界,也以实际行动在浮躁的世界里,固执地坚持自己对于知识、技术和创新追求的程序员们表示致敬。并于之后的最为临近的周末为程序员们举行了一个盛大的狂欢派对。

2015的10月24日,我们SegmentFault 也在5个城市同时举办黑客马拉松这个特殊的形式,聚集开发者开一个编程大爬梯。

特别推荐:

【SF 黑客马拉松】:http://segmentfault.com/hacka...
【1024程序员闯关秀】小游戏,欢迎来挑战 http://segmentfault.com/game/

  • SF 开发者交流群:206236214
  • 黑客马拉松交流群:280915731
  • 开源硬件交流群:372308136
  • Android 开发者交流群:207895295
  • iOS 开发者交流群:372279630
  • 前端开发者群:174851511

欢迎开发者加入~

交流群信息


程序员相关问题集锦:

  1. 《程序员如何选择自己的第二语言》
  2. 《如何成为一名专业的程序员?》
  3. 《如何用各种编程语言书写hello world》
  4. 《程序员们最常说的谎话是什么?》
  5. 《怎么加入一个开源项目?》
  6. 《是要精于单挑,还是要善于合作?》
  7. 《来秀一下你屎一般的代码...》
  8. 《如何区分 IT 青年的“普通/文艺/二逼”属性?》
  9. 程序员必读书籍有哪些?
  10. 你经常访问的技术社区或者技术博客(IT类)有哪些?
  11. 如何一行代码弄崩你的程序?我先来一发
  12. 编程基础指的是什么?
  13. 后端零起步:学哪一种比较好?
  14. 大家都用什么键盘写代码的?

爱因斯坦

程序猿崛起

关注 108223

认证与成就

  • 获得 2 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 5月9日
个人主页被 102 人浏览