c - 如何优化MAC的搜索

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 4 年前。

Improve this question

我必须加快在数组(大小:32k)中搜索 MAC 地址的速度。我想从中获得更好的性能，我编写了一些示例代码来显示问题(请注意，阵列中的 MAC 将是随机数(随机端口、随机 VLAN)并且没有很好地排序(如示例代码)。现在我正在寻找如何改进的建议，即加快速度:

#include <stdio.h>
#include <string.h>

#define MAX_MAC 32768
typedef unsigned char l2_mac_t[6];
typedef struct l2_s {
    int prt;
    int vln;
    l2_mac_t mac;
}l2_t;
int find_mac(int port, int vlan, l2_mac_t mac);
void fill_mac(void);

static l2_t arr[MAX_MAC] = {0};

int main (void) {
    int i = 0;
    int res = 0;
    fill_mac();
    for (i=0;i<MAX_MAC;i++) {
        res = find_mac(arr[i].prt,arr[i].vln,arr[i].mac);
        if (res%1000 == 0 )
            printf("Got MAC %d\n",res);
    }

}
int find_mac(int port, int vlan, l2_mac_t mac) {
    int i = 0;

    for (int i = 0;i< MAX_MAC; i++) {
        if (arr[i].prt == port) {
            if (arr[i].vln == vlan) {
                if (memcmp(arr[i].mac,mac,sizeof(l2_mac_t)) == 0 ) {
                //found
                    return i;
                }
            }
        }
    }
}

void fill_mac(void) {
    int i = 0;
    for (i=0;i<MAX_MAC; i++) {
        arr[i].prt = 4;
        arr[i].vln = 10;
        arr[i].mac[5] = i%255;
        arr[i].mac[4] = i%65025;

    }
}

下面是收到一些评论后编辑的代码:

好的，

我打算使用哈希并想出以下内容(这给了我一个段错误，因为它不想在 init() 中分配这么多内存)。另外，这感觉有点像使用大锤，一定有比下面的 MacSum() 更好的方法来散列它。 ，欢迎任何建议!

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_MAC 32768

#define MacSum(x)   (x)[0]*(2^24) \
                   +(x)[1]*(2^20) \
                   +(x)[2]*(2^16) \
                   +(x)[3]*(2^12)\
                   +(x)[4]*(2^8)\
                   +(x)[5]


typedef unsigned char l2_mac_t[6];
typedef struct l2_s {
    int prt;
    int vln;
    l2_mac_t mac;
}l2_t;

static unsigned short *L2Hash=0;

int find_mac(int port, int vlan, l2_mac_t mac);
void fill_mac(void);
void init(void);

static l2_t arr[MAX_MAC] = {0};

int main (void) {
    int i = 0;
    int res = 0;
    init();
    fill_mac();
    for (i=0;i<MAX_MAC;i++) {
        res = find_mac(arr[i].prt,arr[i].vln,arr[i].mac);
        /*if (res%1000 == 0 )
            printf("Got MAC %d\n",res);*/
    }

}
int find_mac(int port, int vlan, l2_mac_t mac) {
    int i = 0;
    int key = 0;

    key = MacSum(mac);
    if (memcmp(arr[key].mac,mac,sizeof(l2_mac_t)) == 0 ) {
        return key;
    } else {
        for (int i = 0;i< MAX_MAC; i++) {
            if (arr[i].prt == port) {
                if (arr[i].vln == vlan) {
                    if (memcmp(arr[i].mac,mac,sizeof(l2_mac_t)) == 0 ) {
                        return i;
                    }
                }
            }
        }
    }
}

void fill_mac(void) {
    int i = 0;
    int key = 0;
    for (i=0;i<MAX_MAC; i++) {
        arr[i].prt = 4;
        arr[i].vln = 10;
        arr[i].mac[5] = i%255;
        arr[i].mac[4] = i%65025;
        key = MacSum(arr[i].mac);
        L2Hash[key] = i;
    }
}

void init(void) {
    static int init = 0;
    if (init)
        return;
    L2Hash = (unsigned short*) malloc(0xffffffffffff*sizeof(unsigned short));
}

有关问题的进一步更新，请向下滚动到第二个答案

Answer 1

文体注释:嵌套的 if() 很难阅读。有些人更喜欢:

<小时/>

int find_mac(int port, int vlan, l2_mac_t mac) {
    int i = 0;

    for (int i = 0;i< MAX_MAC; i++) {
        if (arr[i].prt != port) continue;
        if (arr[i].vln != vlan) continue;
        if (memcmp(arr[i].mac,mac,sizeof(l2_mac_t)) continue;
        //found
        return i;
    }
return WHAT; //!!11!!1
}

<小时/>

[这应该是一条评论，但我需要格式。]