Алгоритм поиска сущности, на которую не ссылаются

@Джон Кофи · Регистрация: 05.04.2018

Студворк — интернет-сервис помощи студентам

Привет. Есть массив сущностей с 2 полями id, parentId. Где id - идентификатор сущности, parentId - идентификатор родителя. Нужно найти все сущности, которые не являются родителем, те найти конец ветки. Массив 12500 элементов.
Я сделал так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i(0); i < size; ++i) {
    Entity *foundEnt = entites[ findChild(entities[i]->id) ];
    result.append(foundEnt);
}
//Возвращает позицию элемента, на которую нет ссылок
int findChild(const int id) const
{
    for(int i(0); i < size; ++i)
    {
        Entity *entity = entities[i];
        //Если на эту сущность ссылаются
        if(entity->parentID == id)
            findChild(entity->id);
        if(i == size - 1)
            return i;
    }
}

Не смотрите на указатели, синатксис и пр, я еще не запускал код, накидал, чтобы обсудить. Хочу найти решение оптимальней, тк это будет запускаться на JS.

Добавлено через 57 минут
тут в чем еще может быть проблема - браузерам не очень нарвится рекусрия, хром, к примеру, может кинуть ошибку, если будет глубина рекурсии большой, вроде такую RangeError: Maximum call stack size exceeded. Я в веб только окунулся, на плюсах как-то всё проще было, если честно, тут много нюансов.

@Ygg · 22.06.2021, 13:12

Мне кажется, что ваш код не рабочий. findChild может возвращать только одно число. Теоретически, вашу рекурсию можно заменить циклом. Однако, ваша структура данных может содержать кольца, последний элемент цепочки может ссылается на уже пройденный элемент цепочки. Ещё поиск по ID можно немного ускорить, если отсортировать данные по родительскому ID.

Добавлено через 18 минут
Не, тут что-то не так)
У родителя может быть много потомков. Тут цепочки вообще не нужно смотреть. Достаточно понять, есть ли хоть один элемент, у которого проверяемый элемент в родителях. Если нет таких, то проверяемый элемент подходит под условия. В противном случае проверяем следующий элемент.

@vantfiles · 22.06.2021, 14:02

Сообщение от Джон Кофи

если будет глубина рекурсии большой

По определению, любую рекурсию можно развернуть в цикл. О самой задаче ничего сказать, простите, не могу.

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

Добавлено через 13 минут

Сообщение от Джон Кофи

Массив 12500 элементов.

В крайнем случае:

создаем массив 12500 элементов, заполняем его false.
бежим по массиву и меняем на true все parentId.
уцелевшие от этого прохода будут листьями.

Добавлено через 6 минут
я не очень сумбурно объяснил?

@Джон Кофи · 22.06.2021, 14:08 **[ТС]**

Сообщение от vantfiles

я бы подумал о реорганизации структуры данных

сделаю вроде такого, наврное. Тк сущность тянется из бд, то можно добавить поле-флаг указывающий является ли строка концом, те на неё нет ссылок. Либо, я, правда, не знаю возможно ли такое силами мускула, сделать внутренние связи в таблице id-parentId, и перед выборкой смотреть ссылается ли на id кто-то только в пределах таблицы (тк есть ссылки на эти id у других таблиц). Если ссылок внутри таблицы нет - наш клиент, забираем) Должно быть быстро. Тогда на JS ничего и перебирать не надо, уже готовыми данными буду распологать.

Добавлено через 1 минуту

Сообщение от vantfiles

я не очень сумбурно объяснил?

нет, спасибо, вроде понял))

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@Ygg 2735 / 890 / 331 Регистрация: 10.02.2018 Сообщений: 2,112
	22.06.2021, 13:12
	Мне кажется, что ваш код не рабочий. findChild может возвращать только одно число. Теоретически, вашу рекурсию можно заменить циклом. Однако, ваша структура данных может содержать кольца, последний элемент цепочки может ссылается на уже пройденный элемент цепочки. Ещё поиск по ID можно немного ускорить, если отсортировать данные по родительскому ID. Добавлено через 18 минут Не, тут что-то не так) У родителя может быть много потомков. Тут цепочки вообще не нужно смотреть. Достаточно понять, есть ли хоть один элемент, у которого проверяемый элемент в родителях. Если нет таких, то проверяемый элемент подходит под условия. В противном случае проверяем следующий элемент. 1