Re: [問題] C語言列舉、指標、標準問題 (x6)
推
09/17 01:24,
09/17 01:24
→
09/17 01:24,
09/17 01:24
→
09/17 01:26,
09/17 01:26
→
09/17 01:26,
09/17 01:26
舉個實際的例子來說好了，以這個陣列為例：
int a[] = {4, 2, 1, 3};
它在記憶體裡面可能是長這樣的：
address 0x100 0x104 0x108 0x10c
value 4 2 1 3
我們把它sort以後，就會變成這樣：
address 0x100 0x104 0x108 0x10c
value 1 2 3 4
接下來我們存取的時候，就是循序的讀下去：0x100 -> 0x104 -> 0x108 -> 0x10c
這樣當然非常好，但是假設data不是int而是欄位很多的物件，一直複製效率就不好
std::vector<int> v{4, 2, 1, 3};
std::sort(v.begin(), v.end());
for (const int x: v)
{
use(x); // 1 2 3 4
}
------------------------------------------------------------------------------
你在文中提到的方法是這樣，假設malloc給的空間很爛：
address 0x10000 0x00004 0x10004 0xffffc
value 4 2 1 3
address 0x00200 0x00204 0x00208 0x0020c
value 0x10000 0x00004 0x10004 0xffffc
int** arr = 0x00200;
我們sort完成以後，就變成了這樣：
address 0x00200 0x00204 0x00208 0x0020c
value 0x10004 0x00004 0xffffc 0x10000
於是我們存取的時候就變成了：0x10004 -> 0x00004 -> 0xffffc -> 0x10000，
這樣可視為隨機存取，造成大量cache miss也難以pre-fetch，效能不好，
當然優點是排序的時候我們只有移動pointer而已:)
std::vector<std::unique_ptr<int>> v;
v.emplace_back(new int(4));
v.emplace_back(new int(2));
v.emplace_back(new int(1));
v.emplace_back(new int(3));
std::sort(boost::make_indirect_iterator(v.begin()),
boost::make_indirect_iterator(v.end()));
for (const auto& p: v)
{
use(*p); // 1 2 3 4
}
------------------------------------------------------------------------------
而你推文所述的方式是這樣的：
address 0x100 0x104 0x108 0x10c
value 4 2 1 3
address 0x200 0x204 0x208 0x20c
value 0x100 0x104 0x108 0x10c
int** arr = 0x200;
因為{4, 2, 1, 3}的空間是一起分配連續的，所以不會有上面那種到處亂放的狀況，
而我們sort完了以後，就變成了：
address 0x200 0x204 0x208 0x20c
value 0x108 0x104 0x10c 0x100
access pattern是：0x108 -> 0x104 -> 0x10c -> 0x100，
一樣排序時我們只需要移動pointer，不用搬動真正的data，
原則上避免了多次malloc所造成的問題，但access pattern還是屬於隨機
std::vector<int> v{4, 2, 1, 3};
std::vector<decltype(v)::iterator> its;
for (auto it = v.begin(); it != v.end(); ++it)
{
its.push_back(it);
}
std::sort(its.begin(), its.end(), // write your own indirect_less
[](decltype(its)::value_type lhs, decltype(its)::value_type rhs)
{
return *lhs < *rhs;
});
for (const auto it: its)
{
use(*it); // 1 2 3 4
}
------------------------------------------------------------------------------
至於哪一個效能會最好就要看你的使用情況了，我只能稍微分析一下他們的差異，
另外第二種作法乍看之下好像沒啥用，但它有個特別之處：
它可以是polymorphic objects的容器(hetrogeneous container)，例如這樣：
struct base
{
// base can even be an abstract class.
virtual void pure_virtual() = 0;
};
struct derived : public base
{
virtual void pure_virtual() override
{
}
};
std::vector<std::unique_ptr<base>> bases;
bases.emplace_back(new derived); // ok!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.252.42
推
09/17 03:04, , 1F
09/17 03:04, 1F
→
09/17 03:06, , 2F
09/17 03:06, 2F
→
09/17 03:07, , 3F
09/17 03:07, 3F
→
09/17 03:19, , 4F
09/17 03:19, 4F
→
09/17 03:20, , 5F
09/17 03:20, 5F
→
09/17 04:56, , 6F
09/17 04:56, 6F
→
09/17 04:58, , 7F
09/17 04:58, 7F
推
09/17 06:01, , 8F
09/17 06:01, 8F
→
09/17 07:33, , 9F
09/17 07:33, 9F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：