Список для максимально быстрого поиска по нему - C#

Формулировка задачи:

Сейчас у меня есть два списка строк -

List<string>

один

MainBase

, второй

TempBase

, мне надо выбрать из

TempBase

все строчки, которых нет в

MainBase

, ну что бы потом их добавить в

MainBase

. Программа работает в многопоточном режиме, много этих

MainBase

и они относительно большие, короче при относительном количестве потоков неплохо загружает процессор, я так подозреваю из за поиска. Сейчас выборку я делаю так:

List<string> NewList = (from item in TempBase
           let temp = item.Replace(SameText, "").Trim()
           where
           string.IsNullOrEmpty(temp) == false && MainBase.Contains(temp) == false
           select temp).ToList();

тут есть нюанс, перед поиском с переменной осуществляется некоторое действие и только после этого идет поиск:

let temp = item.Replace(SameText, "").Trim()

Подскажите, что не так, как можно ускорить, может есть еще какой то список в котором поиск будет осуществляться быстрее (ну допустим в нем элементы будут не просто добавятся по очередной, а сортироваться как то так) и еще вопрос, на сколько я помню существует такая штука как бинарное дерево, есть в фреймворке готовый вариант?

Решение задачи: «Список для максимально быстрого поиска по нему»

textual
                            Листинг программы 
                        

                            static void Tester()
{
    List<string> mainFile = new List<string>(); // 532641 строк
    List<string> secondFile = new List<string>(); // 150309 строк
    
    TestSortedSet(mainList, secondList);
    TestHashSet(mainList, secondList);
    TestLinq(mainList, secondList);
    TestFor(mainList, secondList);
    TestExt(mainList, secondList);
}
 
static void TestHashSet(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestHashSet");
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<string> hs = new HashSet<string>(mainFile);
    sw.Stop();
    Console.WriteLine("Размер списка: {0}, времени понадобилось: {1}", mainFile.Count, sw.ElapsedMilliseconds);
 
    sw.Reset();
    int countDo = mainFile.Count;
 
    sw.Start();
    for (int i = 0; i < secondFile.Count; i++) hs.Add(secondFile[i].Trim());
    sw.Stop();
 
    Console.WriteLine("Новый размер списка: {0}, новых элементов: {1}, времени понадобилось: {2}", hs.Count, (hs.Count - countDo), sw.ElapsedMilliseconds);
    Console.WriteLine();
}
 
 
static void TestSortedSet(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestSortedSet");
    Stopwatch sw = new Stopwatch();
    sw.Start();
    SortedSet<string> ss = new SortedSet<string>(mainFile);
    sw.Stop();
    Console.WriteLine("Размер списка: {0}, времени понадобилось: {1}", mainFile.Count, sw.ElapsedMilliseconds);
 
    sw.Reset();
    int countDo = mainFile.Count;
 
    sw.Start();
    for (int i = 0; i < secondFile.Count; i++) ss.Add(secondFile[i].Trim());
    sw.Stop();
 
    Console.WriteLine("Новый размер списка: {0}, новых элементов: {1}, времени понадобилось: {2}", ss.Count, (ss.Count - countDo), sw.ElapsedMilliseconds);
    Console.WriteLine();
}
 
 
static void TestLinq(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestLinq");
    Stopwatch sw = new Stopwatch();
 
    sw.Start();
    List<string> NewList = (from item in secondFile
                         let temp = item.Trim()
                         where
                            mainFile.Contains(temp) == false
                            select temp).ToList();
    sw.Stop();
 
    Console.WriteLine("Новых элементов: {0}, Времени понадобилось: {1}", NewList.Count, sw.ElapsedMilliseconds);
    Console.WriteLine();
}
 
 
static void TestFor(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestFor");
    Stopwatch sw = new Stopwatch();
 
    List<string> NewList = new List<string>();
 
    sw.Start();
    for (int i = 0; i < secondFile.Count; i++)
    {
        string temp = secondFile[i].Trim();
        if (mainFile.Contains(temp) == false) NewList.Add(temp);
    }
    sw.Stop();
 
    Console.WriteLine("Новых элементов: {0}, Времени понадобилось: {1}", NewList.Count, sw.ElapsedMilliseconds);
    Console.WriteLine();
}
 
 
static void TestExt(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestExt");
    Stopwatch sw = new Stopwatch();
 
    sw.Start();
    List<string> NewList = secondFile.Select(i => i.Trim()).Except(mainFile).ToList();
    sw.Stop();
 
    Console.WriteLine("Новых элементов: {0}, Времени понадобилось: {1}", NewList.Count, sw.ElapsedMilliseconds);
    Console.WriteLine();
}
                        