计数出现次数

• 下载 C、C++、Lua 源代码文件 - 3.7 KB

引言

计数符号的出现次数可以回答这样的问题：“这段文本中有多少个空格？”。除此之外，它还可以用作某些数据压缩算法的预处理步骤。

在这里，我将展示使用 C 和 Lua 编程语言实现的简单算法。此外，还提供了 C++ 实现供下载。为简洁起见，此处不一一列出。

问题

给定一些输入数据，例如“hello world!”，生成类似以下格式的输出

符号	code	出现次数
o	111	2
w	119	1
r	114	1
h	104	1
e	101	1
d	100	1
	32	1

其中“code”是字符的 ASCII 码（字节的值）。由于我们要处理大型二进制文件，让我们这样表述：“计算二进制文件中每个字节值（0..255）的出现次数，然后按出现次数排序”。

算法

该算法非常简单：假设我们一次读取一个字节的数据，当前字节的值是，例如，104（即刚刚读取了字符 'h'）：我们需要增加 104 的出现次数，并对下一个字节重复此操作，直到所有输入数据都处理完毕。一种快速“增加字节值出现次数”的方法是使用一个出现次数数组，其隐含的假设是某个值的出现次数存储在该值本身的索引所对应的项中（例如，104 的出现次数存储在 occurrences[104] 中）。最后对该数组进行排序以获得预期的输出。

C 代码

C 实现相当直接：程序初始化出现次数数组，然后使用 4KiB 的缓冲区从 stdin 读取数据。每次读取操作后，都会调用一个函数来更新出现次数数组。最后，使用 C 库的 qsort 函数执行排序步骤。

以下是存储符号代码及其出现次数的 struct（我们需要存储符号代码以便执行排序步骤）。

#define BYTES 256
 
typedef struct TagSymbolInfo
{
  int symbol; // the byte [0..255] value
  int occurrences; // number of occurrences of the symbol in the given buffer
} SymbolInfo;

初始化函数（设置符号代码，重置出现次数）。

// initialise the symbol array
void reset_occurrences(SymbolInfo si[])
{
  int n;
  for (n = 0; n < BYTES; ++n)
  {
    si[n].symbol = n;
    si[n].occurrences = 0;
  }
}

以下函数是该算法的核心：它处理输入数据以更新出现次数数组。

 // counts the occurrences in the given buffer, updating accordingly the array of symbols
int increment_occurrences(SymbolInfo si[], const void * buffer, size_t size)
{
  unsigned char * p = (unsigned char *) buffer;
  int success = 0;
 
  while ( size-- )
  {
    si[p[size]].occurrences++; // since si[n].symbol == n, we can use p[size] as index.
    if ( ! si[p[size]].occurrences )
      success = -1; // error on counter overflow
  }
  return success;
} 

用于按出现次数（出现次数相同时按代码）对项进行排序的函数。

// this is the predicate for qsort.
int compare_symbols(const void * symbola, const void * symbolb)
{
  const SymbolInfo * a = (const SymbolInfo *) symbola;
  const SymbolInfo * b = (const SymbolInfo *) symbolb;
 
  if ( a->occurrences > b->occurrences || 
  (a->occurrences == b->occurrences && a->symbol > b->symbol)) return -1;
  return 1;
}

最后是主函数，附带一些样板代码。

 #define INBUFSIZE 4*1024
 
int main()
{
  long total = 0; // total number of occurrences, must be equal to file size
  unsigned char buffer[INBUFSIZE]; // the read buffer
  int n;
  SymbolInfo si[BYTES]; // the array of symbols

  reset_occurrences(si); // initialization

  // reading stdin until EOF (or error)
  for(;;)
  {
    int nread = fread (buffer, sizeof(buffer[0]), INBUFSIZE, stdin);
    if ( ! nread ) break;
    if ( increment_occurrences(si, buffer, nread) )
      printf("occurrences counter(s) overflow\n");
  }
  // calling qsort for the sorting step
  qsort( si, BYTES, sizeof(si[0]), compare_symbols);
 
 
  // some output
  for (n=0; n<BYTES; ++n)
  {
    char c = si[n].symbol;
    if (! si[n].occurrences) break;
    total += si[n].occurrences;
 
    c = isprint(c) ?  c : '.';
 
    printf("{symbol ='%c', code= %3d,  
    occurrences = %d}\n", c, si[n].symbol, si[n].occurrences);
  }
  printf("total occurrences = %ld\n", total);
 
  return 0;
}

Lua 代码

Lua 是一种很棒的脚本语言，轻量级、快速且易于嵌入（更多信息可在 Lua 网站找到）。

由于它在 CodeProject 上是一种“比较冷门”的语言，因此我将对提供的代码做一些详细说明。

local INBUFSIZE = 4096
 
local function init_occurrences()
  local si = {}
  for i=1,256 do
    si[i] = { occurrences = 0, symbol = (i-1) }
  end
  return si
end

init_occurrences 函数创建 *出现次数数组* si 并对其进行初始化。

更详细地说，local si = {} 语句创建了一个 table，这是 Lua 提供的 *唯一* 数据结构。

表是一种关联数组。在 for 循环内部，会创建一个新的表，初始化并赋值给 si 的每个项。

语句...

si[i] = { occurrences = 0, symbol = (i-1) } 

...是以下语句的快捷方式：

s[i] = {}
s[i]["occurrences"] = 0
s[i]["symbol"] = i-1 

或者...

s[i] = {}
s[i].occurrences = 0
s[i].symbol = i-1 

...使用点运算符提供的“语法糖”。

最后，return si 终止函数并将 si 提供给调用者，避免其在下次垃圾回收时被移除。

increment_occurrences 函数相当直接，它展示了缺少方便的增量运算符。

 local function increment_occurrences(si, buffer)
  for i=1,#buffer do
    local index = buffer:byte(i)+1
    si[index].occurrences = si[index].occurrences + 1
  end
end 

程序的其余部分，样板代码...

 local function main()
 
  local total = 0
  local si = init_occurrences()
 
  repeat
    local buf = io.read(INBUFSIZE)
    if  buf then
      increment_occurrences(si, buf)
    end
  until not buf
 
  table.sort(si,
    function (a,b)
      if (a.occurrences > b.occurrences or (a.occurrences == b.occurrences and a.symbol > b.symbol)) then
        return true
      end
    end)
 
  for i=1,256 do
    if si[i].occurrences == 0 then break end
    local c = string.char(i):match("([%g])") or "-"
 
    print(string.format("{symbol ='%s', code= %3d,  occurrences = %d}", c, si[i].symbol, si[i].occurrences));
 
    total = total + si[i].occurrences
  end
 
  print("total occurrences = " .. total)
end 

main() 

有一个不错的亮点：接下来的语句使用 table.sort 函数和一个 *匿名* 函数对 si 表进行排序。

  table.sort(si,
    function (a,b)
      if (a.occurrences > b.occurrences or (a.occurrences == b.occurrences and a.symbol > b.symbol)) then
        return true
      end
    end)

C++ 代码

David Delaune，又名 Randor 向我建议了一种巧妙的输入读取方法（您可以在页面底部的讨论串中找到他的评论）。现在展示 C++ 代码是很有意义的。

struct SymbolInfo
{
  int symbol; // the byte value [0..255]
  int occurrences; // the number of occurrences of the symbol
};

int main()
{
  std::cin >> std::noskipws;
  std::array<SymbolInfo , 256> si={{0}};
  std::istream_iterator<unsigned char> input(std::cin),end;
  std::for_each(input,end,[&](unsigned char c){si[c].occurrences++;});

  for (int n=0; n<256; ++n) si[n].symbol=n;

  std::sort(si.begin(), si.end(),
    [](const SymbolInfo & a, const SymbolInfo &b) {return (a.occurrences > b.occurrences || (a.occurrences == b.occurrences && a.symbol > b.symbol));}
  );
}

就是这样！（我只是省略了 include 指令和样板打印代码）。

Using the Code

目前，C/C++ 代码可以在 Linux 控制台上运行（尽管将其修改为在 Windows 控制台上运行非常简单）。

Lua 代码需要 Lua 解释器，在类 Ubuntu 发行版中作为 lua5.2 包（apt-get install lua5.2）提供。此外，在此处可以找到 Lua 的二进制文件（也包括 Windows 版本）：Lua 二进制文件在 SourceForge。

C 代码

使用以下命令编译：

 gcc -Wall -O3 -o occurrences occurrences.c 

使用以下命令运行：

./occurrences < <FILE PATH>

（例如 ./occurrences < myfile.bin）

为了计算文件的出现次数，必须使用输入重定向运算符（<）（否则命令将计算 stdin 中的出现次数，即用户输入的字符直到 CTRL^D）。

C++ 代码

使用以下命令编译程序 (1)：

 g++ -std=c++11 -Wall -O3 -o occurrences occurrences.cpp

并使用以下命令编译程序 (2)：

g++ -std=c++11 -Wall -O3 -o occurrences_ran occurrences_ran.cpp  

（C++ 程序需要较新版本的 g++，我使用的是 4.7.3 版本）

像 C 程序一样运行。

Lua 代码

当然，它不需要编译。您可以这样运行它：

lua occurrences.lua < <FILE PATH>  

基准测试

我知道使用一个相当底层的算法来比较 Lua 和 C/C++ 代码的性能是不公平的，但我并不公平，所以这里有一个小测试。

详细说明

• 在 Lubuntu 13.04 系统上执行。
• 输入文件：lubuntu-13.10-desktop-i386.iso (729,808,896 字节)。
• g++ 和 gcc 的优化级别为 -O3。
• Lua 版本为 5.2.1。
• 报告的时间是通过 Linux time 命令生成的。

language	文件大小 (MiB)	实际时间 (秒)	用户时间 (秒)	系统时间 (秒)	速度 (MiB/秒)
C++ (1)	696	9.07	1.31	1.51	76.74
C++ (2)	696	41.47	37.20	3.50	16.78
C	696	9.94	0.62	1.63	70.02
Lua	696	165.38	155.87	4.38	4.21

注释

1. '传统' C++ 程序（源代码文件 occurrences.cpp 可在下载部分找到）
2. 更优雅的程序（文章中展示的那个，可在下载部分找到，名为 occurrences_ran.cpp）

备注

• 显然 C 和 C++ (1) 的性能非常相似。正如 real 与 user 和 sys 图所示，它们主要受 I/O 限制。
• C++ (2) 比 C++ (1) 明显慢。
• Lua 比 C/C++ 慢大约 17 倍，其执行时间主要由 user 部分决定。

历史

• 2014 年 2 月 8 日 - 添加了 C++ 代码（感谢 David Delaune aka Randor）
• 2014 年 2 月 6 日 - 添加了下载所需的源文件
• 2014 年 2 月 6 日 - 首次发布