java - 将一组随机整数从输入文件分发到 N 个输出(桶)文件的算法

Question

我正在尝试改进我的算法，该算法将输入数据从单个输入文件分发到 N 个输出文件。输入数据按以下方式分布:

例如，如果输入文件包含值 5 2 4 6 3 1 0 8 5 9 并且我有 N = 4 个输出文件，则这些值的分布如下:

• 文件_0: 2 1 0
• 文件_1:5 4 3 5
• 文件_2:6 8
• file_3:9

所以每个值都应该“映射”到 [0, N-1] 范围内的适当文件。这些文件中的每一个稍后都会被排序，正如您所看到的，它们的串联将产生输入值的排序序列。

所有输出文件路径都存储在一个名为 bucket_files 的文件数组中，我在这里想做的是使用某种哈希函数 H(input_value) 将 input_value 映射到 [0, N 范围内的数组索引-1].

我目前的情况是

private static void distributeData(int N, File main_string_file) {
    int min = 1;
    int max = 9;
    long left_interval_border;
    long right_interval_border;

    int input_buff_size = 8;
    File bucket_files[] = new File[N];
    int input_buffer[] = new int[input_buff_size / 2];
    BufferedWriter bucket_file_writers[] = new BufferedWriter[N];
    BufferedReader main_file_reader = new BufferedReader(new FileReader(main_string_file));

    left_interval_border = min;
    long range = (int) Math.ceil(max / N);
    right_interval_border = range;

    for (int i = 0; i < N; i++) {
        bucket_files[i] = new File("/path/to/files/file_" + i + ".txt");
        bucket_file_writers[i] = new BufferedWriter(new FileWriter(bucket_files[i], true));
    }

    try {
        while (main_file_reader.ready()) {
            for (int i = 0; i < input_buffer.length; i++) {
                input_buffer[i] = Integer.parseInt(main_file_reader.readLine());
            }

            for (int i = 1; i <= N; i++) {
                for (int j = 0; j < input_buffer.length; j++) {
                    if (input_buffer[j] >= left_interval_border && input_buffer[j] <= right_interval_border) {
                        bucket_file_writers[i - 1].write(Integer.toString(input_buffer[j]));
                        bucket_file_writers[i - 1].write(System.getProperty("line.separator"));
                    }
                }

                left_interval_border = right_interval_border + 1;
                right_interval_border = left_interval_border + range;
            }

            left_interval_border = min;
            right_interval_border = range;
        }
    }

    catch (EOFException eofe) {
        System.out.println("Reached end of file!");
    }
}

这种方法是我第一个想到的，它很慢，如果输入文件大得多，效果会不好，任何一种更好的解决方案都非常受欢迎:)那个双循环是一个瓶子我想把它换成更好更快的东西。

谢谢!

注释

• 所有文件都是.txt文件，每个值都用新行分隔
• N 至少为 2，最多为一个合理的数字，假设最大为 200
• main_string_file 会更大，并且包含 0 到 Integer.MAX_VALUE-1 范围内的随机值
• min 和 max 是预先设置的(0 和 Integer.MAX_VALUE-1)，这意味着没有专门搜索文件中的实际 min 和 max

Answer 1

根据您所说的分解桶的方式，您的桶大小由 range/(numBuckets-1) 计算得出。范围除以桶数的情况除外。所以你拥有的是:

int bucketSize;
if (range % bucketSize == 0)
    bucketSize = range / numBuckets;
else
    bucketSize = range / (numBuckets-1);

一旦您知道桶的数量和项目的范围，这就是一次性计算。

然后，您可以通过简单的除法计算每个项目的桶。如果项目是 i，则:

int bucket = i/bucketSize;