Java位图排序与归并排序

短命女 2022-12-13 12:58 75阅读 0赞

### 文章目录 ###

*  Java位图排序与归并排序
 *   *  前言
     *  位图数据结构
     *  比较位图排序与归并排序
     *   *  生成一个混排的测试文件
         *  归并排序
         *  位图排序
         *  结果比较
         *  用时比较
     *  位图排序的限制

# Java位图排序与归并排序 #

## 前言 ##

在《编程珠玑》一书的“第1章 开篇”中描述了如何使用位图（bit map）的数据结构来在有限内存空间时进行排序，即位图排序。

本文描述了在Java8中如何进行位图排序，并比较了位图排序和归并排序的效率。

## 位图数据结构 ##

> 可使用一个20位（bit）长的字符串来表示一个所有元素都小于20的简单的非负数整数集合。
> 
> 例如，可以用如下字符串来表示集合 \{1, 2, 3, 5, 8, 13\}：
> 
> 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

Java中使用BitSet来表示位图（bit map）数据结构：

@Test
    public void test_bit_set() { 
        BitSet bitSet = new BitSet(20);
        bitSet.set(1);
        bitSet.set(2);
        bitSet.set(3);
        bitSet.set(5);
        bitSet.set(8);
        bitSet.set(13);
    
        System.out.println(bitSet.toString());
        System.out.println(convertBitSetToBinaryString(bitSet, 20));
    }
    
    private static String convertBitSetToBinaryString(BitSet bitSet, int numOfBits) { 
        return IntStream.range(0, numOfBits)
          .mapToObj(i -> bitSet.get(i) ? "1" : "0")
          .collect(Collectors.joining(" "));
    }

## 比较位图排序与归并排序 ##

为简洁起见，下面的示例代码省去了计算用时的代码，比如：

Instant startTime = Instant.now();
    ...
    Instant endTime = Instant.now();
    System.out.printf("Elapsed time: %d ms", Duration.between(startTime, endTime).toMillis());

### 生成一个混排的测试文件 ###

生成一个顺序被打乱的测试文件：

*  每行一个正整数，正整数范围为\[1000000, 10000000)
 *  一共900万行

生成的测试文件示例：

@Test
    public void test_produce_numbers_shuffle() throws IOException { 
        List<String> list = IntStream.range(1000000, 10000000).boxed().map(x -> x.toString()).collect(Collectors.toList());
        Collections.shuffle(list);
        Files.write(path, list, StandardCharsets.UTF_8);
    }

说明：

*  用`IntStream.range(1000000, 10000000)` 来限定整数范围。
 *  用`Collections.shuffle(list)` 来混排（打乱排序）。
 *  在终端用`less numbers.txt | wc -l` 的命令检查文件行数为900万行。
 *  在终端用`ll -h`查看文件大小，生成的numbers.txt文件大小为69MB。
 *  程序用时大约为10秒，还是比较快的。

### 归并排序 ###

采用Java的`Collections.sort`归并排序（merge sort）作为基准：

@Test
    public void test_sort_file_via_collection_sort() throws IOException { 
        List<String> lines = Files.readAllLines(path);
        Collections.sort(lines);
        Files.write(collectionSortedPath, lines, StandardCharsets.UTF_8);
    }

说明：

*  先将硬盘上的numbers.txt逐行读取直到全部加载到内存的lines列表中。
 *  用`Collections.sort`对lines列表作归并排序。
 *  将排序后的lines列表写入到collection\_sorted\_numbers.txt中。

各阶段用时如下：

Elapsed time for reading all lines: 9166 ms 
    Elapsed time for sorting: 11383 ms 
    Elapsed time for writing file: 2285 ms 
    Total elapsed time: 22840 ms

### 位图排序 ###

用Java8的BitSet和Stream来作位图排序：

@Test
    public void test_sort_file_via_bit_set_sort() throws IOException { 
        // Initialize a bit set
        int lineCount = (int) Files.lines(path, StandardCharsets.UTF_8).count();
        BitSet bitSet = new BitSet(lineCount);
    
        // Insert present elements into the bit set
        Files.lines(path, StandardCharsets.UTF_8).map(Integer::parseInt).forEach(bitSet::set);
    
        // Write from bit set to sort output file
        try (Writer out = Files.newBufferedWriter(bitSetSortedPath, StandardCharsets.UTF_8, StandardOpenOption.APPEND) ) { 
                bitSet.stream().mapToObj(i -> i + System.lineSeparator()).forEach(line -> { 
                    try { 
                        out.append(line);
                    } catch (IOException e) { 
                        e.printStackTrace();
                    }
                });
            }
    }

说明：

*  创建一个和numbers.txt文件行数（900万）一样的位长的BitSet，默认每位都为0。
 *  用`File.lines()`方法获得一个`Stream<String>` ，再计算文件中的行数。该方法为懒加载，并未一次性将文件的全部内容都加载到内存中，而是用到的内存才加载到内存中。
 *  用`File.lines()`方法获得一个`Stream<String>` ，再将每一行从字符串转换成整数，逐个写入到BitSet中。
 *  将BitSet转换成IntStream，再将每个整数转换成字符串，再将每个字符串写入到bit\_set\_sorted\_numbers.txt文件中。
 *  用BufferedWriter方式将每一行写入文件中

各阶段用时如下：

Elapsed time for initializing bit set: 1285 ms 
    Elapsed time for setting bit set: 2227 ms 
    Elapsed time for writing file: 1319 ms 
    Total elapsed time: 4839 ms

如果不考虑内存使用限制，也可以一次性将BitSet转换成lines列表，再写入到文件中：

List<String> lines = bitSet.stream().mapToObj(String::valueOf).collect(Collectors.toList());
    Files.write(bitSetSortedPath, lines, StandardCharsets.UTF_8);

### 结果比较 ###

用`ll`命令比较3个文件，可以看到文件大小都一样。

用`head`和`tail`命令查看bit\_set\_sorted\_numbers.txt的头和尾的几行，证明是有序的。

用`diff bit_set_sorted_numbers.txt collection_sorted_numbers.txt`命令比较两种排序的输出文件，是完全一致的。

### 用时比较 ###

在本例中，归并排序大约用时23秒，而位图排序只大约用时5秒：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>归并排序</th> 
   <th>位图排序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>阶段1：读文件</td> 
   <td>reading all lines: 9166 ms</td> 
   <td>initializing bit set: 1285 ms</td> 
  </tr> 
  <tr> 
   <td>阶段2：排序</td> 
   <td>sorting: 11383 ms</td> 
   <td>setting bit set: 2227 ms</td> 
  </tr> 
  <tr> 
   <td>阶段3：写文件</td> 
   <td>writing file: 2285 ms</td> 
   <td>writing file: 1319 ms</td> 
  </tr> 
  <tr> 
   <td>总用时</td> 
   <td>22840 ms</td> 
   <td>4839 ms</td> 
  </tr> 
 </tbody> 
</table>

说明：

*  阶段1: 归并排序需要读取硬盘文件的全部内容到内存中，而位图排序只需要计算文件的行数，因此位图排序较快。
 *  阶段2:位图排序只是将指定位置设为true或false，不需要真正地去排序，因此位图排序较快。
 *  阶段3:两种排序方法写入文件的用时差不多。

## 位图排序的限制 ##

位图排序只适用于某些特殊的场景：

*  输入数据限制在较小的范围 （本例为900万位）。
 *  数据没有重复（本例中数据没有重复）。
 *  对每条记录而言，除了单一整数外，没有任何其他关联数据（本例数据为1000000 ~ 9999999的正整数）。