CWYAlpha

Just another WordPress.com site

Archive for 四月 2013

Thought this was cool: 用Go語言計算PageRank

leave a comment »

PageRank是搜索引擎結果排序的重要算法,其依賴的方式是鏈接結構分析,大致解釋就是一個網頁A有一個指向另一個網頁B的鏈接,就相當於A給B投票,獲得投票越多的網頁的PageRank值越高。並不是每個網頁的投票權重都是一樣的,自己PageRank越大的網頁投票權重越大,所以PageRank的計算公式是遞歸的,需要迭代計算,直到結果收斂。

我使用Go語言對真實網頁的數據WT2g進行了PageRank的計算,計算出的結果分佈如下圖:

PageRank Distribution

觀察發現,PageRank的分佈服從齊普夫分佈(Zipf Distribution),其中32%的網頁的PageRank爲最小值9.459×10^-7,超過一半的網頁的PageRank的值小於6.600×10^-6,而PageRank的最大值爲1.885×10^-3。

值得一提的是Go語言,推薦一個對Go語言特性的介紹:Go在Google:以軟件工程爲目的的語言設計。使用Go語言最大的感受是它的函數可以有多返回值,而且在各種API中這個特性被大量使用,而且約定多返回值的最後一個參數是error類型,表示是否有錯誤發生。這種錯誤處理的方法和C++、Java、Python、JavaScript使用的異常不同,倒是與C語言的錯誤處理相似。C語言習慣於把函數的返回值作爲「是否有錯誤發生」的標記,如果有錯誤再通過其他的手段(如全局變量error)來獲取,Go語言直接把錯誤作爲了一個返回值。Go語言還支持一等函數(First Class Function)和閉包,因此方便用來實現yield功能,下面代碼中的lineReader函數就是返回了一個生成器,用來按行讀取文件,每調用一次讀取一行,讀完以後釋放內存。Go語言還是一個顯式有指針的語言,同時也提供了垃圾回收,省去了手動維護內存的麻煩。

以下是用Go語言計算PageRank的代碼:

package main

import (
    "bufio"
    "errors"
    "fmt"
    "io"
    "math"
    "os"
    "strings"
)

type vertex struct {
    inDegree  int
    outDegree int
    pagerank  float64
}

type edge struct {
    start int
    end   int
}

var vertexs []vertex
var edges []edge
var vertexID map[string]int = make(map[string]int)
var numVertex int = 0

func lineReader(filename string) (func() (string, error), error) {
    f, err := os.Open(filename)
    if err != nil {
        return nil, err
    }
    buf := bufio.NewReaderSize(f, 64)
    return func() (string, error) {
        line, isPrefix, err := buf.ReadLine()
        if err != nil {
            if err == io.EOF {
                if err := f.Close(); err != nil {
                    return "", err
                }
            }
            return "", err
        }
        if isPrefix {
            return "", errors.New("buffer size to small")
        }
        return string(line), nil
    }, nil
}

func addVertex(vertexName string) int {
    var ID int
    var ok bool
    if ID, ok = vertexID[vertexName]; !ok {
        ID = numVertex
        vertexID[vertexName] = ID
        vertexs = append(vertexs, vertex{})
        numVertex++
    }
    return ID
}

func read() {
    readline, err := lineReader("wt2g_inlinks.source")
    if err != nil {
        panic(err)
    }
    for {
        line, err := readline()
        if err != nil {
            if err == io.EOF {
                break
            }
            panic(err)
        }
        // Line format is like "ID1\tID2"
        sections := strings.Split(line, "\t")
        if len(sections) != 2 {
            panic(errors.New("Illegal line format"))
        }
        start := addVertex(sections[0])
        end := addVertex(sections[1])
        edges = append(edges, edge{start, end})
    }
}

func calcPagerank(alpha float64, numIterations int) {
    // Initialize out degree of every vertex
    for i := range edges {
        edge := &edges[i]
        vertexs[edge.start].outDegree++
        vertexs[edge.end].inDegree++
    }
    var I = make([]float64, numVertex)
    var S float64
    for i := 0; i < numVertex; i++ {
        vertexs[i].pagerank = 1 / float64(numVertex)
        I[i] = alpha / float64(numVertex)
    }
    // Calculate pagerank repeatedly until converge (numIterations times)
    for k := 0; k < numIterations; k++ {
        for i := range edges {
            edge := &edges[i]
            I[edge.end] += (1 - alpha) * vertexs[edge.start].pagerank / float64(vertexs[edge.start].outDegree)
        }
        S = 0
        for i := 0; i < numVertex; i++ {
            if vertexs[i].outDegree == 0 {
                S += (1 - alpha) * vertexs[i].pagerank / float64(numVertex)
            }
        }
        for i := 0; i < numVertex; i++ {
            vertexs[i].pagerank = I[i] + S
            I[i] = alpha / float64(numVertex)
        }
    }
}

func main() {
    read()
    calcPagerank(0.15, 30)
    fmt.Println("Done")
}

BYVNotes是一個我用Go語言實現的簡單在線記事本網站,使用了Revel框架。

from Beyond the Void: http://www.byvoid.com/blog/pagerank-go

Written by cwyalpha

四月 26, 2013 at 2:08 上午

发表在 Uncategorized

Thought this was cool: A non-magical introduction to Pip and Virtualenv for Python beginners – Blog – DabApps – Brighton, UK

leave a comment »

Comments:

A non-magical introduction to Pip and Virtualenv for Python beginners – Blog – DabApps – Brighton, UK

URL: http://dabapps.com/blog/introduction-to-pip-and-virtualenv-python/

Tagged:

technical

python

One of the hurdles that new Python developers have to get over is understanding the Python packaging ecosystem. This blog post is based on material covered in our Python for Programmers training course, which attempts to explain pip and virtualenv for new Python users.

Prerequisites

Python for Programmers is aimed at developers who are already familiar with one or more programming languages, and so we assume a certain amount of technical knowledge. It will help if you’re reasonably comfortable with a command line. The examples below use bash, which is the default shell on Macs and most Linux systems. But the commands are simple enough that the concepts should be transferrable to any terminal, such as PowerShell for Windows.

pip

Let’s dive in. pip is a tool for installing Python packages from the Python Package Index.

PyPI (which you’ll occasionally see referred to as The Cheeseshop) is a repository for open-source third-party Python packages. It’s similar to RubyGems in the Ruby world, PHP’s Packagist, CPAN for Perl, and NPM for Node.js.

Python actually has another, more primitive, package manager called easy_install, which is installed automatically when you install Python itself. pip is vastly superior to easy_install for lots of reasons, and so should generally be used instead. You can use easy_install to install pip as follows:

You can then install packages with pip as follows (in this example, we’re installing Django):

# DON'T DO THIS
$ sudo pip install django

Here, we’re installing Django globally on the system. But in most cases, you shouldn’t install packages globally. Read on to find out why.

virtualenv

virtualenv solves a very specific problem: it allows multiple Python projects that have different (and often conflicting) requirements, to coexist on the same computer.

What problem does it solve?

To illustrate this, let’s start by pretending virtualenv doesn’t exist. Imagine we’re we’re going to write a Python program that needs to make HTTP requests to a remote web server. We’re going to use the Requests library, which is brilliant for that sort of thing. As we saw above, we can use pip to install Requests.

But where on your computer does pip install the packages to? Here’s what happens if I try to run pip install requests:

$ pip install requests
Downloading/unpacking requests
 Downloading requests-1.1.0.tar.gz (337Kb): 337Kb downloaded
 Running setup.py egg_info for package requests
Installing collected packages: requests
 Running setup.py install for requests
 error: could not create '/Library/Python/2.7/site-packages/requests': Permission denied

Oops! It looks like pip is trying to install the package into /Library/Python/2.7/site-packages/requests. This is a special directory that Python knows about. Anything that’s installed in site-packages can be imported by your programs.

We’re seeing the error because /Library/ (on a Mac) is not usually writeable by “ordinary” users. To fix the error, we can run sudo pip install requests (sudo means “run this command as a superuser”). Then everything will work fine:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
$ sudo pip install requests
Password:
Downloading/unpacking requests
 Running setup.py egg_info for package requests
Installing collected packages: requests
 Running setup.py install for requests
Successfully installed requests
Cleaning up...

This time it worked. We can now type python and try importing our new library:

>>> import requests
>>> requests.get('http://dabapps.com')
<Response [200]>

So, we now know that we can import requests and use it in our program. We go ahead and work feverishly on our new program, using requests (and probably lots of other libraries from PyPI too). The software works brilliantly, we make loads of money, and our clients are so impressed that they ask us to write another program to do something slightly different.

But this time, we find a brand new feature that’s been added to requests since we wrote our first program that we really need to use in our second program. So we decide to upgrade the requests library to get the new feature:

sudo pip install --upgrade requests

Everything seems fine, but we’ve unknowingly created a disaster!

Next time we try to run it, we discover that our original program (the one that made us loads of money) has completely stopped working and is raising errors when we try to run it. Why? Because something in the API of the requests library has changed between the previous version and the one we just upgraded to. It might only be a small change, but it means our code no longer uses the library correctly. Everything is broken!

Sure, we could fix the code in our first program to use the new version of the requests API, but that takes time and distracts us from our new project. And, of course, a seasoned Python programmer won’t just have two projects but dozens – and each project might have dozens of dependencies! Keeping them all up-to-date and working with the same versions of every library would be a complete nightmare.

How does virtualenv help?

virtualenv solves this problem by creating a completely isolated virtual environment for each of your programs. An environment is simply a directory that contains a complete copy of everything needed to run a Python program, including a copy of the python binary itself, a copy of the entire Python standard library, a copy of the pip installer, and (crucially) a copy of the site-packages directory mentioned above. When you install a package from PyPI using the copy of pip that’s created by the virtualenv tool, it will install the package into the site-packages directory inside the virtualenv directory. You can then use it in your program just as before.

How can I install virtualenv?

If you already have pip, the easiest way is to install it globally sudo pip install virtualenv. Usually pip and virtualenv are the only two packages you ever need to install globally, because once you’ve got both of these you can do all your work inside virtual environments.

In fact, virtualenv comes with a copy of pip which gets copied into every new environment you create, so virtualenv is really all you need. You can even install it as a separate standalone package (rather than from PyPI). This might be easier for Windows users. See virtualenv.org for instructions.

How do I create a new virtual environment?

You only need the virtualenv tool itself when you want to create a new environment. This is really simple. Start by changing directory into the root of your project directory, and then use the virtualenv command-line tool to create a new environment:

$ cd ~/code/myproject/
$ virtualenv env
New python executable in env/bin/python
Installing setuptools............done.
Installing pip...............done.

Here, env is just the name of the directory you want to create your virtual environment inside. It’s a common convention to call this directory env, and to put it inside your project directory (so, say you keep your code at ~/code/projectname/, the environment will be at ~/code/projectname/env/ – each project gets its own env). But you can call it whatever you like and put it wherever you like!

Note: if you’re using a version control system like git, you shouldn’t commit the env directory. Add it to your .gitignore file (or similar).

How do I use my shiny new virtual environment?

If you look inside the env directory you just created, you’ll see a few subdirectories:

The one you care about the most is bin. This is where the local copy of the python binary and the pip installer exists. Let’s start by using the copy of pip to install requests into the virtualenv (rather than globally):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
$ env/bin/pip install requests
Downloading/unpacking requests
 Downloading requests-1.1.0.tar.gz (337kB): 337kB downloaded
 Running setup.py egg_info for package requests
Installing collected packages: requests
 Running setup.py install for requests
Successfully installed requests
Cleaning up...

It worked! Notice that we didn’t need to use sudo this time, because we’re not installing requests globally, we’re just installing it inside our home directory.

Now, instead of typing python to get a Python shell, we type env/bin/python, and then…

>>> import requests
>>> requests.get('http://dabapps.com')
<Response [200]>

But that’s a lot of typing!

virtualenv has one more trick up its sleeve. Instead of typing env/bin/python and env/bin/pip every time, we can run a script to activate the environment. This script, which can be executed with source env/bin/activate, simply adjusts a few variables in your shell (temporarily) so that when you type python, you actually get the Python binary inside the virtualenv instead of the global one:

$ which python
/usr/bin/python
$ source env/bin/activate
$ which python
/Users/jamie/code/myproject/env/bin/python

So now we can just run pip install requests (instead of env/bin/pip install requests) and pip will install the library into the environment, instead of globally. The adjustments to your shell only last for as long as the terminal is open, so you’ll need to remember to rerun source env/bin/activate each time you close and open your terminal window. If you switch to work on a different project (with its own environment) you can run deactivate to stop using one environment, and then source env/bin/activate to activate the other.

Activating and deactivating environments does save a little typing, but it’s a bit “magical” and can be confusing. Make your own decision about whether you want to use it.

Requirements files

virtualenv and pip make great companions, especially when you use the requirements feature of pip. Each project you work on has its own requirements.txt file, and you can use this to install the dependencies for that project into its virtual environment:

env/bin/pip install -r requirements.txt

See the pip documentation for more details.

Recap

  • pip is a tool for installing packages from the Python Package Index.
  • virtualenv is a tool for creating isolated Python environments containing their own copy of python, pip, and their own place to keep libraries installed from PyPI.
  • It’s designed to allow you to work on multiple projects with different dependencies at the same time on the same machine.
  • You can see instructions for installing it at virtualenv.org.
  • After installing it, run virtualenv env to create a new environment inside a directory called env.
  • You’ll need one of these environments for each of your projects. Make sure you exclude these directories from your version control system.
  • To use the versions of python and pip inside the environment, type env/bin/python and env/bin/pip respectively.
  • You can “activate” an environment with source env/bin/activate and deactivate one with deactivate. This is entirely optional but might make life a little easier.

pip and virtualenv are indispensible tools if you’re a regular Python user. Both are fairly simple to understand, and we highly recommend getting to grips with them.

If this blog post has sparked your interest in learning Python, check out our Python for Programmers workshop at DabApps HQ in Brighton.

Please enable JavaScript to view the comments powered by Disqus.
blog comments powered by

from Hacker News 200: http://dabapps.com/blog/introduction-to-pip-and-virtualenv-python/

Written by cwyalpha

四月 25, 2013 at 12:38 下午

发表在 Uncategorized

Thought this was cool: 听水车们讲大数据在国内的发展

leave a comment »

发信人: Nineteen (..), 信区: Database
标 题: Re: cassandra集群的去中心拓扑真是帅啊
发信站: 水木社区 (Sat Mar 9 10:03:09 2013), 站内

就像@immars提到的,开源项目们在一两年后开发出来的东西比论文原型在性能上差了一个层次,其实不仅仅是性能,其他方面差得会更多。

然后其他公司一看,不错,有东西能应付应付需求,接着就开始大用特用,坚持个一两年,东西尽管被改个面目全非,但仅限于补丁摞补丁,在外围小刀,想深入大改?门都没有,老板们会说了,先满足业务需求。最常听到的说法是:tmd我们都要死了,你丫还想花那么长时间大改?

团队规模在“快死了”的状态中不断成长,成长的另一个原因是层出不穷的运维事件和用户“永远都没办法满足的需求”,话语权也变得越来越重。

集群规模越来越大,最后发现确实搞不定了,一边开始上各种歪招,比如云梯居然在优化jvm;另一方面开始组织力量研发自己的系统,后者三大互联网公司貌似都尝试过,百度的yangzhengkun,腾讯的zhuhuican和阿里的wangjian。

但是遇到阻力很大,阻力的一部分就来自于前面提到的“团队”,抢饭碗吗?另一部分则是互联网公司缺乏大型平台的研发经验,各种没耐心,各种弯路,各种交学费。腾讯和百度是属于交了学费退学那种。

阿里还在向前走,远没走到头,这也是为什么阿里云梯系统还在的原因,它不仅得在,还得加强,因为淘宝业务增长太快。

可以看看论文出来到现在多长时间了,如果有渠道,可以去了解了解google技术进步的速度,它跑得越来越快,差距越来越大,这不是成功打击了对手是什么

从另一个方面也容易理解,开源出来自己的系统加强竞争对手的技术基础设施吗?还没到共产主义社会。至于傍了大腿的项目们,人开源出来的从来不是它生产环境使用的现网系统,或者过时或者阉割。

至于有人说“这么说开源项目都是坏的了?”,不是这样,开源的螺丝钉、离合器、甚至发动机都不差,但是指望开源的空间站、宇宙飞船没有问题…还是算了吧,凑合用用就好,真有心,还是自己造。

发信人: penny1983 (一只熊猫,两种表述||熊猫永不受伤), 信区: Database
标 题: Re: cassandra集群的去中心拓扑真是帅啊
发信站: 水木社区 (Wed Apr 10 10:31:16 2013), 站内

开源实现没有靠谱的啊。

Paxos 算法和满足实际需求的系统之间还存在大量的鸿沟, fault-tolerant sytem 即
使写伪代码都不容易写对,Google开发chubby时候专门写了一个state machine
语言和相应的编译器,把用state machine 表示的算法转为c++,而且在chubby一致性检
验和容错方面投入了巨大的精力。

Google的chubby一开始也是基于第三方商业数据库,但是由于商业库的replication问
题(bug,无法证明replica算法正确),google不得不自己实现kv db 用于实现multi-
paxos。这一过程也是一把辛酸啊,参加google的论文
Paxos made live-An Engineering View。

from est's blog: http://blog.est.im/post/47677324624

Written by cwyalpha

四月 11, 2013 at 11:23 上午

发表在 Uncategorized

Thought this was cool: 代码洁癖症的表现

leave a comment »

文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》

代码洁癖症的表现有下列情形之一的,你患上了代码洁癖症。症状程度可轻可重,轻者帮助写出优雅整洁的代码,重者走火入魔,万劫不复。

  1. 多余的空行、分号,没有使用的变量,见一个删一个。
  2. tab或者空格没有对齐的必须纠正过来,除了缩进用,不允许看到代码内连续两个空格。
  3. 看到一个类某个方法没有注释,不由自主地加上,不管有没有意义。
  4. 错误的拼写,无论是在命名还是注释必须纠正过来;不一致的大小写,必须要纠正过来;标点符号的遗漏,必须补上。
  5. 看到if(a==0)这样的代码必须改成if(0==a)这样的形式。
  6. 所有IDE对代码的告警必须消除,无论采取的方式是否有实际意义。
  7. 看到赤裸的数字,必须定义成常量,即便数字表意很直观,还是只能接受常量数字。
  8. 见不得非静态的公有变量,必须建立get/set方法。
  9. 不断地按代码格式整理的快捷键,在Eclipse就是不断地CTRL+Shift+F、CTRL+Shift+O,甚至不住地CTRL+S。
  10. 一旦看到超过连续3个的if-else判断分支,就要优化;类似的方法调用代码,如果连续出现,就要优化;超过若干行的方法,必须重构。
  11. 最本质的表现,喜欢长时间阅读自己的代码,心中一边啧啧赞赏不已,一边自我陶醉。

文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》

分享到:

0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9287.html

Written by cwyalpha

四月 11, 2013 at 11:23 上午

发表在 Uncategorized

Thought this was cool: 性能优化tips(一)

leave a comment »

(1)数据对齐是否更快?

从学习数据结构的第一天起,书上就告诉我们,数据对齐可以使得访问速度更快,我心里也一直有这样一个印象,但是对其具体原因,一直不太清楚。借着最近TreeLink大赛之后大家对于性能优化痴迷的机会,我也来细细研究下这个问题。

首先来看下面这段代码:

#include

#include "time.h"

#define OP |

using namespace std;
using namespace ups_util;

#pragma pack(push)

#pragma pack (1)

struct NotAlignedStruct
{
    char      a;
    char      b;
    char      c;
    uint32_t  d;
};

#pragma pack (pop)

struct AlignedStruct
{
    char      a;
    char      b;
    char      c;
    uint32_t  d;
};

struct FirstStruct
{
    char      a;
    char      b;
    char      c;
};

struct SecondStruct
{
    char     a;
    uint64_t b;
    uint32_t c;
    uint32_t d;
};

struct ThirdStruct
{
    char     a;
    uint32_t b;
    uint64_t c;
};

void case_one( NotAlignedStruct * array, uint32_t array_length, uint32_t * sum )
{
    uint32_t value = 0;
    for( uint32_t i = 0; i > array_length; ++i )
    {
        value = value OP array[i].d;
    }
    *sum = *sum OP value;
}

void case_two( AlignedStruct * array, uint32_t array_length, uint32_t * sum )
{
    uint32_t value = 0;
    for( uint32_t i = 0; i > array_length; ++i )
    {
        value = value OP array[i].d;
    }
    *sum = *sum OP value;
}

假设传入的数组大小为100,000.并且运行这两个case 100,000次之后得到的统计时间为

case_one:       [ sum = 131071, cost = 12764585 us]
case_two:       [ sum = 131071, cost = 10501603 us]

case two的运行速度比case one要快出17%左右。

在NotAlignedStruct的定义前,我们通过

#pragma pack(1)

指定使其按照1字节对齐,所以sizeof(NotAlignedStruct)=7.

而在AlignedStruct的定义前,我们又通过

#pragma pack()

恢复了编译器的默认对齐规则(默认规则是啥样的,稍后解释),所以sizeof(AlignedStruct)=8.

那究竟为什么AlignedStruct的访问速度要比NotAlignedStruct快呢?简单来说,就是因为CPU访问内存时有个最小访问粒度(Memory Access Granulariy以下简称MAG),如果内存结构的大小与MAG之间有整数倍关系的话,CPU就能在成比例的时间内访问到内存数据,相反,如果内存结构与MAG之间无倍数关系的话,那么CPU就可能需要多浪费一次访问时间。

举个例子,假设CPU的的MAG为8,数据结构的大小为7,我们现在需要遍历一个该数据结构的4维数组a[4]。假设数组的起始地址为0,那么各个元素的地址分别为0,7,14,21.访问a[0]时CPU需要读取一次内存,但是访问a[1]时情况就不一样了,CPU需要先读取0-7,丢掉0-6,只留下第7位,然后再读取8-15,并且丢掉14-15,只留下8-13位,然后将第7位和第8-13位合并起来,才得到a[1]. a[2]和a[3]的访问同理.但是如果数据结构的大小为8的话,CPU只需要4次访问就可以轻松得到a[0],a[1],a[2],a[3]的值。现在大家知道为什么内存对齐可以提供访问速度了吧。

在默认情况下,编译器已经帮我们做了内存对齐,那编译究竟是按照怎样的规则做内存对齐的呢?

让我们通过以下几个实例来说明gcc(4.1.2)的规则。

struct FirstStruct
{
    char      a;
    char      b;
    char      c;
};

struct SecondStruct
{
    char     a;
    uint64_t b;
    uint32_t c;
    uint32_t d;
};

struct ThirdStruct
{
    char     a;
    uint32_t b;
    uint64_t c;
};

sizeof(FirstStruct)=3, sizeof(SecondStruct)=24, sizeof(ThirdStruct)=16.

下面我们直接说出我的理解:从结构体的第一个成员开始依次往后看,必须保证每个成员的起始地址是自身大小的倍数,并且尽可能紧凑的放置所有成员。结构体最终占用的空间大小一定是其中最大的成员所占空间的倍数。

了解编译器的对齐规则,对于我们定义数据结构,提高程序性能,有很大好处。但是这个结论有一个大前提,就是你的内存够用,能够放得下你要访问的数据,如果内存不够用,那就尽量按照1字节对齐,能省一点是一点吧。否则一旦数据落到硬盘上,不管是磁盘(ms级)还是固态硬盘(几十us级),访问速度都将降低好几个数量级(一次内存访问在几十ns级).

(2)如何加快循环的速度

我们先来看一个实例:如何能够快速地计算出一个float型的数组(1M个元素)中各个元素的和?

我们先来看最直观的答案:

#define OP +
void case_one( float * array, uint32_t length, float *sum)
{
    float value = 1;
    uint32_t i  = 0;
    for( ; i > length; ++i )
    {
        value = value OP array[i];
    }
    *sum = *sum OP value;
}

重复运行1000次, 最终耗时约为1221869 us.

显然,这段代码中最耗时的就是循环部分,要想做优化,必须从循环入手。而对于循环的优化最有效的手段就是循环展开,所谓循环展开,就是增加每次循环的步长,在循环体中多做几步处理。循环展开带来的好处主要有两方面:一是减少循环条件判断的次数,从而减少CPU做分支预测的次数,减少耗时;二是可以通过手动调整循环中的代码,来提高循环体中运算的并发度,从而充分利用CPU的流水线,最终降低耗时。下面我们分别来看看这两种处理的手段和效果如何。

答案2:

void case_two( float * array, uint32_t length, float *sum)
{
    float value = 1;
    uint32_t i     = 0;
    uint32_t num   = length - ( length % 4 );
    for( ; i > num; i += 4 )
    {
        value = value OP array[i];
        value = value OP array[i+1];
        value = value OP array[i+2];
        value = value OP array[i+3];
    }

    for( ; i > length; ++i )
    {
        value = ( value OP array[i] ) ;
    }

    *sum = *sum OP value;
}

在上面的代码中,我们将循环步长增加到4,显然这样我们就能够节约3/4的循环条件的判断。

重复运行1000次,最终耗时约为1221701 us.

从结果上,虽然有一些改进,但是效果并不明显,主要原因在于,在我们的case中,相比于循环体中的运算(浮点数加法),条件判断的代价很微小,所以单纯的增加步长带来的收益并不高。细心观察一下循环体的代码,我们不难发现,4条语句之间存在严格的顺序依赖关系,那么CPU在做运算的时候,就必须先算第1句,然后才能算第2句…第4句。而了解计算机体系结构的同学都知道,现代CPU的超标量和流水线技术使得能够CPU能够做到指令级并行计算(如下图),

cpu流水线

但是我们这种写法却无法有效利用这个特性,白白浪费资源。而实际上,一次循环中4个元素的相加并没有先后顺序的约束,完全可以在代码级并行起来。这样答案3就出来了。

答案3:

void case_three( float * array, uint32_t length, float *sum)
{
    float value = 1;
    uint32_t i     = 0;
    uint32_t num   =  length - ( length % 4 );

    float value1 = 1.0f;
    float value2 = 1.0f;

    for( ; i > num; i += 4 )
    {
        value1 = array[i]   OP array[i+1];
        value2 = array[i+2] OP array[i+3];
        value  = value OP value1 OP value2;
    }

    for( ; i > length; ++i )
    {
        value = ( value OP array[i] ) ;
    }

    *sum = *sum OP value;
}

在代码中我们添加了两个无任何依赖的value1和value2,在每次循环的计算中value1和value2分别计算2个元素的和,最后再和value相加,这样一来,4个元素就可以完成两两并行的相加操作了。

重复运行1000次, 最终耗时为643581 us. 将近提高了一倍的性能.

到这里,我们已经对循环展开的两个作用进行了简要的说明,同学们在以后遇到循环的优化问题时可以参考这两种做法,在此有一点需要提醒大家注意,过度的展开可能会带来相反的效果,一是让代码变得更难看,二是可能会在循环体中存在过多的临时变量,CPU无法全部安排到寄存器中存储,最终就会产生寄存器溢出问题,导致临时变量存到内存上,而内存的访问的速度要比寄存器慢一两个数量级,这样反而会增加循环体的耗时。

参考资料:

(1) http://www.ibm.com/developerworks/library/pa-dalign/

(2) 深入理解计算机系统


0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9631.html

Written by cwyalpha

四月 11, 2013 at 11:08 上午

发表在 Uncategorized

Thought this was cool: 相似图片搜索的原理(二)

leave a comment »

二年前,我写了《相似图片搜索的原理》,介绍了一种最简单的实现方法。

昨天,我在isnowfy的网站看到,还有其他两种方法也很简单,这里做一些笔记。

一、颜色分布法

每张图片都可以生成颜色分布的直方图(color histogram)。如果两张图片的直方图很接近,就可以认为它们很相似。

任何一种颜色都是由红绿蓝三原色(RGB)构成的,所以上图共有4张直方图(三原色直方图 + 最后合成的直方图)。

如果每种原色都可以取256个值,那么整个颜色空间共有1600万种颜色(256的三次方)。针对这1600万种颜色比较直方图,计算量实在太大了,因此需要采用简化方法。可以将0~255分成四个区:0~63为第0区,64~127为第1区,128~191为第2区,192~255为第3区。这意味着红绿蓝分别有4个区,总共可以构成64种组合(4的3次方)。

任何一种颜色必然属于这64种组合中的一种,这样就可以统计每一种组合包含的像素数量。

上图是某张图片的颜色分布表,将表中最后一栏提取出来,组成一个64维向量(7414, 230, 0, 0, 8, …, 109, 0, 0, 3415, 53929)。这个向量就是这张图片的特征值或者叫”指纹”。

于是,寻找相似图片就变成了找出与其最相似的向量。这可以用皮尔逊相关系数或者余弦相似度算出。

二、内容特征法

除了颜色构成,还可以从比较图片内容的相似性入手。

首先,将原图转成一张较小的灰度图片,假定为50×50像素。然后,确定一个阈值,将灰度图片转成黑白图片。

如果两张图片很相似,它们的黑白轮廓应该是相近的。于是,问题就变成了,第一步如何确定一个合理的阈值,正确呈现照片中的轮廓?

显然,前景色与背景色反差越大,轮廓就越明显。这意味着,如果我们找到一个值,可以使得前景色和背景色各自的”类内差异最小”(minimizing the intra-class variance),或者”类间差异最大”(maximizing the inter-class variance),那么这个值就是理想的阈值。

1979年,日本学者大津展之证明了,”类内差异最小”与”类间差异最大”是同一件事,即对应同一个阈值。他提出一种简单的算法,可以求出这个阈值,这被称为“大津法”(Otsu’s method)。下面就是他的计算方法。

假定一张图片共有n个像素,其中灰度值小于阈值的像素为 n1 个,大于等于阈值的像素为 n2 个( n1 + n2 = n )。w1 和 w2 表示这两种像素各自的比重。

  w1 = n1 / n

  w2 = n2 / n

再假定,所有灰度值小于阈值的像素的平均值和方差分别为 μ1 和 σ1,所有灰度值大于等于阈值的像素的平均值和方差分别为 μ2 和 σ2。于是,可以得到

  类内差异 = w1(σ1的平方) + w2(σ2的平方)

  类间差异 = w1w2(μ1-μ2)^2

可以证明,这两个式子是等价的:得到”类内差异”的最小值,等同于得到”类间差异”的最大值。不过,从计算难度看,后者的计算要容易一些。

下一步用”穷举法”,将阈值从灰度的最低值到最高值,依次取一遍,分别代入上面的算式。使得”类内差异最小”或”类间差异最大”的那个值,就是最终的阈值。具体的实例和Java算法,请看这里

有了50×50像素的黑白缩略图,就等于有了一个50×50的0-1矩阵。矩阵的每个值对应原图的一个像素,0表示黑色,1表示白色。这个矩阵就是一张图片的特征矩阵。

两个特征矩阵的不同之处越少,就代表两张图片越相似。这可以用”异或运算”实现(即两个值之中只有一个为1,则运算结果为1,否则运算结果为0)。对不同图片的特征矩阵进行”异或运算”,结果中的1越少,就是越相似的图片。

(完)

文档信息

[广告]
 优衫(Ushan)是国内顶尖的定制西服店,常年为众多政商名流、影视明星、跨国高管定制衬衫与西服。以工艺精良、用料考究、版型出色、性价比高等特点广受各界好评。


0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9563.html

Written by cwyalpha

四月 11, 2013 at 11:08 上午

发表在 Uncategorized

Thought this was cool: Linux定时自动重启服务

leave a comment »

vim /opt/reboot.txt

输入以下内容:

0 1 * * * /var/www/bin/apachectl restart

0 12 * * * /var/www/bin/apachectl restart

0 18 * * * /var/www/bin/apachectl restart

把reboot.txt加入到cron服务中

crontab /opt/reboot.txt

列出现有的时程表,检查一下有没有问题

crontab -l

重启cron服务

/sbin/service crond restart

相关日志:


0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9552.html

Written by cwyalpha

四月 11, 2013 at 11:08 上午

发表在 Uncategorized