1

设置：我需要存储与字符串对关联的特征向量。字符串-字符串对编码输入-输出关系。将有相对较少数量的输入X（例如 5），并且对于每个输入x，将有相对较少数量的输出Y|x（例如 10）。

问题是，什么数据结构最快？

其他相关信息：

  1. 每个输入的输出通常不同，并且不能假设每个输入X具有相同数量的输出。
  2. 查找将进行“很多”次（可能是 1000 次）。
  3. 输入将被同样频繁地采样，但对于每个输入，通常会频繁访问一个或两个输出，其余的将不经常访问或根本不访问。

目前我在考虑三种可能：

  1. list-of-lists：使用索引访问外部列表（表示输入X[i]），使用索引访问内部列表（表示输出Y[i][j]）。
  2. hash-of-hashes：与上面相同。
  3. 平散列：key = (input,output)。
4

1 回答 1

0

如果您有字符串，则不清楚如何查找索引以有效地使用列表列表而不使用散列。如果您可以传递一些保持对索引的引用的东西（例如，如果输出集是固定的，并且您可以定义它们的枚举），而不是字符串，列表列表会更快（假设您的意思是列表'不一定是链表'的意义，具有 O(1) 元素访问）。否则，您不妨直接散列并节省自己的精力。

如果不是，那就留下散列的散列与平面散列。你的访问模式是什么样的？您是否总是会要求 X、Y，或者您是否需要访问 X 的所有输出？Hash(X+Y) 可能大致相当于 hash(X) + hash(Y) （两者通常都会遍历所有字母以生成散列。因此单个散列更灵活，稍微（几乎可以肯定可以忽略不计） ) 开销。从 3 开始，听起来你可能需要散列的散列，无论如何。

于 2013-03-10T03:08:46.113 回答