c – 如何估算LUT指数？

概述我有一个阵列 ...//a b{860, -30},{853, -29},{846, -28},{838, -27},{830, -26},{822, -25},{814, -24},... 使用C查找给定值的b的最快方法是什么？我想这需要一些近似值？例如,当a = 851时,我想尽快找到-29. 最快的通用算法是二进制搜索.根据映射数组的大 我有一个阵列

...//a      b{860,-30},{853,-29},{846,-28},{838,-27},{830,-26},{822,-25},{814,-24},...

使用C查找给定值的b的最快方法是什么？我想这需要一些近似值？例如,当a = 851时,我想尽快找到-29.

解决方法 最快的通用算法是二进制搜索.根据映射数组的大小,您可以考虑手动编码搜索;对于32码来说这可能是合理的,但我不会变得更大.如果你很幸运的话,在微控制器上,完全扩展的二进制搜索可能会快50％.

但如果映射不是非线性的,那么有一个很好的选择.

将a的范围除以k个相等大小的范​​围,其中k不大于映射数组中的条目数,使得每个范围端点的映射与下一个范围端点相同或比一个更多. (如果这是可能的;这正是我所说的“不太非线性”).创建另一个数组,将每个端点映射到原始数组的索引中. (您只需要索引,而不是端点,因为端点均匀分布.)对于每个范围,底部端点的对应索引值是原始数组中最小值的索引,不小于范围的顶端点.请注意,由于上面提出的要求,每个范围中最多只能有一个值,因此每个端点的索引将始终指向范围结束的a值,以及a的开头的a值.范围将始终是相同或先前的索引.

现在,要查找一个值,首先要找出合适的范围索引,这是一个简单的线性计算((val-minval)/ k),然后通过查找比较的索引将该值与指示的值进行比较.如果该值小于查找的a,则从索引中减去1.然后从索引返回b值.

有关此类算法的示例,请参阅我的答案here.

总结

以上是内存溢出为你收集整理的c – 如何估算LUT指数？全部内容，希望文章能够帮你解决c – 如何估算LUT指数？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。