Optimizacion de algoritmo recursivo, convertirlo a iterativo

24/10/2005 - 04:16 por amota | Informe spam

Tengo un algoritmo para recorrer unas tablas, hecho de modo recursivo pero
necesito hacerlo lo mas eficiente posible. Cualquier idea es bienvenida.

Debo construir un conjunto de los items relacionados con un un item x.
Para construirlo, debo buscar los que están relacionados, y si el
PesoRelacion es > PesoItem, debo agregar los que esten relacionados con ese
item.

Esto sigue hasta que:
- PesoRelacion < PesoItem
- Ya se han "expandido" todos los items.

Ojo: por un mismo item se puede pasar varias veces. Aunque solo tengo que
expandirlo una sola vez.

Tengo 2 tablas:
Items ( ItemID, PesoItem)
Relationships ( Item1, Item2, PesoRelacion)

Sub Main()
BuscarItemsRelacionados(Item)
end sub

Function IncluirItem(Item)
' Guarda los items que han sido expandidos
' Devuelve true, si el item no estaba y lo incluyo
' Devuelve False, si el item ya estaba

Sub IncluirItemFinal(Item)
'Guarda los items que NO fueron expandidos.

Sub BuscarItemsRelacionados(Item)
Dim idit As Integer

If IncluirItem(idItem) Then
' Buscar los items relacionados directamente
Set rlinks = CurrentDb().OpenRecordset("Select iditem1, iditem2,
linkweight from linkweight where iditem1 = " & idItem & " or iditem2 = " &
idItem)

While Not rlinks.EOF
If rlinks.iditem1 = idItem Then
idit = rlinks.iditem2
Else
idit = rlinks.iditem1
End If

If rlinks.linkweight < GetItemTh(idit) Then
IncluirItemFinal (idit)
Else
BuscarItemsRelacionados(idit)
End If
rlinks.MoveNext
Wend
End If
End Sub

Esto ya hace lo que quiero. Pero el problema es que la tabla de items puede
ser de mas de 1 millon de items.
No lo puedo hacer de modo recursivo. Me pueden ayudar?
Cual seria la mejor manera de hacerlo?

Gracias.
amota

Siga el debate

1 respuesta

Tengo una respuesta

Preguntas similare

Mostrar todos los temas similares

Leer las respuestas

#1 Isaias

24/10/2005 - 16:20 | Informe spam

Espero y sirva:

create table tempo ( idclave int, descripcion char(10),
idpadre int )
go
insert into tempo values ( 1, 'AAA', 0 )
insert into tempo values ( 2, 'AAA', 1 )
insert into tempo values ( 3, 'AAA', 1 )
insert into tempo values ( 4, 'AAA', 2 )
insert into tempo values ( 5, 'AAA', 2 )
insert into tempo values ( 6, 'AAA', 4 )
go
create table tempodes ( iddes int, nivel int )
go

2) Grabamos en la tabla tempodes los descendientes del
parámetro solicitado (en eset caso lo pongo en una
variable):

declare @param int
SET @param = 1

declare @nivel int
DELETE FROM tempodes
INSERT INTO tempodes SELECT idclave, 1 FROM tempo WHERE
idpadre = @param
SET @nivel = 2
WHILE ( EXISTS ( SELECT iddes FROM tempodes WHERE nivel =
@nivel - 1 ) )
BEGIN
INSERT INTO tempodes SELECT idclave, @nivel FROM tempo
WHERE idpadre IN ( SELECT iddes FROM tempodes WHERE nivel
= @nivel - 1 )
SET @nivel = @nivel + 1
END

3) Si vemos el detalle de la tabla con SELECT * FROM
tempodes tenemos :

iddes nivel
2 1
3 1
4 2
5 2
6 3

4) Si deseamos que todo se encuentre en una cadena :

declare @cadena varchar(1000)
SET @cadena = ''
select @cadena = @cadena + convert(varchar,iddes) + ';'
from tempodes
select @cadena

tenemos :

-
2;3;4;5;6;
Saludos
IIslas

"amota" escribió:

Tengo un algoritmo para recorrer unas tablas, hecho de modo recursivo pero
necesito hacerlo lo mas eficiente posible. Cualquier idea es bienvenida.

Debo construir un conjunto de los items relacionados con un un item x.
Para construirlo, debo buscar los que están relacionados, y si el
PesoRelacion es > PesoItem, debo agregar los que esten relacionados con ese
item.

Esto sigue hasta que:
- PesoRelacion < PesoItem
- Ya se han "expandido" todos los items.

Ojo: por un mismo item se puede pasar varias veces. Aunque solo tengo que
expandirlo una sola vez.

Tengo 2 tablas:
Items ( ItemID, PesoItem)
Relationships ( Item1, Item2, PesoRelacion)

Sub Main()
BuscarItemsRelacionados(Item)
end sub

Function IncluirItem(Item)
' Guarda los items que han sido expandidos
' Devuelve true, si el item no estaba y lo incluyo
' Devuelve False, si el item ya estaba

Sub IncluirItemFinal(Item)
'Guarda los items que NO fueron expandidos.

Sub BuscarItemsRelacionados(Item)
Dim idit As Integer

If IncluirItem(idItem) Then
' Buscar los items relacionados directamente
Set rlinks = CurrentDb().OpenRecordset("Select iditem1, iditem2,
linkweight from linkweight where iditem1 = " & idItem & " or iditem2 = " &
idItem)

While Not rlinks.EOF
If rlinks.iditem1 = idItem Then
idit = rlinks.iditem2
Else
idit = rlinks.iditem1
End If

If rlinks.linkweight < GetItemTh(idit) Then
IncluirItemFinal (idit)
Else
BuscarItemsRelacionados(idit)
End If
rlinks.MoveNext
Wend
End If
End Sub

Esto ya hace lo que quiero. Pero el problema es que la tabla de items puede
ser de mas de 1 millon de items.
No lo puedo hacer de modo recursivo. Me pueden ayudar?
Cual seria la mejor manera de hacerlo?

Gracias.
amota

Siga el debate Respuesta

Responder a este mensaje

Ads by Google

Hacer una pregunta

Tengo una respuesta

Busqueda sugerida