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

Question

[WebDev]

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

Comments

[hint000]

а массивы - это на самом деле хеш-таблицы

За пределами php это в основном не так.

[Vitsliputsli]

hint000, да и в php, это не всегда так.

Answer 1

[Wataru]

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

Comments

[WebDev]

Но ведь любое решение на PHP имеет большой оверхед по сравнению с нативными функциями? Неужели создание вручную дерева и метода поиска может быть быстрее встроенной функции?

[Wataru]

WebDev, даже код на php иногда можно ускорить в сотни раз, если использовать правильный алгоритм и структуры данных. Это с запасом покроет медленность этого решения на пхп против быстроты тупого решения на встроенных функциях.

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

Answer 2

[12rbah]

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

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

Answer 3

[KoreanGuy]

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

Answer 4

[Владимир Куц]

Assembler

Answer 5

[Василий Банников]

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

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

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

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

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

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

Answer 6

[Saboteur]

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

Assembler, C (не С++)

Answer 7

[АртемЪ]

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

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

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

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