c++ - 从文件高效构建排序数组

Question

我有一个数组以二进制文件形式保存在磁盘中，长度为N。数组的每个元素都是唯一，并且值在1 到N 之间(含)。数组中1 到N 之间的所有值都存在。我想在 C++ 中创建一个函数，它接收索引 vector (从零开始)，长度为 n 的 idx ，并从二进制文件中返回排序后的元素指数。

示例:

// saved_array = [2,6,4,10,7,1,9,3,5,8] with N = 10

idx = [0,5,8]; // zero-based index
readAndSortedArray(idx); // returns [1,2,5]

第 0 个元素是 2，第 5 个元素是 1，第 8 个元素是 5。变量 idx 始终已排序，但保存的数组未排序。 idx的长度约为N的1%，N的典型值为10,000。

我的代码目前如下。

vector<int> readAndSortedArray(vector<int> idx) {
    vector<int> elements(idx.size());
    for (int i = 0; i < idx.size(); i++) {
        elements[i] = read_element_from_file(idx[i]);
    }
    sort(elements.begin(), elements.end());
    return elements;
}

由于该函数将被调用很多次(百万次)，因此我希望高效地实现它。

关于如何改进上述算法有什么想法吗？

我的一些想法是:

• 直接将新元素放入正确的位置(即从文件中读取元素后，对新元素进行二分搜索，并将新元素放在该位置)，但这将在 O( n^2) 时间(因为一次插入需要 O(n) 时间)
• 创建一个大小为 N 的空数组，标记新元素的位置，最后从数组中取出非零元素，这将在 中运行O(N) 时间。

Answer 1

这里最简单的优化思想是读取一次数组，然后重用它:

vector <int> readArray() { /* some code to read it from file */ }

vector<int> sortedArray(const vector<int>& arr, const vector<int>& idx) {
    vector<int> elements(idx.size());
    for (int i = 0; i < idx.size(); i++) {
        elements[i] = arr[idx[i]];
    }
    sort(elements.begin(), elements.end());
    return elements;
}

然后在某个地方

vector<int> arr(readArray());
for (/* yor loop */) {
    ....
    some_vec = sortedArray(arr,some_idx)
    ....
}