Есть ли более быстрый способ поиска содержимого одного файла в другом?

Question

У меня есть два файла

Файл f1 (содержит около 10000 уникальных строк только в одном столбце)

Column1  
line1  
line2  
line3  
....  
line 10000

Файл f2 (содержит несколько столбцов и около 300000 строк)
Первый столбец файла f2 имеет общие элементы с файлом f1. Я хочу grep этих общих элементов (все 10000) вместе с содержимым других столбцов в file2.

До сих пор я пробовал

grep -f f1 f2  
and also 
grep -F -f f1 f2 

, но оба из них дают мне дополнительные строки в конечном выводе (10000 +). В первом столбце обоих файлов есть некоторое содержимое, разделенное символом «/», что может потребовать дополнительных операций с текстом, например. Столбец1
a / b / c
e / f / g
x / y

Answer 1

grep -f - хорошее начало, однако есть две проблемы:

1. В зависимости от данных может быть проблематично убедиться, что сопоставляется именно столбец 1 из файла 2 (не только его части и никаких других столбцов). Примеры:

   • Для файлов f1 = line1 и f2 = line100 a b вы получаете ложное срабатывание, поскольку grep находит строку line1 в line100. Это можно предотвратить с помощью опции grep -w.
   • Для файлов f1 = line1 и f2 = line2 a line1 вы получаете ложное срабатывание, поскольку grep находит строку line1 в третьем столбце, которую вообще не нужно искать. Подобные ошибки трудно предотвратить, используя grep. Безопасный способ - генерировать расширенные шаблоны регулярных выражений (что-то вроде grep -Ef <(sed 's/.*/^& /' f1) f2, требует дополнительных усилий для цитирования строк из f1), но это будет сложно и медленно.

2. Команда может быть более эффективной. В зависимости от реализации grep -f может проверять все n строки из файла 1 для каждой из m строк в файле 2. В худшем случае будут O(n*m) строковые операции.

Следующая команда может выполняться быстрее. Также не будет ложных срабатываний. Это простая версия для файлов без заголовков:

join <(sort f1) (sort f2)

, и это версия для файлов с заголовками

hsort() { IFS= read -r header; printf %s\\n "$header"; sort; }
join --header <(hsort < f1) <(hsort < f2)

Я ожидаю, что это будет делать максимум O(m log m) строковых операций.

_{O (сортировка f1 + сортировка f2 + объединение)
= O (n log n + m log m + max (n, m)) | n = O (2 м log m + m)
= O (m log m)}