shell排序

blackold

这些都没学过。惭愧，要补课了。

昭襄王

以前用php做过一个标签云，规则是提及次数多的权重大（表现为字体大），在固定大小的框里尽可能塞进更多数量的标签，无序排列。后来才知道，这是“背包”的一种。。。。

starwing83

回复 131# blackold


    = =黑哥太谦虚了，要是我经验有黑哥这么丰富就不愁工资低了~~

starwing83

回复 132# 昭襄王


    肯定还有其他的规则吧？（比如时间啥的），否则最优算法肯定会把那些占位置的最大的标签都喀嚓掉的……

昭襄王

回复  昭襄王


    肯定还有其他的规则吧？（比如时间啥的），否则最优算法肯定会把那些占位置的最大的 ...
starwing83 发表于 2010-09-30 14:22

    有其他规则，年代久远，忘了，大体是这个意思。字号是有上限的，还有只考虑前多少位的，当然是有时间限制的。

昭襄王

用php写了一个，排序后冒泡

1. <?php
   
2. /**
   
3. * file "lines" gives like this
   
4. * a:0.13 b:0.23 c:0.05 d:0.45 e:0.07
   
5. * p:0.01 q:0.20 r:0.13 s:0.33 t:0.23
   
6. *
   
7. * */
   
8. $content = file_get_contents('lines');
   
9. $rows = explode("\n",$content);
   
10. 
    
11. function string2KeyedArray($string, $delimiter = " ", $kv = ":") {
    
12.   if ($a = explode($delimiter, $string)) { // create parts
    
13.     foreach ($a as $s) { // each part
    
14.       if ($s) {
    
15.         if ($pos = strpos($s, $kv)) { // key/value delimiter
    
16.           $ka[trim(substr($s, 0, $pos))] = trim(substr($s, $pos + strlen($kv)));
    
17.         } else { // key delimiter not found
    
18.           $ka[] = trim($s);
    
19.         }
    
20.       }
    
21.     }
    
22.     return $ka;
    
23.   }
    
24. } // string2KeyedArray
    
25. 
    
26. function arrSumMax($arrSum , $sortedArr){
    
27.   if($arrSum < 0.5){ //print the line
    
28.     foreach($sortedArr as $k => $v){
    
29.       echo $k.":".$v." ";
    
30.     }
    
31.       echo "<br />";   
    
32.   }
    
33. }
    
34. 
    
35. foreach($rows as $line){
    
36.   $sortedArr = string2KeyedArray($line);
    
37.   $arrSum = array_sum($sortedArr);
    
38.   arrSumMax($arrSum , $sortedArr);
    
39.   asort($sortedArr); //sort array return 1
    
40.   while($arrSum > 0.5) {
    
41.     $arrSum = array_sum($sortedArr) - array_pop($sortedArr); //pop last
    
42.     arrSumMax($arrSum , $sortedArr);
    
43.   }  
    
44. }
    
45. ?>
    

复制代码

expert1

呵呵，真没提及过这些，严蔚敏的那本书。

expert1

回复 129# starwing83

晕了，是等于0.4，唉，中午脑子有问题啊。哈哈
下午专门跑去看了这个算法，很有趣。

bruclan

不好意思，shell有点生疏了，还是perl好，嘿嘿。

#!/usr/bin/perl -w
use strict;

open(FHANDLE, "a.txt" or die "Can't open file: $!\n";
while(<FHANDLE> {
    my @arr = split(/ /, $_);
    my $arrlen = $#arr+1;
    my %hash;
    for(my $i=0; $i<$arrlen; $i++) {
        my ($key, $value) = split(/:/, $arr[$i]);
        $hash{$key} = $value;
    }
    my @ordered_arr = sort { $hash{$a} <=> $hash{$b} } keys(%hash);
    my $sum = 0;
    for(my $j=0; $j<$arrlen; $j++) {
        if(($sum += $hash{$ordered_arr[$j]}) >= 0.5) {
            $sum -= $hash{$ordered_arr[$j]};
            print "sum: " . $sum . " - ";
            for(my $k=0; $k<$j; $k++) {
                print "$ordered_arr[$k]hash{$ordered_arr[$k]} ";
            }
            print "\n";
            last;
        }
    }
}

输出：
sum: 0.48 - c:0.05 e:0.07 a:0.13 b:0.23
sum: 0.34 - p:0.01 r:0.13 q:0.20

expert1

回复 139# bruclan


    是用了hash表吗？
PS：那个最优解用shell搞有无思路？