使用二叉搜索子字符串搜索数组字符串

本文关键字：字符串 搜索 数组 | 更新日期: 2023-09-27 18:34:15

我有一个文件.txt包含大约 200,000 条记录。

每条记录的格式为 123456-99-文本。123456是唯一的帐号，99 是我需要的位置代码(它从 01 更改为 99(，文本无关紧要。这些帐号按顺序排序，并在文件中按 ac(111111、111112、111113 等(使用换行符。

我制作了一个视觉工作室文本框和搜索按钮，让某人搜索帐号。帐号实际上是 11 位数字，但只有前 6 位很重要。我把它写成字符串actnum = textbox1.text.substring(0,6)

我写了一篇foreach (string x in file.readline('file.txt'))，上面有一个if (x.contains(actnum))然后string code = x.substring(8,2))声明。

该程序运行良好，但是因为如果有人搜索不存在的帐号或列表底部的数字，则记录太多，因此程序会锁定 10 秒，然后转到"找不到数字"else 语句，或者永远需要很长时间才能找到最后一条记录。

我的问题：

阅读有关二进制搜索的信息，我试图尝试一个没有多大成功。我似乎无法让数组或文件像合法的二进制搜索一样运行。有没有办法从 textbox1 中获取 6 位数字 actnum，将其与 6 位帐号的数组子字符串进行比较，然后从该特定行中获取子字符串 99 代码？

二进制搜索将有很大帮助！我可以拿 555-555 并将其与记录文件的上半部分或下半部分进行比较，然后继续搜索，直到我细化我需要的行，抓住整行，然后将 99 子串起来。我遇到的问题是我似乎无法获得文件的正确整数转换，因为它同时包含数字和文本，因此我无法正确使用 <、>、= 符号。

对此的任何帮助将不胜感激。我目前拥有的程序实际上可以工作，但有时非常慢。

使用二叉搜索子字符串搜索数组字符串

作为一种可能的解决方案(不一定是最好的(，您可以将记录 ID 添加到Dictionary<string, int>(如果所有记录 ID 都是数字，甚至可以添加到Dictionary<long, int>(，其中每个键是一行的 ID，每个值是行索引。当您需要查找特定记录时，只需查找字典(它将为您进行有效的查找(并为您提供行号。如果该项不存在(不存在 ID(，则不会在字典中找到它。

此时，如果文件中存在记录 ID，则您有一个行号 - 您可以将整个文件加载到内存中(如果它不是太大(，或者只是寻找正确的行并读取数据所在的行。

为此，您必须至少遍历一次文件，并从所有行中收集所有记录 ID 并将它们添加到字典中。您不必实现二叉搜索 - 字典将在内部为您执行查找。

编辑：

如果你不需要来自特定行的所有数据，只需要一位(如你提到的位置代码(，你甚至不需要存储行号(因为你不需要回到文件中的行( - 只需将位置数据存储为字典中的值。

我

个人仍然会存储行索引，因为根据我的经验，此类项目开始时很小，但最终会收集特征，并且在某些时候您必须拥有文件中的所有内容。如果您预计随着时间的推移会发生这种情况，只需将每一行的数据解析为数据结构并将其存储在字典中 - 这将使您的未来生活更简单。如果你非常确定你永远不需要比一点信息更多的数据，你可以把数据本身藏在字典里。

下面是一个简单的示例(假设您的记录 ID 可以解析为long(：

public class LineData
{
    public int LineIndex { get; set; }
    public string LocationCode { get; set; }
    // other data from the line that you need
}
// ...
// declare your map
private Dictionary<long, LineData> _dataMap = new Dictionary<long, LineData> ();
// ...
// Read file, parse lines into LineData objects and put them in dictionary
// ...

要查看记录 ID 是否存在，只需调用 TryGetValue() ：

LineData lineData;
if ( _dataMap.TryGetValue ( recordID, out lineData ) )
{
    // record ID was found
}

这种方法基本上将整个文件保存在内存中，但所有数据只解析一次(在开始时，在构建字典期间(。如果此方法使用太多内存，只需将行索引存储在字典中，然后在找到记录并动态解析行时返回到文件。

您不能真正对文件进行二进制搜索。ReadLine，因为您必须能够以不同的顺序访问这些行。 相反，您应该将整个文件读入内存(文件。ReadAllLines将是一个选项(

假设您的文件按子字符串排序，您可以创建一个实现 IComparer 的新类

public class SubstringComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return x.Substring(0, 6).CompareTo(y.Substring(0, 6));
        }
    }

然后你的二叉搜索将如下所示：

int returnedValue = foundStrings.BinarySearch(searchValue, new SubstringComparer());

假设文件不经常更改，那么您可以使用在更快的时间内处理搜索的结构将整个文件加载到内存中。如果文件可以更改，那么您将需要决定重新加载文件的机制，无论是重新启动程序还是更复杂的过程。

看起来您正在寻找完全匹配(搜索123456只会产生一条标记为 123456 的记录(。如果是这种情况，那么您可以使用 Dictionary .请注意，要使用字典，您需要定义键和值类型。看起来在您的情况下，它们都会string.

虽然我没有找到更好的搜索类型的方法，但我确实设法了解了嵌入式资源，这大大加快了程序的速度。扫描整个文件现在只需几分之一秒，而不是 5-10 秒。发布以下代码：

   string searchfor = textBox1.Text
    Assembly assm = Assembly.GetExecutingAssembly();
    using (Stream datastream = assm.GetManifestResourceStream("WindowsFormsApplication2.Resources.file1.txt"))
    using (StreamReader reader = new StreamReader(datastream))
    {
        string lines;
        while ((lines = reader.ReadLine()) != null)
        {
            if (lines.StartsWith(searchfor))
            {
                label1.Text = "Found";
                break;
            }
            else
            {
                label1.Text = "Not found";
            }
        }
    }
相关文章：