Re: [討論] 給排序過的Array 用最少運算資源找值

看板C_and_CPP (C/C++)作者OnlyRD (里巷人)時間1年前 (2022/06/08 11:50)推噓1(1推 0噓 9→)

留言10則, 2人參與討論串2/2 (看更多)

#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://www.ptt.cc/bbs/C_and_CPP/M.1654660245.A.427.html