c++ - 处理大型数据集 - 算法结果与 1k 条目测试匹配，但在 100 万条目测试中失败 - 相同的算法

Question

问题是什么: 我正在解析一个文件，该文件可以是 1k 行文件或 100 万行文件。我的 1k 文件的输出数据与预期结果 1:1 匹配，但我的 100 万行文件给出了错误的结果。

我的算法可能出了什么问题，会产生如此奇怪的结果？

算法解释

这应该返回的是一组例如 100 万个值(用于某些计算以计算确定分数的结果的值)中按升序排列的前 10 个结果

这是我执行计算的算法。

std::vector<ResultType> circularSubvectorMatch(const unsigned int vector_size, std::vector<float>* searchVector, VectorsMap* circularVector, const unsigned int n, unsigned int begin_index, unsigned int end_index, unsigned int shm_start, unsigned int shm_end, float* shm, const bool is_test){
    unsigned int i, j, row_index;
    const unsigned int item_size = (*circularVector).size();
    //vector for the returned top N results;
    std::vector<ResultType> results;
    results.reserve(n);
    ResultType one;
    std::vector<float> tmp;
    float x, y, dist, dist_tmp;
    int offset;

    //iterate over the whole set of vectors parsed from the file.
    for (row_index=begin_index; row_index < end_index; row_index++) {
        //get a copy of the the vector at position row_index and remove it
        tmp = (*circularVector).at(row_index);
        //get the first and second key and erase them
        x = tmp.at(0);
        tmp.erase(tmp.begin());
        y = tmp.at(0);
        tmp.erase(tmp.begin());

        //run through every vector point at steps of 5
        for(i=0; i<VECTOR_COUNT; i+=5){
            dist = 0;
            offset = i;
            dist_tmp = 0;
            //loop through the vector size(9,11,17,29)
            for(j=0; j<vector_size; j++){
                dist_tmp = fabs((*searchVector).at(j) - tmp.at((j+i)%360));
                dist += dist_tmp;
            }

            //put the result into the structure

            one.x = x;
            one.y = y;
            one.offset = i;
            one.dist = dist;

            //Begins min heap process
            if(results.size() < 10){
                results.push_back(one);
            }
            // Compare it to the max element in the heap 
            else if (one < results.front()) {
                 // Add the new element to the vector
                 results.push_back(one);
                 // Move the existing minimum to the back and "re-heapify" the rest
                 std::pop_heap(results.begin(), results.end());
                 // Remove the last element from the vector
                 results.pop_back();
            }
        }
    }
    //sort to fix the min heap operations
    std::sort(results.begin(), results.end());
    results.resize(n);
    int count = 0;

    //if we are not running a test, save to memory
    if(!is_test){
        for(i=shm_start; i<shm_end; i++){
            shm[i] = results.at(count).x;
            shm[i+1] = results.at(count).y;
            shm[i+2] = results.at(count).offset;
            shm[i+3] = results.at(count).dist;
            count++;
            i+=3;
        }
    }
    return results;
}

Answer 1

也许你可以使用优先级队列。每次计算一行后，将值放入队列中。如果队列的大小为11，则从队列中删除最小值。处理完所有行后，只需删除队列中的 10 个值即可。