oshliaer

Алгоритм для сравнения двух массивов данных с выявлением новых, удаленных и измененных записей. Каждая запись идентифицируется уникальным ID и может содержать несколько полей с данными.

Типы данных

// Базовые типы значений в коллекции
type CollectionType = string | number | boolean | Date;

// Структура значения элемента коллекции
interface CollectionItemValue {
  __val: CollectionType;     // Само значение
  __row: number;      // Номер строки
  __col: number;      // Номер колонки
}

// Структура элемента коллекции
interface CollectionItem {
  [key: string]: CollectionItemValue;
}

// Тип коллекции - массив элементов
type Collection = CollectionItem[];

Реализация

Алгоритм реализован в виде класса StateComparator, который инкапсулирует всю логику сравнения и предоставляет удобный интерфейс для работы с данными.

Основные методы

class StateComparator {
  /**
   * Создает экземпляр компаратора
   * @param newValues - Новый массив данных
   * @param oldValues - Старый массив данных
   */
  constructor(newValues: DataArray, oldValues: DataArray)

  /**
   * Находит новые элементы, которых нет в старой коллекции
   */
  public getNewItems(): CollectionItem[]

  /**
   * Находит удаленные элементы, которых нет в новой коллекции
   */
  public getOldItems(): CollectionItem[]

  /**
   * Находит измененные элементы и их различия
   */
  public getChangedItems(): ModifiedItem[]
}

Принцип работы

1. При создании экземпляра класса:
   • Преобразуются заголовки колонок в нижний регистр
   • Создаются коллекции объектов с метаданными
   • Формируются карты (Map) для быстрого доступа по ID
2. Методы сравнения:
   • Используют Set для оптимизации поиска элементов
   • Выполняют единый проход по заголовкам при сравнении
   • Возвращают типизированные результаты
3. Оптимизации:
   • Кэширование преобразованных данных
   • Использование Set вместо includes для проверки наличия ключей
   • Объединение проверок заголовков в один проход
   • Строгая типизация для безопасности данных

Пример использования

// Входные данные
const newValues = [
  ['id', 'param', 'status', 'mark'],
  ['Заказ 4', 1, 'done', 'mark'],
  ['Заказ 2', 1, 'in proc', 'mark'],
  ['Заказ 3', 1, 'in proc', 'mark'],
];

const oldValues = [
  ['id', 'param', 'status', 'mark'],
  ['Заказ 1', 1, 'done', 'mark'],
  ['Заказ 2', 2, 'done', 'mark'],
  ['Заказ 3', 1, 'done', 'mark'],
];

// Создание компаратора
const comparator = new StateComparator(newValues, oldValues);

// Получение результатов
const newItems = comparator.getNewItems();
const oldItems = comparator.getOldItems();
const changedItems = comparator.getChangedItems();

console.log('Новые записи:', newItems);
console.log('Удаленные записи:', oldItems);
console.log('Измененные записи:', changedItems);

Результат сравнения

Алгоритм возвращает три набора данных:

1. newItems: Новые записи (только в новом массиве)

   CollectionItem[]
   

2. oldItems: Удаленные записи (только в старом массиве)

   CollectionItem[]
   

3. changedItems: Измененные записи

   {
     __modified: {
       __status: boolean;
       [key: string]: { new: CollectionType; old: CollectionType } | boolean;
     };
     id: string;
     new: CollectionItem;
     old: CollectionItem;
   }[]
   

Особенности реализации

• Объектно-ориентированный подход с инкапсуляцией логики в классе
• Строгая типизация всех структур данных
• Оптимизированные алгоритмы сравнения
• Сохранение метаданных о расположении значений
• Игнорирование поля id при сравнении изменений
• Поддержка отсутствующих полей в записях

Сложность алгоритма

Временная сложность алгоритма:

• Создание компаратора: O(n), где n - общее количество элементов в обоих массивах
  • Преобразование заголовков: O(h), где h - количество заголовков
  • Создание коллекций: O(n)
  • Создание карт доступа: O(n)
• Поиск новых элементов: O(n)
• Поиск удаленных элементов: O(n)
• Поиск измененных элементов: O(n * h), где h - количество заголовков

Пространственная сложность: O(n), где n - общее количество элементов

• Хранение преобразованных коллекций: O(n)
• Хранение карт доступа: O(n)
• Хранение множеств для сравнения: O(n)

Примеры вывода

Для входных данных из примера выше, результат будет следующим:

// Новые записи
[
  {
    "id": { "__val": "Заказ 4", "__row": 2, "__col": 1 },
    "param": { "__val": 1, "__row": 2, "__col": 2 },
    "status": { "__val": "done", "__row": 2, "__col": 3 },
    "mark": { "__val": "mark", "__row": 2, "__col": 4 }
  }
]

// Удаленные записи
[
  {
    "id": { "__val": "Заказ 1", "__row": 2, "__col": 1 },
    "param": { "__val": 1, "__row": 2, "__col": 2 },
    "status": { "__val": "done", "__row": 2, "__col": 3 },
    "mark": { "__val": "mark", "__row": 2, "__col": 4 }
  }
]

// Измененные записи
[
  {
    "__modified": {
      "__status": true,
      "param": { "new": 1, "old": 2 },
      "status": { "new": "in proc", "old": "done" }
    },
    "id": "Заказ 2",
    "new": {
      "id": { "__val": "Заказ 2", "__row": 3, "__col": 1 },
      "param": { "__val": 1, "__row": 3, "__col": 2 },
      "status": { "__val": "in proc", "__row": 3, "__col": 3 },
      "mark": { "__val": "mark", "__row": 3, "__col": 4 }
    },
    "old": {
      "id": { "__val": "Заказ 2", "__row": 3, "__col": 1 },
      "param": { "__val": 2, "__row": 3, "__col": 2 },
      "status": { "__val": "done", "__row": 3, "__col": 3 },
      "mark": { "__val": "mark", "__row": 3, "__col": 4 }
    }
  }
]

Ограничения и edge cases

1. Требования к входным данным:
   • Массивы должны содержать как минимум строку заголовков
   • Первая строка должна содержать заголовок ‘id’
   • Значения ID должны быть уникальными в пределах каждого массива
2. Особые случаи:
   • Пустые массивы (кроме заголовков):
     • Новый массив пуст → все записи считаются удаленными
     • Старый массив пуст → все записи считаются новыми
   • Отсутствующие значения:
     • Пропущенные колонки заполняются undefined
     • Пустые ячейки (null, undefined) считаются валидными значениями при сравнении
   • Регистр заголовков:
     • Все заголовки приводятся к нижнему регистру
     • ‘ID’, ‘Id’, ‘iD’ считаются одним и тем же заголовком
3. Ограничения:
   • Алгоритм не поддерживает вложенные структуры данных
   • Максимальный размер массивов ограничен только доступной памятью
   • Порядок элементов в результирующих массивах может отличаться от исходного