У меня есть список 1M записей, и я хочу исключить подмножество из 20000 из этих записей (два списка в другом порядке имеют один и тот же ключ (строка)). Может ли кто-нибудь предложить быстрый алгоритм поиска в C для этого?C Найти подмножество строк из списка
Я не хочу читать каждый из 20K-идентификаторов и каждый раз просматривать список 1M. Любые предложения были бы наиболее полезными.
спасибо.
Сортируйте оба списка в первую очередь. Затем вы можете пересечь их вместе, продвигая указатель в списке, который находится за указателем в другом.
Вам нужно использовать C? Это похоже на работу для Perl.
Что вы хотите использовать, это хэш-набор. Хэш-набор является частным случаем хэш-таблицы, которая в основном записывает, существует ли элемент в наборе или нет, в постоянное время. Итак, что вам нужно сделать, это вставить ваши 20k ID в хеш-набор, а затем запустить через 1 миллион строк и посмотреть, существуют ли они в хэш-наборе.
Для справки, вот реализация хэша набора в C: https://github.com/avsej/hashset.c
Вашего времени работы будет O (N), так как для каждой проверки для строк 1M, это будет постоянное время.
Перед тем, как начать поиск, введите 20 000 ключей в hash table. Затем для каждого элемента в списке, если этот ключ находится в хеш-таблице, исключить элемент из списка.
Мне нужно использовать C, так как остальная часть анализа должна быть выполнена в C, и perl будет слишком медленным для остальной части кода – user19758