|
|
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
По таблицам: 148 и 149 (четвертое поколение от 29) - брат и сестра!!! Инцест налицо. Не исключено что таких пар больше чем одна. По моему алгоритму их потомки считаются дважды. а 93907 - это вообще гермафродит - то он жена, то муж. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 02:12 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2 lobodava В этой жизни и не такое возможно :) Между прочим, это родичи Рюрика... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 07:05 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
вероятно, проблема во внутрисемейных браках между поколениями. За счет этого число вхождений потомка в таблицу быстро растет. (чтобы отсеять подозрения на петли, запускаем ваш первый рекурсивный алгоритм (с моими правками, ес-сно). Там, если бы мы наткнулись на петлю, то рекурсия бы из этой ветки никогда не вышла, и число вхождений некоего потомка в таблицу росло бы бесконечно (если петля короткая, то это было бы и легко заметно). Пока я не вижу быстрого роста числа входений одной и той же выделенной группы лиц (может быть группа и есть, но "слабо изолирована" - т.е. имеет множество "непетлевых" потомков, число входений которых в группу растет. Но, мне кажется, это пока не подверждается) запускаем (у меня таблица "потомки" не индексирована !!! - т.е. возможно многократное повторение вставки потомка на уровень): Start(7) при числе потомков 155090 (не дожидаясь окончания счета) прерываемся и видим: Код: plaintext 1. 2. 3. 4. 5. 6. это запрос вида: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. и Код: plaintext 1. 2. 3. 4. 5. 6. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. О графике: Именно потому, что количество потомков на уровень быстро растет, видимо будут расти и размеры массивов текущего/следующего уровня при нерекурсивной процедуре. А это потребует изрядного времени на их копирование (из одного в другой). При наличии уникальных индексов в таблице потомков, будет расти время работы вхолостую (попытки вставить имеющейся пары (потомок,уровень) Если надо найти только потомков (т.е. хотя бы одно вхождение), то скорость счета можно увеличить, отбрасывая повторные вхождения потомка в набор (в другом поколении). ___ Как ускорить текущую задачу: 1. Так же надо добавить процедуру(ы) "индексирования" массивов (быстрое упорядочивание массива поколения с удалением дубликатов, или даже вставки в уже упорядоченный набор (без вставки дублей). Тогда разрастания массива за счет множественности вхождений не потребуется. 2. Возлагать отбрасывание повторных вхождений потомков на уровень на Jet - за счет уникального индекса (потомок, уровень) - для нерекурсиной процедуры вряд ли имеет смысл (если только не заменять процедуру заполнение массива текущего уровня чтением из таблицы). И я не уверен, что проверка уникальности на большой таблице (т.е. с чтением индекса) будет быстрее (таких же) методов быстрого поиска, но внутри исключительно (!уже) размещенного в памяти массива. Однако подкупает простота реализации. Попробуйте. (Не надо передирать методов быстрого поиска/сортировки/вставки_в_сортированный_список из каких - нить букварей - все реализовано в движке jet). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 11:38 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
итак, не входя в сортировку массивов, добавляем потомкам уникальные индексы (iGen,Childe) и наоборот + правим рекурсивные процедуры (по крайней мере "моя" StartT(7) - прогонка по рекордсету начинает завершаться в разумное время -222718 потомков(с вероятностью нескольки вхождений на РАзные уровни), из них 36874 уникальных. (а сл-но, петель таки нет). Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. Код: plaintext 1. 2. 3. 4. 5. 6. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 12:09 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
и напоследок времена (все модифицировано аналогично) запускаем подряд: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. удач. С праздничком. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 12:40 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2 фыыф/assa Супер! Для Рюрика (40436) ищет 33886 потомков за 5 сек! авторНо, поскольку задачка сродни любой иерархической (справочники/каталоги и т.п.), то попозже посмотрю - имеет не токмо факультативный интерес. Не забудьте и про поиск предков :) Спасибо и с наступающим праздником! З.Ы. Для №29 находит 33046 потомков,а по упомянутой выше программе 33047. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.05.2004, 12:55 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
Постскриптум предыдущего сообщения ошибочен! Там к потомкам добавляется и сама персона. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.05.2004, 04:25 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
Еще одна заморочка :( В таблице нужно поле parent. Добавляем в код Код: plaintext Код: plaintext 1. 2. Нужно заменить поле parent в соответствии с новой нумерацией. Делаю так: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Может есть лучшее решение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.05.2004, 11:15 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
Что-то я зарапортовался в последнем посте. Правильная последовательность в детях (которая определена в таблице "дети" по счетчику) нарушается при создании таблицы "потомки", т.к. сортировка производится по индексу "СемьяРебенок". Это касается и последовательности семей. Нужно в таблицу "семьи" добавить счетчик и сортировку проводить с его участием. В случае, когда более одного брака, нужна привязка ребенка к номеру брака. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.05.2004, 07:06 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
Вообщем, последовательность записей для 40436 д.б. такой: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.05.2004, 09:25 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
Гы. А я сразу понял, что вам никакая рекурсия на..фих не нужна. Вам нужен эффективный механизм построения выборок из почти статических данных в аксесс (т.е. в системе, не поддерживающей запросы иерархического вида /вроде в оракле что-то есть)). Тогда вам, видимо, надо построить "индексную таблицу". Такую, из которой все последующие вещи считаются простыми запросами (наборы полей связи для всех мыслимых запросов проиндексировать). Поскольку первичные данные меняются редко, то и перестройка вспомогательной таблицы должна проводиться не каждый раз, а только при изменении, причем перестройка не всей таблицы, а только конкретного участка. __________ Нумеровать "логический" порядок счетчиками – гнилое дело. Да и для семей в счетчике может крыться проблема. Добавьте поля "физическая очередность брака" для каждой из персон (тут в общем счетчике возможна масса логических казусов, особо для активных единовременных многоженцев, повторных браков со старым партнером и т.п., боюсь, возможен и некоторый "релятивизм", когда один порядок потребуется для одного партнера, другой – для другого. А поле-то общее. Некой экономии, кажется, можно добиться объявив поля меньшей длинны – например - как байтовые, но идущие физически друг за другом). ____ PS Если вы хотите модифицировать способ хранения данных – 3 минуты - не проблема. (Продумайте один раз способ хранения и время от времени (по изменении данных) перестраивайте вспомогательные структуры. Если же нужна именно выборка – не делайте UPDATE (дисковая операция), просто верните NewNumber(parent) (и т.п. – если нужно выводить несколько значений, - при первом обращении к функции заполните _коллекцию_, с индексом (key) элементов cStr( id) (id – старый id предка), простым MoveNext (а не Find!!! – что много быстрее, тогда и набор можете открыть только для прямого прохода) при повторных вызовах дергайте члены из коллекции по id , представляется, для коллекции васиком должно строиться что-то типа индекса в памяти по key – что много ускоряет поиск, если я ошибаюсь (в догадках) - получите тот же результат, что и Find-ом (еще и память похерите зря)). А rst, по любому, открывайте как статический набор. ___ ЗЫ ( к "нерекурсивной процедуре): (кстати, переприсваивать массивы потомков из "следующих" в "текущие" не обязательно. Надо разветвить процедуру для четных/нечетных поколений. (можно и простым копи/пастом). Одно из "изячных" решений – объявить тип "поколение" содержащий массив поколения, и объявить массив p(0 To 1) из двух поколений – на уровне модуля pC==p(iG mod 2); pN==p((iG+1) mod 2)), а "ветвить" не код а просто за счет подстановки нужных индексов при четном/нечетном поколении менять поколение – источник и поколение – адресат.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.05.2004, 13:00 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2фыыф авторТогда вам, видимо, надо построить "индексную таблицу". Такую, из которой все последующие вещи считаются простыми запросами (наборы полей связи для всех мыслимых запросов проиндексировать). Можно какой-нибудь пример? И еще вопрос: что означает "0" в выражении Код: plaintext ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.05.2004, 13:20 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
вот ваша табличка потомков и есть вспомогательная, если добавить id семьи, есс-но (и не надо ее перестраивать по запросу, а только по изменению данных удалять не все, а только "ветку" от этой семьи удалить/вставить). чтобы таблица была удобна для шустрых выборок, нужны соответствующие индексы (id,ребенок) - он и так видимо ключ (или могабыть (id,уровень,ребенок) - если учитываете все сепени родства по всем линиям - тут надо подумать над оптимальным порядком полей (уровень,ребенок) - чтобы не строить лишних индексов) - будут пользоваться в запросах на потомков id; (ребенок,уровень,id) - // - в запросах на предков ребенка, (ну, посмотрите, как у вас строятся запросы, так и индексы составные подберите). И будет это все зело огромным, но за счет индексов выборки будут строиться быстро. Причем чем индексов больше, тем цена вставки и редактирования выше. Но если данные почти не меняются (таблица не переписывается целиком), то основной минус - объем базы. И время восстановления/сжатия (при сжатии аксесс, кажется, перестраивает индексы целиком). :) Да, наткнулся я тут, образовываясь, на тип индексов "битовые карты" - там составные индексы не нужны. ибо эти карты, кажется аддитивны (как средства поиска) поиск по составному индексу - просто на лету производимая комбинация поиска по простым. (не копал, надо посмотреть). Но, к сожалению, в аксессе их нет. ______ 0- просто второе поле поиска индекса пишите при первом вызове .Seek ">=", id - в данном случае это не важно (ребенок>=0, not null) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.05.2004, 14:13 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2 фыыф После долгих раздумин, определил структуру таблицы "потомки" для правильной ее сортировки: Код: plaintext 1. 2. 3. 4. Для получения orderPehson в функцию нужно включить третий аргумент, определяемый из поля "счетчик" таблицы "дети" для предка в семье его родителей. С первым вызовом все понятно, а дальше ничего не смог придумать :( Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 09:04 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
1. для ПРАВИЛЬНОГО получения номера поколения по КРАТЧАЙШЕЙ ЛИНИИ надо таки отказаться от иерархического вызова (пишет первое найденное вхождение потомка, по первой попавшейся линии). Или дополнить (в случае Err в .Add проверкой записанного и текущего (в рекурсивной процедуре) поколения, а при необходимости и .Edit (номер поколения, и генетические веса, если потребуется). 2. НАстоятельно рекомендую не завязываться на id предка но на id семьи (вдвое снизит объем таблицы, запросы будут более прозрачными логически). Но если вы склоняетесь не к постоянно заполненной (редко обновляемой) таблице, то возможно имеет смысл делать как сочтете нужным. 3. не совсем понимаю, что такое "номер персоны в семье" и на кой он нужен (внутри поколения нумерация вообще произвольна). Но такого рода нумерация легко производится в нерекурсивной (последовательный перебор по поколениям) процедуре. ______ для "постоянно заполненной таблицы транзиктивных связей" примерно следующая структура: id персона pid семья предков (соотв уровня) generation поколение (уровень наследования) weght вес (семьи предков) в генетическом наследстве, Double /* (степень родства суммарно по всем линиям) */ при этом семья: id муж жена nмуж № брака, байт nжена № брака, байт дети - как есть Семья Ребенок /* счетчик в вашей структуре лишний == Ребенок*/ + желательо поле очередности ребенка в семье. но я б ввел вместо него дату рождения - дата/время, правда не всегда оно известно, а для близнецов пришлось бы манипулировать искуственно временем +- часы/минуты. Т.ч. возможно и очередность не худший выход. и я бы ввел пол, и избавился от муж/жена в структуре данных для семьи, но, как я понял, встречаются гермафродиты хотя для семей возможно лучше разбить таблицы: семья: (уникум, служит для организации связей с потомками и супругами) id -PKey супруги: id - Fkey семья(id) idp - персона Fkey дети ( sx - роль в семье, boolean nсемьи - номер брака В таком виде данных в семье/супруги/дети более чем достаточно для первичного расчета таблицы связей "потомки", а полного набора таблиц с (учетом последней таблицы) - для формирования практически за счет одного SQL всех возможных отчетов. Если же вы настаиваете на нумерации внутри "линии", то это заведомо относительное (отсчитывается от произвольно выбранного предка) поле можно расчитывать динамически (как я писал - заполняя коллекцию или массив) при выводе отчетов, не перестраивая таблицу "потомков". __________ ЗЫ - Если затруднились переформировать нерекурсивную разновидность процедуры, то сейчас поищу... вот, с какими-то лишними наворотами: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. и я б еще поэкспериментировал с поиском в большой коллекции по "key". если окажется быстрее, чем выборка из массива перебором по значению (или модификаций с вставкой в упорядоченные массивы - с "раздвижкой", что долго), то легко решается проблема пересчета генетического веса без вызова .edit при повторном нахождении (на этапе прохода по поколению результаты грузятся в коллекцию записей с инедексом str(id) (определенный пользователем тип, вес в поколении просто пересчитывается, при ошибке добавления по ключу), а по проходу все поколение записывается из коллекции в таблицу (add or edit ранее вставленных записей). Но это именно в случае желания иметь степень генетического родства с учетом множественности линий наследования. В конце-концов может оказаться что даже вся ваша табла "потомков" шустро влезет в такую коллекцию в разумный объем памяти (у вас что-то до 40000 "записей" длиной 8 байт, +, если я праильно соображаю на счет конструкции "коллекций" и их "индексов", структурка будет более рыхлой, чем массив (записей) на некий множитель, не больший, видимо, 5-10 (вроде как даже таблички не более чем в 5 раз более рыхлы, чем плоские файлы), и ваша коллекция записей (для одного предка) влезет в 1.6 -3.2 мегабайта. Что уже интересно с точки зрения переноса логики связи не на таблицу потомков, а на функцию(и) связей, рботающую с такими массивами по предложенной ранее схеме... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 11:41 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2 фыыф автор3. не совсем понимаю, что такое "номер персоны в семье" и на кой он нужен (внутри поколения нумерация вообще произвольна). Но такого рода нумерация легко производится в нерекурсивной (последовательный перебор по поколениям) процедуре. Внутри поколения нумерация д.б. не произвольна! Потомков нужно показывать по старшинству предков. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 12:34 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
а где вы возьмете старшинство внутри одной семьи (старшинство предков-то тут одинаково)? а то у вас в таблицах старшинства детей в семье и нет [:0) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 16:16 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
2 фыыф авторв таблицах старшинства детей в семье и нет [:0) Есть - это счетчик. Дети в каждой семье записаны уже в нужном порядке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 16:51 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
я так и думал, что применено какое-нить мм... решение. :0) постройте индекс "новый" по "детям" ==(семья,счетчик, ребенок) вместо (Семья,ребенок) и бегайте по этому индексу. (замените на rstD.Index ="новый") к тому ж в неиерархическом случае Seek у вас используется только во входе (".=", id). Внутри семьи потомки будут перебираться в порядке "счетчика", вот в этом порядке и наваривайте ваше поле старшинства по всей иерархии. ---- или, чтобы не переписывать: обновите мужей/жен в семьях на значение "счетчик" из детей затем "ребенков" в "детях" на (то же) значение "счетчик" (после чего поле счетчика можете грохнуть за ненадобностью, и ввести нормальное поле для учета порядка в семьях) (Семья,ребенок) станут упорядочены внутри семей по старшинству детей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 19:11 |
|
||
|
Иерархия и рекурсия
|
|||
|---|---|---|---|
|
#18+
авторобновите мужей/жен в семьях на значение "счетчик" из детей затем "ребенков" в "детях" на (то же) значение "счетчик" (после чего поле счетчика можете грохнуть за ненадобностью, и ввести нормальное поле для учета порядка в семьях) (Семья,ребенок) станут упорядочены внутри семей по старшинству детей. Вот этого я и добиваюсь, пока безуспешно :( Знаю что нужно, не знаю как... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2004, 20:26 |
|
||
|
|

start [/forum/topic.php?fid=45&msg=32517086&tid=1674665]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
169ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
62ms |
get tp. blocked users: |
1ms |
| others: | 245ms |
| total: | 518ms |

| 0 / 0 |
