Зачем разработчику изучать алгоритмы и структуры данных? Помогает ли это в повседневной жизни? Это может быть очень долгая дискуссия, поэтому сегодня я покажу просто простой случай, который можно решить очень быстро, если знать, где искать ;)
Определим задачу: у нас есть бесконечный поток событий, которые приходят не по порядку. Порядок определяется порядковым номером события.
Проблема: события ДОЛЖНЫ обрабатываться в правильном порядке.
Упрощение: события выходят не по порядку в каком-то окне. Размер окна ограничен константой. Но: в пределах этого ограничения размер окна может отличаться. Окно №1 может быть размером 5, окно №2 — размером 3, окно №3 — снова размером 5 и так далее.
Другими словами, вот поток событий:
И вот как это должно быть обработано:
Попробуем решить задачу.
Подход №1
Читать полное окно событий, сортировать их, выдавать отсортированную кучу событий для дальнейшей обработки. Почему нет? Если фактический размер полученного окна меньше максимального размера, то полученное окно все равно будет упорядочено. И часть следующего окна идет сразу после первого окна. Правильно?
Во второй группе упорядоченных событий мы получили событие №7, которое должно быть обработано ДО события №10 из первой группы. Ой…
Подход №2
Теперь давайте вспомним структуры данных. Что выглядит способным обрабатывать упорядоченные данные и поддерживать вставку и извлечение событий с минимальным порядковым номером? Приоритетная очередь! Единственное, что вам нужно сделать, это установить соответствующий размер очереди и реализовать какое-то уведомление, когда размер очереди превышает пороговое значение (равное размеру окна).
С Go эта задача решается очень просто.
- PriorityQueue можно реализовать с помощью https://golang.org/pkg/container/heap/
- Когда в очередь добавляется новое событие, а размер очереди превышает пороговое значение, другое событие должно быть извлечено из очереди и отправлено в канал.
- Канал прослушивается потребителем, который обрабатывает событие.
Этот хотя бы эксперимент реализован здесь: https://github.com/elgris/eventqueue.
Так что же происходит сейчас?
Это был всего лишь небольшой пример, но когда я оглядываюсь назад, я вижу много возможностей, где знание алгоритмов и структур данных могло бы помочь (и помогло!!).
Если вы еще не потратили достаточно времени на их изучение, самое время закрыть эту статью и найти себе хороший курс на https://www.edx.org/. Позже, когда вы поймете, сколько времени вы сэкономили на своей работе по разработке программного обеспечения, потому что вы знали, где искать эффективное решение, улыбнитесь и продолжайте делать добрые дела :).