Курсы по программированию

Формула программиста
основатель — Волосатов Евгений Витольдович

Коллекция графа

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




2,000 руб.


Для подписки на пакет необходимо авторизоваться.

Список уроков | фото | видео

# Название видеоурока Решило Рейтинг Доступ
1 ArrayList 00:12:16 29 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Ознакомился с коллекцией ArrayList. 
Сложности: Ничего. 
Комментарии: Я выбрал метод OfType() который перебирает все элементы коллекции и возвращает, только те, которые соответствуют указанному типу TResult. На скриншоте представлен результат отбора элементов типа int. Изначально коллекция заряжена на 0 элементов. Но при добавлении первого элемента в коллекцию, она создает массив размером 4 элемента, так как это стандартная емкость и каждый следующий раз, когда мы превысим число элементов в массиве, создается новый массив размерностью в 2 раза больше, в который переписываются все элементы с предыдущего массива. 
2 List 00:12:57 29 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Поработал с типизированной коллекцией List. Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Я выбрал метод Average(), который возвращает среднее значение для элементов последовательности. Результат представлен на скриншоте. 
3 Array vs List 00:11:04 28 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Сoздaл три отдeльныe фyнкции List0(), List1(), List2(), которые реализуют соответственно базовый массив, ArrayList и типизированный список List
Сложности: Ничего. 
Комментарии: В своем случае я я выбрал такой набор операций: for (int i = 0; i < length; i++) al.Add(length - i); В общем случаем я заполняю массив / коллекцию по спадению от 1 000 000 до 1. Потом вызываю метод сортировки Sort() или Array.Sort(T[] array), который работает с худшим вариантом для сортировки, потому, что ему нужно полностью переставить все элементы в обратном порядке. И измеряю время которое затрачивается на это. Результаты показывают, что на сортировку типизированного списка List затрачивается не много больше времени, чем для обычного массива (и учтите, что при добавлении элементов в список он часто увеличивал свою емкость). А коллекция ArrayList ужасно проигрывает по времени всем. Результаты представлены на 1 скриншоте. Во 2м случае тестировки я немного выровнял шансы и указывал при инициализации коллекций емкость в 1 000 000 элементов. Результаты тестировки представлены на 2м скриншоте. 
4 ListDictionary 00:15:19 28 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: В дополнительных методах ничего стоящего не нашел. Сделал еще один цикл вывода содержимого словаря: IDictionaryEnumerator idict = dict.GetEnumerator(); while (idict.MoveNext()) { DictionaryEntry item = (DictionaryEntry)idict.Current; Console.WriteLine("{0}: {1}", item.Key, item.Value); } 
5 Hashtable 00:11:56 27 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Ознакомился со словарями. Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Для тестирования я выбрал коллекцию HybridDictionary, в 1 варианте создается массив из 1 000 000 HybridDictionary по 9 элементов в каждом, во 2 варианте создается один HybridDictionary с 9 000 000 элементами. Результаты тестирования, которые вы можете видеть на скриншоте показывают, что лучше использовать второй вариант (один экземпляр коллекции с множеством элементов), при этом время создания во 2м случаем примерно на 40-50% меньше. Соответственно 2й вариант работает быстрее. 
6 BitArray 00:14:00 27 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Ознакомился с коллекцией BitArray, которая позволяет работать с отдельными битами. 
Сложности: Ничего. 
Комментарии: Массив из 40000 элементов занимает в памяти всего 5000 байт. Если в памяти хранить аналогичный массив из 40000 элементов типа bool, то понадобиться 40000 байт. Очевидный выигрыш в занимаемой памяти в 8 раз, который дает BitArray . Для тестирования я выбрал методы Xor(), Or(), And() и Not() сделал с помощью их таблицу истинности, которую вы можете видеть на скриншоте. 
7 Граф 00:13:48 27 чел. ★ 4.9 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Ознакомился с понятием графа, способом их представления в виде матриц. 
Сложности: Ничего. 
Комментарии: Изобретать велосипед снова желания нету. Еще во время вебинара я говорил, что для хранение графа в памяти мы будем использовать коллекции. Поэтому придумать что-то опять не получается. 
8 Вершины 00:14:15 27 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Трудно переключаться между русской и английской раскладкой. Это вызывает внутреннее противоречие. 
Комментарии: Подход ЕВ я понимаю, это хорошая демонстрация возможностей си шарпа и главное можно не разбираться в переводе каких-то терминов. Как хранить рёбра? Нужно записать какие две вершины соединяет ребро. Это можно сделать разными способами - списками, словарями, даже массивами. 
9 Рёбра 00:12:47 26 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Продолжаем доработку графа. 
10 Инициация 00:11:15 26 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 12 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Графически отображать граф очень наглядно. 
11 Отображение 00:16:18 26 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Самостоятельные задания это хорошо. 
12 Шахматная доска 00:19:58 26 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Создал граф шахматной доски и отобразил его на экране. 
Сложности: Ничего. 
Комментарии: Немножко изменил стиль отображения графа. Евгений Витольдович нашел ошибку, почему у вас пропадает отрисовка ребер на панеле. Код можете просмотреть на 2-м скриншоте. 
13 Широкий поиск 00:14:59 26 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Проработал алгоритм поиска вширь с использованием очереди. 
Сложности: Самостоятельно проработать весь алгоритм поиска в ширь. 
Комментарии: Пример моего графа можно увидеть на скриншоте. Итак очередь для графа будет выглядеть так: 8 7 6 5 4 3 2 1 Конечно такая последовательность чистая случайность.  
14 Широкий алгоритм 00:14:12 25 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 20 мин. [Показать отчёт]
Научился: Написал и разобрался с алгоритмом поиска в ширь. 
Сложности: Разобраться в этом самостоятельно и действительно понять, как работает алгоритм. 
Комментарии: Ошибка нашел еще во время вебинара и справил её, мое решение выделено красным на скриншоте. 
15 Широкий пошаговый ход 00:11:46 25 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Визуализация выглядит красиво и очень наглядно демонстрирует работу алгоритма. 
16 Визуализация процесса 00:14:07 22 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 15 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: Ничего. 
Комментарии: Добавил numericUpDown для задания паузы отображения алгоритма поиска. 
17 Глубокий поиск 00:09:58 22 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 10 мин. [Показать отчёт]
Научился: Проработал и разобрался в алгоритме поиска вглубь. 
Сложности: Разобраться в этом самостоятельно. 
Комментарии: Кладем 1 вершину в стек и сразу же выталкиваем ее, кладем 2 и 3, берем 3 вершину и выталкиваем ее, кладем 4. Берем 4 и выталкиваем ее, кладем 5 и 6, берем 6 вершину и выталкиваем ее, кладем 7 и 8, берем 8 выталкиваем её, потом 7, потом 5 и в конце концов 2. Стэк на протяжении операций: 1 2 3 2 4 2 5 6 2 5 7 8 2 5 7 2 5 2 
18 Глубокий алгоритм 00:15:07 22 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 16 мин. [Показать отчёт]
Научился: Выполнил все задания. 
Сложности: После прохождения стольких уроков сложностей не возникает. 
Комментарии: Вебинар был просто замечательный как и сам курс, который дает очень основательные знания для работы с коллекциями. Рассмотрены и визуализированы два замечательных алгоритма, к которым думаю в свое время обращался или обратиться каждый программист. 
19 ФИНАЛЬНЫЙ УРОК 22 чел. ★ 5 Done
  Отчёт отправил: 4467. Alcatraz Решено за 5 мин. [Показать отчёт]
Научился: На протяжении курса научился многим вещам, понятиям и т.п. 
Сложности: Ничего. 
Комментарии: Вебинар был просто замечательный как и сам курс, который дает очень основательные знания для работы с коллекциями. Рассмотрены и визуализированы два замечательных алгоритма, к которым думаю в свое время обращался или обратиться каждый программист. Курс просто замечательный. 
  Итого:   19 видеоуроков общей продолжительностью 4 час. 06 мин. 22 чел. ★ 5  
  Финалисты:   Максим,   Alcatraz,   Дмитрий,   Tekashnik,   Denis,   Иван,   Дмитрий 199,   Николай,   Михаил,   Дмитрий,   Ender,   Платон,   Владимир,   Андрей Н.,   Владимир Борисенко,   Максим Лапшинов,   Permitin Alexey,   Новопашин Владимир,   Максим Саратов,   Алексей В.,   Denchik,   Елена .

Начинаем практику по языку C#




Чтобы стать хорошим программистом — нужно писать программы. На нашем сайте очень много практических упражнений.

После заполнения формы ты будешь подписан на рассылку «C# Вебинары и Видеоуроки», у тебя появится доступ к видеоурокам и консольным задачам.

Несколько раз в неделю тебе будут приходить письма — приглашения на вебинары, информация об акциях и скидках, полезная информация по C#.

Ты в любой момент сможешь отписаться от рассылки.
Научился: Узнал о паре новых коллекций, сравнил скорость их работы и не только вспомнил теорию графов, но и реализовал наглядное отображение поиска в ширину и глубину.
Трудности: Ничего
Мне всё понравилось =) Особенно часть, где ты видишь, как написанный тобой код пошагово показывает тебе работу различных способов поиска по графу. А кто не любит, когда работу программу можно буквально увидеть своими глазами? =)
Научился: На протяжении курса научился многим вещам, понятиям и т.п.
Трудности: Ничего.
Вебинар был просто замечательный как и сам курс, который дает очень основательные знания для работы с коллекциями. Рассмотрены и визуализированы два замечательных алгоритма, к которым думаю в свое время обращался или обратиться каждый программист. Курс просто замечательный.