Зачем разработчику изучать алгоритмы и структуры данных? Помогает ли это в повседневной жизни? Это может быть очень долгая дискуссия, поэтому сегодня я покажу просто простой случай, который можно решить очень быстро, если знать, где искать ;)

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

Проблема: события ДОЛЖНЫ обрабатываться в правильном порядке.

Упрощение: события выходят не по порядку в каком-то окне. Размер окна ограничен константой. Но: в пределах этого ограничения размер окна может отличаться. Окно №1 может быть размером 5, окно №2 — размером 3, окно №3 — снова размером 5 и так далее.

Другими словами, вот поток событий:

И вот как это должно быть обработано:

Попробуем решить задачу.

Подход №1

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

Во второй группе упорядоченных событий мы получили событие №7, которое должно быть обработано ДО события №10 из первой группы. Ой…

Подход №2

Теперь давайте вспомним структуры данных. Что выглядит способным обрабатывать упорядоченные данные и поддерживать вставку и извлечение событий с минимальным порядковым номером? Приоритетная очередь! Единственное, что вам нужно сделать, это установить соответствующий размер очереди и реализовать какое-то уведомление, когда размер очереди превышает пороговое значение (равное размеру окна).

С Go эта задача решается очень просто.

  1. PriorityQueue можно реализовать с помощью https://golang.org/pkg/container/heap/
  2. Когда в очередь добавляется новое событие, а размер очереди превышает пороговое значение, другое событие должно быть извлечено из очереди и отправлено в канал.
  3. Канал прослушивается потребителем, который обрабатывает событие.

Этот хотя бы эксперимент реализован здесь: https://github.com/elgris/eventqueue.

Так что же происходит сейчас?

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

Если вы еще не потратили достаточно времени на их изучение, самое время закрыть эту статью и найти себе хороший курс на https://www.edx.org/. Позже, когда вы поймете, сколько времени вы сэкономили на своей работе по разработке программного обеспечения, потому что вы знали, где искать эффективное решение, улыбнитесь и продолжайте делать добрые дела :).