Help with effective algorithm

[Tamir Khason]

I have parent-child hashtable with more then 900K items and I have to build
all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist




--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Picho]

Re: Help with effective algorithm

Tamir,

out of cuiriosity,
why do you use a Hashtable to hold all the data in the first place?
why not go on the old safe tree structure?
maybe each node will hold a HashTable to the child nodes?
it might not be so memory-effective but performance might be good
as i see it, you have to itterate or search or query the main hashtable for
each path.

just a thought/question.

Picho


"Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
news:%23k1G3UhU FHA.228@TK2MSFT NGP12.phx.gbl.. .[color=blue]
>I have parent-child hashtable with more then 900K items and I have to build
>all pathes for this. E.G
> Key ParentKey
> 1 0
> 2 1
> 3 2
> 4 8
> 5 3
> 6 1
> 7 3
> 8 7
> To build:
> 0-1-2-3-5
> 0-1-6
> 0-1-2-3-7-8-9-4
> This is just example.
>
> I tried 5 different algorithms, but noting gave me good performance.
> Please assist
>
>
>
>
> --
> What dot.NET? Just ask:
> "Please, www.dotNET.us !"
>[/color]

[Tamir Khason]

Re: Help with effective algorithm

Picha, thank you for reply
[color=blue]
> why do you use a Hashtable to hold all the data in the first place?[/color]
The data I recieve in input is two hashtables from selialized source first
is ID/Value information
the second is Parent/Child relation, where Child and Parent are IDs from
first hashtable
[color=blue]
> why not go on the old safe tree structure?[/color]
It makes sense if trees are small. We are speaking about at least 900K items
with complicated relationships, thus the parsing of even just creation of
TreeView will take a while
[color=blue]
> maybe each node will hold a HashTable to the child nodes?[/color]
Not nessesery, 'cos it might be Child-Of-Child structures

--
Tamir
[color=blue]
> "Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
> news:%23k1G3UhU FHA.228@TK2MSFT NGP12.phx.gbl.. .[color=green]
>>I have parent-child hashtable with more then 900K items and I have to
>>build all pathes for this. E.G
>> Key ParentKey
>> 1 0
>> 2 1
>> 3 2
>> 4 8
>> 5 3
>> 6 1
>> 7 3
>> 8 7
>> To build:
>> 0-1-2-3-5
>> 0-1-6
>> 0-1-2-3-7-8-9-4
>> This is just example.
>>
>> I tried 5 different algorithms, but noting gave me good performance.
>> Please assist
>>
>>
>>
>>
>> --
>> What dot.NET? Just ask:
>> "Please, www.dotNET.us !"
>>[/color]
>
>[/color]

[Picho]

Re: Help with effective algorithm

this is getting more a question than helping thread but anyway,

thinking outloud, seems to me it can go only two ways (as allways...)
either you have a data structure that supports your need (object graph->Tree
structure of some sort)
or you have a flat and fast data structure that is supported by a fast graph
rendering algorithm.

on the first option, you have a long construction time and a large memory
consumption.
on the other option, you have a "skinny" memory consumption, but a longer
construction time for each request.

seems to me, analyticly speaking, that it narrows down to one question (for
me at least):
how often do you query for these graphs/paths?
if its often, I would take the first approach, since all the paths are
visible and constructed,
if not... well I will not.

but : this is a question, not an answer. I am trying to learn something here
too. I am ignorant when it comes to performance and memory usage.


"Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
news:eC4EOfhUFH A.628@tk2msftng p13.phx.gbl...[color=blue]
> Picha, thank you for reply
>[color=green]
>> why do you use a Hashtable to hold all the data in the first place?[/color]
> The data I recieve in input is two hashtables from selialized source first
> is ID/Value information
> the second is Parent/Child relation, where Child and Parent are IDs from
> first hashtable
>[color=green]
>> why not go on the old safe tree structure?[/color]
> It makes sense if trees are small. We are speaking about at least 900K
> items with complicated relationships, thus the parsing of even just
> creation of TreeView will take a while
>[color=green]
>> maybe each node will hold a HashTable to the child nodes?[/color]
> Not nessesery, 'cos it might be Child-Of-Child structures
>
> --
> Tamir
>[color=green]
>> "Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
>> news:%23k1G3UhU FHA.228@TK2MSFT NGP12.phx.gbl.. .[color=darkred]
>>>I have parent-child hashtable with more then 900K items and I have to
>>>build all pathes for this. E.G
>>> Key ParentKey
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 8
>>> 5 3
>>> 6 1
>>> 7 3
>>> 8 7
>>> To build:
>>> 0-1-2-3-5
>>> 0-1-6
>>> 0-1-2-3-7-8-9-4
>>> This is just example.
>>>
>>> I tried 5 different algorithms, but noting gave me good performance.
>>> Please assist
>>>
>>>
>>>
>>>
>>> --
>>> What dot.NET? Just ask:
>>> "Please, www.dotNET.us !"
>>>[/color]
>>
>>[/color]
>
>[/color]

[Roni]

Re: Help with effective algorithm

hi,

i posted today an article which is waitung for approving. The article is
about sorting algorithms. As far as it's proved search about "Algorithms
and Sorting".

best regards,
roni schuetz



*** Sent via Developersdex http://www.developersdex.com ***

[Tamir Khason]

Re: Help with effective algorithm

ok, following answers:
The "line" structures quered very often, the rebuild procedure less in use,
however it will be rather greed procedure

"Picho" <SPAM_picho@tel hai.ac.il> wrote in message
news:%23HqZNvhU FHA.2128@TK2MSF TNGP14.phx.gbl. ..[color=blue]
> this is getting more a question than helping thread but anyway,
>
> thinking outloud, seems to me it can go only two ways (as allways...)
> either you have a data structure that supports your need (object
> graph->Tree structure of some sort)
> or you have a flat and fast data structure that is supported by a fast
> graph rendering algorithm.
>
> on the first option, you have a long construction time and a large memory
> consumption.
> on the other option, you have a "skinny" memory consumption, but a longer
> construction time for each request.
>
> seems to me, analyticly speaking, that it narrows down to one question
> (for me at least):
> how often do you query for these graphs/paths?
> if its often, I would take the first approach, since all the paths are
> visible and constructed,
> if not... well I will not.
>
> but : this is a question, not an answer. I am trying to learn something
> here too. I am ignorant when it comes to performance and memory usage.
>
>
> "Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
> news:eC4EOfhUFH A.628@tk2msftng p13.phx.gbl...[color=green]
>> Picha, thank you for reply
>>[color=darkred]
>>> why do you use a Hashtable to hold all the data in the first place?[/color]
>> The data I recieve in input is two hashtables from selialized source
>> first is ID/Value information
>> the second is Parent/Child relation, where Child and Parent are IDs from
>> first hashtable
>>[color=darkred]
>>> why not go on the old safe tree structure?[/color]
>> It makes sense if trees are small. We are speaking about at least 900K
>> items with complicated relationships, thus the parsing of even just
>> creation of TreeView will take a while
>>[color=darkred]
>>> maybe each node will hold a HashTable to the child nodes?[/color]
>> Not nessesery, 'cos it might be Child-Of-Child structures
>>
>> --
>> Tamir
>>[color=darkred]
>>> "Tamir Khason" <tamir-NOSPAM@tcon-NOSPAM.co.il> wrote in message
>>> news:%23k1G3UhU FHA.228@TK2MSFT NGP12.phx.gbl.. .
>>>>I have parent-child hashtable with more then 900K items and I have to
>>>>build all pathes for this. E.G
>>>> Key ParentKey
>>>> 1 0
>>>> 2 1
>>>> 3 2
>>>> 4 8
>>>> 5 3
>>>> 6 1
>>>> 7 3
>>>> 8 7
>>>> To build:
>>>> 0-1-2-3-5
>>>> 0-1-6
>>>> 0-1-2-3-7-8-9-4
>>>> This is just example.
>>>>
>>>> I tried 5 different algorithms, but noting gave me good performance.
>>>> Please assist
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> What dot.NET? Just ask:
>>>> "Please, www.dotNET.us !"
>>>>
>>>
>>>[/color]
>>
>>[/color]
>
>[/color]

[Tamir Khason]

Re: Help with effective algorithm

Where you posted it?


"Roni" <rsc@v-1.ch> wrote in message
news:ugKyH$hUFH A.3944@tk2msftn gp13.phx.gbl...[color=blue]
> hi,
>
> i posted today an article which is waitung for approving. The article is
> about sorting algorithms. As far as it's proved search about "Algorithms
> and Sorting".
>
> best regards,
> roni schuetz
>
>
>
> *** Sent via Developersdex http://www.developersdex.com ***[/color]