我正在研究一个Arduino项目,这意味着C++方言目前是C++ 11 的gnu ++ 11超集,并且stdlib不可用(没有元组,没有数组,没有任何东西;命名空间std只是空的!) .
出于优化原因(CPU有16K的FLASH,2K的RAM和这个特殊的低电压版本运行在8MHz)我希望编译器尽可能地预先计算以提供运行时代码,尤其是中断服务程序,"友好的"数据.
现在我想做的是以下内容:
给定一个(唯一的)整数列表,我想提取与任意过滤器匹配的值.然后我想构建一个索引表,允许通过它们的初始索引到达过滤后的元素
例如2,10,4,7,9,3,过滤器value < 8可以产生过滤列表2,4,7,3和索引表0,-1,1,2,-1,3.
只要索引表保持一致,过滤后的数组中元素的顺序就无关紧要了.
我坚持认为我需要不断的数组.动态生成这些数据是微不足道的,但我希望编译器能够完成这项工作,而无需在运行时执行单个指令.
初始列表将由plain提供#define,结果将是常量数组,例如:
#define my_list 2,10,4,7,9,3
constexpr bool filter (int value) { return value < 8; }
const int filtered_list [] = filter_list <filter>(my_list);
const size_t filtered_index[] = filter_index<filter>(my_list);
问题是,如果可行的话,如何使用准系统C++ 11和没有stdlib 来实现这些filter_list和filter_index模板？
我对错误处理不感兴趣,已经处理了空列表或重复值等异常情况.我宁愿看到最简单的可能实现,即使对数据有效性做出了一些假设.
模板,过滤器或初始列表的确切形式也无关紧要.重要的是从唯一的列表定义中获取数组.
例如,我不介意一种语法,其中列表的每个元素是单独声明的(虽然我无法想象它是如何工作的).
我更喜欢拥有一个独立的C++源代码.另一方面,如果Python可以在几十行中实现,需要隐藏模板的页面,包括重写std :: array和std :: tuple,我宁愿写一些外部预处理器.
考虑这个例子
(请注意,这只是我用来说明问题的方法.我很清楚有更有效的方法来解析算术表达式,虽然主题很吸引人,但这与我的实际问题无关.它只是一个半- 现实的例子,如果我可以这样说.
我同意解析器的事情可能会使问题看起来更复杂,但我想不出更抽象的例子).
假设您想要一个简单的表达式解析器.你将从tokenizer中获取一些字符串,其中一些可能是模糊的.
例如,字符串" - "可以表示一元减号或二元减号.
假设您希望获得字符串" - "的所有可能含义.
你可以这样做:
1)定义描述所有可能运算符的排序数组
// types of operators
enum class opType: char { unary, lasso, rasso, none };
// operator descriptors
struct opDesc {
string symbol;
opType type;
char priority;
// partial order comparison
bool operator< (const opDesc& a) const
{
// unary operators first
if (symbol == a.symbol) return type < a.type;
return symbol < a.symbol;
}
// comparison with strings
static bool comp_desc_str (const opDesc& a, const …我有一个非常具体的问题:
我有一个15x50网格上的均匀随机值,我想要散列的样本对应于以任何可能的网格位置为中心的5x5单元格的正方形.
因此,样本的数量可以从25(远离边界,大多数情况)到20,15(靠近边界)到最小值9(在角落中)变化.
因此,即使单元格值是随机的,该位置也会引入序列长度的确定性变化.
哈希表大小是一个小数字,通常在50到20之间.
该函数将在大量随机生成的网格上运行(几百/千),每个网格可能会被调用几千次.网格上的位置可以被认为是随机的.
我想要一个可以尽可能均匀地传播15x50个可能样本的函数.
我试过以下伪代码:
int32 hash = 0;
int i = 0; // I guess i could take any initial value and even be left uninitialized, but fixing one makes the function deterministic
foreach (value in block)
{
hash ^= (value << (i%28))
i++
}
hash %= table_size
但结果虽然不是非常不平衡,但对我来说似乎并不顺利.也许这是因为样本太小,但是情况使得难以在更大的样本上运行代码,而我宁愿不必编写一个完整的测试工具,如果一些计算机知识有一个为我准备的答案:).
我不确定将值二乘二并且使用通用字节散列策略将是最佳解决方案,尤其是因为值的数量可能是奇数.
我已经尝试使用第17个值来表示离网格细胞,但这似乎引入了偏差(来自边界附近的单元格的序列将具有许多"离网格"值).
我不确定什么是测试各种解决方案效率的最佳方法(例如,我应该生成多少网格以了解性能).