Как вычесть одну базу номеров из другой: сравнение алгоритмов

База на 500 тысяч телефонных номеров. Список уже обзвоненных клиентов — 80 тысяч. Задача: убрать обзвоненные из основной базы, чтобы не беспокоить людей повторными звонками. Классическая операция вычитания баз данных.

Вычитание одной базы из другой — это операция A \ B (set difference), где из множества A удаляются все элементы, которые есть в множестве B. В этой статье разберём четыре способа: от ручного сравнения в Excel до оптимизированных алгоритмов с O(1) сложностью. С замерами производительности на реальных данных.

Зачем вычитать базы данных

Реальные сценарии из практики:

• Фильтрация обзвоненных клиентов — вы провели рассылку, собрали список ответивших, теперь нужно исключить их из следующей кампании
• Удаление черных списков — есть база потенциальных клиентов и база отписавшихся/жаловавшихся, нужно убрать последних
• Очистка от конкурентов — вы купили базу, но в ней есть номера ваших партнёров или конкурентов
• Удаление дублей между кампаниями — две параллельные рекламные кампании, нужно исключить пересечения
• Сегментация аудитории — из общей базы нужно убрать уже купивших товар или отписавшихся

Типичная задача: основная база 200 тысяч номеров, blacklist 30 тысяч. Наивный подход (перебор) займёт 6 миллиардов операций (200к × 30к). Оптимизированный через Set — всего 200 тысяч. Разница — в 30 000 раз.

Excel с VLOOKUP или условным форматированием

Excel предлагает несколько способов найти и удалить совпадения между двумя столбцами.

Использование VLOOKUP

1. Откройте оба файла в Excel
2. Скопируйте blacklist в отдельный лист
3. В основной базе добавьте столбец с формулой:

   =ЕСЛИОШИБКА(ВПР(A2;Blacklist!A:A;1;0);"Оставить")
   

4. Протяните формулу на все строки
5. Отфильтруйте по столбцу, оставьте только «Оставить»
6. Удалите вспомогательный столбец и скопируйте результат в новый файл

Условное форматирование

1. Выделите столбец с номерами в основной базе
2. Главная → Условное форматирование → Создать правило
3. Выберите «Использовать формулу»
4. Введите формулу: =СЧЁТЕСЛИ(Blacklist!A:A;A2)>0
5. Установите форматирование (например, красный фон)
6. Отфильтруйте по цвету и удалите выделенные строки

Производительность Excel

Тест на реальных данных — основная база 50 тысяч строк, blacklist 10 тысяч:

Проблемы Excel-подхода

• Квадратичная сложность — VLOOKUP перебирает весь blacklist для каждой строки основной базы (O(n × m))
• Ограничение на размер — Excel тормозит после 500 тысяч строк, зависает после 1 млн
• Чувствительность к формату — номера +79001234567 и 89001234567 не будут считаться одинаковыми
• Риск ошибки — легко случайно удалить не те строки или забыть снять фильтр

Вердикт: подходит только для маленьких баз (до 10 тысяч строк). Для больших объёмов неэффективен.

Командная строка (Unix)

В Linux и macOS есть утилиты для работы с отсортированными текстовыми файлами.

Использование comm

Утилита comm сравнивает два отсортированных файла и выводит различия.

# Сначала сортируем оба файла
sort база.csv > база_sorted.csv
sort blacklist.csv > blacklist_sorted.csv

# Находим строки, которые есть только в первом файле
comm -23 база_sorted.csv blacklist_sorted.csv > результат.csv

Параметры comm:

• -1 — не показывать строки только из первого файла
• -2 — не показывать строки только из второго файла
• -3 — не показывать общие строки
• -23 — показать только строки из первого файла

Использование grep -v -F -f

Более простой способ — использовать grep для фильтрации:

# Удалить из базы все строки, которые есть в blacklist
grep -v -F -f blacklist.csv база.csv > результат.csv

Параметры:

• -v — инвертировать совпадение (показать НЕ совпавшие строки)
• -F — искать точное совпадение строк, не regex
• -f — читать паттерны из файла

Производительность CLI-инструментов

Тест на базах 200 тысяч и 50 тысяч строк:

Важно: comm работает быстро, но требует предварительной сортировки. grep проще в использовании, но имеет квадратичную сложность — для каждой строки базы он перебирает весь blacklist.

Ограничения CLI-подхода

• Точное совпадение строк — если номера записаны в разных форматах, они не будут распознаны как дубликаты
• Порог входа — нужно знать синтаксис командной строки
• Нет нормализации — инструменты работают на уровне текста, не понимая содержимое

Python с set-операциями

Python предоставляет встроенную структуру данных set с O(1) операциями проверки членства.

Простая реализация

def subtract_databases(base_file, blacklist_file, output_file):
    # Читаем blacklist в set
    with open(blacklist_file, 'r', encoding='utf-8') as f:
        blacklist = set(line.strip() for line in f)

    # Фильтруем основную базу
    with open(base_file, 'r', encoding='utf-8') as f_in:
        with open(output_file, 'w', encoding='utf-8') as f_out:
            for line in f_in:
                phone = line.strip()
                if phone not in blacklist:
                    f_out.write(phone + '\n')

    return len(blacklist)

# Использование
count = subtract_databases('база.csv', 'blacklist.csv', 'результат.csv')
print(f'Удалено {count} номеров из blacklist')

Вычитание с нормализацией номеров

Для учёта разных форматов номеров добавим нормализацию:

import re

def normalize_phone(phone):
    """Приводит номер к формату 79XXXXXXXXX"""
    # Убираем все символы кроме цифр
    phone = re.sub(r'[^\d]', '', phone)

    # Приводим к формату 79XXXXXXXXX
    if phone.startswith('89') and len(phone) == 11:
        phone = '7' + phone[1:]
    elif phone.startswith('9') and len(phone) == 10:
        phone = '7' + phone
    elif phone.startswith('79') and len(phone) == 11:
        pass
    else:
        return None

    return phone if len(phone) == 11 else None

def subtract_with_normalization(base_file, blacklist_file, output_file):
    # Читаем и нормализуем blacklist
    blacklist = set()
    with open(blacklist_file, 'r', encoding='utf-8') as f:
        for line in f:
            normalized = normalize_phone(line.strip())
            if normalized:
                blacklist.add(normalized)

    # Фильтруем основную базу
    subtracted = 0
    kept = 0
    with open(base_file, 'r', encoding='utf-8') as f_in:
        with open(output_file, 'w', encoding='utf-8') as f_out:
            for line in f_in:
                normalized = normalize_phone(line.strip())
                if normalized and normalized not in blacklist:
                    f_out.write(normalized + '\n')
                    kept += 1
                elif normalized and normalized in blacklist:
                    subtracted += 1

    print(f'Было в основной базе: {subtracted + kept}')
    print(f'В blacklist: {len(blacklist)}')
    print(f'Вычтено: {subtracted}')
    print(f'Осталось: {kept}')

subtract_with_normalization('база.csv', 'blacklist.csv', 'результат.csv')

Почему Set так быстр

Магия кроется в реализации set через хеш-таблицу. Разберём на примере:

Наивный подход (массив + перебор):

# O(n × m) — для каждого номера перебираем весь blacklist
for phone in база:
    if phone not in blacklist_array:  # O(m) операция
        результат.append(phone)

Для базы 200к и blacklist 50к это 10 миллиардов операций.

Set-based подход:

# O(n) — для каждого номера одна O(1) проверка
blacklist_set = set(blacklist)  # O(m) создание set
for phone in база:
    if phone not in blacklist_set:  # O(1) операция!
        результат.append(phone)

Для тех же данных это всего 250к операций (50к для создания set + 200к проверок).

Замеры производительности

Тест на реальных данных — база 500 тысяч, blacklist 100 тысяч, разные форматы номеров:

Разница между наивным и set-based подходом — более 200 раз. На больших базах (1 млн × 500к) разница достигает тысяч раз.

Базальт — оптимизированный инструмент

Базальт использует тот же Set-based алгоритм, но с удобным интерфейсом и автоматической нормализацией.

Как вычесть базу в Базальте

1. Откройте раздел «Вычесть базу»
2. Выберите основную базу (из которой вычитаем)
3. Выберите базу для вычитания (blacklist)
4. Укажите название выходного файла
5. Нажмите «Вычесть базу»
6. Получите результат со статистикой

Что делает Базальт под капотом

Базальт использует оптимизированную реализацию на TypeScript:

// Упрощённый код из Базальта
const subtractSet = new Set<string>()

// 1. Загружаем blacklist в Set — O(m)
for (const item of subtractPhones) {
  for (const phone of item.phone) {
    subtractSet.add(phone)  // O(1) операция
  }
}

// 2. Фильтруем основную базу — O(n)
for (const item of basePhones) {
  for (const phone of item.phone) {
    if (!subtractSet.has(phone)) {  // O(1) проверка
      resultPhones.push(phone)
    }
  }
}

Итоговая сложность: O(n + m), где n — размер основной базы, m — размер blacklist.

Особенности Базальта

• Автоматический парсинг — извлекает номера из любого текстового формата
• Нормализация номеров — приводит все номера к единому виду (79XXXXXXXXX)
• Set-based алгоритм — O(1) lookup, эффективен даже на миллионах записей
• Детальная статистика — показывает было/стало/вычтено
• Офлайн-обработка — данные не покидают ваш компьютер

Производительность Базальта

Тест на больших данных — основная база 1 млн, blacklist 200 тысяч, разные форматы:

Реальный кейс

Компания проводит холодные звонки. Основная база — 2,5 млн номеров. За месяц работы:

• Обзвонили 180 тысяч
• Собрали 15 тысяч отказов (просили больше не звонить)
• Выявили 8 тысяч недействительных номеров

Задача: убрать все три категории из основной базы.

Базальт: три последовательных операции вычитания, общее время — 42 секунды.

Excel: попытка загрузить базу приводит к зависанию на час, потом вылет из памяти.

Python: нужно написать скрипт на 50 строк, время выполнения — около минуты.

Сравнение производительности алгоритмов

Наглядное сравнение на разных объёмах данных:

Вывод: разница между алгоритмами становится критичной при работе с большими данными. На базах больше 100 тысяч записей только Set-based подходы дают приемлемую производительность.

Практические советы

1. Всегда проверяйте арифметику: размер_базы минус размер_blacklist должен примерно равняться результату (с учётом пересечений).
2. Делайте резервные копии обеих баз перед операцией — если что-то пойдёт не так, можно повторить.
3. Нормализуйте номера перед вычитанием, если они в разных форматах — иначе дубликаты не будут распознаны.
4. Документируйте blacklist — записывайте, откуда он взялся и когда был создан.
5. Проверяйте несколько случайных номеров вручную — убедитесь, что номера из blacklist действительно отсутствуют в результате.
6. Учитывайте время актуальности — blacklist может устареть, особенно если это отписавшиеся клиенты (они могут снова подписаться).

Частые подводные камни

Разные форматы номеров

База содержит +79001234567, blacklist — 89001234567. Без нормализации эти номера не будут считаться одинаковыми, и номер не будет удалён.

Решение: всегда нормализуйте номера к единому формату перед операцией.

Частичные номера

В blacklist попали номера без кода страны (например, 9001234567). Такие номера не совпадут с полными номерами в базе.

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

Проблемы с кодировкой

Если файлы в разных кодировках (UTF-8 и Windows-1251), номера могут некорректно читаться, особенно если в файле есть текстовые комментарии.

Решение: конвертируйте все файлы в UTF-8 перед обработкой.

Что выбрать для разных задач

Маленькие базы (до 10 тысяч строк), разовая задача — Excel с VLOOKUP. Не нужно устанавливать дополнительные инструменты.

Работаете в Unix, файлы чистые и в одном формате — используйте comm. Это самый быстрый способ для стандартных текстовых файлов.

Нужна сложная логика или интеграция с другими процессами — Python с set-операциями. Полный контроль, возможность добавить логирование и валидацию.

Регулярная работа с телефонными базами, разные форматы номеров — используйте Базальт. Автоматическая нормализация, Set-based алгоритм O(n+m), удобный интерфейс, работает офлайн.

Ключевой момент: для баз больше 100 тысяч записей критична сложность алгоритма. Наивные подходы (Excel VLOOKUP, grep без оптимизации) имеют O(n × m) сложность и становятся неприменимы. Set-based подходы, которые использует Базальт, дают O(n + m) и масштабируются линейно даже на миллионы записей. Разница — в десятки и сотни раз по времени выполнения.