精华内容
参与话题
问答
  • FP算法

    万次阅读 2011-10-17 22:13:51
    Apriori算法和FPTree算法都是数据挖掘中的关联规则挖掘算法,处理的都是最简单的单层单维布尔关联规则。 转自http://blog.csdn.net/sealyao/article/details/6460578 Apriori算法 Apriori算法是一种最有影响的...

    Apriori算法和FPTree算法都是数据挖掘中的关联规则挖掘算法,处理的都是最简单的单层单维布尔关联规则。

    转自http://blog.csdn.net/sealyao/article/details/6460578

    Apriori算法

    Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。是基于这样的事实:算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合。该集合记作L1L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。

    这个算法的思路,简单的说就是如果集合I不是频繁项集,那么所有包含集合I的更大的集合也不可能是频繁项集。

    算法原始数据如下:

    TID

    List of item_ID’s

    T100

    T200

    T300

    T400

    T500

    T600

    T700

    T800

    T900

    I1,I2,I5

    I2,I4

    I2,I3

    I1,I2,I4

    I1,I3

    I2,I3

    I1,I3

    I1,I2,I3,I5

    I1,I2,I3

    算法的基本过程如下图:

    image

    首先扫描所有事务,得到1-项集C1,根据支持度要求滤去不满足条件项集,得到频繁1-项集。

    下面进行递归运算:

    已知频繁k-项集(频繁1-项集已知),根据频繁k-项集中的项,连接得到所有可能的K+1_项,并进行剪枝(如果该k+1_项集的所有k项子集不都能满足支持度条件,那么该k+1_项集被剪掉),得到clip_image002项集,然后滤去该clip_image002[1]项集中不满足支持度条件的项得到频繁k+1-项集。如果得到的clip_image002[2]项集为空,则算法结束。

    连接的方法:假设clip_image004项集中的所有项都是按照相同的顺序排列的,那么如果clip_image004[1][i]和clip_image004[2][j]中的前k-1项都是完全相同的,而第k项不同,则clip_image004[3][i]和clip_image004[4][j]是可连接的。比如clip_image006中的{I1,I2}和{I1,I3}就是可连接的,连接之后得到{I1,I2,I3},但是{I1,I2}和{I2,I3}是不可连接的,否则将导致项集中出现重复项。

    关于剪枝再举例说明一下,如在由clip_image006[1]生成clip_image008的过程中,列举得到的3_项集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5},但是由于{I3,I4}和{I4,I5}没有出现在clip_image006[2]中,所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。

    海量数据下,Apriori算法的时空复杂度都不容忽视。

    空间复杂度:如果clip_image010数量达到clip_image012的量级,那么clip_image014中的候选项将达到clip_image016的量级。

    时间复杂度:每计算一次clip_image018就需要扫描一遍数据库。

    FP-Tree算法

    FPTree算法:在不生成候选项的情况下,完成Apriori算法的功能。

    FPTree算法的基本数据结构,包含一个一棵FP树和一个项头表,每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要注意的是项头表需要按照支持度递减排序,在FPTree中高支持度的节点只能是低支持度节点的祖先节点。

    image

    另外还要交代一下FPTree算法中几个基本的概念:

    FP-Tree:就是上面的那棵树,是把事务数据表中的各个事务数据项按照支持度排序后,把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中,同时在每个结点处记录该结点出现的支持度。

    条件模式基:包含FP-Tree中与后缀模式一起出现的前缀路径的集合。也就是同一个频繁项在PF树中的所有节点的祖先路径的集合。比如I3在FP树中一共出现了3次,其祖先路径分别是{I2,I1:2(频度为2)},{I2:2}和{I1:2}。这3个祖先路径的集合就是频繁项I3的条件模式基。

    条件树:将条件模式基按照FP-Tree的构造原则形成的一个新的FP-Tree。比如上图中I3的条件树就是:

    image

     

    1、 构造项头表:扫描数据库一遍,得到频繁项的集合F和每个频繁项的支持度。把F按支持度递降排序,记为L。

    2、 构造原始FPTree:把数据库中每个事物的频繁项按照L中的顺序进行重排。并按照重排之后的顺序把每个事物的每个频繁项插入以null为根的FPTree中。如果插入时频繁项节点已经存在了,则把该频繁项节点支持度加1;如果该节点不存在,则创建支持度为1的节点,并把该节点链接到项头表中。

    3、 调用FP-growth(Tree,null)开始进行挖掘。伪代码如下:

    procedure FP_growth(Treea)

    if Tree 含单个路径then{

             for 路径P中结点的每个组合(记作b

             产生模式b U a,其支持度support = 中结点的最小支持度;

    } else {

             for each i 在Tree的头部(按照支持度由低到高顺序进行扫描){

                      产生一个模式b = i U a,其支持度support .support

                      构造b的条件模式基,然后构造b的条件FP-树Treeb;

                      if Treeb 不为空 then

                                调用 FP_growth (Treeb, b);

               }

    }

    FP-growth是整个算法的核心,再多啰嗦几句。

    FP-growth函数的输入:tree是指原始的FPTree或者是某个模式的条件FPTree,a是指模式的后缀(在第一次调用时a=NULL,在之后的递归调用中a是模式后缀)

    FP-growth函数的输出:在递归调用过程中输出所有的模式及其支持度(比如{I1,I2,I3}的支持度为2)。每一次调用FP_growth输出结果的模式中一定包含FP_growth函数输入的模式后缀。

    我们来模拟一下FP-growth的执行过程。

    1、 在FP-growth递归调用的第一层,模式前后a=NULL,得到的其实就是频繁1-项集。

    2、 对每一个频繁1-项,进行递归调用FP-growth()获得多元频繁项集。

    下面举两个例子说明FP-growth的执行过程。

    1、I5的条件模式基是(I2 I1:1), (I2 I1 I3:1),I5构造得到的条件FP-树如下。然后递归调用FP-growth,模式后缀为I5。这个条件FP-树是单路径的,在FP_growth中直接列举{I2:2,I1:2,I3:1}的所有组合,之后和模式后缀I5取并集得到支持度>2的所有模式:{ I2 I5:2, I1 I5:2, I2 I1 I5:2}。

    绘图1

    2、I5的情况是比较简单的,因为I5对应的条件FP-树是单路径的,我们再来看一下稍微复杂一点的情况I3。I3的条件模式基是(I2 I1:2), (I2:2), (I1:2),生成的条件FP-树如左下图,然后递归调用FP-growth,模式前缀为I3。I3的条件FP-树仍然是一个多路径树,首先把模式后缀I3和条件FP-树中的项头表中的每一项取并集,得到一组模式{I2 I3:4, I1 I3:4},但是这一组模式不是后缀为I3的所有模式。还需要递归调用FP-growth,模式后缀为{I1,I3},{I1,I3}的条件模式基为{I2:2},其生成的条件FP-树如右下图所示。这是一个单路径的条件FP-树,在FP_growth中把I2和模式后缀{I1,I3}取并得到模式{I1 I2 I3:2}。理论上还应该计算一下模式后缀为{I2,I3}的模式集,但是{I2,I3}的条件模式基为空,递归调用结束。最终模式后缀I3的支持度>2的所有模式为:{ I2 I3:4, I1 I3:4, I1 I2 I3:2}

          image         绘图2




                                             图1                                                                     图2

     

    根据FP-growth算法,最终得到的支持度>2频繁模式如下:

    item

    条件模式基

    条件FP-树

    产生的频繁模式

    I5

    I4

    I3

    I1

    {(I2 I1:1),(I2 I1 I3:1)

    {(I2 I1:1), (I2:1)}

    {(I2 I1:2), (I2:2), (I1:2)}

    {(I2:4)}

    <I2:2, I1:2>

    <I2:2>

    <I2:4, I1:2>, <I1:2>

    <I2:4>

    I2 I5:2, I1 I5:2, I2 I1 I5:2

    I2 I4:2

    I2 I3:4, I1 I3:4, I2 I1 I3:2

    I2 I1:4

    FP-growth算法比Apriori算法快一个数量级,在空间复杂度方面也比Apriori也有数量级级别的优化。但是对于海量数据,FP-growth的时空复杂度仍然很高,可以采用的改进方法包括数据库划分,数据采样等等。

    展开全文
  • 为什么要使用堆栈? sp和fp的解释

    万次阅读 2014-11-19 23:34:16
     为什么要使用堆栈?  一个过程调用可以象跳转(jump)命令那样改变程序的控制流程, 但是与跳转不同的是, 当工作完成时,函数把控制权返回给调用之后的语句或指令。 这种高级抽象实现起来要靠堆栈的帮助。...
    
    为什么要使用堆栈?
        一个过程调用可以象跳转(jump)命令那样改变程序的控制流程, 但是与跳转不同的是, 当工作完成时,函数把控制权返回给调用之后的语句或指令。 这种高级抽象实现起来要靠堆栈的帮助。
        堆栈也用于给函数中使用的局部变量动态分配空间, 同样给函数传递参数和函数返回值也要用到堆栈。

    堆栈区详解
        堆栈是一块保存数据的连续内存。 一个名为堆栈指针(SP)的寄存器指向堆栈的顶部。堆栈的底部在一个固定的地址。 堆栈的大小在运行时由内核动态地调整。

        堆栈由逻辑堆栈帧组成。当调用函数时逻辑堆栈帧被压入栈中, 当函数返回时逻辑堆栈帧被从栈中弹出。 堆栈帧包括函数的参数, 函数地局部变量, 以及恢复前一个堆栈帧所需要的数据, 其中包括在函数调用时指令指针(IP)的值。

        堆栈既可以向下增长(向内存低地址)也可以向上增长, 这依赖于具体的实现。在我们的例子中, 堆栈是向下增长的。堆栈指针(SP)也是依赖于具体实现的。它可以指向堆栈的最后地址,或者指向堆栈之后的下一个空闲可用地址。 在我们的讨论当中, SP指向堆栈的最后地址。

        除了堆栈指针(SP指向堆栈顶部的的低地址)之外, 为了使用方便还有指向帧内固定地址的指针叫做帧指针(FP)。有些文章把它叫做局部基指针(LB-local base pointer)。从理论上来说, 局部变量可以用SP加偏移量来引用。 然而, 当有字被压栈和出栈后, 这些偏移量就变了。 尽管在某些情况下编译器能够跟踪栈中的字操作, 由此可以修正偏移量, 但是在某些情况下不能。而且在所有情况下, 要引入可观的管理开销。 而且在有些机器上, 比如Intel处理器, 由SP加偏移量访问一个变量需要多条指令才能实现。

        因此, 许多编译器使用第二个寄存器, FP, 对于局部变量和函数参数都可以引用, 因为它们到FP的距离不会受到PUSH和POP操作的影响。 在Intel CPU中, BP(EBP)用于这个目的。 在Motorola CPU中, 除了A7(堆栈指针SP)之外的任何地址寄存器都可以做FP。考虑到我们堆栈的增长方向, 从FP的位置开始计算, 函数参数的偏移量是正值, 而局部变量的偏移量是负值。

        当一个例程被调用时所必须做的第一件事是保存前一个FP(这样当例程退出时就可以恢复)。 然后它把SP复制到FP, 创建新的FP, 把SP向前移动为局部变量保留空间。 这称为例程的序幕(prolog)工作。当例程退出时, 堆栈必须被清除干净, 这称为例程的收尾(epilog)工作。 Intel的ENTER和LEAVE指令, Motorola的LINK和UNLINK指令, 都可以用于有效地序幕和收尾工作。
    这里利用了一个简单的例子来做堆栈溢出示例。首先描述了该例子编
    译后的内存分配情况,然后修改这个例子,使它成为一个典型的溢出程
    序。分析溢出时的堆栈情况。

    ------------------------------------------------------------------

    一个简单的堆栈例子
    example1.c:
    ------------------------------------------------------------------
    void function(int a, int b, int c) {
      char buffer1[5];
      char buffer2[10];
    }

    void main() {
      function(1,2,3);
    }
    ------------------------------------------------------------------
        使用gcc的-S选项编译, 以产生汇编代码输出:
          $ gcc -S -o example1.s example1.c

        通过查看汇编语言输出, 我们看到对function()的调用被翻译成:
            pushl $3
            pushl $2
            pushl $1
            call function
     
        以从后往前的顺序将function的三个参数压入栈中, 然后调用function()。 指令call会把指令指针(IP)也压入栈中。 我们把这被保存的IP称为返回地址(RET)。 在函数中所做的第一件事情是例程的序幕工作:
            pushl ëp
            movl %esp,ëp
            subl $20,%esp

        将帧指针EBP压入栈中。 然后把当前的SP复制到EBP, 使其成为新的帧指针。 我们把这个被保存的FP叫做SFP。 接下来将SP的值减小, 为局部变量保留空间。

        内存只能以字为单位寻址。 一个字是4个字节, 32位。 因此5字节的缓冲区会占用8个字节(2个字)的内存空间, 而10个字节的缓冲区会占用12个字节(3个字)的内存空间。 这就是为什么SP要减掉20的原因。 这样我们就可以想象function()被调用时堆栈的模样(每个空格代表一个字节):
    内存低地址                                            内存高地址
              buffer2      buffer1  sfp  ret  a    b    c
    <------  [            ][        ][    ][    ][    ][    ][    ]
    堆栈顶部                                                堆栈底部

    制造缓冲区溢出
        现在试着修改我们第一个例子, 让它可以覆盖返回地址, 而且使它可以执行任意代码。堆栈中在buffer1[]之前的是SFP, SFP之前是返回地址。 ret从buffer1[]的结尾算起是4个字节。应该记住的是buffer1[]实际上是2个字即8个字节长。 因此返回地址从buffer1[]的开头算起是12个字节。 我们会使用这种方法修改返回地址, 跳过函数调用后面的赋值语句'x=1;', 为了做到这一点我们把返回地址加上8个字节。 代码看起来是这样的:
    example3。c:
    --------------------------------------------------------------------
    void function(int a, int b, int c) {
      char buffer1[5];
      char buffer2[10];
      int *ret;

      ret = buffer1 + 12;
      (*ret) += 8;
    }

    void main() {
      int x;

      x = 0;
      function(1,2,3);
      x = 1;
      printf("%d\n",x);
    }
    -------------------------------------------------------------------
        我们把buffer1[]的地址加上12, 所得的新地址是返回地址储存的地方。 我们想跳过赋值语句而直接执行printf调用。

    如何知道应该给返回地址加8个字节呢? 我们先前使用过一个试验值(比如1), 编译该程序, 祭出工具gdb:

    -----------------------------------------------------------------
    [aleph1]$ gdb example3
    GDB is free software and you are welcome to distribute copies of it
    under certain conditions; type "show copying" to see the conditions。
    There is absolutely no warranty for GDB; type "show warranty" for details。
    GDB 4。15 (i586-unknown-linux), Copyright 1995 Free Software Foundation, Inc...
    (no debugging symbols found)...
    (gdb) disassemble main
    Dump of assembler code for function main:
    0x8000490 :      pushl  ëp
    0x8000491 :    movl  %esp,ëp
    0x8000493 :    subl  $0x4,%esp
    0x8000496 :    movl  $0x0,0xfffffffc(ëp)
    0x800049d :    pushl  $0x3
    0x800049f :    pushl  $0x2
    0x80004a1 :    pushl  $0x1
    0x80004a3 :    call  0x8000470
    0x80004a8 :    addl  $0xc,%esp
    0x80004ab :    movl  $0x1,0xfffffffc(ëp)
    0x80004b2 :    movl  0xfffffffc(ëp),êx
    0x80004b5 :    pushl  êx
    0x80004b6 :    pushl  $0x80004f8
    0x80004bb :    call  0x8000378
    0x80004c0 :    addl  $0x8,%esp
    0x80004c3 :    movl  ëp,%esp
    0x80004c5 :    popl  ëp
    0x80004c6 :    ret
    0x80004c7 :    nop
    ------------------------------------------------------------------

        我们看到当调用function()时, RET会是0x8004a8, 我们希望跳过在0x80004ab的赋值指令。 下一个想要执行的指令在0x8004b2。 简单的计算告诉我们两个指令的距离为8字节。
    展开全文
  • FP-growth算法,fpgrowth算法详解

    万次阅读 2016-01-15 08:40:32
    FP-growth算法,fpgrowth算法详解 使用FP-growth算法来高效发现频繁项集 前言 你用过搜索引擎挥发现这样一个功能:输入一个单词或者单词的一部分,搜索引擎酒会自动补全查询词项,用户甚至实现都不知道搜索引擎...

    FP-growth算法,fpgrowth算法详解


    使用FP-growth算法来高效发现频繁项集

    前言

    你用过搜索引擎挥发现这样一个功能:输入一个单词或者单词的一部分,搜索引擎酒会自动补全查询词项,用户甚至实现都不知道搜索引擎推荐的东西是否存在,反而会去查找推荐词项,比如在百度输入“为什么”开始查询时,会出现诸如“为什么我有了变身器却不能变身奥特曼”之类滑稽的推荐结果,为了给出这些推荐查询慈祥,搜索引擎公司的研究人员使用了本文要介绍的一个算法,他们通过查看互联网上的用词来找出经常在一块出现的词对,这需要一种高效发现频繁集的方法。该算法称作FP-growth,又称为FP-增长算法,它比Apriori算法要快,它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。不同于Apriori算法的”产生-测试”,这里的任务是将数据集存储在一个特定的称做FP树的结构之后发现频繁项集或者频繁项对,即常在一块出现的元素项的集合FP树,这种做法是的算法的执行速度要快于apriori,通常性能要好两个数量级以上。

    FP树表示法

    FP树时一种输入数据的压缩表示,它通过逐个读入事务,并把事务映射到FP树中的一条路径来构造,由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好,如果FP树足够小,能够存放在内存中,就可以直接从这个内存中的结构提取频繁项集,而不必重复地扫描存放在硬盘上的数据。

    下图显示了一个数据集,它包含10个事务和5个项。(可以把一条事务都直观理解为超市的顾客购物记录,我们利用算法来发掘那些物品或物品组合频繁的被顾客所购买。)

    图1

    下图绘制了读入三个事务之后的FP树的结构以及最终完成构建的FP树,初始,FP树仅包含一个根节点,用符号null标记,随后,用如下方法扩充FP树:

    图1
    图2
    图3
    图4

    通常,FP树的大小比未压缩的数据小,因为购物篮数据的事务常常共享一些共同项,在最好的情况下,所有的事务都具有相同的项集,FP树只包含一条节点路径,当每个事务都具有唯一项集时,导致最坏情况发生,由于事务不包含任何共同项,FP树的大小实际上与原数据的大小一样,然而,由于需要附加的空间为每个项存放节点间的指针和技术,FP树的存储需求增大。

    FP树还包含一个连接具有相同项的节点的指针列表,这些指针再上图中用虚线表示,有助于快速访问树中的项。

    FP增长算法的频繁项集产生

    FP-growth是一种以自底向上方式探索树,由FP树产生频繁项集的算法,给定上面构建的FP树,算法首先查找以e结尾的频繁项集,接下来是b,c,d,最后是a,由于每一个事务都映射到FP树中的一条路径,因为通过仅考察包含特定节点(例如e)的路径,就可以发现以e结尾的频繁项集,使用与节点e相关联的指针,可以快速访问这些路径,下图显示了所提取的路径,后面详细解释如何处理这些路径,以得到频繁项集。

    图五
    图六
    图七
    图八
    图九

    上面的图演示了讲频繁项集产生的问题分解成多个子问题,其中每个子问题分别涉及发现以e,d,c,b和a结尾的频繁项集

    发现以e结尾的频繁项集之后,算法通过处理与节点d相关联的路径,进一步寻找以d为结尾的频繁项集,继续该过程,直到处理了所有与节点c,b和a相关联的路径为止,上面的图分别显示了这些项的路径,而他们对应的频繁项集汇总在下表中

    图十

    FP增长采用分治策略将一个问题分解为较小的子问题,从而发现以某个特定后缀结尾的所有频繁项集。例如,假设对发现所有以e结尾的频繁项集感兴趣,为了实现这个目的,必须首先检查项集{e}本身是否频繁,如果它是平凡的,则考虑发现以de结尾的频繁项集子问题,接下来是ce和ae,依次,每一个子问题可以进一步划分为更小的子问题,通过合并这些子问题的结果,就可以找到所有以e结尾的频繁项集,这种分治策略是FP增长算法采用的关键策略。

    为了更具体地说明如何解决这些子问题,考虑发现所有以e结尾的频繁项集的任务。

    图十一
    图十二
    图十三
    图十四
    图十五
    图十六

    这个例子解释了FP增长算法中使用的分治方法,每一次递归,都要通过更新前缀路径中的支持度计数和删除非频繁的项来构建条件FP树,由于子问题时不相交的,因此FP增长不会产生任何重复的项集,此外,与节点相关联的支持度计数允许算法在产生相同的后缀项时进行支持度计数。

    FP增长是一个有趣的算法,它展示了如何使用事务数据集的压缩表示来有效的产生频繁项集,此外对于某些事务数据集,FP增长算法比标准的Apriori算法要快几个数量级,FP增长算法的运行性能取决于数据集的“压缩因子”。如果生成的FP树非常茂盛(在最坏的情况下,是一颗完全二叉树)则算法的性能显著下降,因为算法必须产生大量的子问题,并且需要合并每个子问题返回的结果

    展开全文
  • FP寄存器

    2017-07-08 20:05:27
    理论上来说,ARM的15个通用寄存器是通用的,但实际上并非如此,特别是在过程调用的过程中。 PCS(Procedure Call Standard for Arm architecture)就定义了过程调用中,寄存器的特殊用途。 ...
    理论上来说,ARM的15个通用寄存器是通用的,但实际上并非如此,特别是在过程调用的过程中。
    
    PCS(Procedure Call Standard for Arm architecture)就定义了过程调用中,寄存器的特殊用途。

    Role in the procedure call standard
    r15 PC The Program Counter.
    r14 LR The Link Register.
    r13 SP The Stack Pointer.
    r12 IP The Intra-Procedure-call scratch register. (可简单的认为暂存SP)

    实际上,还有一个r11是optional的,被称为FP,即frame pointer。

    1,stack frame
    stack我们都知道,每一个进程都有自己的栈。考虑进程执行时发生函数调用的场景,母函数和子函数使用的是同一个栈,在通常的情况下,我们并不需要区分母函数和子函数分别使用了栈的哪个部分。但是,当我们需要在执行过程中对函数调用进行backtrace的时候,这一信息就很重要了。
    简单的说,stack frame就是一个函数所使用的stack的一部分,所有函数的stack frame串起来就组成了一个完整的栈。stack frame的两个边界分别由FP和SP来限定。

    2,backtrace
    在程序执行过程中(通常是发生了某种意外情况而需要进行调试),通过SP和FP所限定的stack frame,就可以得到母函数的SP和FP,从而得到母函数的stack frame(PC,LR,SP,FP会在函数调用的第一时间压栈),以此追溯,即可得到所有函数的调用顺序。

    3,gcc关于stack frame的优化选项
    看起来FP只是在backtrace的时候有用,所以如果我们没有backstrace的需求,我们是否可以不使用FP。
    其实gcc就有一个关于stack frame的优化选项:
    -fomit-frame-pointer
    =================================================================================
    Don't keep the frame pointer in a register for functions that don't need one. This avoids the instructions to save, set up and restore frame pointers; it also makes an extra register available in many functions. It also makes debugging impossible on some machines.

    On some machines, such as the VAX, this flag has no effect, because the standard calling sequence automatically handles the frame pointer and nothing is saved by pretending it doesn't exist. The machine-description macro "FRAME_POINTER_REQUIRED" controls whether a target machine supports this flag.

    ==================================================================================

    这里引用别人关于这一参数的实验,自己就不做了。

    从实验可以看出,优化后的差别是相当明显的。当然,具体能带来多大的性能提升,不好界定。

    另外,x86中EBP寄存器相当于ARM中的FP寄存器。


    ==================================================================================

    http://blog.csdn.net/byzs/article/details/2220461

    环境:X86+Redhat 9.0,gcc 3.2.2

    源文件如下:

    $ cat test.c 
    void a(unsigned long a, unsigned int b)
    {
            unsigned long i;
            unsigned int j;

            i = a;
            j = b;

            i++;

            j += 2;

    }

    默认编译选项:
    $ gcc -c test.c -o with_SFP.o

    反汇编后是这个样子:
    $ objdump -D with_SFP.o

    with_SFP.o:     file format elf32-i386

    Disassembly of section .text:

    00000000 <a>:
       0:   55                      push   %ebp
       1:   89 e5                   mov    %esp,%ebp
       3:   83 ec 08                sub    $0x8,%esp
       6:   8b 45 08                mov    0x8(%ebp),%eax
       9:   89 45 fc                mov    %eax,0xfffffffc(%ebp)
       c:   8b 45 0c                mov    0xc(%ebp),%eax
       f:   89 45 f8                mov    %eax,0xfffffff8(%ebp)
      12:   8d 45 fc                lea    0xfffffffc(%ebp),%eax
      15:   ff 00                   incl   (%eax)
      17:   8d 45 f8                lea    0xfffffff8(%ebp),%eax
      1a:   83 00 02                addl   $0x2,(%eax)
      1d:   c9                      leave  
      1e:   c3                      ret    
    Disassembly of section .data:

    可以看到函数ENTER时首先把上一层函数的EBP入栈,设置本函数的EBP,然后会根据临时变量的数量和对齐要求去设置ESP,也就产生了函数的stack frame。
    我们再看看函数的返回:"leave"指令相当于"mov %ebp,%esp;pop %ebp",也就是ENTER是两条指令的恢复过程,所以,后面的"ret"指令和"call"指令对应。
    这里backtrace就可以根据现有函数EBP指针得知上一个函数的EBP----栈底再往上保存着上一个函数的EBP和EIP,然后就可以得知函数调用的路径。

    SFP是可以在编译时候优化掉的,用"-fomit-frame-pointer"选项

    编译:
    $ gcc -fomit-frame-pointer -c test.c -o no_SFP.o

    $ objdump -D no_SFP.o

    no_SFP.o:     file format elf32-i386

    Disassembly of section .text:

    00000000 <a>:
       0:   83 ec 08                sub    $0x8,%esp
       3:   8b 44 24 0c             mov    0xc(%esp,1),%eax
       7:   89 44 24 04             mov    %eax,0x4(%esp,1)
       b:   8b 44 24 10             mov    0x10(%esp,1),%eax
       f:   89 04 24                mov    %eax,(%esp,1)
      12:   8d 44 24 04             lea    0x4(%esp,1),%eax
      16:   ff 00                   incl   (%eax)
      18:   89 e0                   mov    %esp,%eax
      1a:   83 00 02                addl   $0x2,(%eax)
      1d:   83 c4 08                add    $0x8,%esp
      20:   c3                      ret    
    Disassembly of section .data:


    这里把EBP省掉了,ESP兼职了EBP的部分工作(索引临时变量)。
    显而易见,代码难懂了;-P, 代码执行长度缩短了,应该能引起效率的提升。 可恶的是,不能用backtrace调试了。

    看一下arm下面的情况:
    含有SFP的版本:
    $ arm-linux-objdump -D SFP_arm.o

    SFP_arm.o :     file format elf32-littlearm

    Disassembly of section .text:

    00000000 <a>:
       0:   e1a0c00d        mov     ip, sp
       4:   e92dd800        stmdb   sp!, {fp, ip, lr, pc}
       8:   e24cb004        sub     fp, ip, #4      ; 0x4
       c:   e24dd010        sub     sp, sp, #16     ; 0x10
      10:   e50b0010        str     r0, [fp, -#16]
      14:   e50b1014        str     r1, [fp, -#20]
      18:   e51b3010        ldr     r3, [fp, -#16]
      1c:   e50b3018        str     r3, [fp, -#24]
      20:   e51b3014        ldr     r3, [fp, -#20]
      24:   e50b301c        str     r3, [fp, -#28]
      28:   e51b3018        ldr     r3, [fp, -#24]
      2c:   e2833001        add     r3, r3, #1      ; 0x1
      30:   e50b3018        str     r3, [fp, -#24]
      34:   e51b301c        ldr     r3, [fp, -#28]
      38:   e2833002        add     r3, r3, #2      ; 0x2
      3c:   e50b301c        str     r3, [fp, -#28]
      40:   e91ba800        ldmdb   fp, {fp, sp, pc}
    Disassembly of section .data:

    优化后的版本:
    $ arm-linux-objdump -D no_SFP_arm.o

    no_SFP_arm.o:     file format elf32-littlearm

    Disassembly of section .text:

    00000000 <a>:
       0:   e24dd010        sub     sp, sp, #16     ; 0x10
       4:   e58d000c        str     r0, [sp, #12]
       8:   e58d1008        str     r1, [sp, #8]
       c:   e59d300c        ldr     r3, [sp, #12]
      10:   e58d3004        str     r3, [sp, #4]
      14:   e59d3008        ldr     r3, [sp, #8]
      18:   e58d3000        str     r3, [sp]
      1c:   e59d3004        ldr     r3, [sp, #4]
      20:   e2833001        add     r3, r3, #1      ; 0x1
      24:   e58d3004        str     r3, [sp, #4]
      28:   e59d3000        ldr     r3, [sp]
      2c:   e2833002        add     r3, r3, #2      ; 0x2
      30:   e58d3000        str     r3, [sp]
      34:   e28dd010        add     sp, sp, #16     ; 0x10
      38:   e1a0f00e        mov     pc, lr
    Disassembly of section .data:

    这里,"fp"充当了"EBP"的角色,ESP在X86里面被leave隐含的恢复好了,所以没有显示设置的必要。
    看起来arm平台上"-fomit-frame-pointer"选项的优化作用更加明显。 


    展开全文
  •     FP增长(FP-growth)算法是一种高效发现频繁项集的方法,只需要对数据库进行两次扫描。它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。该算法虽然能更为高效地发现频繁项集,但不能用于发现...
  • 1. FP Tree数据结构  为了减少I/O次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图所示:  第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数,按...
  • Panasonic FP系列编程手册 本手册收集了FP0、FP0R、FP-e 、FPE、FP-X、FP2、FP2SH及FP10SH中可使用的指令、并对存储区的使用、编程时的注意事项进行说明。
  • TP、TN、FP、FN解释说明

    万次阅读 多人点赞 2016-08-22 13:27:39
      首先这几个术语会高频率得出现在论文的实验部分,它是对实验结果的描述,首先我想先解释这几个缩写的含义: precesion:查准率,即在检索后返回的结果中,真正正确的个数占整个结果的比例。...
  • FP-growth 算法与Python实现

    万次阅读 多人点赞 2018-05-23 11:21:13
    FP-growth 算法 介绍   打开你的搜索引擎,输入一个单词或一部分,例如“我”,搜索引擎可能会去统计和“我”一块出现得多的词,然后返回给你。其实就是去找频繁项集,而且需要相当地高效,像Apriori那样的...
  • FP-growth算法理解和实现

    万次阅读 多人点赞 2018-05-16 17:18:58
    FP-growth算法理解 FP-growth(Frequent Pattern Tree, 频繁模式树),是韩家炜老师提出的挖掘频繁项集的方法,是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或频繁项对,即常在一块出现的元素项的集合FP...
  • 深入剖析FP-Growth原理

    千次阅读 2019-04-21 18:40:52
    同步更新公众号:海涛技术漫谈 频繁项挖掘广泛的应用于寻找关联的事物。最经典的就是,电商企业通过分析用户的...接下来介绍并行FP-Growth算法怎么通过3次map-reduce实现了并行化。最后通过分析spark mlib包中PF...
  • int *fp(); 和 int (*fp)(); 的区别

    千次阅读 2006-03-31 17:58:00
    在 《 the c program language 》 中提到int (*comp)(void , void ) comp 为一个指向 一个函数的指针,该函数有两个void参数,返回类型为 int。int *comp(void, void) comp为一个函数,该函数返回一个 int 类型的 ...
  • Fp4autl.dll,Fpencode.dll,Fp4awel.dll

    千次下载 热门讨论 2010-10-06 00:01:17
    安装office2007提示: windows installer 服务不能更新一个或多个受保护的windows文件问题解决. 下载这三个文件保存到对应的路径,即可正常安装.
  • FPTree 理解

    千次阅读 多人点赞 2018-10-08 10:39:33
    FP Tree算法原理总结  在Apriori算法原理总结中,我们对Apriori算法的原理做了总结。作为一个挖掘频繁项集的...为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两...
  • Python实现FP

    千次阅读 2019-02-20 21:37:32
    FP树是用来挖掘最大频繁k项集的一种数据结构,相对来说难度较大,因为在前辈们的博客中,对于FP树的实现讲的是比较清楚了,但是对于FP的编程思路却提的很少。在这里做一个简单的梳理。 FP树的基础知识 首先请花...
  • FP-Growth算法的介绍

    万次阅读 2015-06-28 10:31:45
    引言:在关联分析中,频繁项集的挖掘最常用到的就是Apriori算法。Apriori算法是一种先产生候...它的思路是把数据集中的事务映射到一棵FP-Tree上面,再根据这棵树找出频繁项集。FP-Tree的构建过程只需要扫描两次数据集。
  • Spark MLlib中FPGrowth和FPTree详解之一

    千次阅读 2016-08-20 00:31:42
    一、准备知识 1.1 Scala版本:2.10.4 1.2 Spark版本:1.5.0 Spark中实现关联规则算法的包是:org.apache.spark.mllib.fpm。包中的文件如下图所示: ...1.3 频繁模式增长FP-Growth 要理解Spark MLlib中FPGro
  • java实现fp-growth算法

    千次阅读 2014-06-17 00:12:52
    FP Growth算法利用了巧妙的数据结构,大大降低了Aproir挖掘算法的代价,他不需要不断得生成候选项目队列和不断得扫描整个数据库进行比对。为了达到这样的效果,它采用了一种简洁的数据结构,叫做frequent-pattern ...
  • 2:Apriori算法和FP-growth算法原理 3:使用Apriori算法发现频繁项集 4:使用FP-growth高效发现频繁项集 5:实例:从新闻站点点击流中挖掘新闻报道 以下程序用到的源代码下载地址:GitHub 一:关联分析 1:相关...
  • FP增长算法(FP Growth Algorithm)

    千次阅读 2017-03-03 10:23:08
    FP增长算法

空空如也

1 2 3 4 5 ... 20
收藏数 209,897
精华内容 83,958
关键字:

fp