Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.68/34: Рейтинг темы: голосов - 34, средняя оценка - 4.68
 Аватар для VLK
198 / 170 / 19
Регистрация: 05.05.2013
Сообщений: 1,236

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

26.08.2015, 20:09. Показов 7306. Ответов 29
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Сейчас у меня есть два списка строк - List<string> один MainBase, второй TempBase, мне надо выбрать из TempBase все строчки, которых нет в MainBase, ну что бы потом их добавить в MainBase.
Программа работает в многопоточном режиме, много этих MainBase и они относительно большие, короче при относительном количестве потоков неплохо загружает процессор, я так подозреваю из за поиска.

Сейчас выборку я делаю так:
C#
1
2
3
4
5
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();
тут есть нюанс, перед поиском с переменной осуществляется некоторое действие и только после этого идет поиск:
C#
1
let temp = item.Replace(SameText, "").Trim()
Подскажите, что не так, как можно ускорить, может есть еще какой то список в котором поиск будет осуществляться быстрее (ну допустим в нем элементы будут не просто добавятся по очередной, а сортироваться как то так) и еще вопрос, на сколько я помню существует такая штука как бинарное дерево, есть в фреймворке готовый вариант?
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.08.2015, 20:09
Ответы с готовыми решениями:

Оптимизировать структуру таблицы для быстрого поиска
Здравствуйте. Имеется таблица контактов компаний с огромным количеством данных. Сами контакты хранятся в поле `value`. По этому же полю...

Хэш-таблица для быстрого поиска строки в массиве
Объясните, пожалуйста, как реализуется хэш-таблица. Например, есть двухмерный массив строк с большим количеством записей (строки состоят...

Отсортированный хэш-вектор бинарной схожести для быстрого поиска
Есть набор 64-х разрядных чисел, их может быть примерно 20 000 ... 40 000. Нужна какая-то хеш функция или что-то ещё, что бы эти 64-х...

29
 Аватар для VLK
198 / 170 / 19
Регистрация: 05.05.2013
Сообщений: 1,236
26.08.2015, 23:00  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Ev_Hyper Посмотреть сообщение
secondFile.Where(x => !mainFile.Contains(x.Trim())).ToList();
нет, это не пойдет, мне надо и выполнить действие с элементом и проверить. И в итоге я должен получить список элементов к которым уже примененным к нему Trim.

Добавлено через 5 минут
Цитата Сообщение от Storm23 Посмотреть сообщение
Почитайте про структуры данных и их отличия друг от друга. И тогда не придется делать "шокирующие открытия".
Ну про дерево я знаю (как оно работает), а вот про хеш-таблицу слышал, но не в курсе ее устройства, а вот насчет на чем работает Except я не знал, вот теперь становиться более понятно такая скорость.
1
Администратор
Эксперт .NET
 Аватар для tezaurismosis
9674 / 4826 / 763
Регистрация: 17.04.2012
Сообщений: 9,665
Записей в блоге: 14
26.08.2015, 23:23
Цитата Сообщение от VLK Посмотреть сообщение
вот насчет на чем работает Except я не знал
Оставлю это здесь
referencesource.microsoft.com
1
 Аватар для VLK
198 / 170 / 19
Регистрация: 05.05.2013
Сообщений: 1,236
27.08.2015, 11:27  [ТС]
Вот еще произвел некоторые замеры - выполнить какое то действие над элементом списка, после чего выполнить проверку и потом Except:

Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
static void Tester()
{
    List<string> mainFile = new List<string>(); // 532641 строк
    List<string> secondFile = new List<string>(); // 150309 строк
    
    TestLQ(mainList, secondList);
    TestFOR(mainList, secondList);
    TestEXP(mainList, secondList);
}
 
static void TestEXP(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestEXP");
    Stopwatch sw = new Stopwatch();
 
    sw.Start();
    //List<string> N = mainFile.Select(x => x.Replace("http://example.com", "").Trim()).Where(x => string.IsNullOrEmpty(x) == false).ToList();
    List<string> N = mainFile.Select(x => x.Replace("http://example.com", "").Trim()).Where(x => string.IsNullOrEmpty(x) == false).Except(secondFile).ToList();
    sw.Stop();
 
    Console.WriteLine("заняло времени: {0}", sw.ElapsedMilliseconds);
    Console.WriteLine();
 
}
 
 
static void TestFOR(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestFOR");
    Stopwatch sw = new Stopwatch();
    List<string> N = new List<string>();
 
    sw.Start();
    for (int i = 0; i < mainFile.Count; i++)
    {
        string temp = mainFile[i].Replace("http://example.com", "").Trim();
        if (string.IsNullOrEmpty(temp) == false) N.Add(temp);
    }
 
    N = N.Except(secondFile).ToList();
    sw.Stop();
 
    Console.WriteLine("заняло времени: {0}", sw.ElapsedMilliseconds);
    Console.WriteLine();
}
 
 
static void TestLQ(List<string> mainFile, List<string> secondFile)
{
    Console.WriteLine("TestLQ");
    Stopwatch sw = new Stopwatch();
 
    sw.Start();
    List<string> N = (from item in mainFile
                      let temp = item.Replace("http://example.com", "").Trim()
                      where string.IsNullOrEmpty(temp) == false
                      select temp).Except(secondFile).ToList();
 
    sw.Stop();
 
    Console.WriteLine("заняло времени: {0}", sw.ElapsedMilliseconds);
    Console.WriteLine();
}


Linq медленнее всего - 400
через расширения - 320
через цикл for - 310

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

PS конкретно в моем случае все же подойдет больше работа через расширения, т.к. у меня уже все построено на списках (List<string>) и так я меняю всего одну строку, а если переходить на HashSet то надо кучу всего переписать, а потом еще все время конвертировать из List в HashSet и обратно.
1
TheGreatCornholio
 Аватар для Woldemar89
1255 / 733 / 285
Регистрация: 30.07.2015
Сообщений: 2,408
27.08.2015, 11:52
Цитата Сообщение от VLK Посмотреть сообщение
конвертировать из List в HashSet и обратно.
Это ничего не изменит?
C#
1
HashSet<string> strings = new HashSet<string>(File.ReadAllLines("data.txt",Encoding.GetEncoding(1251)));
Добавлено через 5 минут
Цитата Сообщение от VLK Посмотреть сообщение
т.к. у меня уже все построено на списках (List<string>)
Я к тому что, перестроить может все таки, если это поможет?
1
TheGreatCornholio
 Аватар для Woldemar89
1255 / 733 / 285
Регистрация: 30.07.2015
Сообщений: 2,408
27.08.2015, 13:17
Так будет работать? И насколько быстро? Проверь на своих больших файлах быстродействие, я правильность проверял на вложенных.
C#
1
2
3
4
            HashSet<string> mainbase = new HashSet<string>(File.ReadAllLines("mainbase.txt", Encoding.GetEncoding(1251)));
            HashSet<string> secondbase = new HashSet<string>(File.ReadAllLines("secondbase.txt", Encoding.GetEncoding(1251)));
 
            mainbase.UnionWith(secondbase.Select(x => x.Replace("http://example.com", "").Trim()).Where(x => string.IsNullOrEmpty(x) == false).Except(mainbase));
Вложения
Тип файла: txt mainbase.txt (23 байт, 1 просмотров)
Тип файла: txt secondbase.txt (45 байт, 1 просмотров)
1
 Аватар для VLK
198 / 170 / 19
Регистрация: 05.05.2013
Сообщений: 1,236
27.08.2015, 13:48  [ТС]
Woldemar89, у меня отдельный класс который отвечает за получение и запись данных в файл, он построен на List.

Но я свой этот класс-переборщик (ну там где надо сначала Replace и Trim, потом IsNullOrEmpty и потом..) переписал с List на HashSet и кода стало меньше? да и перезаписывать не так часто приходится, я все так организовал, теперь посмотрим как пашет.
0
307 / 284 / 102
Регистрация: 06.05.2014
Сообщений: 861
27.08.2015, 13:56
Цитата Сообщение от VLK Посмотреть сообщение
он построен на List
Был бы на IEnumerable - вообще бы проблем с заменой не почувствовал. Не зря же Dependency inversion principle рус придумали.
1
Администратор
Эксперт .NET
 Аватар для tezaurismosis
9674 / 4826 / 763
Регистрация: 17.04.2012
Сообщений: 9,665
Записей в блоге: 14
27.08.2015, 14:23
Цитата Сообщение от BozKurt Посмотреть сообщение
Был бы на IEnumerable
Ну или на ICollection или IList (или других), а то у IEnumerable прямо таки спартанский набор методов. Хотя только с помощью foreach и LINQ можно сделать без проблем почти что угодно.
0
307 / 284 / 102
Регистрация: 06.05.2014
Сообщений: 861
27.08.2015, 14:37
Цитата Сообщение от tezaurismosis Посмотреть сообщение
Хотя только с помощью foreach и LINQ
Так вроде как автор на LINQ и методах расширения это всё и делает. Да и HashSet - IList не реализовывает, поэтому лучше тогда уже действительно ICollection.
0
 Аватар для VLK
198 / 170 / 19
Регистрация: 05.05.2013
Сообщений: 1,236
27.08.2015, 16:21  [ТС]
Woldemar89, BozKurt, tezaurismosis, вот я создал отдельную тему для этого вопроса: Получение и возвращение неопределенной коллекции
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
27.08.2015, 16:21

Разработка приложения для более быстрого, индексированного поиска файлов по заданному имени (хэширование)
Задача: разработать приложение для более быстрого, индексированного поиска файлов по заданному пользователем имени. Индексирование и поиск...

Алгоритм быстрого поиска
Ребят, помогите, кто чем может, для курсовой очень надо(( если есть какие-то предложения, пишите здесь алгоритм быстрого...

Конец "быстрого поиска"?
_http://ya.ru похоже доживает последние дни. :( Яша запускает новый сервис, который пока виден по этому адресу: _http://beta.ya.ru ...

Задача быстрого поиска
Предыстория. Когда-то давно была написана некая программа, которыя собирала статистику и хранила значения в виде пары (key1, key2)....

Метод быстрого последовательного поиска
Написать алгоритм поиска данных из файла согласному указанному методу (метод быстрого последовательного поиска)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Новые блоги и статьи
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru