1. О данных и проблемах с ними
Как я писала, данные могут быть в не перевариваемом на первый взгляд виде, а ещё есть ньюансы, которые аналитик должен учитывать (мне это напоминает мутации в генетическом коде: вставки, пропуски, замены...:) ):
- Пропуски в данных
типо как мы видим график валют - вот эти падения в выходные неспроста, если посмотреть тренд... просто выхи не торговались!
-Выбросы в данных
Раз и скачок от тренда, и иногда выбросы надо выбрасывать, а иногда, напротив, их и смотреть - зависит от целей исследований
-Ошибки ручного ввода данных
это наподобие автоправки, бах, и что-то не то, а потом надо это анализировать...
- Актуальность данных
Это уже решать с экспертами...
График поможет понять, есть ли у вас эти траблы:
Структура данных (data structure) — реализация данных, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.
2. Какие бывают данные?
Есть разные классификации.
Бывают статические и динамические.
Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы, связанный список, стеки и очереди.
Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.
1). К неструктурированным относят текстовые, видеопотоки, фото, звуковые, которые хранятся с исходном формате, часто в спец.хранилищах.
2). Полуструктурированные данные не подчиняются табличной структуре моделей данных и содержат теги или другие маркеры для разделения семантических элементов и обеспечения иерархии. К ним относят, например, XML (eXtensible Markup Language — расширяемый язык разметки)и JSON (JavaScript Object Notation) - текстовый формат, основанный на JavaScript, служащий для обмена данными. От самого языка он не зависит и может использоваться с любым языком.
Типы Записей:
▪ Число
▪ Строка
▪ Литералы (null, false, true)
▪ Объект json (вложенное определение)
▪ Одномерный массив (объектов (число, строка, литерал, объект json)).
Плюсы:
▪ Читабельный / не зависит от языка
▪ Экономичней xml
▪ Поддержка множества библиотек
▪ Представляет собой текст.
* html vs xml не эквиваленты и служат для разных целей: первый для представления данных, второй для их использования:
3). Структурированные данные -
1. массивы -
Одномерные, элементы идут подряд в строчку. Многомерные, массивы внутри массивов.
Основные действия с массивом:
▪ Insert - вставляет элемент по заданному индексу
▪ Get - возвращает элемент по заданному индексу
▪ Delete - удаление элемента по заданному индексу
▪ Sort - сортировка массива по возрастанию
▪ Size - получить общее количество элементов в массиве
2. очереди построены по принципу FIFO - first in first out
Основные действия с очередью:
▪ Enqueue - вставляет элемент в конец очереди
▪ Dequeue - удаляет элемент из начала очередиis
▪ Empty - возвращает значение true, если очередь пуста
▪ Top - возвращает первый элемент очереди
3. стеки - принцип LIFO - Last in first out
Основные действия со стэком:
▪ Push - вставляет элемент сверху
▪ Pop - возвращает верхний элемент после удаления из стека
▪ isEmpty - возвращает true, если стек пуст
▪ Top - возвращает верхний элемент без удаления из стека
▪ Pip - отобразить содержимое стэка
4. мар - это структура данных, которая хранит данные в парах ключ / значение, где каждый ключ уникален. Map иногда называется ассоциативным массивом или словарем. Она часто используется для быстрого поиска данных.
Основные действия:
▪ Добавление пары в коллекцию;
▪ Удаление пары из коллекции;
▪ Изменение существующей пары;
▪ Поиск значения по ключу
5. хэш-таблицы
Хэш-таблица - это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.
Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше.
Поэтому, когда вы вводите пару ключ / значение в хеш-таблице, ключ проходит через хеш-функцию и превращается в число. Это числовое значение затем используется в качестве фактического ключа, в котором значение хранится. Когда вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ и вернет тот же числовой результат. Затем число будет использовано для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (1) в среднем.
Эффективность хэширования зависит от функции хэширования и метода борьбы с коллизиями.
6. графы
Графы представляют собой совокупности узлов (также называемых вершинами) и связей (называемых ребрами) между ними. Графы также известны как сети.
Одним из примеров графов является социальная сеть. Узлы - это люди, а ребра - дружба.
Ориентированные - есть направление связей.
Неориентированные - нет направления связей.
Два частых способа представления графа - это список смежности и матрица смежности.
Список смежности может быть представлен как список, где левая сторона является узлом, а правая - списком всех других узлов, с которыми он соединен.
Матрица смежности представляет собой таблицу чисел, где каждая строка или столбец представляет собой другой узел на графе. На пересечении строки и столбца есть число, которое указывает на отношение. Нули означают, что нет ребер или отношений. Единицы означают, что есть отношения. Числа выше единицы могут использоваться для отображения разных весов.
Алгоритмы обхода - это алгоритмы для перемещения или посещения узлов в графе. Основными типами алгоритмов обхода являются поиск в ширину и поиск в глубину. Одно из применений заключается в определении того, насколько близко узлы расположены по отношению к корневому узлу. Посмотрите, как реализовать поиск по ширине в JavaScript в приведенном ниже видео.
7. деревья
представляют собой иерархическую структуру, где каждый узел связан с одним родительским узлом и может быть связан с несколькими дочерними, за исключением корневого узла, у которого родительского нет. Могут быть представлены списками смежности, так и с использованием индексов или списков предков для повышения производительности.
Бинарное дерево/Дерево Бинарного Поиска - каждый узел имеет значение (оно же и ключ)/ отсортировано
Сбалансированное/AVL дерево - высота поддеревьев различается <=1 2-3-4 деревья
Варианты обхода дерева:
▪ В прямом порядке (сверху вниз) - префиксная форма.
▪ В симметричном порядке (слева направо) - инфиксная форма.
▪ В обратном порядке (снизу вверх) - постфиксная форма.
Не сбалансированное
Дерево для поиска текста (Т9/Текстовые процессоры)
Свойства Trie:
▪ Слова хранятся сверху вниз
▪ Каждый узел содержит одну букву слова.
▪ Дерево ветвиться, когда порядок букв отличается от других имеющихся в нем слов или же когда слово заканчивается.
▪ Каждый узел так же и булево значение указывающее, является ли он последним в слове.
В информатике двоичное дерево поиска (binary search tree, BST), также называемое упорядоченным или отсортированным двоичным деревом, представляет собой корневую структуру данных двоичного дерева, в которой ключ каждого внутреннего узла больше, чем все ключи в левом поддереве.
- оба поддерева — левое и правое — являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X;
- у всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных самого узла X.
Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:
- «Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека и операцией добавления новой записи.
- Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.
- Namespace — хранилище имён переменных с их значениями, возникающее в трансляторах языков программирования.
По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.
Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.
3. Измерения в данных
Существуют разные типы шкал (и каждый тип имеет несколько эквивалентных названий в литературе):
Соответственно, это разные типы данных, в разной форме, и между ними возможны различные типы манипуляций, и навряд ли будет возможен переход из одной в другую, если только при снижении уровня и дроблении.
Немного о кортежах
Кортеж — упорядоченный набор фиксированной длины. В теории множеств порядок элементов не важен.
На практике при описании поведения объектов, свойств объектов при перечислении элементов в структуре какого-то объекта обычно порядок следования элементов является существенным.
Любой массив данных, например, текст, множество чисел, полученных в результате измерения температуры в разные моменты времени.
С учётом обстоятельств реальность мы рассмотрим новый объект данных, который называется упорядоченным множеством - или кортежем.
Примером кортежа является очередь, составленная из людей, в которых один и тот же человек может занимать очередь не один раз.
Различают кортежи разной длины:
- пустой кортеж <>
- единичный <a>
- "двойка" <e,1> или точка в плоскости <x,y>
- "тройка" <a,b,c> или трёхмерный вектор в пространстве <x,y,z>
- "чётверки" - содержат 4 компонента
- "n-ки" - содержат n компонентов.
В некоторых языках программирования, например, Python, и в ML, кортеж как тип данных встроен в язык.
Кортеж отличается от списка тем, что элементы кортежа могут принадлежать разным типам, и набор таких типов заранее определён типом кортежа, а значит, и размер кортежа также определён. С другой стороны, коллекции (списки, массивы) имеют ограничение по типу хранимых элементов, но не имеют ограничения на длину. Так, например, в языке Rust функция может вернуть несколько значений с помощью упаковки в кортеж.
В реляционных базах данных кортеж — это элемент отношения.
Для N-ного отношения кортеж представляет собой упорядоченный набор из N значений, по одному значению для каждого атрибута отношения.