Posts Tagged ‘Code杂谈’

Combination Sum 思路

June 1st, 2015

最新刷leetcode的题目,发现了Combination Sum题目,这个题目分为I、II、III。难度层层递进,题目就是遍历vector容器,选择出符合target number的sum组合,这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板,首先要构造dfs函数。

一般情况下,我们需要五个参数:结果,原始数据集,中间结果,当前指向的数据,满足target number的值:

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集,深搜这个数据集的各种可能性,将达成target的path中间结果加入result,按照通用模版

void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

第一步:收敛也就是target==0
第二步:使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步:如果通过第二部,也就意味着这个current合格,可以将这个加入到path中,然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的,可以多次使用。如果只使用一次的话,也就意味着我们需要sort(),然后需要将上个满足条件的值跳过,也就是II中的nums[i]==nums[i-1]比较Combination Sum II

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

 

 

题目:

 

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

Coccinelle 使用

January 20th, 2015

Coccinelle是一个程序的匹配和转换引擎,它提供了语言SMPL(语义补丁语言)用于指定C代码所需的匹配和转换。Coccinelle 最初是用来帮助Linux的演变,支持更改库应用程序编程接口,比如重命名一个函数,增加一个依赖于上下文的函数参数或者重新组织一个数据结构。除此之外,Coccinelle页被人用来查找或者修复系统代码的bug。

项目地址:https://github.com/coccinelle/coccinelle

安装在这里不再赘述,这里要注意的是需要安装python的devel包,否则这个程序无法运行!

$git clone https://github.com/coccinelle/coccinelle
$git tag > git checkout -b build coccinelle-1.0.0-rc21
$apt-get install python2.6-dev libpycaml-ocaml-dev libmenhir-ocaml-dev menhir ocaml-native-compilers \
ocamlduce camlp4-extra ocaml-findlib pkg-config texlive-fonts-extra
$./configure --with-python --with-menhir
$make all
$apt-get remove coccinelle (prevent conflict)
$make install

安装完毕之后,我们可以定义脚本

@search@
identifier fn,call;
statement s1,s2;
expression E1,E2;
int fd;
position p;
constant C;
@@

<+...
* fd=open@p(...);
//  ...when != fn(<+...fd...+>);
  ...when !=fd=C
* if (fd<0||...){...}
...+>   

@script:python@
p << search.p;
@@

print "%s equal expression" % (p[0].line)

之后我们可以运行这个脚本,可以快速从代码中匹配。

$spatch -sp_file demos/simple.cocci demos/simple.c -o /tmp/new_simple.c

目前这个项目的问题是文档不是很完善,期待之后这个项目的发展。这个工具吸引人的地方在于可以智能的匹配譬如i++ <=> i=i+1这种形式。

目前我们可以更多的参考/usr/local/share/coccinelle/standard.iso

 

 

Safety Engineering 关键概念学习

January 19th, 2015

1.Safety is about understanding potential causality in systems with limited determinism.

  • Control
  • Reduce Hazard

在中文中Safety与Security 概念很类似,都是安全的含义,但是我们要分清楚,区别在于是否得到system Administrator guarantee .

Security 是在没有 guarantee保证的情况下,hacker walks into system without guarantee.

Safety 则是让系统在任何情况下under my control.

2.Fault/Error/Failure

  • Fault is a defect within the system – Software Bugs/Hardware fault/Memory Fault
  • Error is a deviation from the required operation of system or subsystem
    • A fault may lead to an error, i.e., error is a mechanism by which the fault becomes apparent
  • A system failure occurs when the system fails to perform its required function

所以总的来说,Failure对于system可能会造成灾难性后果(catastrophe)。

Functional safety is a resonable response to the increased safety needs but the first option should stay to design simple and clean systems from
the start and Say No where resonable safety is not possible.

3.Fault Tolerance and Robustness

System happened fault ,system won’t walk into fails to perform its required function This is tolerance !

When system faces hazard,failure lead system walk into unsafety state while reliability make system safety (It ‘s really hard!)

Reliability Definitions The ability of an item to perform a required function, under given environmental and operational conditions and for a stated period of
time

4.Mechanisms and Policies

  • Mechanisms specifies how it is to be done(与硬件软件结合相关,不能轻易改变)
  • Policies is what is to be done(具体算法)

The separation of mechanism and policy is important to provide flexibility to a system. If the interface between mechanism and policy is well defined, the change of policy may affect only a few parameters. On the other hand, if interface between these two is vague or not well defined, it might involve much deeper change to the system.

http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/mechanicPolicy.htm

正如kernel中的scheduler一样,这个就是Mechanisms/Policies分离的例子,Mechanisms负责切换进程实体prev,next tasks,包括context_switch,而Policies 负责根据某个策略去是选取特定的task,包括RR,CFS等等…具体对应的函数就是pick_next_task()

 

参考:

http://lxr.free-electrons.com/source/kernel/sched/core.c#L2693

优化程序性能(读书笔记)

November 28th, 2013

1.gcc -o1
gcc -o2 使程序全面优化

» Read more: 优化程序性能(读书笔记)

统计单词出现数目(更新)

August 13th, 2013

这里有一个大文本(一些经典英文小说的集合),文件在解压后大约有20m。
文本中都是英文单词,空格以及英文的标点符号: [.,;-~”?’!] (句号,逗号,分号,破折号,波浪号,双引号,问号,单引号,感叹号)
» Read more: 统计单词出现数目(更新)