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

Ответ 1

Нашел список в аналогичном вопросе, ранее в StackOverflow:

Hash Table - используется для быстрого поиска данных - таблица символов для компиляторов, индексирование базы данных, кеширование, уникальное представление данных.

Trie - словарь, например, найденный на мобильном телефоне для автозаполнение и проверка орфографии.

Дерево суффикса - быстрый поиск полного текста, используемый в большинстве текстовых процессоров.

Stack - отменить\повторить операцию в текстовых процессорах, оценку выражения и синтаксический анализ, многие виртуальные машины, такие как JVM, ориентированы на стек.

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

Приоритетные очереди - планирование процесса в ядре

Деревья - парсеры, файловая система

Дерево Radix - таблица IP-маршрутизации

Дерево BSP - трехмерная компьютерная графика

Графики - Связи/отношения в социальных сетях, Маршрутизация, сети связи, организация данных и т.д.

Куча - распределение динамической памяти в lisp

Это ответ, первоначально отправленный RV Pradeep

Некоторые другие, менее полезные ссылки:

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

Не сфокусировано на приложении, по хорошему резюме и релевантности

Ответ 2

Я в той же лодке, что и ты. Мне нужно учиться для технических интервью, но запоминание списка не очень полезно. Если у вас есть 3-4 часа, чтобы сэкономить, и вы хотите сделать более глубокое погружение, я рекомендую проверить

mycodeschool
Ive посмотрел на Coursera и другие ресурсы, такие как блоги и учебники, но я нахожу их либо недостаточно исчерпывающими, либо на другом конце спектра, слишком плотными с предпосылкой компьютерных терминов.

У чувака в видео есть куча лекций по структурам данных. Не обращайте внимания на глупые рисунки или небольшой акцент. Вам нужно понять не только, какую структуру данных выбрать, но и другие моменты, которые следует учитывать, когда люди думают о структурах данных:

• плюсы и минусы общих структур данных
• почему существует каждая структура данных.
• как он работает в памяти
• конкретные вопросы/упражнения и решение о том, какую структуру использовать для максимальной эффективности
• lucid Big 0 описание

Я также разместил заметки о github, если вы заинтересованы.

Ответ 3

В соответствии с моей структурой данных понимаются любые данные, хранящиеся в памяти любой электронной системы, которая может быть эффективно управляема. Много раз это игра памяти или более высокая доступность данных. С точки зрения памяти снова есть компромиссы с управлением данными, основанными на стоимости для компании этого конечного продукта. Эффективно управляемый говорит нам, как лучше всего получить доступ к данным на основе основного требования конечного продукта. Это объяснение очень высокого уровня, но структуры данных - обширные предметы. Большинство интервьюеров погружаются в структуры данных, которые они могут позволить себе обсуждать в интервью, в зависимости от времени, которое они имеют, которые связаны списками и смежными темами.

Теперь эти типы данных можно разделить на примитивные, абстрактные, составные, основанные на том, как они логически построены и доступны.

• примитивные структуры данных являются основными строительными блоками для всех структур данных, у них есть непрерывная память для них: boolean, char, int, float, double, string.
• составные структуры данных - это структуры данных, состоящие из нескольких примитивных типов данных. класс, структура, объединение, массив/запись.
• абстрактные типы данных представляют собой составные типы данных, которые имеют способ эффективного доступа к ним, который называется алгоритмом. В зависимости от способа доступа к данным структуры данных делятся на линейные и нелинейные типы данных. Связанные списки, стеки, очереди и т.д. Являются линейными типами данных. кучи, двоичные деревья и хеш-таблицы и т.д. являются нелинейными типами данных.

Надеюсь, это поможет вам погрузиться.

Ответ 4

Отличная книга "" Руководство по разработке алгоритмов" от Skienna содержит огромное хранилище алгоритмов и структуры данных.

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

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

Другим важным ресурсом является NIST Dictionary of Data структуры и алгоритмы.

Ответ 5

Любое ранжирование различных структур данных будет по крайней мере частично связано с проблемным контекстом. Это поможет узнать, как анализировать время и пространство в алгоритмах. Как правило, используется "обозначение большой O", например. бинарный поиск находится в O (log n) времени, что означает, что время поиска элемента - это журнал (в базе 2, неявно) числа элементов. Интуитивно, поскольку каждый шаг отбрасывает половину оставшихся данных как нерелевантных, удвоение количества элементов увеличивает время на 1 шаг. (Бинарные поисковые шкалы довольно хорошо.) Космическая производительность касается того, как увеличивается объем памяти для больших наборов данных. Также обратите внимание на то, что примечание "большой О" игнорирует постоянные факторы - для небольших наборов данных алгоритм O (n ^ 2) может все же быть быстрее, чем алгоритм O (n * log n), который имеет более высокий постоянный коэффициент. Сложные алгоритмы часто имеют больше работы для запуска.

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

В то время как вам нужно изучить поведение нескольких структур данных, чтобы иметь возможность их сравнивать, один из способов развить смысл, почему они отличаются по производительности, - это внимательно изучить некоторые из них. Я бы предложил сравнить односвязные списки, двоичные деревья поиска и пропустить списки, все из которых относительно просты, но имеют очень разные характеристики, Подумайте, сколько работы требуется, чтобы найти значение, добавить новое значение, найти все значения в порядке и т.д.

Существуют различные тексты по анализу производительности алгоритмов/данных, которые рекомендуют люди, но то, что действительно заставило их иметь смысл, - это изучение OCaml. Работа со сложными структурами данных - это сильный подход ML, и их поведение намного яснее, когда вы можете избежать указателей и управления памятью, как в C. (Изучение OCaml просто для понимания структуры данных почти наверняка является длинным, хотя.))

Ответ 6

Я думаю, что более разумно просто изучать особенности структур данных.

Основываясь на сценарии, который дает ваш интервьюер, выберите подходящий.

Я говорю ложь людям, которые утверждают, что разработка программного обеспечения и программирование не являются творческими.

Ответ 7

Несколько практических применений структур данных

Красно-черные деревья (используется при частом вставке/удалении и несколько поисков) - К-средняя кластеризация с использованием красного черного дерева, Базы данных, Простодушная база данных, поиск слов внутри словарей, поиск в Интернете

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

Min Heap - Алгоритмы кластеризации

Ответ 8

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

Проблема с алгоритмом решения