使用字符串作为数组索引（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的索引更接近。

- Cantfindname

---

一开始我误解了你的问题。你所问的问题比我回答的那个问题更有趣 :-) - Sergey Kalinichenko

@Philip：他指的是CPU缓存。显然，内存消耗将保持不变，但如果在时间上紧密访问的元素在内存中靠近，处理数据将会更快。 - Cameron

@PhilipAdler 速度是我的主要关注点，但如果需要增加速度，则内存应该在合理范围内。 - Cantfindname

@Emilien 是的，几乎就是这样，但是“保留昂贵函数调用的结果，并在再次出现相同输入时返回缓存的结果”部分是由系统的缓存内存显式处理的。我只想启用它。 - Cantfindname

@cantfindname：我删除了答案，因为它只解决了单个调用的问题，即在数组中查找一次后，您会得到所有四个“下一个可能值”。显然，您不想再次使用您的字符串转整数函数...一旦您搜索，您期望所有可能的下一个值...递归地。 - user1666959

Answer 1

如果以下假设对于您的问题是正确的，那么您实现的解决方案是最佳的。

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

原因： 当我第一次阅读您的问题时，我得出了以下树形结构：（为简单起见，将您的问题简化为长度为三个字符和只有两个可能字符A和B）。请注意，根节点的最左子节点（在此例中为AAA）始终与根节点（AAA）相同，因此我不会进一步构建该分支。

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

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

• AAA 0
• AAB 1
• ABA 2
• ABB 3
• BAA 4
• BAB 5
• BBA 6
• BBB 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个字符的字符串，其中可能的字符为A B C）。 脚本链接 因此，除非在开始时做出的2个假设是错误的，否则您的解决方案已经考虑了缓存优化。

- Ravichandra Sutrave

Answer 2

我认为我们可以先定义“更接近”的概念。

例如，我们可以定义一个函数F，它接受一种计算字符串索引的方法。然后，F将检查每个字符串的索引，并根据相邻字符串索引的距离返回某个值。

然后，我们可以比较各种计算索引的方法，并找到最佳方法。当然，我们可以先检查较短的字符串。

- Shane Lu