使用字符串索引数组(C)

Question

我有一个无符号整数数组,每个整数对应一个12个字符的字符串,可以包含4个不同的字符,即'A','B','C','D'.因此,该阵列将包含4 ^ 12 = 16777216个元素.数组中元素的排序是任意的; 我可以选择哪一个对应于每个字符串.到目前为止,我已经实现了这一点:

unsigned int my_array[16777216];
char my_string[12];
int index = string_to_index(my_string);

my_array[index] = ...;

string_to_index()简单地为每个字符分配2位,如下所示:A - > 00,B - > 01,C - > 10,D - > 11例如,ABCDABCDABCD对应索引(000110110001101100011011)₂ =(1776411)₁₀

但是,我知道一个事实是,用于访问数组的每个字符串都是前一个字符串,它向左移动了一个新的最后一个字符.例如,在我使用ABCDABCDABCD访问后,下一次访问将使用BCDABCDABCDA或BCDABCDABCDB,BCDABCDABCDC,BCDABCDABCDD.

所以我的问题是:有没有更好的方法来实现string_to_index函数来考虑最后这个事实,以便连续访问的元素在数组中更接近？我希望通过这样做来提高我的缓存性能.

编辑:也许我不太清楚:我正在寻找一个完全不同的字符串来索引对应方案,以便ABCDABCDABCD和BCDABCDABCDA的索引更接近.

Answer 1

如果以下假设适用于您的问题，那么您实施的解决方案就是最好的解决方案。

1. 对于每个有效字符，以相等的概率随机选择下一个字符串的最右边的字符
2. 序列的开始并不总是相同的（它是随机的）。

原因：当我第一次读到你的问题时，我想到了以下树：（为了简单起见，将你的问题减少到长度为三个字符的字符串，并且只有 2 个可能的字符 A 和 B）请注意，根节点的左子节点（在本例中为 AAA） ）始终与根节点（AAA）相同，因此我不会进一步构建该分支。

                      AAA
                     /  \
                        AAB       
                       /  \         
                     ABA    ABB
                    /  \    /   \ 
                 BAA   BAB  BBA  BBB

在该树中，每个节点都有其下一个可能的序列作为子节点。为了改进缓存，您需要使用广度优先遍历来遍历这棵树，并以相同的顺序将其存储在数组中。对于上面的树，我们得到以下字符串索引组合。

• AAA 0
• 氨基苯甲酸1
• ABA 2
• ABB 3
• BAA 4
• 巴布5
• 工商管理学士6
• 血脑屏障7

假设 value(A) = 0 且 value(B) = 1，则指数可以计算为

index = 2^0 * (value(string[2])) +  2^1 * (value(string[1])) + 2^2 * (value(string[0]))

这与您正在使用的解决方案相同。我编写了一个 python 脚本来检查其他组合（例如长度为 4 个字符的字符串，其中 ABC 作为可能的字符）。脚本链接

因此，除非开始时所做的两个假设是错误的，否则您的解决方案已经考虑了缓存优化。