- 论坛徽章:
- 16
|
本帖最后由 expert1 于 2010-10-02 19:47 编辑
假期看算法，想到了这个，平时我们需要找出2个文件里相同的部分，假如a内容是排序后的。比如
10
20
30
40
50
50
60
70
而b：
15
10
70
45
300
50
找出a,b中公共的部分，一般做法- awk 'NR==FNR{a[$0]}NR>FNR{if($0 in a)print }'
下午搞了个二分查找- #!/bin/awk -f
- # date :2010-10-02
- # binary search by awk ,just for fun
- NR==FNR {
- a[k++] = $0 }
- NR>FNR {
- start= 0;end = k-1
- while(start<= end) {
- mid =int(start+ ((end - start)/2))
- #start,end都很大时，比如元素达到 2^30 时，平常做法mid =int((start+ end)/2)将超过整数的最大值 2^31 -1，此时讲溢 #出，值为负了。所以要用这个办法，O(∩_∩)O~
- split(a[mid], b)
-
- if($1==b[1]) {print "ok "$1 " was found";break}
- else if ($1 > b[1]) start = mid+1
- else end= mid-1 }
-
- }
此时a必须是排序过的，当然这些废话了，学过数据结构的都晓得为什么。
效率很高，呵呵，当然数据量小的时候看不出来，有兴趣可以去看下这个算法。
经过多次测试没发现问题。有问题欢迎回复。
突然想起了以前我发的一个贴“shell的效率和Perl，Python处理文本方面谁高”现在想起真是感觉自己浅薄了，根据具体情况，采取合适的方法（算法）。想起了当时一片争论，大家各执一词，当然没几个人说得清为什么，呵呵，做事不可不严谨啊。 |
|
免费注册
发表于 2010-10-02 15:46
