Алгоритм сравнения двух городов из списка

Question

Есть массив с городами

var cities = ["Москва", "Санкт-Петербург", "Саратов", "Екатеринбург", "Новосибирск"];

И есть таблица, где сравниваются эти города между друг другом. Итогом должно быть булевое значение (true/false) согласно этой таблице.

Каким наиболее грамотным способом можно реализовать подобное сравнение без написания огромной кучи IF'ов?

function compare(city1, city2) {
    ...
    if(...) return true;
    else    return false;
}

Answer 1

Один из вариантов:

const cities = ["Москва", "Санкт-Петербург", "Саратов", "Екатеринбург", "Новосибирск"];

const table = {
  "Москва": new Set(["Саратов"]),
  "Санкт-Петербург": new Set(["Санкт-Петербург", "Екатеринбург", "Новосибирск"]),
  "Саратов": new Set(["Москва", "Саратов"]),
  "Екатеринбург": new Set(["Санкт-Петербург", "Новосибирск"]),
  "Новосибирск": new Set(["Санкт-Петербург", "Екатеринбург", "Новосибирск"]),
};

function compare(city1, city2) {
  return table[city1].has(city2);
}

console.log(compare("Москва", "Саратов"));
console.log(compare("Москва", "Санкт-Петербург"));

Answer 2

Относительно универсальная реализация хранения и проверки двоичных отношений между значениями (не только строковыми, объекты тоже поддерживаются):

class BinaryRelations {
  #dict  = {};
  #items = new Map();

  constructor(items) {
    Object.assign(this.#dict, Object.fromEntries(items.map((c, i) => [c, i])));
  }

  get(a, b) {
    b = this.#dict[b];
    return !isFinite(this.#dict[a] + b) ? null
      : Boolean(this.#items.get(a) & (1 << b));
  }
  set(item, relations) {
    const val = isFinite(relations) ? +relations : this.encode(relations);
    this.#items.set(item, val);
    return this;
  }
  encode(relObj) {
    return Object.entries(relObj).reduce((rslt, [to, rel]) => {
      if (!isFinite(this.#dict[to]))
        console.warn(`Неизвестный элемент "${to}" будет пропущен.`);
      else
        rslt |= (+Boolean(+rel) << this.#dict[to]);
      return rslt;
    }, 0);
  }
}

const cities = ["Москва", "Санкт-Петербург", "Саратов", "Екатеринбург", "Новосибирск"];

const relations = new BinaryRelations(cities);
relations.set('Москва', {                   // самая громоздкая запись отношений - объектом
  'Москва'         : false, 
  'Санкт-Петербург': false,
  'Саратов'        : true,
  'Екатеринбург'   : false,
  'Новосибирск'    : false,
});
relations.set('Санкт-Петербург', 0b01101)   // установка отношений числом в двоичной записи (значения в порядке повышения разрядов!)
  .set('Саратов', 0b00101)                  // поддержка чейнинга (почему бы и нет)
  .set('Екатеринбург', 18)                  // можно и десятичной записью числа пользоваться...
  .set('Новосибирск', 0x1A);                // ...и шестнадцатеричной

console.log(
  relations.get('Москва', 'Саратов'),            // ? true
  relations.get('Новосибирск', 'Москва'),        // ? false
  relations.get('Екатеринбург', 'Новосибирск'),  // ? true
);

Принцип действия:
Отношения каждого элемента к другим кодируются битовой маской и хранятся в приватном свойстве #items типа Map.
Для того чтобы не тратить время на перебор элементов при каждом обращении, номера двоичных разрядов элементов хранятся в простом объекте (свойство #dict).
Метод get - возвращает значение бита в разряде элемента, приводя это значение к boolean. Например, здесь отношению к элементу 'Екатеринбург' соответствует четвертый бит в каждой хранимой записи.
Метод set просто устанавливает значением записи битовую маску (при необходимости, сериализуя объект в нее).
Ну а сериализацией объекта занимается метод encode - проходя по ключам переданного объекта, он получает двоичный разряд каждого, и в этом разряде результата ставит битовый флажок если значение отношения (взятое из объекта) true или 1.

Быстродействие этой штуки должно быть очень хорошим, но максимальное количество элементов ограничено - их может быть до 53. Ограничение можно "снять" если переделать с битовых маск на строки (заодно, это позволит кодировать больше двух состояний отношения, насколько диапазона UTF-16 хватит, но со строками быстродействие снизится конечно).

p.s.: Тут есть возможность дописать пополнение словаря уже после инициализации, выборочную установку отдельных флагов вместо всех целиком, и "декодирование" отношений в объект - но со всем этим код примера раздуется, так что я ограничился задачей (только организация и чтение отношений).

БЛОГ НА HUSL

Алгоритм сравнения двух городов из списка

Ответы (2 шт):