在3.12版本中 Node拿掉getOrderOfArrival
可是在排序的时后 还是使用std::sort
std::sort(std::begin(_children), std::end(_children), nodeComparisonLess);
以上是否应该改成
std::stable_sort(std::begin(_children), std::end(_children), nodeComparisonLess);
在Android上 Node一多的时后LocalZOrder又都是相同的 有可能会造成不是稳定的排序
不知官方是否比较过
getOrderOfArrival & std::stable_sort
两个的效能
假如std::stable_sort效能较差 是否应该把getOrderOfArrival 加回来
交换与否，对性能有影响？ 这个需要实测一下, 以及两个函数的具体实现
实测VS2015: 100W+数据, std::sort稳定， 相等数据不会发生交换，
NDK也大概看了一下，实现大体思想和MSVC差不多:
std::sort: 内部选择使用插入排序，快速排序，堆排序
std::stable_sort: 内部选择使用插入排序，快速排序，归并排序
以上结论有问题，当某一个节点localZOrder不同时sort不能保证原有顺序
逻辑上: std::stable_sort 或 OrderOfArrival 是合理的
关于性能: std::sort明显快于std::stable_sort
MSVC: release模式， 数据100W, 全相等：
getOrderOfArrival & std::stable_sort 性能比较:
MSVC: release模式， 数据10W:
测试结果:
测试代码:
std::vector<std::pair<int, int>*> vec2;
for (auto i = 0; i < 100000; ++i)
vec2.push_back(new std::pair<int, int>(2, i + 1));
clock_t start = 0;
for (int i = 0; i < 5; ++i) {
start = clock();
std::stable_sort(vec2.begin(), vec2.end(), [](const std::pair<int, int>* l, const std::pair<int, int>* r) {
return l->first < r->first;
});
cocos2d::log("std::stable_sort, test round:%d, %lf seconds used.", i + 1, (clock() - start) / (double)CLOCKS_PER_SEC);
}
for (int i = 0; i < 5; ++i) {
start = clock();
std::sort(vec2.begin(), vec2.end(), [](const std::pair<int, int>* l, const std::pair<int, int>* r) {
return l->first < r->first || ((l->first == r->first) && (l->second < r->second));
});
cocos2d::log("std::sort, test round:%d, %lf seconds used.", i + 1, (clock() - start) / (double)CLOCKS_PER_SEC);
}
经过测试，这里提出优化方案（使用位操作合并localZOrder和OrderOfArrival, 存储为64位整数）
OrderOfArrival优化代码:
std::vector<std::pair<int, int>*> vec2;
for (auto i = 0; i < 100000; ++i)
vec2.push_back(new std::pair<int, int>(2, i + 1));
clock_t start = 0;
for (int i = 0; i < 5; ++i) {
start = clock();
std::stable_sort(vec2.begin(), vec2.end(), [](const std::pair<int, int>* l, const std::pair<int, int>* r) {
return l->first < r->first;
});
printf("std::stable_sort, test round:%d, %lf seconds used.\n", i + 1, (clock() - start) / (double)CLOCKS_PER_SEC);
}
for (int i = 0; i < 5; ++i) {
start = clock();
std::sort(vec2.begin(), vec2.end(), [](const std::pair<int, int>* l, const std::pair<int, int>* r) {
return *(long long*)l < *(long long*)r;
});
printf("std::sort, optimize orderOfArrival storage, test round:%d, %lf seconds used.\n", i + 1, (clock() - start) / (double)CLOCKS_PER_SEC);
}
X64程序测试结果, X86没明显性能提升
神人啊!!!
希望官方可以看到这篇文章
谢谢各位，已经合并了。