blocks|key|75846|text|使用哈希集。它将给出O(1)的查找时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|75847|下面的代码假设您可以将值0保留为“空”值，即不会出现在实际数据中。该解决方案可以针对不是这种情况的情况进行扩展。|offset|length|style|CODE|75848|#define+HASH(x)+(((x+>>+16)+%5E+x)+&+1023)
#define+HASH_LEN+1024
uint32_t+my_hash[HASH_LEN];

int+lookup(uint32_t+value)
{
++++int+i+=+HASH(value);
++++while+(my_hash[i]+!=+0+&&+my_hash[i]+!=+value)+i+=+(i+%2B+1)+%25+HASH_LEN;
++++return+i;
}

void+store(uint32_t+value)
{
++++int+i+=+lookup(value);
++++if+(my_hash[i]+==+0)
+++++++my_hash[i]+=+value;
}

bool+contains(uint32_t+value)
{
++++return+(my_hash[lookup(value)]+==+value);
}|code-block|syntax|javascript|75849|在这个示例实现中，查找时间通常会非常短，但在最坏的情况下可能会达到存储的条目数量。对于实时应用程序，您还可以考虑使用二叉树的实现，这将具有更可预测的查找时间。|75850|entityMap^0|0|C|1|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@$D|S|E|T|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|U|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Use a hash set. It will give O(1) lookup time.

The following code assumes that you can reserve value <code>0</code> as an 'empty' value, i.e. not occurring in actual data.
The solution can be expanded for a situation where this is not the case.

<pre><code>#define HASH(x) (((x &gt;&gt; 16) ^ x) &amp; 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
 int i = HASH(value);
 while (my_hash[i] != 0 &amp;&amp; my_hash[i] != value) i = (i + 1) % HASH_LEN;
 return i;
}

void store(uint32_t value)
{
 int i = lookup(value);
 if (my_hash[i] == 0)
 my_hash[i] = value;
}

bool contains(uint32_t value)
{
 return (my_hash[lookup(value)] == value);
}
</code></pre>

In this example implementation, the lookup time will typically be very low, but at the worst case can be up to the number of entries stored. For a realtime application, you can consider also an implementation using binary trees, which will have a more predictable lookup time.

blocks|key|75911|text|如果事先知道表中的常量集，则可以使用perfect+hashing来确保只对表进行一次访问。完美的散列确定了一个散列函数，该散列函数将每个感兴趣的键映射到一个唯一的槽(该表并不总是密集的，但你可以决定如何去密集你能负担得起的表，而不那么密集的表通常会导致更简单的散列函数)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|75912|通常，针对特定键集的完美散列函数相对容易计算；您不希望计算太长且复杂，因为这会争用时间，也许花在多个探测上会更好。|75913|完美哈希是一种“最大1探测”方案。人们可以推广这个想法，认为应该在计算哈希码的简单性和进行k个探测所需的时间之间进行权衡。毕竟，我们的目标是“总查找时间最短”，而不是最少的探测或最简单的散列函数。然而，我从来没有见过任何人构建k-probes+max散列算法。我怀疑有人可以做到这一点，但这可能是研究。|75914|另一种想法是:如果您的处理器非常快，那么从完美散列到内存的探测可能会控制执行时间。如果处理器不是很快，那么k>1探测器可能是实用的。|75915|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Perfect_hash_function^0|I|F|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|C|$]]|$1|J|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]]]

If the set of constants in your table is known in advance, you can use <a href="http://en.wikipedia.org/wiki/Perfect_hash_function" rel="noreferrer">perfect hashing</a> to ensure that only one access is made to the table. Perfect hashing determines a hash function
that maps every interesting key to a unique slot (that table isn't always dense, but you can decide how un-dense a table you can afford, with less dense tables typically leading to simpler hashing functions).

Usually, the perfect hash function for the specific set of keys is relatively easy to compute; you don't want that to be long and complicated because that competes for time perhaps better spent doing multiple probes.

Perfect hashing is a "1-probe max" scheme. One can generalize the idea, with the thought that one should trade simplicity of computing the hash code with the time it takes to make k probes. After all, the goal is "least total time to look up", not fewest probes or simplest hash function. However, I've never seen anybody build a k-probes-max hashing algorithm. I suspect one can do it, but that's likely research. 

One other thought: if your processor is extremely fast, the one probe to memory from a perfect hash probably dominates the execution time. If the processor is not very fast, than k>1 probes might be practical.

blocks|key|75976|text|在这种情况下，研究Bloom+filters可能是值得的。它们能够快速确定值不存在，这是一件好事，因为2%5E32个可能值中的大多数都不在1024个元素数组中。但是，也有一些误报需要额外检查。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|75977|由于您的表显然是静态的，因此您可以确定Bloom+filter存在哪些误报，并将这些误报放入一个完美的散列中。|75978|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Bloom_filter^0|9|D|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

In this case, it might be worthwhile investigating <a href="https://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom filters</a>. They're capable of quickly establishing that a value is not present, which is a good thing since most of the 2^32 possible values are not in that 1024 element array. However, there are some false positives that will need an extra check.

Since your table is apparently static, you can determine which false positives exist for your Bloom filter and put those in a perfect hash.

blocks|key|4582735|text|如果我的答案已经被回答了，我很抱歉--只是我是一个懒惰的读者。你可以自由地投反对票))|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4582736|1)你可以删除计数器'i‘-只要比较指针，即|4582737|for+(ptr+=+&the_array[0];+ptr+<+the_array%2B1024;+ptr%2B%2B)
{
++++if+(compareVal+==+*ptr)
++++{
+++++++break;
++++}
}
...+compare+ptr+and+the_array%2B1024+here+-+you+do+not+need+validFlag+at+all.|code-block|syntax|javascript|4582738|尽管所有这些都不会带来任何显著的改进，但这样的优化可能是由编译器本身实现的。|4582739|2)正如其他答案已经提到的那样，几乎所有的现代CPU都是基于RISC的，例如ARM。据我所知，即使是现代的英特尔X86+CPU也在内部使用RISC内核(从X86+on+fly编译而来)。RISC的主要优化是流水线优化(以及Intel和其他CPU+)，最大限度地减少代码跳跃。这种优化的一种类型(可能是一种主要的)是“循环回滚”。这是难以置信的愚蠢和高效，即使是英特尔编译器也能做到AFAIK。看起来是这样的：|4582740|if+(compareVal+==+the_array[0])+{+validFlag+=+true;+goto+end_of_compare;+}
if+(compareVal+==+the_array[1])+{+validFlag+=+true;+goto+end_of_compare;+}
...and+so+on...
end_of_compare:|4582741|这种方式的优化是在最坏的情况下管道不会中断(如果数组中没有compareVal+)，所以它尽可能快(当然不包括其他答案中提到的哈希表、排序数组等算法优化，这可能会根据数组大小提供更好的结果。顺便说一句，循环回滚方法也可以在那里应用。我在这里写的是我认为我在其他人中看不到的东西)|4582742|此优化第二部分是通过直接寻址(在编译阶段计算，请确保使用静态数组)获取数组项，且不需要额外的加法操作来从数组的基地址计算指针。这种优化可能没有显著效果，因为AFAIK+ARM架构具有加快阵列寻址速度的特殊功能。但不管怎样，知道你直接在C代码中做得最好总是更好的，对吧？|4582743|由于ROM的浪费，周期回滚可能看起来很笨拙(是的，如果你的主板支持这个功能，你把它放在RAM的快速部分是正确的)，但实际上它是基于RISC概念的速度的公平报酬。这只是计算优化的一个要点--你为了速度而牺牲空间，反之亦然，这取决于你的需求。|4582744|如果您认为1024个元素数组回滚对于您的情况来说太大了，您可以考虑“部分回滚”，例如将数组分成两部分，每部分512项，或4x256，等等。|4582745|3)现代CPU通常支持SIMD操作，例如ARM霓虹灯指令集-它允许并行执行相同的操作。坦率地说，我不记得它是否适合比较操作，但我觉得它可能是，你应该检查一下。谷歌搜索显示，可能也有一些技巧，以获得最大速度，请参阅https://stackoverflow.com/a/5734019/1028256|offset|length|4582746|我希望它能给你一些新的想法。|4582747|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/5734019/1028256^0|0|0|0|0|0|0|0|0|0|0|2Y|17|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1B|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1C|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|1D|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1E|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|1F|8|@]|9|@]|A|$G|H]]|$1|O|3|P|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1H|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1I|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1J|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1K|8|@]|9|@$Y|1L|Z|1M|1|1N]]|A|$]]|$1|10|3|11|5|6|7|1O|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|1P|8|@]|9|@]|A|$]]]|13|$14|$5|15|16|17|A|$18|19]]]]

I'm sorry if my answer was already answered - just I'm a lazy reader. Feel you free to downvote then ))

1) you could remove counter 'i' at all - just compare pointers, ie 

<pre><code>for (ptr = &amp;the_array[0]; ptr &lt; the_array+1024; ptr++)
{
 if (compareVal == *ptr)
 {
 break;
 }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.
</code></pre>

all that won't give any significant improvement though, such optimization probably could be achieved by the compiler itself.

2) As it was already mentioned by other answers, almost all modern CPU are RISC-based, for example ARM. Even modern Intel X86 CPUs use RISC cores inside, as far as I know (compiling from X86 on fly). Major optimization for RISC is pipeline optimization (and for Intel and other CPU as well), minimizing code jumps. One type of such optimization (probably a major one), is "cycle rollback" one. It's incredibly stupid, and efficient, even Intel compiler can do that AFAIK. It looks like:

<pre><code>if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:
</code></pre>

This way the optimization is that the pipeline is not broken for the worst case (if compareVal is absent in the array), so it is as fast as possible (of course not counting algorithm optimizations such as hash tables, sorted arrays and so on, mentioned in other answers, which may give better results depending on array size. Cycles Rollback approach can be applied there as well by the way. I'm writing here about that I think I didn't see in others)

The second part of this optimization is that that array item is taken by direct address (calculated at compiling stage, make sure you use a static array), and do not need additional ADD op to calculate pointer from array's base address. This optimization may not have significant effect, since AFAIK ARM architecture has special features to speed up arrays addressing. But anyway it's always better to know that you did all the best just in C code directly, right?

Cycle Rollback may look awkward due to waste of ROM (yep, you did right placing it to fast part of RAM, if your board supports this feature), but actually it's a fair pay for speed, being based on RISC concept. This is just a general point of calculation optimization - you sacrifice space for sake of speed, and vice versa, depending on your requirements.

If you think that rollback for array of 1024 elements is too large sacrifice for your case, you can consider 'partial rollback', for example dividing the array into 2 parts of 512 items each, or 4x256, and so on.

3) modern CPU often support SIMD ops, for example ARM NEON instruction set - it allows to execute the same ops in parallel. Frankly speaking I do not remember if it is suitable for comparison ops, but I feel it may be, you should check that. Googling shows that there may be some tricks as well, to get max speed, see <a href="https://stackoverflow.com/a/5734019/1028256">https://stackoverflow.com/a/5734019/1028256</a>

I hope it can give you some new ideas.

blocks|key|76151|text|我是哈希法的铁杆粉丝。当然，问题是要找到一种既快速又占用最少内存的高效算法(尤其是在嵌入式处理器上)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|76152|如果您事先知道可能出现的值，则可以创建一个程序，该程序运行多种算法来找到最优的一个-或者更确切地说，为您的数据找到最佳的参数。|76153|我创建了这样一个程序，你可以在this+post中读到它，并获得了一些非常快的结果。16000个条目大致相当于2%5E14，或者平均14次比较，以使用二进制搜索来查找该值。我明确的目标是非常快的查找-平均在<=1.5查找中找到值-这导致了更大的内存需求。我相信使用更保守的平均值(比如<=3)可以节省大量内存。相比之下，在256或1024个条目上进行二进制搜索的平均情况将分别导致8次和10次比较。|offset|length|76154|我的平均查找需要大约60个周期(在使用英特尔i5的笔记本电脑上)，使用通用算法(利用一个除法除以变量)和40-45个周期(使用专门的(可能利用乘法))。这应该转化为在MCU上的亚微秒查找时间，当然这取决于它执行的时钟频率。|76155|如果条目数组跟踪条目被访问的次数，那么它可以在现实生活中进一步调整。如果在计算指数之前，条目数组从访问次数最多到访问次数最少排序，那么它将通过一次比较找到最常出现的值。|76156|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/13898687/the-fastest-way-to-retrieve-16k-key-value-pairs/13899165#13899165^0|0|0|F|9|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@$F|W|G|X|1|Y]]|A|$]]|$1|H|3|I|5|6|7|Z|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|10|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|S]]]]

I'm a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).

If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one - or, rather, the best parameters for your data.

I created such a program that you can read about in <a href="https://stackoverflow.com/questions/13898687/the-fastest-way-to-retrieve-16k-key-value-pairs/13899165#13899165">this post</a> and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups - on average finding the value in &lt;=1.5 lookups - which resulted in greater RAM requirements. I believe that with a more conservative average value (say &lt;=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.

My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.

It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it'll find the most commonly occuring values with a single comparison.

I have an embedded application with a time-critical ISR that needs to iterate through an array of size 256 (preferably 1024, but 256 is the minimum) and check if a value matches the arrays contents. A <code>bool</code> will be set to true is this is the case.

The microcontroller is an NXP LPC4357, ARM Cortex M4 core, and the compiler is GCC. I already have combined optimisation level 2 (3 is slower) and placing the function in RAM instead of flash. I also use pointer arithmetic and a <code>for</code> loop, which does down-counting instead of up (checking if <code>i!=0</code> is faster than checking if <code>i&lt;256</code>). All in all, I end up with a duration of 12.5&nbsp;µs which has to be reduced drastically to be feasible. This is the (pseudo) code I use now:

<pre><code>uint32_t i;
uint32_t *array_ptr = &amp;theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
 if (compareVal == *array_ptr++)
 {
 validFlag = true;
 break;
 }
}
</code></pre>

What would be the absolute fastest way to do this? Using inline assembly is allowed. Other 'less elegant' tricks are also allowed.

Quickly find whether a value is present in a C array?

微控制器

编译器

我有一个具有时间关键型ISR的嵌入式应用程序，它需要迭代大小为256的数组(最好是1024，但256是最小值)，并检查值是否与数组内容匹配。如果是这种情况，bool将被设置为true。微控制器采用恩智浦LPC4357，ARM Cortex M4内核，编译器为GCC。我已经组合了优化级别2 (3更慢)，并将函数放在RAM...

问快速查找C数组中是否存在值？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问快速查找C数组中是否存在值？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问快速查找C数组中是否存在值？
EN