3

目前我有一个包含两个字符串的对象：

class myClass
{
    public string string1 { get; set; }
    public string string2 { get; set; }

    public bool MatcheString1(string newString)
    {
        if (this.string1 == newString)
        {
            return true;
        }
        return false;
    }
}

然后我有第二个类，它使用 List 制作上述对象的列表。

class URLs : IEnumerator, IEnumerable
{
    private List<myClass> myCustomList;
    private int position = -1;

    //  Constructor
    public URLs()
    {
        myCustomList = new List<myClass>();
    }
}

在那个类中，我使用一种方法来检查列表中是否存在字符串

//  We can also check if the URL string is present in the collection
public bool ContainsString1(string newString)
{
    foreach (myClass entry in myCustomList)
    {
        if (entry. MatcheString1(newString))
        {
            return true;
        }
    }

    return false;
}

本质上，随着对象列表增长到 100,000 个标记，此过程变得非常缓慢。检查该字符串是否存在的快速方法是什么？我很高兴在课堂之外创建一个列表以进行验证，但这对我来说似乎很奇怪？

4

3 回答 3

5

一旦项目列表稳定，您可以计算匹配的哈希集，例如：

// up-front work
var knownStrings = new HashSet<string>();
foreach(var item in myCustomList) knownStrings.Add(item.string1);

（请注意，这不是免费的，需要随着列表的变化重新计算）；然后，稍后，您可以检查：

return knownStrings.Contains(newString);

然后非常便宜（O（1）而不是O（N））。

于 2013-11-01T12:11:12.630 回答
2

如果您不介意使用不同的数据结构，而不是列表，您可以使用字典，其中您的对象按其string1属性进行索引。

public URLs()
{
    myDictionary = new Dictionary<string, myClass>();
}

由于通常Dictionary<TKey, TValue>可以在 O(1) 时间内找到元素，因此您可以非常快速地执行该检查。 

if(myDictionary.ContainsKey(newString))
  //...
于 2013-11-01T12:11:48.450 回答
0

搜索已排序的数组（列表）需要 O(logN)

        var sortedList = new SortedSet<string>();
        sortedList.Add("abc");
        // and so on
        sortedList.Contains("test");

搜索 HashSet 需要 O(1)，但我猜在 100k 个元素的情况下（Log(100000)=5），与占用更多内存的 HashSet 几乎没有区别。

于 2013-11-01T12:11:04.143 回答