作者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/cn.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