Кто и когда использует бинарные деревья и другие структуры данных?

@kirill-93

Здравствуйте. Существуют разные структуры данных (связные списки, деревья, хэш-таблицы) и разные алгоритмы (quick sort, heap sort и тд). Я разработчик php+js и не пользуюсь ими, но как я понимаю, в основе языка лежат все эти структуры данных и алгоритмы. Например, функция sort внутри использует какой-то такой алгоритм, а массивы — это на самом деле хеш-таблицы.
Есть ли какой-то язык программирования или область, где нужно самостоятельно строить бинарное дерево или писать скрипт поиска в массиве или эти знания нужны только в академических целях, чтоб понимать как все работает?
Во всех известных мне ЯП уже есть встроенные функции для этого. Даже в «низкоуровневом» C есть функция qsort.
Спасибо.

Решения вопроса 1

@wataru Куратор тега Алгоритмы

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

2
комментария

Ответы на вопрос 6

@KoreanGuy

из личных примеров: в игре жанра Line Tower Defence с полем из шестиугольников нужно было реализовать поиск пути. Стандартный механизм Юнити был явным оверкиллом, поэтому вручную написал простой алгоритм, который использовал граф. Второй пример буквально недельной давности: имея набор из 11 футболистов и зная какие позиции они предпочитают, определить наиболее вероятную расстановку на поле, чтобы можно было в UI нарисовать. Через деревья реализовал. А связные списки вообще повсеместно используются.

@fox_12

Assembler

@vabka

Я разработчик php+js и не пользуюсь ими

Тебе кажется. На самом деле обычный js-объект и есть хэш-таблица. Ну и ассоциативные массивы в php тоже.

Я разработчик php+js и не пользуюсь ими

Вот чтобы такие глупости и нужно знать о них.

Есть ли какой-то язык программирования или область, где нужно самостоятельно строить бинарное дерево или писать скрипт поиска в массиве или эти знания нужны только в академических целях, чтоб понимать как все работает?

В принципе любой, если стандартная реализация не подходит.

@12rbah

Есть ли какой-то язык программирования или область, где нужно самостоятельно строить бинарное дерево или писать скрипт поиска в массиве или эти знания нужны только в академических целях, чтоб понимать как все работает?

От языка программирования это не зависит, т.к. это все обычно реализуется стандартными средствами, попытка написать свои реализации грозит наличием в них ошибок. Свои реализации обычно пишут под конкретную задачу, например ast дерево популярно для написания парсеров, https://habr.com/ru/company/mailru/blog/323242/ тут самописная реализация хэш-таблиц.

@saboteur_kiev Куратор тега Программирование

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

Assembler, C (не С++)

@Jump

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

Неправильно понимаете, хотя они и используются.

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

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

Похожие записи:

Добавить комментарий Отменить ответ