Вход | Регистрация
 
1С:Предприятие :: 1С:Предприятие 8 общая

Быстрый поиск по дереву. в дереве n уровней. поиск по последнему элементу в дереве.

Быстрый поиск по дереву. в дереве n уровней. поиск по последнему элементу в дереве.
Я
   zladenuw
 
11.03.20 - 01:46
Поиск по последнему элементу в дереве. как реализовать ?
 
 
   DEVIce
 
1 - 11.03.20 - 05:41
(0) Рекурсивный обход. Пара строчек кода.
   strange2007
 
2 - 11.03.20 - 05:57
Если по последнему элементу, тогда рекурсивно позиционироваться на последнюю строку коллекции родительской строки, пока не получишь строку без строк. Это и будет последний элемент в дереве
А вот если по последнему уровню, тогда да, рекурсивно спускаться до нижнего уровня и НайтиСтроки
   rphosts
 
3 - 11.03.20 - 06:19
(0) уровней("самых глубоких") может быть несколько... как и элементов в разных ветках иерархии. Задача неоднозначна
   rphosts
 
4 - 11.03.20 - 06:27
+ (3) любая рекурсия заменяется циклом, да менее удобно, но скорость и память! С точки зрения программиста (а не одинэсника, хотя и тут есть разные мнения) глубоковложенная рекурсия куда контекстно тащатся десятки и сотни килобайт данных - прекрасный образчик говнокода. И к тому-же даже при минимальном контексте рекурсия глубже примерно 4500 приводит к падению сеанса, но до этой глубины мало кому удавалось нырять.
   strange2007
 
5 - 11.03.20 - 06:55
(4) >> С точки зрения программиста
Уточняй, что с точки зрения явиста или сишника, которые вообще не представляют о программировании ни-че-го. Со стороны машины, многие рекурсии потребляют меньше памяти, чем при плоском обходе. А то нашёл тут программистов, которые вообще не представляют как данные располагаются в памяти. Хех!
А знаешь почему рекурсия меньше памяти ест? Да потому что у тебя данные о вложенности более структуированы и компактны, нежели при плоском анализе, где иногда такая каша собирается только по информации про уровни, что просто жесть. Вот как раз 1С-ники про это знают.
А то ишь, блин, 1С-ников записал в непонятно кого)))))))

Примечание: ассемблер, это на всю жизнь
   rphosts
 
6 - 11.03.20 - 06:59
(5) Сишняк наше всё! каждая рекурсия - это ты снова хапаешь памяти для передачи параметров. Сам по себе цикл работает с одной копией данных в памяти, хотя конечно и внутри цикла можно начать какие-то таблицы создавать/заполнять.
Ассемблер... ничего красивее адресации к данным на уровне машкода чем в PDP-11 не видел (возможно у VAX было ещё красивее, но не приходилось)...
   DEVIce
 
7 - 11.03.20 - 07:30
(6) "каждая рекурсия - это ты снова хапаешь памяти для передачи параметров". Указатели? Не, не слышали. :)
   strange2007
 
8 - 11.03.20 - 07:59
(6) Та неееее, там самая трубень начинается, когда расслабленный и воодушевлённый красивостью рекурсии, передаёшь вниз копию за копией данных. А вот когда используешь обход плоской модели, то тут расчётные данные узлов могут сделать тоже самое - многократное дублирование данных на каждой итерации. И самая главная фигня, из-за которой не люблю плоские обходы, это когда создаёшь трансформированные данные для всего дерева. Там избыточность иногда получается большая.

В общем я должен был защитить рекурсию, потому что моё дерево на ассемблере как раз часто обходится рекурсивно. Ну не буду же признаваться в своей слабости то
   strange2007
 
9 - 11.03.20 - 08:10
(0) Если надо периодически производить поиски, тогда можно первый раз закэшировать нужные ветки дерева во что-то круто индексируемое и потом искать уже очень быстро. Но тут памяти будет расходоваться больше
   rphosts
 
10 - 11.03.20 - 08:14
(8) ВК на асме для 1С?
   strange2007
 
11 - 11.03.20 - 08:20
(10) Не, я для своих поделок. Такое представление данных более удобно. Ну и что я, не 1С-ник что ли? Куда ж без дерева то?
   rphosts
 
12 - 11.03.20 - 08:21
(7) для дерева не канает, типичный обход дерева рекурсией: http://catalog.mista.ru/public/72380/

Процедура СчитатьСуммыДЗ(СтрокиДЗ)
    Для Каждого СтрокаДерева Из СтрокиДЗ Цикл
        // Если мы в строке, у неё нет итогов, пропустим

        Если СтрокаДерева.Строки.Количество() = 0 Тогда
            Продолжить;
        КонецЕсли;
        СчитатьСуммыДЗ(СтрокаДерева.Строки);
        // Для текущей записи вычислим сумму строк колонки

        СтрокаДерева.ФактОстаток = СтрокаДерева.Строки.Итог("ФактОстаток");
    КонецЦикла;
КонецПроцедуры// СчитатьСуммыДЗ()


на каждой новой итерации пока идёшь вглубь новая коллекция строк, да она будет передана по ссылке, но если это не последний уровень - на следующем шаге будет создана ещё 1 коллекция
   APXi
 
13 - 11.03.20 - 08:28
Засунь данные во что нибудь где будут поля поле поиска(желательно индексируемое) и ссылка на строку дерева.
   Сияющий в темноте
 
14 - 11.03.20 - 09:01
я так и не понял,какой последний элемент мы хотим найти.
ну,сидим мы у корня дерева,смотрим вверх,куда нужно смотреть,на шидирующмй побег или на самую ветвистую ветвь?
а если у нам куст?
на ассемблере под параметры расходуется стек,однако.
   trad
 
15 - 11.03.20 - 09:10
(12) " да она будет передана по ссылке, но если это не последний уровень - на следующем шаге будет создана ещё 1 коллекция"
Нет не будет.
В следующую вложенность будет передана ссылка на другую, уже существующую в дереве, коллекцию строк.
   strange2007
 
16 - 11.03.20 - 09:15
(14) >> на ассемблере под параметры расходуется стек,однако.
Это кто как придумает. Не всегда стек используется, можно просто в памяти структуру организовать и её использовать
   strange2007
 
17 - 11.03.20 - 09:42
Нафиг ассемблер. Расплодили ассемблеров, теперь вообще в них фиг разберёшься. Раньше был tasm и masm, всё просто. А сейчас...
Автор, люди дело говорят, с рекурсией будь аккуратней, но я задам вопрос публике:
Подскажите, а как в 1С обойти дерево без рекурсии, если уровень вложенности неизвестен?
   Сияющий в темноте
 
18 - 11.03.20 - 19:03
(17) массив вложенности и цикл
добавляем в массив корень
в цикле берем из массива строку выбираем к ней подстроки и пихаем в массив,закончив идем к следующему элементу массива.
когда мы пройдем весь массив,то в нем будут все строки дерева.
   Сияющий в темноте
 
19 - 11.03.20 - 19:05
на самом деле,очень затратная по памяти операция,можно имитацию рекурсии делать,сохраняя в массив только родительские строки.
   fisher
 
20 - 12.03.20 - 12:11
(0) Два вопроса.
1) О каком дереве речь? Об одинэсном или другом каком?
2) Что такое "последний элемент дерева"?
ЗЫ. Есть несколько классических способов обхода деревьев. Легко гуглится.
   pechkin
 
21 - 12.03.20 - 12:16
если дерево упорядоченно, то можно методом дихотомии
   pechkin
 
22 - 12.03.20 - 12:17
(17) это называется перебор с возвратом
   fisher
 
23 - 12.03.20 - 13:24
(17) > Подскажите, а как в 1С обойти дерево без рекурсии, если уровень вложенности неизвестен?
А в чем проблема-то? Реализуешь стек на массиве и заменяешь рекурсию на циклы с явным запоминанием/восстановлением состояний в стеке. Только зачем?
Как раз для обхода деревьев рекурсия как правило самое оно.
   fisher
 
24 - 12.03.20 - 13:25
Не говоря уже о том, что работа с суррогатным стеком в 1С выйдет дороже, чем рекурсия.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.