/search_tickets_emulator

Simple search ticket emulator on Rust (Just test exercise )

Primary LanguageRustMIT LicenseMIT

search_tickets_emulator

Simple search ticket emulator on Rust (Just test exercise )

Основная концепция - мультиграф. Почему? Потому-что возможны перелеты в обе стороны => необходим неориентированный граф.

Batch request

В БД записываются данные по билетам где ключ определяется как МД5 (не надежный зато самый быстрый) от 4х значений полей:

{
    departure_code: String,
    arrival_code: String,
    departure_time: u32,
    arrival_time: u32,
}

Почему отсутствует цена ? Чтобы при вставке переписать билет в случае изменения цены при прочих равных.

Если передается ИД то структура записывается напрямую без подсчета хэш-суммы (не реализовано)

search

На втором этапе можно использовать алгоритм дейкстры для определение кратчайшего маршрута Разбиение графа на кластера не требуется (наверно) в силу возможности хранения всего графа в оперативной памяти.

Необходимо строить и поддерживать мультиграф, где вершины это точки маршрута, а ребра это структура FlightWeight. В ней храниться вектор МД5 хэшей билетов и вес перелета для нахождения кратчайшего маршрута. (см допущение А)

Допущения

  • (А) Так как в нашем батче инсерте билетов отсутствует поле distance (расстояние между двумя точками), то считаем что весом будет разница между departure_time - arrival_time. Вес нам необходимо для определения кратчайшего маршрута.
  • Нужна хэшмапа всех нод на их NodeIndex чтобы O1 при поиске NodeIndex. В обратном случае приходиться проходиться по списку всех нод графа для проверки - есть ли уже надо с таким индексом или нет - что плохо. Пока что делаем проходы.

TODO

  • Переехать с u32 на SystemTime