代码之家 › 专栏 › 技术社区 › Georgi Angelov

C++-读取1000个浮点数,并将它们插入大小为10的向量中,只保留最小的10个数字

queue vector data-structures sorting c++

Georgi Angelov · 技术社区 · 12 年前

所以我对c++很陌生,我不确定是否已经创建了一个数据结构来促进我正在尝试做的事情(所以我不会重新发明轮子):

我想做什么

我正在读取一个文件,需要解析该文件,对该文件每行的每个浮动值进行一些计算,并按升序返回该文件的前10个结果。

我要优化什么 我处理的是一个1k文件和一个190万行文件,所以对于每一行,我会得到一个大小为72的结果,所以在1k行中,我需要分配72000个元素的向量,对于190万行。。。你明白了。

到目前为止我所拥有的

我目前正在处理一个结果向量,然后将其排序并调整为10。

const unsigned int vector_space = circularVector.size()*72;
//vector for the results
std::vector<ResultType> results;
results.reserve(vector_space);

但这是极其低效的。

* 我想完成的* 我只想保留一个大小为10的向量,每当我执行计算时,我会简单地将值插入向量中,并删除向量中最大的浮点,从而按升序保持前10个结果。

c++中是否已经存在这样的结构?

谢谢

4 回复 | 直到 12 年前

Tristan Brindle 12 年前

编辑: 更改为使用最低的10个元素,而不是最高的元素,因为问题现在明确了需要哪些元素

您可以使用 std::vector 共10个元素 最大堆 ,其中元素被部分排序,使得第一个元素始终包含最大值。请注意,以下内容都是未经测试的,但希望它能让您开始。

// Create an empty vector to hold the highest values
std::vector<ResultType> results;

// Iterate over the first 10 entries in the file and put the results in the vector
for (... ; i < 10; i++) {
    // Calculate the value of this row
    ResultType r = ....
    // Add it to the vector
    results.push_back(r);
}

// Now that the vector is "full", turn it into a heap
std::make_heap(results.begin(), results.end());

// Iterate over all the remaining rows, adding values which are lower than the
// current maximum
for (i = 10; .....)  {
    // Calculate the value for this row
    ResultType r = ....

    // Compare it to the max element in the heap
    if (r < results.front()) {
         // Add the new element to the vector
         results.push_back(r);
         // 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();
    }
}

// Finally, sort the results to put them all in order
// (using sort_heap just because we can)
std::sort_heap(results.begin(), results.end());

user207421 12 年前

对你想要的是 优先级队列 或堆定义为删除最低值。如果插入后的大小大于10,则只需执行这样的删除。您应该能够使用STL类来实现这一点。

yinqiwen 12 年前

只需使用std::set即可,因为在std::set中,所有值都从最小值到最大值排序。

void insert_value(std::set<ResultType>& myset, const ResultType& value){
    myset.insert(value);
    int limit = 10; 
    if(myset.size() > limit){
       myset.erase(myset.begin());
    }
}

HadeS 12 年前

我认为MaxHeap可以解决这个问题。

1- Create a max heap of size 10.
2- Fill the heap with 10 elements for the first time.
3- For 11th element check it with the largest element i.e root/element at 0th index.
4- If 11th element is smaller; replace the root node with 11th element and heapify again.

重复相同的步骤,直到解析完整个文件。