如何快速统计出一亿行由0和1组成的数字里面的1连续出现几次及标记后出现的次数？

Question

如何快速统计出一亿行由0和1组成的数字里面的1连续出现几次及标记后出现的次数？请提供具体思路及代码。

Answer 1

任务概述

你需要统计一亿行由 0 和 1 组成的数字中，连续出现的 1 的次数，并且标记每次连续 1 出现后紧接着的数字是 0 的次数。也就是说，我们要找出连续的 1 的“段”以及这些段后跟随的 0 的个数。

这是一个典型的大数据处理任务。由于数据量巨大，我们的目标是设计一个 高效的算法，尽量减少内存消耗并提升计算速度。考虑到你可能在使用 C++ 和 Python，下面我会分别给出两种语言的实现思路及代码。

解决思路

1. 逐行遍历输入数据：对每一行数据进行扫描，查找连续的 1 的区间。
2. 统计连续 1 的段数：每次遇到一个连续的 1，就统计该段的长度。
3. 标记该段后紧接的 0 的次数：一旦结束连续的 1 后，检查下一个数字是否为 0，并记录该 0 后出现的次数。
4. 优化内存与计算：考虑到数据量很大，我们可以通过 流式处理 或 批量读取 来避免一次性加载整个数据集，同时利用 并行计算 来加速处理过程。

1. C++ 方案

1.1 思路

• 我们将逐行读取数字（0 或 1），并用一个简单的状态机来记录连续的 1 和后跟的 0。
• 每次遇到一个 1，就增加连续 1 的计数；每次遇到一个 0，如果当前连续的 1 数量大于 0，就记录当前段的数量。
• 使用 流式读取（逐行读取），并使用 内存映射（mmap）来处理大文件。
• 输出结果时，记录连续 1 的段数以及后面紧跟着 0 的数量。

1.2 C++ 代码示例

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

// 统计连续 1 的段数及每段后跟随的 0 的次数
void count_consecutive_ones_and_zeros(const string& filename) {
    ifstream file(filename);
    string line;
    
    int total_one_segments = 0;  // 连续 1 的段数
    int total_zero_after_ones = 0;  // 每段 1 后跟的 0 的次数
    
    while (getline(file, line)) {
        int consecutive_ones = 0;
        bool in_one_segment = false;
        
        for (size_t i = 0; i < line.size(); ++i) {
            if (line[i] == '1') {
                if (!in_one_segment) {
                    in_one_segment = true;
                    total_one_segments++;  // 开始一个新的连续 1 的段
                }
                consecutive_ones++;
            } else {
                if (in_one_segment) {
                    // 结束连续 1 的段，记录后面的 0
                    if (i + 1 < line.size() && line[i + 1] == '0') {
                        total_zero_after_ones++;
                    }
                }
                in_one_segment = false;
                consecutive_ones = 0;
            }
        }
    }
    
    cout << "Total segments of consecutive 1s: " << total_one_segments << endl;
    cout << "Total zeros following 1s: " << total_zero_after_ones << endl;
}

int main() {
    string filename = "big_data.txt";  // 输入文件名
    count_consecutive_ones_and_zeros(filename);
    return 0;
}

1.3 C++ 方案解释

1. 读取数据：我们逐行读取文件，并对每行数据进行处理。
2. 状态机：用一个布尔变量 in_one_segment 来标记是否当前正在遍历连续的 1。
3. 统计：
   • 每遇到一个新的连续 1 段，就增加 total_one_segments 计数器。
   • 如果一个连续 1 后紧接着是 0，则增加 total_zero_after_ones 计数器。
4. 输出结果：最后打印出结果：连续 1 的段数和每个段后跟的 0 的次数。

1.4 优化建议

• 内存映射（mmap）：对于极大文件，可以使用内存映射（mmap）来高效读取文件，不需要将整个文件加载到内存。
• 多线程：可以使用多线程来处理多个文件或多个数据块，从而加速处理过程。

2. Python 方案

2.1 思路

Python 可以利用 流式处理 来避免一次性将数据全部加载到内存。我们将逐行读取数字，使用类似的状态机方法来统计连续的 1 和后跟的 0 的次数。

2.2 Python 代码示例

def count_consecutive_ones_and_zeros(filename):
    total_one_segments = 0  # 连续 1 的段数
    total_zero_after_ones = 0  # 每段 1 后跟随的 0 的次数
    
    with open(filename, 'r') as file:
        for line in file:
            line = line.strip()  # 去掉行尾换行符
            in_one_segment = False
            
            for i in range(len(line)):
                if line[i] == '1':
                    if not in_one_segment:
                        in_one_segment = True
                        total_one_segments += 1  # 新的连续 1 段
                else:
                    if in_one_segment and i + 1 < len(line) and line[i + 1] == '0':
                        total_zero_after_ones += 1  # 连续 1 后面跟 0
                    in_one_segment = False

    print(f"Total segments of consecutive 1s: {total_one_segments}")
    print(f"Total zeros following 1s: {total_zero_after_ones}")


if __name__ == "__main__":
    filename = "big_data.txt"  # 输入文件名
    count_consecutive_ones_and_zeros(filename)

2.3 Python 方案解释

1. 读取数据：通过 open(filename) 逐行读取文件，避免将整个数据加载到内存。
2. 状态机：用 in_one_segment 来标记是否当前在一个连续 1 的段中。
3. 统计：
   • 每次遇到一个新的连续 1 段时，增加 total_one_segments。
   • 如果连续 1 后跟的是 0，则增加 total_zero_after_ones。
4. 输出结果：最终打印出连续 1 的段数和后面紧跟的 0 的次数。

3. 性能考虑与优化

3.1 内存映射（Memory-mapped files）

对于非常大的数据集，可以使用内存映射方式来高效读取数据，避免每次读取都消耗大量的时间。在 C++ 中，使用 mmap，在 Python 中，可以使用 mmap 模块。

3.2 多线程 或 多进程 计算

• 如果计算非常耗时，可以考虑将数据分割成多个部分，使用多线程或多进程并行处理。
• 在 C++ 中，可以使用 std::thread，在 Python 中，可以使用 concurrent.futures.ThreadPoolExecutor。

3.3 批量读取 和 优化文件读取方式

• 对于非常大的文件，可以考虑使用文件的 批量读取 技术（例如，使用 readlines 或按块读取），避免每次读取一行。

4. 总结

通过流式读取和状态机方法，我们能够高效地统计一亿行由 0 和 1 组成的数字中连续出现的 1 的段数以及每段后跟的 0 的次数。这种方法避免了内存的浪费，适用于大规模数据的处理。同时，适当的优化（如多线程、内存映射）可以进一步提升计算性能。