Ruby

以Ruby为例浅谈动态语言的赋值机制

Posted on
  1. 问题提出
  2. 结论
  3. 数组解释
  4. 数字解释 1
  5. 数字解释 2
  6. 对该特性的思考
  7. Ruby与Python的内存管理机制
1.问题提出

最近的数值计算实验纠结了一下最后想用Ruby解决,结果在中途发现了这样的一个问题。

定义一个二维数组ary,我先是给 ary[0][0]赋值为 1,再是给 ary[1][0]赋值为 233,结果输出 ary[0][0] 居然为 233,输出整个ary ,发现每个数组第一项都是 233 。

详细介绍的可以看我在Ruby China发的帖子

2.结论

在这里我以Ruby为例详细介绍一下动态语言的赋值机制。

首先我们先明确几点:
1. 在ruby中参数的传递永远都是引用。
2. 每一个变量保存的都是对对象的引用。
3. 我们访问对象都是通过引用间接访问的。

3.数组解释

这该如何理解呢?以我上面那个Array.new(6,Array.new(6,0))来说,ruby先执行里表达式,创建一个Array对象并返回其引用 设为α;然后执行,外Array.new,创建6个对 α 的引用,就是对引用的引用,但最后还是引用自对象。因此ary的6个对象都为引用,如果我改变这个对象的值,那么ary的6个引用都将随之改变。

那么如果我要定义一个数组,并初始化其中几个值又应该怎么做呢。

当然是去从本质上解决问题啊。答案应该是将后一个Array.new通过块传入:

Arrar.new(6) { Array.new(6,0) }

假设你拥有block的知识,在 6 次Array.new 的每个块中,都会执行一次 Array.new(6,0)并返回这个Array.new的引用,就会得到6个不相同的对象。简单说,通过block传参,block中的代码每次都会被重新执行一遍。而直接传参就只会将参数的引用传递过来。

4.数字解释 1

解决了数组问题,再来解释一下最平常不过的数字。先贴上我的理解来源,并向大佬表示感谢。

def pref3(a)
  a = 5
  a.object_id
end

a = 1
a.object_id #输出3

pref3(a) #输出11
puts a 

这段代码很容易陷入怀疑 在ruby中参数的传递永远都是引用 正确性的误区:
“如果我传递的是引用,那么我在函数内部发生的变化理应对外部也产生影响呀,为什么输出仍然是1呢??”

在这里,经过 pref3 的调用, a仍然会是 3 ,然而在函数内和函数外的 object_id 却是不同的。这很显然,我们会很自然地去认为,这两个 a 所引用的并不是同一个对象,而实际上也是如此。

现在让我们来重新理解一下Ruby的赋值机制。它大致分为两个步骤:
1. 根据右值创建对象并返回该对象的引用。
2. 不论左值是否为空,左值所引用的对象又是什么类型,右值的引用都会将其覆盖。

也就是说在函数体 pref3 中的 a 初始是 ==对象 1== 的引用,而在执行 a = 5 时,ruby会先创建一个==对象 5== , 并使其引用覆盖掉 a 的原引用对象 ==对象 1==。
至此,一切都理论都得以成立。

5.数字解释 2

再试着来理解一下这段代码

def pref3(a,b)
  a,b = b,a
end

a,b = 1,2
pref3(a,b)
puts a,b #输出 1,2

根据上述,每一个变量保存的都是对 对象的引用,那么在 pref3 中,a,b,其实是对函数外 a,b的引用,即==对象 1和对象 2==引用的引用,通过递归仍然是对==对象 1和对象 2==的引用。
而在此我交换 a,b 实质上是把,b的对象引用覆盖给了a,a的对象引用覆盖给了b,而函数中的两个变量 a,b ,因为其本身是局部变量,且为引用,引用之间的交换并不会对函数外的对象引用产生任何影响,更不会对所引用对象产生任何影响。

于是乎,结果仍然是

1,2

6. 对该特性的思考

总的来说,这个赋值机制还是比较方便的,比较纯粹的。我本人就比较喜欢纯粹的事物,Linux下一切皆文件,Ruby下一切皆对象,动态语言下一切变量皆引用,一切问题皆网络流!!

但是,在我突然意识到,如果我的理论一切都完美成立的话,就会发生内存上的问题。因为我们在创建对象的时候返回的是其引用,我们根本无法直接访问到它,更别谈什么主动释放了。

为什么我想主动释放呢,也许我们对一些特殊的变量一申请,一创建,就会从头用到尾,但是Ruby下一切皆对象,对于数字和字符串这些频繁使用的对象来说,不释放空间非常容易产生内存问题。

然而睡了个觉,回头一想,突然想起了Programming Ruby中关于内存释放有一个自己的机制:
ruby在每次创建变量,传递参数的时候都会对被引用次数进行计数,如果这个被引用次数变为0了,就会自动被释放。这个机制实在是妙哉!!

一想到这,我想我跟松本弘行应该是想到一块去了。蛤蛤蛤!


updated time : May 16

6. Ruby与Python的内存管理机制

自己YY就以为这个问题解决了,没想到被大佬指出了错误,真的是醍醐灌顶。

引用计数这种内存管理机制是地的确确存在的,并且是python所使用的,但Ruby用的是另外一种管理机制 mark and sweep。
首先献给处大佬给我学习的 博文 ,并对大佬和作者表示感谢,然而这篇文章,主要针对的还是小白,如果用来复习就有点得不偿失了。所以我这里简单说一下个人理解,如果与原博文有任何冲突,一切以原博文为主。

Ruby:
预先创建一个空闲链表,一旦有 new 申请就直接从里面拿取空间,如果链表空间不够,则停止其他所有程序活动,不断迭代所有对象的引用,对 所得到的链表内部对象 进行标记,最后遍历链表,清理未标记内存,将其重新构建成一个新的空闲链表。
更深的,基于弱代假说:

年亲的对象通常死得快,而老对象则很有可能存活更长的时间。

对一次 sweep 后被标记的对象,就会被Ruby划分为成熟对象,并在之后很长一段时间内,打赌他们不会再被取消标记。也就是说这些对象 ruby 在很长一段时间内将不会去遍历判断。
而当成熟对象的数目双倍于上次全局回收的数目时,Ruby会清理所有的标记并将所有的对象都视为新对象以重新清理。

Python:
python采取引用标记机制,因为互相引用的情况存在,python不得不用上了类似与ruby的方法,建立一个引用链表称为0代链表,如果内存空间达到阈值就对链表内部进行 对循环引用的检测。其中,存留下来的转移至 1代链表 ,同理会转移至 2代链表(最多2代)。虽然都是转移,但是阈值显然是不同的,对于 0 代链表的操作显然要活跃一些,所以阈值应该是要低一些(猜测,原文中并没有说……)。然而对 2代链表之后的事情我就不清楚了……

然而说到底,这些都是博主说的,是否正确我也无法证实,但是看上去貌似灰常有道理。如果要深入研究,到头来还是得看源码……

二叉查找树

关于传参的两种方式 传值与传址 的深入理解 (附 hdu3999

Posted on

真的真的真的真的好久没码了………………

最近因为要复习数据结构所以才兴起想要码一些跟考试相关的

于是找了一下 BST 和 AVL 的题做做 结果一下搜就找到了 hdu3999

解法很简单 只要建立一个 BST 再对其先序遍历即可
然而…………

问题出在这个代码上

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(root,tmp);
            if(root==NULL)
                cout<<1111<<endl;
        }
        FirstOrderSearch(root);
        puts("");
    }
    return 0;
}

插入函数如下

void InsertNode(node* now,int value)
{
    if(now==NULL)
    {
        now = new node;
        now -> value = value;
        return ;
    }
    else if(value < now -> value)
        InsertNode(now->left,value);
    else if(value > now -> value)
        InsertNode(now -> right, value);
}

咋看下真的没什么问题 然而实际上还是会输出n个 1111
这就说明 root 它一直都没有变化

“纳尼不是只要传地址 , 那么这个变量就一定会随之改变的不是么。。。”

想了一下才想通 传参在本质上来说完全只有一种方法 就是传值

传址传址 也只是把指针这个变量的值 给传了过去 而如果我们对这个地址取值那么自然而然的就可以改变这个变量的值

以这里的代码为例 我在主函数中的 root变量初始化为 NULL 传给 InsertNode 变量now拥有了 NULL 但是在这里now的所有变化将根本不会影响到main中的root

换言之 对于指针的传参 只有 *指针(指针所指的值)才会能在全局变化

所以如果要继续我以上的写法 解法有二:

  1. 只要将这个root 这个指针的地址传给函数处理即可
  2. 当然 我也可以在最开始的时候就先把根节点给定义了 再对根节点传参也可

综上

传参在本质上只有将实参的值传给形参 而所谓的传址 我们只能理解成一个小技巧 否则会带来很多习惯性误导

AC Code

法 1 :(因为第一次这么写 运算符的等级忘了 所以保险点就都加了括号…………)

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
int n;

struct node
{
    int value;
    node *left;
    node *right;
    node():left(NULL),right(NULL) {}
};

void InsertNode(node** now,int value)
{
    if(*now==NULL)
    {
        *now=new node;
        (*now)->value=value;
        return ;
    }
    if(value < (*now) -> value)
        InsertNode(&((*now)->left),value);
    else if(value > (*now) -> value)
        InsertNode(&((*now) -> right), value);
}

void FirstOrderSearch(node* now,node* root)
{
    if(now==root)
        printf("%d",now->value);
    else printf(" %d",now->value);
    if(now->left)
        FirstOrderSearch(now->left,root);
    if(now->right)
        FirstOrderSearch(now->right,root);
    delete now;
}

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        node* root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(&root,tmp);
        }
        FirstOrderSearch(root,root);
        puts("");
    }
    return 0;
}
C

setjmp 与 longjmp

Posted on

最近看到C看到一个很让人费解的函数组合 setjmp 和 longjmp 使用方法还是比较简单的
setjmp设置跳跃点 longjmp表示跳跃

具体的操作如下
首先定义一个 唯一的标志性 flag jmp_buf变量
再加上 函数申明 int setjmp(jmp_buf env); void longjmp(jmp_buf env, int value);
当设置 jmp 即第一次执行 setjmp时 函数的返回值都为 0
通过longjmp 跳跃至相同jmp_buf 的setjmp函数里并执行 set_jmp的返回值将变成 long_jmp设置的 value
理解起来后发现实际上是跟 goto 差不多的 但long_jmp 跳得更远一些 goto只限于同一函数内 long_jmp无限制 包括文件

附个代码理解一下

#include <stdio.h>
#include <setjmp.h>
jmp_buf buf;
void haha()
{
    printf("in haha()\n");
    longjmp(buf,1);
    printf("kaonima\n");
}
int tim=0;

int main()
{
    if(setjmp(buf))
    {
        printf("back in main\n");
        tim++;
    }
    else
    {
        printf("first time through\n");
        haha();
    }
    if(tim<3) longjmp(buf,1);
    return 0;
}

结果是

first time through
in haha()
back in main
back in main
back in main

另外 这两个函数一般来说 可用于C中的异常处理

顺便贴个wiki的 告诫 (太专业 也不是很明白……)

longjmp实现了非本地跳转,微软的IA32程序设计环境中正常的"栈卷回"("stack unwinding")因而没有发生,所以诸如栈中已定义的局部变量的析构函数的调用(用于销毁该局部变量)都没有执行。所有依赖于栈卷回调用析构函数所做的扫尾工作,如关闭文件、释放堆内存块等都没有做。但在微软的X64程序设计环境,longjmp启动了正常的"栈卷回"。
如果setjmp所在的函数已经调用返回了,那么longjmp使用该处setjmp所填写的对应jmp_buf缓冲区将不再有效。这是因为longjmp所要返回的"栈帧"(stack frame)已经不再存在了,程序返回到一个不再存在的执行点,很可能覆盖或者弄坏程序栈

值得深究一下的是 jmp_buf 变量在这里立个flag 吧 以后会来补充

C

关于open操作的O_EXCL的存在应用价值理解

Posted on

在我最近学习Linux C的过程中 总是看到这样的打开方式 open(const* pathname,O_CREAT|O_EXCL);

O_CREAT 简单 就是想打开的文件如果不存在的话就会自动创建文件

而 O_EXCL 他的作用就是如果要创建一个文件 并且这个文件已经存在的话 会直接返回 并且 如果打开的文件是符号链接文件的话 也会直接返回

一开始真的感觉莫名其妙

之后搜了一下才知道自己的菜逼思维

如果不加O_EXCL 的话 如果文件存在 那么这个文件依旧会被打开

此时我们假设有这样的一个需求:某个任务只能单个进程处理执行 多进程会影响到该任务的执行

为了不让多进程打开处理这个文件 并且不用O_EXCL的话

可能会这样写

if( access(file, R_OK) == -1 ) /* 首先检查文件是否存在 /
open(file, O_RDWR | O_CREAT,0666); /
如果不存在,那我创建一个这样的文件 /
... /
继续执行任务 */

其实这个逻辑存在一个潜在性错误的

如果当我的进程1执行了access并判断这个文件并不存在 由于操作系统关于多进程的调度策略 若此时进程1暂停 进程2执行 那么进程2也会判定这个文件不存在

结果自然是有两个进程会打开这个文件 这与我们的目标相违背

而相对的 如果我们用了 O_EXCL 我们就把判断和创建放在了一起 就能避免这个错误的发生

小白的粗浅理解,欢迎指正

另外说个题外的内容 傻逼了 看这些源代码的时候一直看到 errno 的判断 然后就傻兮兮的去记所有的错误代码 记到恶心

然后有个煞笔告诉我直接 对 errno.h grep 不就好了

恍然大悟 我真是个智障