0

我有一个很长的字符串（数千行）。我正在针对字符串运行 RegEx 表达式并尝试识别匹配的行号。但是，如果我的匹配计数很高（例如，10,000），每次查找行号都需要再次搜索 html 字符串，这会变得很昂贵。

我想要做的是事先搜索字符串并构建行号字符位置的哈希表。所以我可以使用 Dictionary 并使用以下代码来查找我的行号。

//find line endings
int lineCount = 0;
for (int charCount = 0; charCount <= html.Length; charCount++)
{
     if (html[charCount] == '\n')
     {
         lineCount++;
         lineEndings.Add(charCount, lineCount);
     }
}

但是，当我运行 RegExes 时，如何搜索这本词典？正则表达式字符位置需要在 lineEndings 字典中的两个值之间。什么是最好/最有效的方法；给定一个带有一组间隔键的字典，给定一个不在键列表中的值，找到下一个最接近的键？

我尝试过的一件事，但我不确定它会如何执行，是

lineEndings.First(n => n.Key >= match.Index).Value
4

2 回答 2

2

当您对“相等”的定义只是“接近”时，字典不起作用。

字典中的项目必须具有交互性，这一点很重要。如果 A = B 和 B = C 那么 A 应该等于 C。如果不是这种情况（事实并非如此，如果平等被定义为“接近”，那么事情就开始崩溃了。

首先，您无法GetHashCode在此处编写有效的实现。让它永远有效的唯一方法是让所有东西都返回相同的值，这意味着无论如何你只是将性能降级为线性搜索。

假设您有一组静态字符串，您可以做的是将它们全部放在一个List或数组中，对它们进行排序，然后使用BinarySearch. 由于数据看起来是静态的，因此将项目添加到查找表的成本很高这一事实应该不是问题。二进制搜索还能够告诉您要搜索的项目是否应该添加到哪里，这意味着您可以转到该位置的索引以找到“下一个”项目，然后减去一个以找到“上一个”项目。

于 2013-09-04T16:58:59.000 回答
1

如果您知道希望键在哪个范围内，则可以将 LINQ 与您的字典一起使用。像这样：

    Dictionary<int, string> Test1 = new Dictionary<int, string>();
    public Form1()
    {
        InitializeComponent();
        Test1.Add(1, "asdf");
        Test1.Add(2, "ghjh");
        Test1.Add(3, "jkl;");
        Test1.Add(4, "qwer");

        int max = 4;
        int min = 1;
        listBox1.DataSource = (from kvp in Test1
                               where (kvp.Key > min && kvp.Key < max)
                               select (kvp.Value)).ToList();

    }

这会从字典中创建一个值集合，其中键在特定范围内。

于 2013-09-04T17:34:43.740 回答