У всех нас есть один вопрос: почему, черт возьми, интервьюеры уделяют внимание структурам данных во время интервью. Мы практически не используем их в реальной жизни.

Но что, если я скажу вам, что выбор неправильной структуры данных - самая большая ошибка, которую может сделать разработчик при проектировании или написании кода для масштабируемой системы.

Прежде чем сильно хвастаться этим обсуждением, давайте разберемся, что заставило меня понять важность выбора правильной структуры данных.

Поэтому, как компания электронной коммерции, мы предоставляем клиентам возможность бронировать авиабилеты, отели, автомобили, мероприятия, происходящие в городе и т. Д.

Но в Индии ни один бизнес не обходится без скидки. Настроить скидки просто для всех остальных вертикалей, кроме отелей.

Человек вручную устанавливает, какая должна быть скидка для списка отелей (отели по всему миру, сумма которых колеблется до одной-двух тысяч). [30% для отелей 1,2,3].

Когда я говорю о списке отелей, список может варьироваться до 40000 отелей со скидкой 20%.

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

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

Поскольку я новичок в этой системе, я недооценил масштаб, в котором сейчас работает Goibibo, и я выбираю структуру данных списка вместо карты при сохранении этих идентификаторов отелей в кеше. Поэтому, когда пользователь выбирает отель, я загружаю все эти идентификаторы отелей в оперативную память, а затем выполняю линейный поиск, чтобы проверить, есть ли отель в списке.

На этом этапе я сделал две ошибки.

  • Думая, что линейный поиск имеет сложность O (n), где n - это ни один элемент в списке. Это неправильно. Для строкового типа данных линейный поиск занимает O (m * n), где m - длина каждой строки. В нашем случае длина m (hotel-Id) составляет 20 букв. (Сравнение строк имеет сложность O (m), где m - это количество символов в строке)
  • Даже если я проведу сравнение списков, я должен был попробовать двоичный поиск вместо линейного, что могло бы уменьшить мою сложность до O (m * log (n))

Что ж, сравнение списков приводит к плохой или худшей производительности, и внезапно наше приложение начало набирать обороты, как у пациента с сердечным приступом.

Время отклика API, которое должно было составлять 5 мс, теперь достигло 35-40 мс.

В результате мы немедленно провели проверку производительности (тестовая оценка) для каждой части кода и узнали, что в этом виновато сравнение списков, и я немедленно изменил это на структуру данных карты.

Бум, наше приложение начало отвечать со скоростью 5 мс, как и ожидалось.

На этом этапе я понял, насколько важно выбрать правильную структуру данных и что происходит, когда мы выбираем неправильную.