Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Microsoft Access [игнор отключен] [закрыт для гостей] / Иерархия и рекурсия / 25 сообщений из 120, страница 1 из 5
  1  все
04.05.2004, 21:23
    #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, 22:08
    #32506674
lobodava
lobodava
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархия и рекурсия
Хорошо бы постановку задачи озвучить целиком. Типа есть то-то и то-то, получить надо вот это...
А то не понятно почему именно такие таблицы. Или это какая-то классическая компоновка о которой все знают?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2004, 22:48
    #32506686
Sergey_New
Sergey_New
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархия и рекурсия
2 lobodava
Эти таблицы - часть генеалогической базы данных, отображающие родственные отношения.
В общепринятом формате (так называемом GedCom стандарте) существуют два вида отношений:
а) персона - семья родителей (отец и мать);
б) персона - супруг(а) - дети.
Эти отношения, имхо, отражают предложенные таблицы. М.б. можно и по другому...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2004, 23:10
    #32506692
lobodava
lobodava
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархия и рекурсия
Вау!!! А где почитать о GedCom стандарте? Ссылки есть?
А то ни как не пойму как цепочка выстраивается из тех таблиц, что предложены.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2004, 00:15
    #32506706
Владимир Саныч
Владимир СанычПривилегированный пользователь
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархия и рекурсия
Вижу логическую ошибку.

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

По-моему, это должно вообще приводить к неправильной работе программы, а не то что к замедлению.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2004, 08:42
    #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, 09:09
    #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, 11:08
    #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:19
    #32507052
Victosha
Victosha
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархия и рекурсия
авторDim rst As Recordset внутрь процедуры?

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

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

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



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

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

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


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