От хаоса к порядку: достижение понимания алгоритмов посредством визуализации
8 апреля 2023 г.TL;DR
Как разработчик, готовящийся к интервью с компаниями FAANG, я столкнулся с трудностями при работе с простыми алгоритмами, такими как обход строки и проверка палиндрома. Однако я выстоял и после девяти месяцев напряженной работы смог освоить еще более специфические алгоритмы, такие как KMP. Все это время я полагался на блокнот и ручку, чтобы визуализировать, как работают алгоритмы сортировки и как сравниваются числа.
С чего все началось
Когда я начал готовиться к собеседованиям с компаниями FAANG, мне было сложно работать с простыми алгоритмами, такими как обход строк и проверка палиндрома. Были времена, когда я почти сдавался, но я всегда был тем, кто заканчивал то, что начал. Тот же подход был применен здесь, и после девяти месяцев напряженной работы я перешел от борьбы с простыми алгоритмами к пониманию более конкретных, таких как KMP (который мне очень нравится).
На своем пути к освоению этих алгоритмов я использовал блокнот и ручку, чтобы визуализировать, как работает сортировка, как сравниваются числа и куда все это идет. Это помогло мне лучше понять алгоритмы и улучшило мою способность с ними работать.
Все мы разработчики
Так почему бы не создать проект, визуализирующий алгоритмы сортировки в более удобном для пользователя виде? Кроме того, написание алгоритмических решений на другом языке дает дополнительную возможность лучше понять и изучить их.
Я воспользовался этой возможностью, чтобы улучшить свои знания и лучше понять путь сортировки. Создав мобильное приложение с помощью Flutter, я смог использовать свой опыт кроссплатформенной разработки для создания эффективного инструмента для визуализации сложных алгоритмов, в частности сортировки. Это позволило мне еще больше улучшить свои знания и понимание этих алгоритмов, а также создать удобную платформу, чтобы другие могли делать то же самое.
Flutter — удобный инструмент
Имея большой опыт разработки кроссплатформенных приложений с использованием платформы Flutter, я решил использовать ее для создания мобильного приложения для операционных систем Android и iOS. В настоящее время один и тот же код может работать на веб- и настольных платформах, если я добавлю поддержку.
В процессе я добился:
- Я смог написать те же алгоритмы с Dart поверх реализаций Java, которые я делал ранее на Leetcode и AlgoExpert (отличные ресурсы для подготовки к интервью).
- Я узнал о поставщике (рекомендуется использовать Riverpod), которого раньше не было в моем стеке разработки. Провайдер позволяет отлично разделить логику и пользовательский интерфейс и оперативно обновлять пользовательский интерфейс с использованием потребляемых данных, что делает процесс обновления очень плавным.
- Я также развил свое воображение и превратил простой набор чисел в приятные на вид виджеты. Чтобы упростить понимание алгоритмов, пользователи могут включать и выключать числа.
Моя реализация
Каждый алгоритм сортировки является потомком BaseSort, который, в свою очередь, является ChangeNotifier. Детали реализации каждого алгоритма описаны в его конкретной реализации: BubbleSort, HeapSort, InsertionSort, MergeSort и SelectionSort. BaseSort охватывает только основные части каждого алгоритма, такие как ссылки на левый и правый указатели, а также индекс отсортированной части. Этот класс отвечает за генерацию случайных данных и уведомление каждого подписчика о новом наборе данных.
class BaseSort with ChangeNotifier {
BaseSort() {
generateData();
}
List<int> array = List.empty(growable: true);
int left = -1;
int right = -1;
int sorted = -1;
bool isSorting = false;
@mustCallSuper
void generateData() {
array.clear();
isSorting = false;
int counter = 0;
final rand = Random();
left = -1;
right = -1;
sorted = -1;
while (counter < 50) {
// to show anything in case of 0 -> shifting it to 1
array.add(rand.nextInt(99) + 1);
counter++;
notifyListeners();
}
}
Future startSorting() async {}
Future sleep() async {
await Future.delayed(const Duration(milliseconds: 150), () {});
}
}
BaseSortWidget — это абстрактный класс, представляющий набор общих частей виджета с несколькими абстрактными методами, которые должны быть реализованы в каждом конкретном виджете алгоритма.
abstract class BaseSortWidget extends StatelessWidget {
@override
Widget build(BuildContext context) => Card(
margin: const EdgeInsets.all(8.0),
elevation: 2.0,
shape: const RoundedRectangleBorder(
borderRadius: BorderRadius.all(Radius.circular(12.0)),
),
child: Padding(
padding: const EdgeInsets.all(12.0),
child: Column(
mainAxisAlignment: MainAxisAlignment.center,
children: <Widget>[
Text(
algorithmName(),
style: const TextStyle(fontWeight: FontWeight.bold),
textAlign: TextAlign.center,
),
const SizedBox(height: 10),
consumerWidget(),
const SizedBox(height: 10),
Text(
algorithmComplexity(),
style: const TextStyle(fontWeight: FontWeight.bold),
textAlign: TextAlign.center,
),
],
),
),
);
}
Каждая реализация виджета алгоритма, за исключением SelectionSort, упрощена до состояния:
class HeapSortWidget extends BaseSortWidget {
@override
String algorithmName() => HEAP_SORT;
@override
String algorithmComplexity() => 'Time: O(n*log(n)) Space: O(1)';
@override
Widget consumerWidget() => Consumer<HeapSort>(
builder: (context, state, _) => Row(
mainAxisAlignment: MainAxisAlignment.center,
crossAxisAlignment: CrossAxisAlignment.end,
children: buildItemsArray(
state.array,
state.left,
state.right,
state.sorted,
Colors.cyan,
),
),
);
}
Все остальные части предназначены исключительно для эстетических целей, для создания более чистого и элегантного кода. Главный экран представляет собой список виджетов сортировки.
Consumer<SortHolder>(
builder: (context, types, _) {
final List<Widget> widgets = types.generateWidgets(context);
return widgets.isEmpty
? Center(
child: Text(
'$DRAWER_TITLEnn$EMPTY_MESSAGE',
textAlign: TextAlign.center,
style: Theme.of(context)
.textTheme
.bodyLarge
.copyWith(fontSize: 18.0),
),
)
: ListView(
padding: const EdgeInsets.all(8),
children: widgets,
);
},
)
Всякий раз, когда мы добавляем или удаляем виджеты, на экране появляется больше или меньше элементов. Для хранения данных о виджетах и для перемешивания данных/начала сортировки мы использовали SortHolder.
Вид
Полученное представление моей работы выглядит очень аккуратно и легко понятно.
Процесс сортировки
Наблюдать за процессом сортировки — сплошное удовольствие. Кроме того, проще понять алгоритм сортировки, увидев, какие данные сравниваются. Левый указатель представлен желтым, а правый указатель представлен красным. Наслаждайтесь!
Обзор
Во время подготовки к собеседованиям по алгоритмам и структурам данных может быть сложно освоить эти сложные темы. Люди используют разные подходы, чтобы сделать его проще и понятнее. Не имея доски, которая могла бы помочь мне визуализировать данные, я нашел простой блокнот и ручку весьма полезными, но для автоматизации процесса и повторения алгоритмов снова я использовал кодирование, один из инструментов, в котором я хорош. Теперь мы можем наблюдать, как работают эти алгоритмы. Но я хотел бы расширить эту базу знаний другими более сложными алгоритмами, визуализировать которые может быть еще сложнее. Но все же возможно.
Я призываю всех, кто хочет участвовать в этом проекте, внести свой вклад в мой gitHub через пулл-реквесты. Я рад посвятить время коротким встречам и совместной работе.
https://github.com/ВадимПинчук/visualizer?embedable=true
Оригинал