编辑“︁外部分治”︁

{{DISPLAYTITLE:外部分治}}

== 概述 ==
'''外部分治'''（External Divide and Conquer）是[[分治算法]]的一种扩展形式，主要用于处理无法完全载入内存的大规模数据集。与经典分治算法不同，外部分治强调将数据分割为适合外部存储（如硬盘）处理的块，通过多轮I/O操作逐步解决问题。该技术在数据库系统、大规模排序、地理信息系统等领域有重要应用。

== 核心思想 ==
外部分治遵循以下三步原则：
# '''分割'''：将大规模数据集划分为多个独立子集，每个子集可单独处理
# '''解决'''：对每个子集递归或迭代地应用算法
# '''合并'''：将子集结果整合为最终解

关键区别在于：
* 数据分割需考虑I/O效率（如按磁盘块大小划分）
* 合并阶段可能需要多轮归并操作
* 需显式管理内存与外部存储的数据交换

== 算法框架 ==
典型伪代码结构：
<syntaxhighlight lang="python">
def external_divide_conquer(data):
    if data_fits_in_memory(data):  # 终止条件
        return solve_in_memory(data)
    
    # 分割阶段
    chunks = split_into_external_chunks(data)
    partial_results = []
    
    # 解决阶段
    for chunk in chunks:
        load_to_memory(chunk)
        partial_results.append(external_divide_conquer(chunk))
        clear_memory()
    
    # 合并阶段
    while len(partial_results) > 1:
        new_results = []
        for pair in group_into_pairs(partial_results):
            merged = merge(pair[0], pair[1])
            new_results.append(merged)
        partial_results = new_results
    
    return partial_results[0]
</syntaxhighlight>

== 复杂度分析 ==
外部分治的时间复杂度通常表示为：
<math>
T(n) = O(\frac{n}{B}) \cdot T(B) + O(\frac{n}{B} \cdot \log_{\frac{M}{B}} \frac{n}{B})
</math>
其中：
* <math>n</math>：数据总量
* <math>B</math>：磁盘块大小
* <math>M</math>：可用内存大小

== 实际案例 ==
=== 外排序（External Sort） ===
最典型的外部分治应用，处理无法装入内存的大文件排序：

<mermaid>
graph TD
    A[原始大文件] --> B[分割为K个块]
    B --> C[逐块读入内存排序]
    C --> D[写入临时文件]
    D --> E[多路归并排序]
    E --> F[最终有序文件]
</mermaid>

示例实现片段：
<syntaxhighlight lang="python">
def external_sort(filename):
    chunk_size = 100_000_000  # 100MB chunks
    temp_files = []
    
    # 分割和排序阶段
    with open(filename) as f:
        while True:
            chunk = list(itertools.islice(f, chunk_size))
            if not chunk:
                break
            chunk.sort()
            temp_file = tempfile.NamedTemporaryFile(delete=False)
            pickle.dump(chunk, temp_file)
            temp_files.append(temp_file.name)
    
    # 归并阶段
    min_heap = []
    for file in temp_files:
        data = pickle.load(open(file, 'rb'))
        heapq.heappush(min_heap, (data[0], data[1:], file))
    
    with open('sorted_output.txt', 'w') as out:
        while min_heap:
            val, rest, file = heapq.heappop(min_heap)
            out.write(str(val) + '\n')
            if rest:
                heapq.heappush(min_heap, (rest[0], rest[1:], file))
            else:
                os.unlink(file)
</syntaxhighlight>

输入/输出示例：
```
输入文件（unsorted.txt）：
593
12
847
...
[10GB数据]

输出文件（sorted_output.txt）：
12
593
847
...
[有序10GB数据]
```

== 优化策略 ==
* '''缓冲技术'''：使用缓冲区减少I/O操作次数
* '''预读取'''：提前加载下一批需要处理的数据
* '''并行处理'''：对独立数据块使用多线程/多进程处理
* '''压缩存储'''：减少磁盘空间占用和I/O时间

== 应用场景 ==
{| class="wikitable"
|-
! 领域 !! 具体应用
|-
| 数据库系统 | 大规模表连接操作、索引构建
|-
| 地理信息系统 | 空间分区查询（如地图渲染）
|-
| 生物信息学 | 基因组序列比对
|-
| 机器学习 | 分布式模型训练
|}

== 挑战与限制 ==
* I/O瓶颈：磁盘访问速度远低于内存
* 数据依赖性：某些问题难以有效分割
* 缓存一致性：多轮处理时需保证数据一致性
* 硬件限制：受存储设备性能影响显著

== 进阶主题 ==
* '''缓存敏感算法'''（Cache-oblivious algorithms）
* '''流式算法'''（Streaming algorithms）与外部分治的结合
* '''分布式外部分治'''（如MapReduce框架）

== 参见 ==
* [[分治算法]]
* [[外排序]]
* [[B树]]（常用于外部分治的数据结构）

[[Category:算法]]
[[Category:数据处理]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:分治算法]]