ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Microsoft Access [игнор отключен] [закрыт для гостей] / Иерархия и рекурсия
25 сообщений из 120, страница 1 из 5
  1  все
Иерархия и рекурсия
    #32506661
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
Windows XP, Office XP
Имеется:
Код: plaintext
1.
2.
3.
4.
5.
Таблица:	дети				Таблица: семьи
    Столбцы				    Столбцы
	Имя	Тип				Имя	Тип
	семья	Длинное целое	∞     -	 1 	id	Длинное целое (ключ)
	ребенок	Длинное целое			муж	Длинное целое
	счетчик	Длинное целое			жена	Длинное целое

Требуется найти всех потомков какой-либо персоны (например 29) и записать их и номер поколения в таблицу потомки.
Код: 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.
Option Compare Database
Option Explicit
  Dim dbs As Database, rstDesc As Recordset, rst As Recordset, n As Long

Sub start()
    Set dbs = CurrentDb
    Set rstDesc = dbs.OpenRecordset("SELECT * FROM потомки")
    FindDescendant  29 ,  1 
End Sub

Sub FindDescendant(id As Long, iGeneration As Long)
    On Error Resume Next
    Dim i As Long
    Set rst = dbs.OpenRecordset( _
        "SELECT ребенок FROM семьи LEFT JOIN дети ON семьи.id=дети.семья WHERE Not ребенок Is Null AND (муж=" _
        & id & " OR жена=" & id & ")")
    With rst
        Do While Not .EOF
            n = .Fields( 0 )
            With rstDesc
                .AddNew
                .Fields( 0 ) = n
                .Fields( 1 ) = iGeneration
                .Update
            End With
            i = iGeneration +  1 
            FindDescendant .Fields( 0 ), i
            .MoveNext
        Loop
    End With
End Sub
Когда потомков одна-две сотни, то время выполнения приемлемо.
При большем количестве производительнось катострофически падает.
Так за 30 мин определяется около 2500 потомков.
Посоветуйте, как существенно повысить производительность?
Все имеющееся на форумах прочел...
...
Рейтинг: 0 / 0
04.05.2004, 21:23
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506674
lobodava
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lobodava
Участник
Хорошо бы постановку задачи озвучить целиком. Типа есть то-то и то-то, получить надо вот это...
А то не понятно почему именно такие таблицы. Или это какая-то классическая компоновка о которой все знают?
...
Рейтинг: 0 / 0
04.05.2004, 22:08
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506686
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 lobodava
Эти таблицы - часть генеалогической базы данных, отображающие родственные отношения.
В общепринятом формате (так называемом GedCom стандарте) существуют два вида отношений:
а) персона - семья родителей (отец и мать);
б) персона - супруг(а) - дети.
Эти отношения, имхо, отражают предложенные таблицы. М.б. можно и по другому...
...
Рейтинг: 0 / 0
04.05.2004, 22:48
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506692
lobodava
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lobodava
Участник
Вау!!! А где почитать о GedCom стандарте? Ссылки есть?
А то ни как не пойму как цепочка выстраивается из тех таблиц, что предложены.
...
Рейтинг: 0 / 0
04.05.2004, 23:10
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506706
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Вижу логическую ошибку.

Переменная rst As Recordset описана на уровне модуля, однако при каждом обращении к процедуре FindDescendant этой переменной заново делается Set и какое-то количество раз MoveNext. При возврате из очередного обращения к FindDescendant эта переменная уже имеет совершенно не то значение, которое было ей дано перед входом туда.

По-моему, это должно вообще приводить к неправильной работе программы, а не то что к замедлению.
...
Рейтинг: 0 / 0
05.05.2004, 00:15
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506814
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 lobodava
Ссылок на стандарт можно найти мгого, только на английском. Например:
The GEDCOM Standard Release 5.5
The GEDCOM Standard Release 5.5 (pdf)
Кратко суть такова:
В текстовом файле последовательно размещаются:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
- персона (с уникальным ключом)
- ссылка на ключ семьи родителей
- ссылка на ключ своей семьи
далее другие персоны
...
- семья (с уникальным ключом)
- ссылка на ключ мужа
- ссылка на ключ жены
- ссылка на ключ  1  ребенка
- ссылка на ключ  2  ребенка и т.д.
Выглядит это так:
Код: 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.
 0  @I1@ INDI
 1  NAME Иван Иванович /Иванов/
 1  SEX M
 1  FAMC @F2@
 1  FAMS @F1@
 0  @I2@ INDI
 1  NAME Марья Ивановна /Петрова/
 1  SEX F
 1  FAMC @F14@
 1  FAMS @F1@
 0  @I3@ INDI
 1  NAME Петр Иванович /Иванов/
 1  SEX M
 1  FAMC @F1@
 1  FAMS @F11@
 0  @I4@ INDI
 1  NAME Анна Ивановна /Иванова/
 1  SEX F
 1  FAMC @F1@
...
 0  @F1@ FAM
 1  HUSB @I1@
 1  WIFE @I2@
 1  CHIL @I3@
 1  CHIL @ 4 @
 0  @F2@ FAM
 1  HUSB @I10@
 1  WIFE @I11@
 1  CHIL @I1@
...
...
Рейтинг: 0 / 0
05.05.2004, 08:42
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32506833
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 Владимиру Санычу
авторПри возврате из очередного обращения к FindDescendant эта переменная уже имеет совершенно не то значение, которое было ей дано перед входом туда.
Именно так!
На этом и построен алгоритм:
Код: plaintext
1.
2.
3.
4.
 1 . Определяем детей персоны.
 2 . Определяем детей  1 -го ребенка.
 3 . Если у  1 -го ребенка детей нет, возвращаемся ко  2 -му ребенку
 4 . Если у  1 -го ребенка дети есть, определяем его детей
и т.д.
Проверено, работает правильно.
В прилагаемом текстовом файле есть реальные таблицы.
Можно было построить следующий алгоритм:
Код: plaintext
1.
2.
3.
 1 . Находим всех детей  1 -го ребенка.
 2 . Находим всех детей  2 -го ребенка.
 3 . Находим всех детей  1 -го ребенка  1 -го ребенка.
и т.д.
Правда, как это сделать и что лучше, не знаю ...
...
Рейтинг: 0 / 0
05.05.2004, 09:09
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507021
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Но если написано

Set rst = dbs.OpenRecordset...
With rst
Do While Not .EOF
'***'
.MoveNext

то, наверно, .MoveNext и While Not .EOF должны относиться к тому же объекту, которому сделан Set. Однако в приведенной программе это не так, потому что в части '***' делается другой Set. Может, все-таки надо перенести Dim rst As Recordset внутрь процедуры?
...
Рейтинг: 0 / 0
05.05.2004, 11:08
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507052
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Victosha
Участник
авторDim rst As Recordset внутрь процедуры?

Саныч, утечку памяти это не предотвратит - что в лоб, что по лбу
...
Рейтинг: 0 / 0
05.05.2004, 11:19
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507060
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Почему не предотвратит? Просто будет несколько экземпляров рекордсета, но каждый будет закрываться когда ему положено.
...
Рейтинг: 0 / 0
05.05.2004, 11:22
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507064
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Victosha
Участник
кто же его закроет, если ему это явно не сказано?
А если сказано, то то и указатели в стеке плодить не обязательно - одного хватит, на уровне модуля.
...
Рейтинг: 0 / 0
05.05.2004, 11:25
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507073
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Close надо добавить, это несомненно. Независимо ни от чего.

Но одного не хватит, потому что они должны использоваться одновременно. Второй должен открываться прежде, чем закроется первый, и т.д.
...
Рейтинг: 0 / 0
05.05.2004, 11:30
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507075
фыыф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
фыыф
Гость
Саныч прав
должно выглядеть так (чтобы рекордсеты разных поколений, и счетчики поколений в рекурсии были автономными)

Код: 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.
Option Compare Database
Option Explicit
  Dim dbs As Database, rstDesc As Recordset

Sub start()
    Set dbs = CurrentDb
    Set rstDesc = dbs.OpenRecordset("SELECT * FROM потомки")
    FindDescendant  1 ,  1  ' 29 ,  1 
    rstDesc.Close
    Set rstDesc = Nothing
End Sub

Sub FindDescendant(id As Long, iGeneration As Long)
    On Error Resume Next
    Dim i As Long, rst As Recordset, n As Long
    Set rst = dbs.OpenRecordset(_
        "SELECT ребенок FROM семьи LEFT JOIN дети ON семьи.id=дети.семья WHERE Not ребенок Is Null AND (муж=" _
        & id & " OR жена=" & id & ")")
    With rst
        Do While Not .EOF
            n = .Fields( 0 )
            With rstDesc
                .AddNew
                .Fields( 0 ) = n
                .Fields( 1 ) = iGeneration
                .Update
            End With
            i = iGeneration +  1 
            FindDescendant .Fields( 0 ), i
            .MoveNext
        Loop
    End With
    rst.Close
    Set rst = Nothing
End Sub
т.е. ваш алгоритм крив.

по мужу и жене наверное надо бы залудить индексы. Но на больших объемах все равно будут проблемы - как вы думаете, сколько стоит взять несколько десятков тысяч разных запросов (да, не дай бог, с предварительной оптимизацией)?
...
Рейтинг: 0 / 0
05.05.2004, 11:30
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507078
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Кстати! Вот если поставить Close, то тут-то и станет очевидно, что программа работает неправильно. Потому что после первого выполненного Close сразу начнутся сообщения об ошибках.
...
Рейтинг: 0 / 0
05.05.2004, 11:31
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507088
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Victosha
Участник
то есть если ты про то, что процедура рекурсивный характер имеет (блин - должна иметь) - это несомненно. Но при этом рекордсет не обязателен. достаточно dcount-ом проверить, есть ли дети и и одним update-запросом. проставить им уровень.

ЗЫ
...
Рейтинг: 0 / 0
05.05.2004, 11:35
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507093
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
2 Victosha:
Полностью согласен.
...
Рейтинг: 0 / 0
05.05.2004, 11:37
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507107
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Victosha
Участник
2 Саныч

Стандарт!
...
Рейтинг: 0 / 0
05.05.2004, 11:42
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507114
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 Владимир Саныч, 2 Victosha
Определенно вы друг-друга понимаете :)
Я вас - нет :(
Нельзя ли конкретизировать в виде кода?
...
Рейтинг: 0 / 0
05.05.2004, 11:45
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507119
фыыф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
фыыф
Гость
и самое главное. на размещение в памяти тысячи рекордсетов потребуется до шиша памяти. т.ч. может и имеет смысл обходиться одним рекордсетом, но по возвращении из рекурсии надо возобновлять _старый_ (т.е. _этого уровня_ наследственности) рекордсет, и вместо MoveNext ходить Find-ом на следующий.



еще одно решение - сделать поле муж/жена общим (персона) (+ поле признака (тип) + уникальный индекс по 3-м полям (семья,персона,тип), открывать семью не запросом, а рекордсетом по указанному индексу и бегать seek-ом (по возвращении во внешний уровень переходить seek-ом на следующее значение индекса). (то же можно и при разных полях мух/жана, но пробегая процедуру по 2-м индексам (семья,муж), (семья,жена))
...
Рейтинг: 0 / 0
05.05.2004, 11:48
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507129
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Код: 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.
Option Compare Database
Option Explicit
  Dim dbs As Database, rstDesc As Recordset, n As Long

Sub start()
    Set dbs = CurrentDb
    Set rstDesc = dbs.OpenRecordset("SELECT * FROM потомки")
    FindDescendant  29 ,  1 
End Sub

Sub FindDescendant(id As Long, iGeneration As Long)
Dim rst As Recordset '!!!'
    On Error Resume Next
    Dim i As Long
    Set rst = dbs.OpenRecordset( _
        "SELECT ребенок FROM семьи LEFT JOIN дети ON семьи.id=дети.семья WHERE Not ребенок Is Null AND (муж=" _
        & id & " OR жена=" & id & ")")
    With rst
        Do While Not .EOF
            n = .Fields( 0 )
            With rstDesc
                .AddNew
                .Fields( 0 ) = n
                .Fields( 1 ) = iGeneration
                .Update
            End With
            i = iGeneration +  1 
            FindDescendant .Fields( 0 ), i
            .MoveNext
        Loop
        .Close '!!!'
    End With
End Sub

Это без учета того, что сказали фыыф и Victosha. Потому что они абсолютно правы, но это потребует более серьезных изменений.
...
Рейтинг: 0 / 0
05.05.2004, 11:53
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507149
фыыф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
фыыф
Гость
Да, действительно, надо выбросить (многократные, и затратные) открытия рекордсетов из рекурсии. Открывать один раз один набор семей снаружи, как dbOpenTable, и при входе/возвращении на уровень изменять только параметры Seek-а (много быстрее чем Find), для чего озаботиться необходимыми индексами и переменными уровня рекурсивной процедуры для их текущего хранения. Это (для mdb) будет наискорейшим выходом.
...
Рейтинг: 0 / 0
05.05.2004, 12:00
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507177
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Victosha
Участник
2 фыыв

модификация - на ado открыь 2 client-side рекордсета, локально их индексировать, дальше и FindFirst (не вижу зачем) и Filter их будут успешно пользовать. Рекурсию придется линеаризировать циклами.

ps
кто ж такие "потомки" - что-то в "ТЗ" их не наблюдается ?....
...
Рейтинг: 0 / 0
05.05.2004, 12:11
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507268
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 Владимир Саныч
Проверил работу твоего кода. Производительность не изменилась :(
Кстати, объявление переменных в рекурсивных процедурах уменьшает память.
Это не я сказал :)
Рекомендуют объявлять их на уровне модуля.
...
Рейтинг: 0 / 0
05.05.2004, 12:44
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507274
Sergey_New
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey_New
Участник
2 Victosha
авторкто ж такие "потомки" - что-то в "ТЗ" их не наблюдается ?....
Не пойму, в чем вопрос?
Родитель > ребенок > его ребенок > и т.д.
...
Рейтинг: 0 / 0
05.05.2004, 12:47
| Ответить | Цитировать | Написать  
Иерархия и рекурсия
    #32507277
Фотография Владимир Саныч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир СанычПривилегированный пользователь
Модератор форума
Я не говорил о производительности. Я говорил о правильности. Если несколько рекурсивно вызванных экземпляров процедуры пользуются одним и тем же экземпляром некой переменной, то возникает конфликт!
...
Рейтинг: 0 / 0
05.05.2004, 12:49
| Ответить | Цитировать | Написать  
25 сообщений из 120, страница 1 из 5
  1  все
Форумы / Microsoft Access [игнор отключен] [закрыт для гостей] / Иерархия и рекурсия
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=45&msg=32507073&tid=1674665]:
 0ms
get settings:
 10ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 188ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 63ms
get tp. blocked users:
 1ms
others: 242ms
total:  537ms
созд. / загр.: 537ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]