字符串排序

Windows19

回复 60# 523066680

3q加了

523066680

新学了一个模块 - DB_File，不熟练。
优点：占用内存少
缺点：特别耗时

处理机制：参考63楼

1. =info
   
2.     Code by 523066680
   
3.     2017-06
   
4. =cut
   
5. 
   
6. #!/usr/bin/perl
   
7. use Fcntl;
   
8. use DB_File;
   
9. use IO::Handle;
   
10. use Data::Dumper;
    
11. use Time::HiRes qw/sleep/;
    
12. STDOUT->autoflush(1);
    
13. 
    
14. our $SRC = "D:/A.txt";
    
15. our $DST = "D:/Final.txt";
    
16. our $FH_SRC;
    
17. our $FH_DST;
    
18. our $DB_KEY    = "F:/keywords.dat";
    
19. our $DB_LINE   = "F:/lines.dat";
    
20. our $DB_OFFSET = "F:/line_offset.dat";
    
21. our $DB_SORT   = "F:/sort.dat";
    
22. 
    
23. our $fold = "D:/tempfolder_words";  #尽可能独立的目录名称
    
24. 
    
25. our %keywords;
    
26. our @lines;
    
27. our @offset;   #保存每一行的索引位置+长度
    
28. our %rank;     #每行的元素次数信息
    
29. 
    
30. unlink $DB_KEY;
    
31. unlink $DB_LINE;
    
32. unlink $DB_OFFSET;
    
33. unlink $DB_SORT;
    
34. 
    
35. tie %keywords, "DB_File", $DB_KEY, O_WRONLY|O_CREAT, 0666, $DB_BTREE or die $!;
    
36. tie @lines, "DB_File", $DB_LINE, O_WRONLY|O_CREAT, 0666, $DB_RECNO or die $!;
    
37. tie @offset, "DB_File", $DB_OFFSET, O_WRONLY|O_CREAT, 0666, $DB_RECNO or die $!;
    
38. 
    
39. # 排序函数设置
    
40. $DB_BTREE->{'compare'} = \&Compare ;
    
41. tie %rank, "DB_File", $DB_SORT, O_WRONLY|O_CREAT, 0666, $DB_BTREE or die $!;
    
42. 
    
43. #our %rank;           #等级索引
    
44. 
    
45. LOAD_DATA:
    
46. {
    
47.     print "Loading ... \n";
    
48.     open $FH_SRC, "<:raw", $SRC or die $!;
    
49. 
    
50.     my $filesize = -s $SRC;
    
51.     my $curr = 0;
    
52.     my $prev = 0;
    
53. 
    
54.     my $time_a = time();
    
55.     my $percent;
    
56. 
    
57.     #每行的偏移量
    
58.     my $offsetA = 0;
    
59.     my $offsetB;
    
60.     my @parts;
    
61. 
    
62.     #单行的重复关键词判断
    
63.     my %inline;
    
64. 
    
65.     while ( my $line = <$FH_SRC>)
    
66.     {
    
67.         #next if ($line=~/^\s*\r?\n$/);  #排除空行
    
68.         %inline = ();
    
69.         @parts = $line =~/([a-zA-Z]+|[\d]+)/g;
    
70. 
    
71.         #累积关键字出现的次数
    
72.         for my $e (@parts)
    
73.         {
    
74.             if ( not exists $keywords{$e} ) { $keywords{$e} = 1    }
    
75.             else { $keywords{$e}++ if (not exists $inline{$e}) }
    
76. 
    
77.             $inline{$e} = 1;
    
78.         }
    
79. 
    
80.         #每行的关键字数据
    
81.         push @lines, join(",", keys %inline);
    
82. 
    
83.         #每行的偏移量和长度信息
    
84.         $offsetB = tell( $FH_SRC );
    
85.         push @offset, join(",", $offsetA, $offsetB - $offsetA);
    
86. 
    
87.         #更新起点位置
    
88.         $offsetA = tell( $FH_SRC );
    
89. 
    
90.         $curr = $offsetA / $filesize * 100.0;
    
91.         if ( ($curr - $prev) > 1.0  )
    
92.         {
    
93.             print ".";
    
94.             $prev = $curr;
    
95.         }
    
96.         
    
97.     }
    
98.     print "\n";
    
99. 
    
100.     close $FH_SRC;
     
101. 
     
102.     printf "Time use: %s seconds\n", time()- $time_a;
     
103. }
     
104. 
     
105. ANALYSE_AND_SORT:
     
106. {
     
107.     my $time_a = time();
     
108.     print "Sorting key of each line ... \n";
     
109. 
     
110.     #利用 DB_File 机制排序
     
111.     for my $idx ( 0 .. $#lines )
     
112.     {
     
113.         # key = 行号，每个关键字的次数（从大到小）
     
114.         $key = join ( ",", $idx,
     
115.                     reverse sort { $a <=> $b } map { $keywords{$_} } split(",", $lines[$idx])
     
116.                 );
     
117. 
     
118.         # value = 该行的位置索引
     
119.         $rank{$key} = $offset[$idx];
     
120.     }
     
121. 
     
122.     printf "Time use: %s seconds\n", time()- $time_a;
     
123. }
     
124. 
     
125. FINAL_OUTPUT:
     
126. {
     
127.     print "Almost finish\n";
     
128. 
     
129.     my $time_a = time();
     
130.     my ($k, $v);
     
131.     my ($site, $len);
     
132.     my $buff;
     
133. 
     
134.     open $FH_SRC, "<:raw", $SRC or die $!;
     
135.     open $FH_DST, ">:raw", $DST or die $!;
     
136. 
     
137.     while ( ($k, $v) = each %rank )
     
138.     {
     
139.         ($site, $len) = split(",", $v);
     
140.         seek($FH_SRC, $site, 0);
     
141.         read($FH_SRC, $buff, $len);
     
142.         $buff=~s/\r?\n$//;
     
143.         print $FH_DST $buff,"\r\n";
     
144.     }
     
145. 
     
146.     close $FH_SRC;
     
147.     close $FH_DST;
     
148. 
     
149.     printf "Time use: %s seconds\n", time() - $time_a;
     
150. 
     
151.     untie %keywords;
     
152.     untie @lines;
     
153.     untie @offset;
     
154.     untie %rank;
     
155. }
     
156. 
     
157. sub Compare
     
158. {
     
159.     my ($ka, $kb) = @_ ;
     
160.     my @ar = split(",", $ka);
     
161.     my @br = split(",", $kb);
     
162.     my $i = 1;
     
163. 
     
164.     while ( ($ar[$i] <=> $br[$i] ) == 0
     
165.             and $#ar > $i
     
166.             and $#br > $i
     
167.             #and $i < 3
     
168.         ) {  $i++;  }
     
169.    
     
170.     $br[$i] <=> $ar[$i]  ||  $#br <=> $#ar || $br[0] <=> $ar[0];
     
171.     #如果最后一位相同，比较元素数量；如果数量相同，按下标大小排列
     
172. }
     
173. 
     
174. __END__
     

复制代码

523066680

以原贴的段落为例，
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com

处理结果：
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5

每行的关键字在全文中出现的次数统计（单行内多次计为一次）
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)

处理后的顺序（按行排序，从最高的频率开始对比；如果最高的次数相同，则对比第二列，以此类推）
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)

纯数字，前后对比：
Before:
[0]6,5,5,5,5,5,5,4,1,1
[1]6,5,5,5,5,5,5,4,2,1
[2]3,2,2,1,1,1,1,1,1,1,1
[3]6,5,5,5,5,5,5,2,1,1
[4]6,5,5,5,5,5,5,3,2,2
[5]6,5,5,5,5,5,5,4,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1

After
[1]6,5,5,5,5,5,5,4,2,1
[0]6,5,5,5,5,5,5,4,1,1
[5]6,5,5,5,5,5,5,4,1
[4]6,5,5,5,5,5,5,3,2,2
[3]6,5,5,5,5,5,5,2,1,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1
[2]3,2,2,1,1,1,1,1,1,1,1

Windows19

回复 62# 523066680

嗯嗯  测试后基本正确  就是效率有点慢,  100m耗时59分钟左右  如果要处理超过100g  估计也得1个月左右
能否加快一点时间?  比如 使用多线程处理  现在好像只用1个cpu来处理   使用多线程处理 效率会不会再快些?

如果能优化效率就太好了

辛苦了  再赏



测试文件97.0 MB耗时
$ perl 123
Loading ...
Time: 538 seconds
Sorting key of each line ...
Almost finish
Time: 1391 seconds




麻烦在有空闲时间抽空关注一下看看能不能再改进一下  谢谢

523066680

回复 64# Windows19

是在服务器跑吗，如果是100G，会生成大约 600G 的临时文件。
如果每行只取一个频率最高的词作为代表 （其他低频率不考虑，可以加快）

比如这两行的每个关键字的频率列表：
[5]6,5,5,5,5,5,5,4,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1

如果只对比开头，都是6次，这两项数据并排，后面的不再对比。

-

不懂多线程 -_-

Windows19

523066680 发表于 2017-06-23 09:27
回复 64# Windows19

是在服务器跑吗，如果是100G，会生成大约 600G 的临时文件。

嗯嗯，ok  还是老师你的意路灵活，

hztj2005

这是个大工程，向523066680学习下。

csccyab

Python

1. import re, collections, operator
   
2. 
   
3. str_dict = collections.defaultdict(list)
   
4. line_number = 0
   
5. lines_printed = []
   
6. 
   
7. f = open("1.txt")
   
8. for line in f:
   
9.         line_number += 1
   
10.         for str in re.findall('[a-zA-Z]', line):
    
11.                 str_dict[str].append(line_number)
    
12. 
    
13. str_dict_sorted = { i: str_dict[i] for i in sorted(str_dict, key = lambda k: len(str_dict[k]), reverse=True) }
    
14. f.close()
    
15. 
    
16. for the_key, the_value in str_dict_sorted.items():
    
17.         for i in the_key:
    
18.                 for j in str_dict_sorted[i]:
    
19.                         with open("1.txt") as file:
    
20.                                 for ln, l in enumerate(file):
    
21.                                         if ln+1 == j and ln not in lines_printed:
    
22.                                                 print (l.strip())
    
23.                                                 lines_printed.append(ln)

复制代码