0

我有 100,000 个字符串，每个字符串都有一个固定的有序索引值，如下所示：

Index   String Value
  0     XXXXXXXXXXXXXXXXXXXXX
  1     XXXXXXXXXX
  2     (empty string)
  3     XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  4     XXXXX
  5     XXXXXXXXX
  6     XXXXXXXXXXXXXXX
  7     (empty string)
  8     XX
  9     XXXXXXXXXX
 10     XXXXXXXXXXXXXXXXXXXXXXXXXX
 ...    ...
99999   XXXXXXXXXXXXXXXXXXX

我的数据结构必须恰好包含 100,000 个有序条目，并且某些（或许多）字符串值可能是空的，至少最初是这样。每个索引值都是唯一的（顺序整数），除了空字符串，每个字符串值也是唯一的。为了在我的 UI 中显示，我通常只是填充我的数据结构，将列表框绑定到它（指定 DisplayMember 和 ValueMember）。但在这种情况下，我只想显示不为空的字符串。所以大概，我需要遍历我的数据结构，并以类似于以下的方式将适用的项目添加到列表框中：

foreach (item in MyDataStructure)
{
    if (item.StringValue != string.Empty)
    {
        listBox1.Items.Add(item);
    }
}

能够始终保持每个字符串与其索引值之间的关系对我来说非常重要。如您所料，我的用户将需要添加/编辑/删除字符串。理论上，所有三个操作都归结为同一件事：更新特定索引处的字符串值。要添加新字符串，我需要首先遍历我的数据结构并确保某处有一个空字符串，以便我可以用新字符串替换它。如果不存在空字符串，我的用户将需要首先“编辑”现有字符串或“删除”另一个字符串，因为我们正在处理固定数量的总字符串（100k）。从编程的角度来看，“删除”字符串也只是在我的数据结构中的适当索引处用空/空字符串替换它的问题。

尽我所能预见，我需要一个数据结构，以便于执行以下操作：

  1. 将每个非空字符串的索引和字符串值添加到列表框，并将索引用作 ValueMember，将字符串用作 DisplayMember。
  2. 快速搜索特定索引的数据结构并检索其字符串值
  3. 快速搜索数据结构中的字符串，看看它是否已经存在

考虑到这些事情，任何人都可以推荐一种适合该任务的特定数据结构吗？我最初在想一个带有键/值对的字典来保存每个索引/字符串。然后有人建议只使用数组，因为总大小是固定的，并且数组索引本身也可以用作每个字符串值的索引值。

4

4 回答 4

2

鉴于您的项目数量固定，List并且每个项目都需要一个索引，因此您只需查看一个数组即可。

string[] arr = new string[100000];

您也可以访问LINQ该阵列，以便满足您的条件。

//1
arr.Where(x => !string.IsNullOrEmpty(x)).Select(str => new { value = Array.IndexOf(arr, str), display = str });
//2
string str = arr[index];
//3
arr.Any(x => x == "SomeString");
于 2012-12-12T16:36:04.430 回答
0

我的第一个想法是双字典。基本上保留两个字典：

Dictionary<int, string> // index-->value
Dictionary<string, int> // value-->index

保持字典同步需要做更多的工作，但如果您根据值进行大量搜索，这可能是值得的。

每次搜索值时，使用数组都需要进行线性搜索，所以我认为它不会是最高性能的。

此外，如果您只是不在任一字典中存储空白/空值，那么您可以直接绑定到它们而无需进行任何过滤。

于 2012-12-12T16:34:59.723 回答
0

当然有很多方法可以做到这一点，但是您可以创建一个集合类，而不是SortedDictionary<int, string>用非空字符串封装 a 。

于 2012-12-12T16:35:09.617 回答
0

我认为您以错误的方式进行此操作...您的内存限制为 5mb 并且您将使用整个包含空白字符串的东西？这个数据结构也将保存在 5mb 中吗？这限制了您可以容纳的字符串数量。字符串是如何保存在这个内存中的？某种数据库？我不知道这是用来做什么的，但是您真的认为您的用户会使用所有 100,000 个字符串吗？我对此表示高度怀疑。

我仍然不明白键与字符串值的关系，但对我来说拥有 100,000 个项目的列表确实没有意义，很可能很多都是空字符串。这是对内存的浪费，更不用说它会产生的搜索/插入/删除开销。在考虑速度时，仅保留当前使用的列表会更有意义。

如果可能的话，我建议使用NoSQL数据库。您可以插入用户创建的字符串，从而为您提供索引值，并且可以随意更新字符串。如果用户删除/将字符串设置为空字符串，您可以将其从数据库中删除（或者，由于您非常热衷于这个想法，请将其设置为数据库中的空字符串）。继续插入，直到达到 100,000 个字符串的限制。

于 2012-12-12T17:16:19.457 回答