作者OnlyRD (里巷人)
看板C_and_CPP
標題Re: [討論] 給排序過的Array 用最少運算資源找值
時間Wed Jun 8 11:50:43 2022
#include <iostream>
#include <tuple>
#include <utility>
template<int E, int H, int... Rest>
struct find_helper {
static constexpr auto rest() -> std::size_t {
if constexpr(H==E)
return std::tuple_size_v<decltype(std::make_tuple(Rest...))>;
else
return find_helper<E, Rest...>::rest();
}
};
template<int E, int H>
struct find_helper<E, H> {
static constexpr auto rest() -> std::size_t {
if constexpr(H==E)
return 0;
else
return -1;
}
};
template<int E, int... Values>
auto find_first() -> std::size_t {
return sizeof...(Values) - find_helper<E, Values...>::rest() - 1;
}
int main() {
std::cout << find_first<0, 1, 1, 1, 0, 0>();
return 0;
}
如果找得到，回傳index，範圍0～N-1，N為Array 長度。
如果找不到，回傳N。
如果Array為空，編譯錯誤。
前提是Array要編譯期就知道內容。
不過如果你是面試IC廠，我想應該是動態Array。
如果裡面的值都是0跟1
我猜應該是儲存的時候就用shift存成Bits
然後使用找第一個0的bit的指令去找
這是IC廠會幹的事
記憶體量最少、計算最快。
--------------------------
#include <initializer_list>
#include <iterator>
#include <iostream>
template<typename Iter, typename T = typename
std::iterator_traits<Iter>::value_type>
constexpr auto find_helper2(Iter begin, Iter end, const T expected) ->
std::size_t {
Iter start = begin;
while(begin != end) {
if (*begin == expected) return begin - start;
++begin;
}
return end - start;
};
template<typename T>
constexpr auto find_first2(const std::initializer_list<T>& list, const T
expected) -> std::size_t {
return find_helper2(list.begin(), list.end(), expected);
};
int main() {
std::cout << find_first2({1,1,1,0,0}, 0);
return 0;
}
今天測試另一個解法
其實編出來的code效能沒有更好
編譯時間也更長
但看起來"更像"a[5]={1,1,1,0,0}
兩個版本沒用最佳化編譯出來有差距
前一版更好
但如果用O3兩個就完全一樣了
其實可以思考一下
在"現代"C++的效能其實也不輸給C或asm
在gcc最新版x86-64 c++20 O3下編譯只有一行主體
mov eax,0x3
用asm寫code都不見得贏
※ 引述《Kuba4ma ()》之銘言：
: 各位大神好
: 本魯最近在準備某間IC廠的面試
: 在網路上找到這題考古題
: 題目如下
: ```
: 給一個sorted array(ex: a[5]={1,1,1,0,0})，請找出第一個0的位置，請使用能降低CPU
: 跟memory負擔的用量
: ```
: 我能想到的就只有用for loop掃過一遍而已
: 請問還有更好的方法嗎
: 謝謝
-----
Sent from MeowPtt on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.57.210 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1654660245.A.427.html
1F：→ hsnuyi: 如果是IC廠 就是在C裡面內嵌assembly 不是用C++ 06/09 02:29
3F：→ CoNsTaR: 雖然沒用到 asm 06/09 06:08
4F：→ hsnuyi: 如果array大到在DRAM內 其實有很多可討論的... 連CPU外的 06/10 00:09
5F：→ hsnuyi: bus上能傳怎樣的指令都可拿出來檢驗... 06/10 00:09
有具體的例子可以說明嗎?
※ 編輯: OnlyRD (118.166.209.186 臺灣), 06/10/2022 01:07:39
6F：推 CoNsTaR: 編譯時期先算好這個 asm 要怎麼贏？XD 06/10 01:50
7F：→ CoNsTaR: 主要的問題應該還是面試想要考你什麼吧 06/10 01:50
8F：→ hsnuyi: IC設計會考的就不會是template 驗證設計也是用asm打AXI傳 06/10 03:51
9F：→ hsnuyi: 輸上bus 有時還要注意MMU和cache 要用C++解就沒啥好評論 06/10 03:51
10F：→ hsnuyi: 的了 06/10 03:51