论坛: 编程破解 标题: !!!出个简单的题目来考考大家!!! 复制本贴地址    
作者: NetDemon [netdemon]    ADMIN   登录
现有一文本文件,以一行一个记录的形式保存着某些信息。
现在请用你用你最熟悉的计算机语言,自认为最有效率的方法,
把此文件中重复的行找出并显示出其重复的次数,
然后生成一个不再有重复的行的新的文件。



地主 发表时间: 05-10-31 05:10

回复: kert_t8 [kert_t8]   论坛用户   登录
用strcmp比较字符串
用二叉树存储字符串,比较的字符串,一样的在树里面存储一个标志,说明是重复行,然后counter++,
最后遍历一遍这个二叉树,组成新的文件,提取每一个元素的counter,是重复的次数,把有重复标记的行打印到屏幕

这个真的要编的话,还需要一点时间。大家先讨论一下这个算法和数据结构有没有什么可以改进

B1层 发表时间: 05-11-01 09:14

回复: flynet [flynet]   论坛用户   登录
关键问题是:是否包含模式行,但是不完全重合的也计算在内?

主要问题归结到如何使用串的模式匹配算法来实现这个解决方案

B2层 发表时间: 05-11-01 11:37

回复: virgoshaka [virgoshaka]   论坛用户   登录
月之御者 方案的时间复杂性是O(n2)吧?  (n的平方)

我觉得可以先对文件中的字符串进行排序,规定a最小,z最大,完毕后遍历文件,遇到相邻相同的字符串合并为同一个,并记录次数,同时输出。
读取阶段:O(n)
排序阶段:这个是关键,好像最快的排序算法是散列排序(不怎么懂。。。),时间复杂性是O(n),慢点的如堆排序和快速排序(这些懂。。。),时间复杂性也有O(nlogn)。
遍历并输出阶段:O(n)
所以总时间理论上最快可以达到 O(n)+O(n)+O(n)=O(n)

不知道说的对不对,大家指正。。。
具体的数据结构还没考虑,呵呵

B3层 发表时间: 05-11-02 12:57

回复: flynet [flynet]   论坛用户   登录
楼上的方法不错哈,可以先排序,这样可以简化不少

另外感觉也可以用LZ系列的压缩算法来做参考的

也就是找匹配


[此贴被 flynet(flynet) 在 11月02日13时02分 编辑过]

B4层 发表时间: 05-11-02 13:01

回复: virgoshaka [virgoshaka]   论坛用户   登录
呵呵,其实我以前想过这个问题,那时候要精简一个很大的字典,觉得一个个比对需要O(n2),
计算量太大了。。。
今天又想了一下,觉得还是先排序比较好。。。

我觉得模式匹配应该是具体比对时的东西,更内层的,当然选择一个好的算法也很重要



[此贴被 处女座的沙加(virgoshaka) 在 11月02日13时19分 编辑过]

B5层 发表时间: 05-11-02 13:10

回复: qwhacker [qwhacker]      登录
俺也觉得先排序好,两个两个的比较。容易实现,不用遍历整个文件了。

B6层 发表时间: 05-11-03 07:28

回复: TecZm [teczm]   版主   登录
一行一行读入模式空间,比对每一行与模式空间行.....sed应该可以....我再想想

B7层 发表时间: 05-11-03 08:45

回复: kert_t8 [kert_t8]   论坛用户   登录
加沙说的有道理,最主要的问题是要在排序上
我们可以设计这样一个散列函数
#define PREFIX 3
int indexOfString ( char * a) {
    int index=0;
    int i;
    for (i=0;i<PREFIX && i<strlen(a);i++) {
        index+=(unsigned int)a[i];
    }
    return index;
}
然后用hash表来做,表里面都是recordNode结构
struct recordNode {
    struct recordNode *next;
    char * record;
}
出现冲突的时候,就把新的recordNode加在这一行的最后一个recordNode后面
表结构就是
+----------+
|  abc    | --> abcd --> abcf
|----------|
|  abd    | --> abdd
|----------|
|  abe    | --> abeab --> abeas -> abedd --> abejk
|----------|
|  abf    | --> abfdd --> abfee -> abfff
+----------+
但是这样我觉得还是不太方便

B8层 发表时间: 05-11-03 10:12

回复: windflower [windflower]   论坛用户   登录
排序,楼主好像并不允许你打乱记录的顺序吧,只是叫你删除重复的行。

我也想不出更有效的办法,但事情总是可以解决的。

用一个数组info来记录行的重复信息(非重复行记0,重复行记1)。
第一次从第1行记录扫描到文件尾,将该行记录置入临时变量tmp,与后续每一记录相比,若相同,则把数组元素info[++i]置值1,否则置0,并用变量count++记录重复次数,扫描完后,若count非零,则打�n该行tmp的值和重复次数count。

第一遍完后,再从第二行开始遍历,当然此时要先看info[2],若其值为1则是己扫描出来的重复行,直接从第三行开始下一次遍历,依此类推。

全部完成后,重复的行和次数己打�n出来了。

再对文件记录一次遍历,把info[i]为0的行输出到另一个文件即可。

设文件记录为n,扫描的次数一定小于n(n+1)/2,最后生成目标文件时小于n次。



B9层 发表时间: 05-11-03 15:53

回复: flynet [flynet]   论坛用户   登录
如果只是查找完全匹配的行的话,那就简单多了,只要一个字不匹配,就放弃,后面的内容就不用匹配了。
模式匹配关键的地方是模式串比较小。到一个很长的字符串里去查这一段比较小的模式串

B10层 发表时间: 05-11-04 11:06

回复: virgoshaka [virgoshaka]   论坛用户   登录
楼上的楼上说的就是O(n2)的方法啊
如果规定不能打乱原有的次序,好像排序就不能用了。。。
不过我在想能不能排序完后再把它逆回来。。。

B11层 发表时间: 05-11-04 15:43

回复: xtsyiu [xtsyiu]   论坛用户   登录
我觉得用二叉树的遍历比较好

B12层 发表时间: 05-11-05 14:59

回复: flynet [flynet]   论坛用户   登录
把这些东西如何组织成二叉树又是一件麻烦事
而且需要占用相当多的堆
并且遍历二叉树也比较花时间哦

应该做的关键是如何简化算法思想使其有效实施

B13层 发表时间: 05-11-06 09:42

回复: kert_t8 [kert_t8]   论坛用户   登录
ND并没有说可以改变顺序,但是也没有说部可以改变顺序啊

B14层 发表时间: 05-11-06 14:18

回复: TecZm [teczm]   版主   登录

sort xxx|uniq -c

B15层 发表时间: 05-11-07 08:14

回复: lida1818 [lida1818]   论坛用户   登录
NetDemon为什么不提供这个文本让楼上的各位都可以写一个程序来验证自己的算法?^_^

B16层 发表时间: 05-11-07 20:59

回复: NetDemon [netdemon]   ADMIN   登录
提出这个问题是我在处理一个考勤纪录的文件的时候想到的,大家随便就能生成一个这样的类似的文件,就10M大小,重复的有10%这样吧,如果这文件只有10行,讨论效率就没什么必要了,如果文件有1G,用文本的方式记录也未免太奇怪了。

对于排序问题,我在实际写的时候是不可以的,不过这问题既然在这里以一个讨论的形势提出来了,那么大家也可以在能改变顺序跟不能改变顺序的两种情况下动动脑筋嘛,能要怎么样,不能又要怎么样都想想啊。

to TecZm
这里是编程版不是应用版阿大哥,要你这样的都能算解决方案的话,那么......
打开excel,导入文本文件,然后....岂不是更简单阿?
再说了,Y这样把不重复的也print出来了

[此贴被 NetDemon(netdemon) 在 11月08日05时05分 编辑过]

B17层 发表时间: 05-11-08 05:01

回复: TecZm [teczm]   版主   登录


B18层 发表时间: 05-11-08 09:00

回复: 286 [unique]   版主   登录
现有一文本文件,以一行一个记录的形式保存着某些信息。
现在请用你用你最熟悉的计算机语言,自认为最有效率的方法,
把此文件中重复的行找出并显示出其重复的次数,
然后生成一个不再有重复的行的新的文件。

main()
{
  struct
  {    int hash;//采用hash是加快比较速度。
        int count=0;//个数
        char *line;
  }buff[100000];
  char *tempbuff;
  int temphash;
  int num=0;
  FILE fpr=fopen("txt.txt",r);
  FILE fpw=fopen("txt2.txt",w);
  while (fgetline(fpr,tempbuff)!=FEOF)
  {
        num++;
        temphash=gethash(tempbuff);//hash函数可任意定义,比如把个数定义为hash函数,也就是说,长度不一样的串,肯定是不一样的,因此就不比较。这样大大加快比较速度。
        for (int i=0;i<num;i++)//此处应该采用二分法查找,也可使效率大大提高。
        {
            if (buff[i].hash==temphash))
            {//如果hash值相当了,再进行逐位比较。
                  if (strcmp(tempbuff,buff[i].line))
                  {
                          buff[i].count++;//如果与此前相等,个数加一。
                          break;
                    }
            }
        }
        buff[i].line=tempbuff;//不相等的加入到匹配队列中,并写入到另一文件中。
        buff[i].hash=temphash;
        fwrite(fpw,tempbuff,len(tempbuff));         
  }

  //打印重复行及重复行个数略。。。。
 
  fclose(fpr);
  fxlose(fpw);
}
 


B19层 发表时间: 05-11-08 10:19

回复: NetDemon [netdemon]   ADMIN   登录
286的算法果然比我的好

B20层 发表时间: 05-11-12 02:06

回复: kert_t8 [kert_t8]   论坛用户   登录


B21层 发表时间: 05-11-14 10:54

回复: lwei889 [lwei889]   论坛用户   登录
才看到,回去研究研究……


B22层 发表时间: 05-11-14 15:38

回复: BBL [bbl]   论坛用户   登录
看来说来说去就只有两个人真正看得懂..一个是ND自己一个是286...

B23层 发表时间: 05-11-17 23:06

回复: sniper167 [sniper167]   论坛用户   登录
果然是:
纵行下天,286足矣。

B24层 发表时间: 05-11-30 22:15

回复: NetDemon [netdemon]   ADMIN   登录
答案揭晓,这个问题的我的程序
代码:

#!/usr/bin/perl
my (%hash,$key,$value);
open(FILE,"in.txt");
while (<FILE>) {
if($hash{$_} == undef){$hash{$_} = 1;}
else{$hash{$_} += 1;}
}
close(FILE);
open(FILE,">out.txt");
while (($key,$value) = each %hash) {
print FILE "$key";
if($value != 1){print "$key重复了$value次\n";}
}
close(FILE);

没了,就这么一点而已

[此贴被 NetDemon(netdemon) 在 12月03日07时22分 编辑过]

B25层 发表时间: 05-12-03 06:50

回复: NetDemon [netdemon]   ADMIN   登录
嗯,注释一下比较好,似乎会perl的兄弟比较少,怕大家看不懂。
然后还要说明一下,俺是看了286的思路才写的这个,我原来的并非这样,大家不要扁我
最后证明了一件事情,原来真的处理文本,没有比perl更好的了,哈哈哈
代码:

#!/usr/bin/perl
my (%hash,$key,$value);#变量定义,hash为一哈希表,key和value是字符串变量
open(FILE,"in.txt");  #打开原始文件
while (<FILE>) {      #遍历文件直到文件结束,每次读取一行,内容在$_中
if($hash{$_} == undef){$hash{$_} = 1;}#如果哈希表的键中没有这行,则把这行置入并设置其值为1
else{$hash{$_} += 1;}#如果哈希表中已有此行,则把其值加1
}
close(FILE);       #关闭文件.....(真鸟废话的这句)
open(FILE,">out.txt"); #打开输出文件
while (($key,$value) = each %hash) { #遍历哈希表,并把其键和值分别赋给变量key和value
print FILE "$key"; #把不再重复的行写入到输出文件中
if($value != 1){print "$key重复了$value次\n";}#如果值不是1,说明那是重复的,就把它打印到屏幕
}
close(FILE); #关闭文件......(真鸟多事,程序退出了不就自动关闭了么.....)



B26层 发表时间: 05-12-03 07:27

回复: NetMelody [mmgg00]   论坛用户   登录
代码:

#!/usr/bin/perl
map { $h{$_}++} <>;
print keys %h;




呵呵,比老大的爽哦


[此贴被 NetMelody(mmgg00) 在 12月06日14时50分 编辑过]

B27层 发表时间: 05-12-06 14:48

回复: hannyu [hannyu]   论坛用户   登录
你们等着,我回去学了PERL再来。。

B28层 发表时间: 06-01-02 18:35

回复: hannyu [hannyu]   论坛用户   登录
引用:
my (%hash,$key,$value);#变量定义,hash为一哈希表,key和value是字符串变量

神奇

B29层 发表时间: 06-01-02 18:37

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号