在数组中查找整数的最快方法是什么? [英] What is the fastest way to find an integer in an array?

问题描述

问题:给定一个userID(整数)，可以快速找到该用户所属的组.组将包含不超过15个用户.另外，我使用的是libev，它无法控制传递给读​​取I/O事件的参数，因此userID(文件描述符/整数)实际上是我只能使用的 .

我的解决方案:对userID进行一次哈希处理，将其哈希到包含groupID和userID对的哈希表中.第二次将groupID散列到包含groupID和15个userID对的数组的散列表中.

该解决方案有效，但这是服务器代码，将被执行不正确的次数.我想知道双重哈希运算是否效率低下，是否有更好的解决方案.

解决方案

您说libev仅给您提供了有限的数据量- ev_io 本身可以处理数据-并得出结论，所有这些都对您有用.有文件描述符.好吧，通常来说，您可能是对的，但是您可以做一个巧妙的窍门.

由于有了libev，您可以自己分配结构，然后让libev初始化它们，所以没有什么阻止您分配太多空间.由于libev不会占用额外的空间，因此您可以在其中放置自己的东西.成功！

那么这在实践中如何工作?您创建一个包含 ev_io 作为第一个成员的新结构，然后将所有其余数据放在其后，如下所示:

  struct my_mutant_io {ev_io句柄；int group_id;}; 

现在，无论您在何处分配 uv_io ，都应分配 my_mutant_io .将数据放入您想要的位置，一旦需要将其传递给libuv函数，只需改用 handle 的地址即可:

  struct my_mutant_io * mutant = malloc(sizeof(struct my_mutant_io));if(！mutant){abort();}突变体-> group_id =/* ... */;ev_io_init(& mutant，some_callback，fd，EV_READ); 

您为libev提供了一个 ev_io ，实际上，它实际上只是较大结构的一部分，这是没有道理的.现在，让我们继续进行回调.您会找回 ev_io 的，但是请稍等！由于 ev_io 是该结构的第一个成员，因此其地址与我们的突变体的地址相同.我们可以将 ev_io * 直接转换回 struct my_mutant_io * 并使用它.(只是不要告诉严格混混的神灵.)

像这样的结构通常被称为警棍.

Problem: Given a userID (integer) quickly find which group the user belongs to. Groups will contain no more than 15 users. Additionally, I am using libev which gives me no control over the parameters passed into the read I/O event, so the userID (file descriptor/integer) is really the only thing I can use.

My solution: hash once on the userID into a hash table containing groupID and userID pairs. Hash a second time on the groupID to a hash table containing groupID and array of 15 userID pairs.

The solution works, but this is server code that will be executed an ungodly amount of times. I wonder if the double hashing will be inefficient and if there may be a better solution.

解决方案

You say that libev only gives you a limited amount of data—the ev_io handle itself—and conclude that all there is useful in there is the file descriptor. Well, normally, you're probably right, but there's a neat trick you can do.

Since with libev, you allocate the structures yourself and then have libev initialize them, there's nothing stopping you from allocating too much space. Since libev won't be touching that extra space, you can put your own stuff in there. Success!

So how does this work in practice? You create a new structure containing an ev_io as the first member, and then put all the rest of your data after it, say like this:

struct my_mutant_io {
    ev_io handle;
    int group_id;
};

Now, wherever you allocate a uv_io, allocate a my_mutant_io instead. Put your data in there however you'd like and once you need to pass it to a libuv function, just take the address of handle instead:

struct my_mutant_io *mutant = malloc(sizeof(struct my_mutant_io));
if(!mutant) {
    abort();
}
mutant->group_id = /* ... */;
ev_io_init(&mutant, some_callback, fd, EV_READ);

You've given libev a ev_io, and it's none-the-wiser that it's actually just a part of a larger struct. Now let's move on to the callback. You'll get your ev_io back, but wait! Since the ev_io is the first member of the struct, its address is the same as the address of our mutant. We can cast the ev_io * right back to a struct my_mutant_io * and use it. (Just don't tell the strict-aliasing gods.)

A struct like this is most commonly called a baton.

这篇关于在数组中查找整数的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！