我创建一个pre-分配与动态内存块的大小，我需要统一连续的内存块。
I'm creating a pre-allocator with dynamic memory chunk size, and I need to unify contiguous memory chunks.
struct Chunk // Chunk of memory
{
Ptr begin, end; // [begin, end) range
}
struct PreAlloc
{
std::vector<Chunk> chunks; // I need to unify contiguous chunks here
...
}
我想一个天真的解决方案，即，根据排序块后，他们的开始，主要做了一通通过矢量检查，如果下一大块的开始等于当前块的结束。我敢肯定，它可以改进。
I tried a naive solution, that, after sorting the chunks based on their begin, basically did a pass through the vector checking if the next chunk's begin was equal to the current chunk's end. I'm sure it could be improved.
有没有好的算法的统一连续范围的？
信息：
大块绝不能重叠。 大块的大小任意大于0。 性能是最重要的因素。 Chunks can never "overlap". Chunks can have any size greater than 0. Performance is the most important factor.推荐答案
这似乎是一个有趣的问题，所以我投资了一些时间在这上面。你拍的形式给出了从天真远。其实它有pretty的好成绩。它可以definetly进一步虽然优化。我将承担块的名单尚未排序，因为你的算法中可能是最佳的话。 优化它我的形式给出是优化的排序本身消除，可以排序期间被组合的组块，从而使排序更快剩余的元素。 下面的code是基本的冒泡排序的修改版本。我也使用std实现您的解决方案::排序只是进行比较。 结果是令人惊讶很好用我的也是。对于1000块的数据集与块的合并的合并排序进行快20倍。 的code的输出是（algo1为std ::排序其次是合并连续元素，算法中2是优化去除可以合并该块排序）：
It seemed like an interesting problem so I invested some time in it. The aproach you took is far from being naive. Actually it has pretty good results. It can definetly be optimized further though. I will assume the list of chunks is not already sorted because your algo is probably optimal then. To optimize it my aproach was to optimize the sort itself eliminating the chunks that can be combined during the sort, thus making the sort faster for the remaining elements. The code below is basically a modified version of bubble-sort. I also implemented your solution using std::sort just for comparison. The results are suprisingly good using my also. For a data set of 10 million chunks the combined sort with the merge of chunks performs 20 times faster. The output of the code is (algo1 is std::sort followed by merging consecutive elements, algo 2 is the sort optimized with removing the chunks that can be merged):
generating input took: 00:00:19.655999
algo 1 took 00:00:00.968738
initial chunks count: 10000000, output chunks count: 3332578
algo 2 took 00:00:00.046875
initial chunks count: 10000000, output chunks count: 3332578
您还可以使用更好的排序算法中像introsort可能改善它。
You can probably improve it further using a better sort algo like introsort.
满code：
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <boostdate_time.hpp>
#define CHUNK_COUNT 10000000
struct Chunk // Chunk of memory
{
char *begin, *end; // [begin, end) range
bool operator<(const Chunk& rhs) const
{
return begin < rhs.begin;
}
};
std::vector<Chunk> in;
void generate_input_data()
{
std::multimap<int, Chunk> input_data;
Chunk chunk;
chunk.begin = 0;
chunk.end = 0;
for (int i = 0; i < CHUNK_COUNT; ++i)
{
int continuous = rand() % 3; // 66% chance of a chunk being continuous
if (continuous)
chunk.begin = chunk.end;
else
chunk.begin = chunk.end + rand() % 100 + 1;
int chunk_size = rand() % 100 + 1;
chunk.end = chunk.begin + chunk_size;
input_data.insert(std::multimap<int, Chunk>::value_type(rand(), chunk));
}
// now we have the chunks randomly ordered in the map
// will copy them in the input vector
for (std::multimap<int, Chunk>::const_iterator it = input_data.begin(); it != input_data.end(); ++it)
in.push_back(it->second);
}
void merge_chunks_sorted(std::vector<Chunk>& chunks)
{
if (in.empty())
return;
std::vector<Chunk> res;
Chunk ch = in[0];
for (size_t i = 1; i < in.size(); ++i)
{
if (in[i].begin == ch.end)
{
ch.end = in[i].end;
} else
{
res.push_back(ch);
ch = in[i];
}
}
res.push_back(ch);
chunks = res;
}
void merge_chunks_orig_algo(std::vector<Chunk>& chunks)
{
std::sort(in.begin(), in.end());
merge_chunks_sorted(chunks);
}
void merge_chunks_new_algo(std::vector<Chunk>& chunks)
{
size_t new_last_n = 0;
Chunk temp;
do {
int last_n = new_last_n;
new_last_n = chunks.size() - 1;
for (int i = chunks.size() - 2; i >= last_n; --i)
{
if (chunks[i].begin > chunks[i + 1].begin)
{
if (chunks[i].begin == chunks[i + 1].end)
{
chunks[i].begin = chunks[i + 1].begin;
if (i + 1 != chunks.size() - 1)
chunks[i + 1] = chunks[chunks.size() - 1];
chunks.pop_back();
} else
{
temp = chunks[i];
chunks[i] = chunks[i + 1];
chunks[i + 1] = temp;
}
new_last_n = i + 1;
} else
{
if (chunks[i].end == chunks[i + 1].begin)
{
chunks[i].end = chunks[i + 1].end;
if (i + 1 != chunks.size() - 1)
chunks[i + 1] = chunks[chunks.size() - 1];
chunks.pop_back();
}
}
}
} while (new_last_n < chunks.size() - 1);
}
void run_algo(void (*algo)(std::vector<Chunk>&))
{
static int count = 1;
// allowing the algo to modify the input vector is intentional
std::vector<Chunk> chunks = in;
size_t in_count = chunks.size();
boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time();
algo(chunks);
boost::posix_time::ptime stop = boost::posix_time::microsec_clock::local_time();
std::cout<<"algo "<<count++<<" took "<<stop - start<<std::endl;
// if all went ok, statistically we should have around 33% of the original chunks count in the output vector
std::cout<<" initial chunks count: "<<in_count<<", output chunks count: "<<chunks.size()<<std::endl;
}
int main()
{
boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time();
generate_input_data();
boost::posix_time::ptime stop = boost::posix_time::microsec_clock::local_time();
std::cout<<"generating input took:t"<<stop - start<<std::endl;
run_algo(merge_chunks_orig_algo);
run_algo(merge_chunks_new_algo);
return 0;
}
我见过下面你提n不是那么高。所以我重新测试1000块，百万运行，使次显著。修改后的冒泡排序仍然执行5倍。基本上，对于1000块总运行时间为3微秒。下面的数字。
I've seen below you mention n is not that high. so I rerun the test with 1000 chunks, 1000000 runs to make the times significant. The modified bubble sort still performs 5 times better. Basically for 1000 chunks total run time is 3 microseconds. Numbers below.
generating input took: 00:00:00
algo 1 took 00:00:15.343456, for 1000000 runs
initial chunks count: 1000, output chunks count: 355
algo 2 took 00:00:03.374935, for 1000000 runs
initial chunks count: 1000, output chunks count: 355
相关推荐
最新文章