代码之家 › 专栏 › 技术社区 › Michael

将整数映射为整数的理想数据结构?

data-structures algorithm c

Michael · 技术社区 · 15 年前

我不会详细说明,但我正在尝试实现类似于 Boyer-Moore-Horspool algorithm ,仅使用十六进制颜色值而不是字符(即范围更大)。

以维基百科为例,我最初有:

size_t jump_table[0xFFFFFF + 1];
memset(jump_table, default_value, sizeof(jump_table);

但是,0xffffff显然是 巨大的 数字和这很快导致C SEG故障(但不是堆栈溢出,令人失望)。

基本上,我需要的是一个有效的关联数组,将整数映射为整数。我正在考虑使用哈希表,但是对于每个条目都有一个malloc'd结构,这对我来说似乎太过分了(我也不需要生成哈希,因为每个键都是一个唯一的整数,并且不能有重复的条目)。

有人有什么可供选择的建议吗?我在这方面是否过于务实?

更新

对于那些感兴趣的人,我最终通过 uthash 图书馆。

7 回复 | 直到 15 年前

Stephen Canon 15 年前

0xffffff 太大了,无法在大多数系统上放入堆栈,但绝对可以 malloc 这种大小的缓冲区(至少在当前的计算机上,在智能手机上没有这么大的缓冲区)。您是否应该为此任务执行此操作是一个单独的问题。

编辑: 根据注释,如果您希望常见情况下除了“此颜色不显示在输入中”跳过值以外的条目数量相对较少,那么您应该继续使用哈希图(显然只存储实际显示在输入中的值)。

(忽略先前对其他数据结构的讨论,这些数据结构基于对讨论中的算法的错误记忆——您希望使用哈希表)

Graphics Noob 15 年前

如果要创建的数组(大小为0xffffff)比较稀疏,可以尝试创建一个较小的数组作为一个简单的哈希表,其大小为 0xFFFFFF / N 哈希函数是 hexValue / N (或) hexValue % (0xFFFFFF / N) )不过,你必须有创造力来处理碰撞。

这是我能预见的唯一出路 malloc 惯性导航与制导 struct S.

prime_number 15 年前

您可以在堆上malloc(3)0xffffff大小的块(为了简单起见),并像处理数组一样对它们进行寻址。

至于栈溢出。基本上,程序接收到一个sigsegv,这可能是堆栈溢出或访问非法内存或在只读段上写入等的结果。它们都是在相同的错误消息“分段错误”下抽象出来的。

但是为什么不使用更高级的语言,比如支持关联数组的Python呢?

Brian 15 年前

以可能的速度代价,您可以尝试修改算法,只找到与某个边界对齐的匹配项(每三个或四个符号一次),然后在字节级别执行搜索。

Evan Teran 15 年前

您可以创建一个类似“pages”的稀疏排序数组(本例使用256个“pages”,因此最上面的字节是页码):

int *pages[256]; 

/* call this first to make sure all of the pages start out NULL! */
void init_pages(void) {
    for(i = 0; i < 256; ++i) {
        pages[i] = NULL;
    }
}

int get_value(int index) {
    if(pages[index / 0x10000] == NULL) {
        pages[index / 0x10000] = calloc(0x10000, 1); /* calloc so it will zero it out */
    }
    return pages[index / 0x10000][index % 0x10000];
}

void set_value(int index, int value) {
    if(pages[index / 0x10000] == NULL) {
        pages[index / 0x10000] = calloc(0x10000, 1); /* calloc so it will zero it out */
    }
    pages[index / 0x10000][index % 0x10000] = value;
}

这将在第一次触摸、读取或写入页面时分配页面。

starblue 15 年前

为了避免malloc的开销,可以使用hashtable,其中表中的条目是您的结构,假设它们很小。在您的例子中,一对整数应该足够了,用一个特殊的值来表示表中槽的空性。

David Claridge 15 年前

输出空间中有多少值,即多少 不同的 您映射到的值在0-0xfffff范围内?

使用 randomized universal hashing 您可以使用一个不超过输出空间中值数量2倍的表(对于静态表)来创建一个无冲突哈希函数。