😇
На testengineer.ru мы не размещаем рекламу, но над сайтом регулярно работают несколько человек. Поддержите нас, подписавшись на телеграм-канал "Тестировщик от бога"!
ДомойОбучениеСтруктуры данных - большой гайд

Структуры данных — большой гайд

Автор

Дата

Категория

Теория: Простое определение — Связь между алгоритмами и структурами данных — Простые структуры: типы данных — Сложные (интегрированные) структуры данных — Статические, динамические, полустатические Связные и несвязныеЛинейные и нелинейные

Стандартные операции и применение Как подобрать структуру данных — Встроенные структуры данных в Python — в Java — в JavaScript — Продвинутые структуры данных: деревья и графы

Практикум: Массивы Дженерики Список Связный списокХэш-сетСловарь/Хэш-картаОчередь Стек Кортеж

Где применяются: Массив Связный список Стек Очередь

Теория

Чтобы понять, что такое структуры данных, сначала уточним, что такое данные: это информация, определенным образом оптимизированная (приспособленная, упорядоченная, организованная) для эффективной обработки и дальнейшей передачи.

Структуры данных — это хранилища данных, упорядоченные особым образом и в определенном формате, что позволяет разработчику (и тестировщику!) эффективно обрабатывать, хранить, и передавать данные.

Более простыми словами

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

Алгоритмы и структуры данных — как это связано

Все приложения состоят из двух логических компонентов: алгоритмов и данных. Данные — это информация; алгоритмы — это правила, “инструкции”, которые обрабатывают эти данные. 

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

Существует классическая книга “Алгоритмы и структуры данных” швейцарского ученого Никлауса Вирта, воспитавшая уже поколения программистов (буквально поколения: первое издание книги вышло в 1976). В ИТ сложилась практика советовать новичкам начинать изучение алгоритмов и структур данных именно с этой книги; ее принято считать фундаментальной. К сожалению, примеры кода в этой книге составлены на древнем языке Оберон (и подобных, тоже древних, вроде Паскаля); вряд ли современный тестировщик когда-нибудь будет работать с кодом на этом языке; есть там и другие проблемы; а времени на учебу может быть мало; поэтому начинать изучение структур данных и алгоритмов (дисциплина «АСД» в университете на первом курсе профильных вузов) — лучше, например, с бесплатных (и при этом неплохих!) курсов в интернете; примеры там изложены на современных (и широко применяемых в QA) языках Python, Java, JavaScript.

Простые структуры данных (типы данных)

Это так называемые примитивы — базовые элементы в классификации структур данных. Типы данных это как бы кирпичики, из которых строятся сложные структуры данных. Типы данных в QA это, например: булевы (логические), целые, с плавающей точкой, двоичные, символы, указатели, строки, и подобные «неделимые». В языках программирования набор простых типов может отличаться.

В наглядном виде иерархия структур данных выглядит так:

data structure hierarchy

Сложные (интегрированные) структуры данных

Состоящие из других структур данных, простых или (тоже) интегрированных. Данный гайд описывает сложные структуры данных. Наиболее часто применяются в QA: массивы, стеки, связные списки, очереди, а также деревья (включая двоичные), и графы (“сложные деревья”).

Статические структуры данных

Данные имеют фиксированный формат, размер и расположение в памяти. Примеры: векторы, массивы, множества, записи.

Динамические структуры данных

Нефиксированный формат, размер и расположение; это изменяется в зависимости от задачи. Примеры: стеки, очереди, строки, списки, графы, деревья.

Полустатические структуры данных

Основная характеристика: изменяемый размер, но это изменение ограниченное, не превышающее какой-то лимит. Пример: однонаправленный связный список.

Линейные структуры данных

Данные упорядочены в последовательном порядке; как в массивах, стеках, очередях, связных списках. Каждый элемент “привязан” в последующему и предыдущему.

Нелинейные структуры данных

Данные расположены как бы в “рендомном” порядке, то есть без последовательности (привязки). Элементы могут быть “привязаны” к одному или многим другим элементам. Нелинейные структуры это деревья, графы.

Связные и несвязные структуры данных

Связные (связанные) структуры данных состоят из записей (узлов, нодов), связанных между собой при помощи указателей (коннекторов, ссылок). 

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

Примеры несвязных структур: массивы, строки, стеки, векторы.

Структуры данных — стандартные операции

  • Создание структуры данных.
  • Вставка данных в структуру. Существует три варианта вставки:
    • В начало
    • В конец
    • В нужное место
  • Обход (traversal) каждого элемента как минимум один раз.
  • Поиск элемента среди других. Варианты поиска:
    • Линейный (последовательный) поиск; простой
    • Бинарный (двоичный, полуинтервальный, логарифмический) поиск; он сложнее логически, но быстрее (производительнее)
  • Сортировка, то есть упорядочивание элементов, выстраивание их в нужном порядке.
    • Сортировка пузырьком (пузырьковая сортировка)
    • Сортировка выбором
    • Быстрая (сортировка Хоара)
    • Сортировка слиянием
    • Сортировка кучей (пирамидальная)
  • Слияние, то есть объединение элементов из двух сортированных структур
  • Обновление, то есть замена значения элемента в структуре новым значением
  • Удаление элемента из структуры; как и создание, удаление может быть из начала, конца, или из нужного места.

Применение структур данных

  • Сохранение новых данных в структуру данных (базу данных, чаще всего)
  • Управление системными ресурсами: выделение памяти, манипуляции с файлами и папками, формирование очередей задач
  • Обмен данными по сети (например, через TCP-IP)
  • Упорядочивание (организация) данных и их сортировка 
  • Индексация элементов в базе данных (присвоение условных номеров в нужном порядке)
  • Поиск нужных данных — самым быстрым и эффективным способом
  • Масштабирование (расширение или уменьшение) крупных объемов данных в Big Data

Как выбрать структуру данных — подходящую для моей задачи в QA

Проанализировать задачу, учитывая:

  • Какие операции поддерживаются в структуре данных
  • Вычислительная сложность. Сколько времени требуется на операции, сколько памяти выделяется? Опытный программист/тестировщик “на лету” оценивает это, учитывая все нюансы, соблюдая баланс краткости и эффективности.
  • Элегантность решения (да!)

Структуры данных в языках программирования: блиц

[имеются в виду встроенные (inbuilt), они же — наиболее часто применяемые, по крайней мере джуниором QA]

Структуры данных в Python

В Python существует 4 встроенных структуры данных: 

  • списки (List)
  • словари (Dictionary)
  • кортежи (или тюплы, Tuple)
  • и множества (или наборы, сеты, Set).

Для Junior QA с Python этих структур может быть достаточно, так как операции с этими структурами составляют примерно 80%  “от общей массы”.

Встроенные структуры данных в Python

СпискиСловари
— На списках следует сделать упор в изучении, поскольку они в Python являются очень функциональным и видимо наиболее часто применяемым инструментом; cловари и кортежи в некотором смысле “работают как вариации списков”
— Квадратные скобки: [ ]
— Допускаются элементы-дубликаты
— В списках можно хранить любые объекты (числа, строки, другие списки)
— Доступ к спискам осуществляется на программном уровне “как к строкам“, то есть используя срезы и конкатенацию
— На более фундаментальном уровне (уровне интерпретатора) списки в Python являются Си-массивами (фактически список это массив указателей)
— Словари похожи на хэши или карты в других языках программирования
— Фигурные скобки: { } — как и в множестве, но:
— Элементы в словаре — последовательность пар ключ:значение, через двоеточие, разделенных запятыми
— Ключи являются уникальными и неизменяемыми объектами
— Не допускаются элементы-дубликаты
— Начиная с версии Питона 3.7, словари являются упорядоченными структурами данных
КортежиМножества
— Круглые скобки: ( )
— Допускаются элементы-дубликаты
— “Как списки”, но неизменяемы (то есть нет методов добавления/удаления); чтобы защитить данные от непреднамеренных изменений
— А если понадобилось изменить данные в кортеже, есть функции преобразования “туда и обратно”: list() и tuple():
— Могут состоять из элементов совершенно разных типов, через запятую
— Занимают меньше места в памяти, чем списки
— В кортежи удобно включать списки
— Неупорядоченная коллекция уникальных (не повторяющихся) и неиндексированных объектов
— И бывают “замороженные множества” (frozenset), то есть неизменяемые
— Фигурные скобки: {} , как в словаре
— Не допускаются элементы-дубликаты
— Элементы множества являются неизменяемыми, но можно удалять их из множества и добавлять новые
— Элементом множества может быть число, строка, список; и не может быть кортеж
— Доступны все стандартные операции с множествами из математики (например объединение, пересечение, разность)

Структуры данных в Java

  • ArrayList
  • LinkedList
  • HashMap
  • Set

Подробнее о структурах данных в Java — в блиц-практикуме далее

Структуры данных в JavaScript

Массив (Array)Множество (Set)
Упорядоченный набор данных; дубликаты разрешены; 

Пример массива в JS:
[1, 2, false, ‘good’]
Неупорядоченный набор данных; дубликаты не разрешены

Пример множества в JS:
new Set ()
set.add(1)
Объект (Object)Карта (Map)
Состоит из пар {ключ:значение}; значения можно менять

Пример: 

{name: ‘Ivan’, age: 28}
Состоит из пар {ключ:значение}; только для хранения; для карты есть методы get, set, delete

Пример: 

new Map()
map.set(‘name’, ‘Ivan’)

Другие, наиболее часто используемые, структуры данных в JS:

  • Стек
  • Очередь
  • Хеш-таблица
  • Связный лист
  • Бинарное дерево

Продвинутые структуры данных: деревья и графы

Дерево

Нелинейная структура данных, состоящая из узлов (нодов, вершин), соединенных ребрами (edges): 

структтуры данных - дерево
Дерево

Более простые структуры данных, перечисленные выше, типа массива, связного списка, стека или очереди, являются линейными, то есть хранят данные в линейном, “последовательном” порядке. Это не всегда удобно; чтобы быстрее опрашивать данные и изменять их, изобрели деревья — нелинейные структуры специфического вида. 

Дерево является иерархической структурой данных. Пример иерархической структуры в ИТ: DOM-дерево HTML-документа, представляющее ее объектную модель. Пример иерархической структуры в жизни — генеалогическое дерево.

Термины

Узел (нод) — одна из “вершин” в древовидной структуре, здесь содержится ключ (значение), и указатель на нижестоящий, или дочерний узел (также потомок); соответственно главный узел называется родительским по отношению к дочернему (родитель). 

Ребра — связные линии, соединяющие узлы.

Корень — первый узел в дереве:

структуры данных - дерево - корень

Листья — последние узлы в дереве (терминальные), то есть они не имеют дочерних узлов. Все другие узлы называются внутренними.

структуры данных - дерево - описание
Источник

Высота дерева — длина самого продолжительного пути к листу.

Глубина узла — длина пути к его корню.

На рисунке ниже показаны высота (h) и глубина (d) каждого узла:

структуры данных - дерево - высота и глубина

Лес — совокупность не соединенных деревьев:

структуры данных - дерево - лес
лес

Наиболее распространённые типы деревьев:

  • Бинарное дерево
  • Бинарное дерево поиска
  • AVL-дерево
  • B-дерево
  • T-дерево

Часто применяется Бинарное дерево (двоичное) — в котором каждый узел имеет не более 2 потомков, левого и правого

структуры данных - бинарное дерево

Обход дерева — алгоритм получения доступа к нужному узлу, путем «обхода» (traversal) всех его узлов, по одному разу.

Существует поиск в глубину (алгоритм «идёт вглубь дерева до упора») и поиск по ширине (последовательный просмотр по «уровням» дерева). 

Поиск в глубину имеет три основных способа: центрированный, прямой, обратный (inorder, preorder, postorder).

Более подробно об обходе дерева.

Применение деревьев:

  • Бинарные деревья поиска (BST) — для очень быстрой проверки, есть ли элемент (в базе)
  • Специфический тип дерева, называемый trie (префиксное дерево), в современных моделях роутеров для хранения данных
  • B (дерево поиска) и T (trie) типы деревьев — в крупных базах данных
  • В компиляторах языков программирования, для проверки синтаксиса написанного кода

Граф

Граф — совокупность узлов (проще говоря, “контейнеров с данными”), соединенных с другими узлами в нужном порядке. 

структуры данных - граф

Граф математически описывается как структура вида G (V, E), где 

  • V — совокупность (коллекция) вершин (англ. vertices)
  • E — коллекция ребер, представляемых как упорядоченные пары вершин (u,v)
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Термины

Смежность (adjacency). Вершина смежна другой вершине, если между ними есть соединяющее ребро. Также ребра считаются смежными (между собой), если соединяют одну вершину.

Петля — ребро, имеющее только одну вершину (“тупиковое”).

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

Длина пути — количество ребер, которые “нужно пройти” в пути.

Цепь — если ребра по пути не повторяются.

Связный граф — в котором можно проложить путь между любыми двумя вершинами.

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

Подробнее терминология графов.

Частые операции с графами

  • Проверка наличия элемента в графе
  • Обход графа
  • Добавление элементов (вершин или ребер)
  • Поиск пути из одной вершины к другой

Пример графа IRL

Современные социальные сети типа Facebook представляют собой пример графа — каждая страница (Профиль, Фотографии, События, Комментарии, Сторис и д.т.) является узлом в графе социальной сети, привязанным к другим узлам ссылками-”ребрами”:

структуры данных - граф - социальная сеть

Структуры данных: практикум

Упомянутый выше ИТ-гуру, автор “Алгоритмов и структур данных” Никлаус Вирт писал, что “обучение путем подачи хорошего примера часто — самый эффективный, а иногда — и единственно возможный метод”. 

Туториал описывает структуры данных, которые наиболее часто применяются в QA (то есть в автоматизированных тестах); эти примеры на C# и Java; описания более-менее релевантны и для других языков.

Ремарка: сейчас ситуация на рынке труда в QA такова, что тестировщик, даже стажер, обязан владеть языком программирования в достаточной мере, чтобы легко оперировать структурами данных (и алгоритмами).

Arrays (Массивы)

Конечно, тестировищик-автоматизатор знаком с этой структурой, с первых недель изучения языка. Массив — это коллекция (сбор, группа) сходных элементов (похожих, однородных, одного типа). Это основная характеристика массива: он состоит из данных одного типа (а тип задается в начале, при описании массива).

Важные свойства массива:

  • Первый элемент в массиве, как правило, с индексом “0” (а не “1”). 
  • Если понадобился второй элемент массива, к нему обращаются по индексу “1”, и так далее.
  • При создании массива задается его размер — далее не изменяемый. 

Если создан массив из четырех элементов, в ячейку под номером 5 (с индексом 4 — см. выше) — уже ничего нельзя добавить, так как ее не существует и система выдаст ошибку-эксепшен

Чтобы добавить новый элемент к такому массиву, надо создать новый массив с новым размером, и скопировать в него предыдущий массив. В таком случае применяется обертка над массивом, об этом далее.

Существуют (и активно применяются в QA) структуры данных, более гибкие и удобные, чем простой массив — generic-обертки массивов; в C# это List, в Java — ArrayList

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

<base_url>?ids=2,5,7

Создается метод, который принимает массив из ID-шек, и конвертирующий их в строку с запятыми:

data_structures_tutorial_1

Другой кейс. Есть строка с цифрами и символами; надо изъять из нее цифры, и вывести их сумму. Вот так:

data_structures_tutorial_2

Как упоминалось выше, существуют genericобертки, более удобно оперирующие массивами. Вообще, тестеру, претендующему на миддла, очень желательно разобраться с дженериками на теоретическом уровне как можно раньше, до того, как приступать к углубленному изучению структур данных; ибо все структуры данных в известном смысле являются дженериками.

Generics (Дженерики)

Итак, что такое дженерик? С более “общей”, теоретической точки зрения, это класс с неким плейсхолдером, позволяющим описать его поля и методы. В дженерике во время компиляции подставляется нужный тип в плейсхолдер:

data_structures_tutorial_3-min
  • В Java и C# встроены дженерики ArrayList и List, Dictionary и так далее.
  • Можно задать ограничение в плейсхолдере, что присваиваемый тип должен соответствовать изначальному типу, или что не может быть “пустым” (null). Бывают и другие ограничения
  • Во многих дженериках предусмотрены удобные методы для манипулирования данными специфического типа
  • Можно даже создавать собственные дженерики (кастомные).

Кастомные дженерики. Например есть у нас REST-API-микросервис, и мы создаем тестовый проект. Наш микросервис всегда возвращает StatusCode (всегда одного типа) и какие-то данные Data (они меняются в зависимости от ответа конечной точки API).

Создаем generic-модель, которую потом можно использовать для всех других конечных точек:

data_structures_tutorial_4-min

Выше создана модель RestResponse, в которой свойства имеют постоянный тип — HttpStatusCode (строковый тип). И также имеется Body с типом T — этот тип может быть задан любым.

Итак, создается метод, который парсит наши JSON-данные для модели, и ожидаем RestResponce типа <T> — с любым типом. 

data_structures_tutorial_5-min

Список (List). List (C#) / ArrayList (Java)

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

Удобство такой обертки состоит в методах для манипулирования данными.

Взглянем на пример:

data_structures_tutorial_6-min

Разумеется, существует намного больше методов, и надо их знать (для QA-миддла это наверное обязательно). List / ArrayList это базовая структура данных, исходя из ее очень частой применяемости в QA, и операции с ней нужно практиковать. Существуют специальные библиотеки, LINQ в C# и Stream API в Java (об этом в конце практикума бонусный пункт).

В Сети много туториалов для практики со списками, в том числе и для QA-автоматизаторов. В них часто встречается задача поиска и сохранения WebElements со страницы, для дальнейшей обработки.

data_structures_tutorial_7-min

Самая частая задача: проверка наличия элемента на странице. Если пытаться найти один элемент, получают ошибку “Нет такого элемента”; если ищут список, можно просто проверить, что количество его элементов равно 0.

Еще бывает кейс ожидания, когда количество элементов превысит какое-то значение:

data_structures_tutorial_8

Аналогично как в предыдущем пункте с дженериками; API-ответ ожидается с каким-то количеством элементов, но мы не знаем, каким. Поэтому задаем List<DataType>:

data_structures_tutorial_9-min

Linked List (Связный список)

Эта структура данных применяется реже, но знать о ней нужно обязательно. Связный (еще называют связанный) список представляет собой последовательную (линейную) коллекцию элементов, порядок которых не соответствует их физическому расположению в памяти. В таком списке просто перечисляются элементы, каждый из которых связан со следующим (иногда связь в обе стороны). Индекс в связном списке не имеет смысла; запрашивают только текущий элемент, и элемент, связанный с ним. Поэтому такой элемент называется узлом (нодом). 

Каждый элемент содержит данные о себе, и может запрашивать следующий элемент. В связном списке нельзя “перепрыгнуть” от первого элемента сразу к последнему. Если нам нужен последний, надо “пройти по порядку” по всем элементам.

Так же у двухстороннего связного списка (иногда еще называется двусвязным). Элементы такого списка “знают” о (то есть имеют связь с) сразу с двумя элементами — предыдущим и следующим.

Hash Set (Хэш-сет)

Разновидность хэш-таблицы. Это набор (сет) коллекций, в которых нет одинаковых элементов; и которые выстроены в каком-то нужном порядке.

Попробуем добавить элементы-дубликаты в созданный хэш-сет:

data_structures_tutorial_10-min

Чем может быть полезен хэш-сет. Например, есть элементы-результаты, принятые от какого-то источника данных, и нужно профильтровать дубликаты. Создается HashSet<T> и в него добавляются все результаты. При этом дубликаты не смогут добавиться.

data_structures_tutorial_11-min

Примечание: в таких случаях можно применить Сортированный Сет (Sorted Set), элементы в нем сортируются автоматически:

data_structures_tutorial_12-min

Dictionary/HashMap (Словарь/Хэш-карта)

Как и хэш-сет, это разновидность Таблицы хэшей (Hash Table). Словарь в Java и C# это дженерик-класс с маппингом (картой), состоящей из пар ключ / значение. 

data_structures_tutorial_13-min
data_structures_tutorial_14-min

Ключи должны быть уникальными; попытка добавить дубликат вызовет ошибку.

data_structures_tutorial_15-min

Из-за своего удобства, такая специфическая структура данных является очень распространенной в практике QA.

Пример. Надо создать некий полезный метод работы с SQL-операторами. Для этого создаем словарь с ключами типа Enum и соответствующими им значениями SQL-операторов:

data_structures_tutorial_16-min

Далее передаем enum-ключ в метод, и получаем его значение:

data_structures_tutorial_17-min

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

data_structures_tutorial_18-min

Примечание. В Java эквивалент Словаря это HashMap:

data_structures_tutorial_19-min

Queue (Очередь)

Дженерик, содержащий коллекцию, организованную по принципу FIFO (“первым вошел — первым вышел”). Как обычная очередь из людей в магазин. Первый элемент, поступивший в Очередь, первым же ее и покидает.

data_structures_tutorial_20-min
data_structures_tutorial_21-min

В тестировании Очереди применяются, когда данные идут как бы “параллельно”, то есть одновременно поступают и отдаются. Например есть хранилище данных, и надо записать туда данные, и параллельно получить данные оттуда. 

data_structures_tutorial_22-min
data_structures_tutorial_23-min
data_structures_tutorial_24-min

Stack (Стек)

Это дженерик-класс с коллекцией, организованной по LIFOпринципу (“последним пришел — первым вышел”). Проще всего визуализировать Стек в виде стопки тарелок: тарелка, положенная в стопку последней, снимается первой.

data_structures_tutorial_25-min
data_structures_tutorial_26-min

Стеки чаще применяются в тестировании API-запросов. Допустим, может быть только одна операция со статусом “Выполняется” у одного Клиента. Но мы можем выполнять тесты параллельно, поэтому можно прописать в тесте на этапе beforeAll присвоение всем Клиентам ID-шек, и сохранить их все в Стеке.

data_structures_tutorial_27-min

Каждый тест пытается получить “самый верхний” ID Клиента и запустить тест с ним.

data_structures_tutorial_28

На cleanupэтапе теста возвращаем Client Id назад в Стек.

 

data_structures_tutorial_29

Итак, Стеки удобно применять в параллелизации тестов.

Tuple (Кортеж)

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

Допустим есть Customer и его заказы Orders, и надо получить данные из User Details и Order Details:

data_structures_tutorial_30

Значит, создаем метод, получающий (возвращающий) User-модель и список заказов Orders:

data_structures_tutorial_31

В конце вызываем этот метод:

data_structures_tutorial_32

Можно возвращать несколько элементов, причем разных типов:

data_structures_tutorial_33

Бонус — LINQ/Stream API

В целом, с самыми распространенными структурами данных в QA мы ознакомились. Но не лишним будет ознакомиться еще с такой вещью, как более удобная обработка списков в LINQ в C# (Language Integrated Query) и Stream API в Java. Эти вещи помогают более эффективно (то есть быстрее и изящнее) обрабатывать данные, особенно что касается их фильтрации по условию, а также конвертации форматов.

Пример. Фильтруем значения больше 80. 

Синтаксис LINQ — через очередь (query):

data_structures_tutorial_34

И через лямбду:

data_structures_tutorial_35

Как видим, одинаковые результаты:

data_structures_tutorial_36

Лямбда — более удобный способ обработки, и в основном применяется именно он. Еще примеры с лямбдой, 

Операции: Sum, Average, Skip, Take

data_structures_tutorial_37

Сумма и Среднее — стандартные примеры из учебников. Пропуск и Отбор надо рассмотреть подробнее. Пример: имеем массив, в котором нужно скипнуть (пропустить) один элемент, и принять в обработку два следующих. То есть пропускаем элемент с индексом 0 и принимаем элементы с индексами 1 и 2; в списке будут элементы со значениями 92 и 81.

data_structures_tutorial_38

Операции с элементами: First, Last, Where, All, Any

data_structures_tutorial_39

Выводятся результаты:

data_structures_tutorial_40

Операция выбора (выбрать все данные и конвертировать). Есть Имя, Должность, и Зарплата:

data_structures_tutorial_41

Выбираем только Имена:

data_structures_tutorial_42
data_structures_tutorial_43

Или можно конвертировать в более сложные объекты:

data_structures_tutorial_44
data_structures_tutorial_45

В Java схожая по функциональности библиотека. Например имеем коллекцию с фамилиями и возрастом:

data_structures_tutorial_46

Фильтруем по возрасту и выводим имена:

data_structures_tutorial_47

Результат:

data_structures_tutorial_48

Источник — Структуры данных в автоматизации QA / Kostiantyn Teltov

Структуры данных — где применяются

Массив

  • Контакты в смартфоне хранятся в массиве
  • Таблица результатов (или лучших игроков) в онлайн-игре хранится в массивах, сортируемых в ниспадающем порядке
  • Обработка изображений (двумерные массивы = матрицы)
  • Обработка речи (каждый звук сохраняется в виде массива)
  • Пиксели на экране — тоже массив
  • Названия книг в онлайн-библиотеке
  • Билеты при заказе в онлайн-букинге хранятся в массиве

Связный список

  • Список выполненных действий в Notepad (или любом редакторе); благодаря связному списку, можно отменить, повторить, или удалить действие
  • И другие системы навигации, например переход Вперед/Назад по посещенным страницам в браузере (двунаправленный связный список)
  • Слайд-шоу, то есть последовательный просмотр фоток тоже через связный список
  • Мультитаскинг в операционной системе с многими пользователями, работающими одновременно: каждому пользователю через связный список выделяется часть ресурсов системы
  • В мультиплеере во многих играх — циклический переход между пользователями
  • В музыкальном плеере — навигация в плейлисте
  • Посты на твоей странице Вконтакте идут в связном списке

Стек

  • В текстовых редакторах вместо связного списка делается стек выполненных операций, которые можно Отменить/Повторить
  • А также в браузерах, для навигации
  • Уведомления (notifications) в Youtube — стеки в LIFO-формате; последние просмотренные видео показываются сначала
  • Стеки управления памятью — важнейший компонент в операционной системе Windows

Очередь

  • В операционной системе: списки ожидания на выполнение в устройствах типа принтера, жесткого диска, процессора
  • А также ожидание прерываний
  • В мессенджерах на смартфонах: когда пропадает мобильное покрытие у получателя, отправленные сообщения на сервере ждут в очереди на доставку
  • В планировщиках задач
  • Действия клавиатуры и мыши (что хорошо видно, когда система тормозит)
  • Управление трафиком на сайтах
  • Управление shared-ресурсами в локальных сетях

***

Также на сайте:

Что такое кросс-браузерное тестирование?

В чем разница между QA и QC?

Какой была ваша первая зарплата в QA и как вы искали первую работу?

Мега обсуждение в нашем телеграм-канале о поиске первой работы. Обмен опытом и мнения.

Подписаться
Уведомить о
guest

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии
$1100*
медианная зарплата в QA в ноябре 2021

*по результатам опроса QA-инженеров в нашем телеграм-канале

Последние публикации

Мы в Telegram

Наш официальный канал
Полезные материалы и тесты
Готовимся к собеседованию
Project- и Product-менеджмент

💬 Telegram-обсуждения

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

Последние комментарии