A Bit? No!!!

事情源于昨天晚上butterfly的一个问题：找出一个文本文件中最长的一行，Find the longest line in a text file

由于我上大学后一些错误的观念，所以对算法极其的不重视。现在我所做的就是从头开始顺序读取，然后使用不同的编程语言看看效果。还是先看看結果吧：

环境：文件list.txt是一个16M的纯文本，测试的编程语言（当然有些不能说是编程语言）包括bash、ruby、gawk、python、wc、C（C写出来的效率竟然是wc命令的10多倍）

顺序：从最慢的bash到最快的C

1、BASH脚本

#FILE: long.sh, Author: ABitNo
#!/bin/bash
max=0
while read line; do
  if [ ${#line} -gt $max ]; then
    max=${#line}
    longest=$line
  fi
done
echo $max, $longest
exit 0

执行結果（結果会把最长的4082个字符给打印出来的，这里就不写了）

[mydream@archlinux c]$ time bash long.sh <list.txt
real	1m15.605s
user	1m8.349s
sys	0m6.910s

2、Ruby语言

#FILE: long.rb, Author: ABitNo
max, longest = 0, ''
IO.foreach(ARGV[0]) do |line|
  max, longest = line.length, line if line.length > max
end
puts max
puts longest

执行結果（結果会把最长的4082个字符给打印出来的，这里就不写了）

[mydream@archlinux c]$ time ruby long.rb list.txt
real	0m3.016s
user	0m2.517s
sys	0m0.463s

3、awk脚本

#FILE: long.awk, Author: ABitNo
{if ( length > max ) {
  max = length
  longest = $0
}}
END { 
  print max
  print longest 
}

执行結果（結果会把最长的4082个字符给打印出来的，这里就不写了）

[mydream@archlinux c]$ time gawk -f long.awk list.txt 
real	0m1.911s
user	0m1.863s
sys	0m0.017s

4、Python语言

#FILE: long.py, Author: ABitNo
maxLen = 0
for line in file(r'list.txt'):
  if maxLen < len(line):
    maxLen = len(line)
    longest = line
print maxLen
print longest

执行結果（結果会把最长的4082个字符给打印出来的，这里就不写了）

[mydream@archlinux c]$ time python long.py list.txt 
real	0m1.046s
user	0m1.027s
sys	0m0.020s

5、wc就是Linux上的一个小命令

执行結果（結果只会找出最长行的字数，而不会打印出那一行）

[mydream@archlinux c]$ time wc -L list.txt 
4082 list.txt
real	0m0.777s
user	0m0.757s
sys	0m0.003s

6、C语言，使用Linux API中文件到内存的存储映射mmap

/*FILE: long.c, Author: ABitNo*/
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

int main(int argc, const char *argv[])
{
  int fd;
  struct stat sb;
  char *map;
  int loc = 0, max = 0, index = 0,  start = 0;

  if (argc < 2) {
    fprintf(stderr, "no input file\n");
    return 1;
  }

  /*打开文件*/
  fd = open(argv[1], O_RDONLY);
  if (fd == -1) {
    perror("open");
    return 1;
  }
  if (fstat(fd, &sb) == -1) {
    perror("fstat");
    return 1;
  }

  /*映射文件到内存*/
  map = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  if (map == MAP_FAILED) {
    perror("mmap");
    return 1;
  }

  /*关闭文件后映射依然可用*/
  if (close(fd) == -1) {
    perror("close");
    return 1;
  }
  
  /*循环遍历内存*/
  while (index < sb.st_size) {
    while('\n' != map[index++]);
    if (index - start > max) {
      loc = index - 1;
      max = loc - start;
    }
    start = index;
  }

  /*打印結果*/
  printf("max size: %d\n", max);
  for (index = loc-max; index < loc; index++) {
    putchar(map[index]);
  }
  putchar('\n');

  /*解除映射*/
  if (munmap(map, sb.st_size) == -1) {
    perror("munmap");
    return 1;
  }
  return 0;
}

执行結果（結果会把最长的4082个字符给打印出来的，这里就不写了）

[mydream@archlinux c]$ time ./long list.txt
real	0m0.053s
user	0m0.053s
sys	0m0.000s

那个执行一分多钟的脚本实在是无法忍受，从现在开始，我发现我相当的喜欢C语言了。

我还是得说，我是个数学天才，只是我一直在荒废自己的数学才华，因为我感觉不出在现在硬件发达的年代数学的作用。不过现在我开始了解到好的算法是很有必要的，即使硬件再发达，也会有一些小程序执行这么长时间，无法忍受的时间。。。

虽然说执行时间从1分15秒降低到了0.05秒，但这不是靠的算法的优化，因为我现在没有什么好的算法可用，现在开始，好好学习算法。。。

PS：我只是个一般的学生，写的代码都很差劲，期待有人指点。。。
再PS：如果有人能给算法的指点更好，但是不要告诉我詳細的程序，我得学习。。。