c# - What datastructure to quickly map multiple objects to another object -

c# - What datastructure to quickly map multiple objects to another object -

i need different datastructure application.

essentially have custom info construction consisting of "nodes". task follows: given number of distinct nodes (where number of nodes unknown) retrieve or create new node. reminds me much of cache function multiple arguments. difference arguments , homecoming value have same type , values returned might given me input later on.

example 1: @ first nodes , c. have create new node (lets name ac) , homecoming it. when nodes , c again in future need able very quickly determine if have created ac node , homecoming it, or, if has not been created before, create , homecoming it.

example 2: when nodes c , have return/create different node! cannot homecoming ac, has new node (ca). order important!

later in processing it's possible nodes created earlier. illustration in 3rd phone call datastructure it's exclusively possible receive nodes "a , ac". 1 time again have create new node "a-ac", cache , homecoming it.

at first used many dictionary<tuple<node, node>, node> has multiple problems: - creating , comparing tuples turned out slow application - number of arguments fixed, need multiple dictionaries each different key (2-tuples, 3-tuples, ...)

i have lot of nodes. filtering incoming info bit have process @ to the lowest degree 15 1000000 20 1000000 different nodes.

a dictionary doesn't seem cutting it, performance memory consumption seem high.

i can freely modify how nodes implemented maybe there trick can utilize straight link many nodes one?

how can solve problem efficiently possible? datastructure used problem usually?

it seems have lot of constraints (time, efficiency, memory footprint). honest, i'm not sure set bar constraints.

i 1 time created little info construction accomplishes similar want. think.

public class stackblock { public string component { get; set; } public myobject resultingobject { get; set; } public list<stackblock> blocks { get; set; } }

the thought utilize these build tree functions cache created objects. little description of properties do:

component store "a" or "c" value resultingobject cached item "ac" blocks utilize create chains of blocks.

so if wanted store "ac" object, construction save in:

stackblock component: "a" resultingobject: null blocks: [ stackblock component: "c" resultingobject: myobject "ac" blocks: [ ... ] ]

edit put, item "cga" found in:

stackblock "c" -> stackblock "g" -> stackblock "a" -> resultingitem

you can maintain stacking blocks create longer , longer combinations. when need retrieve object, have traverse tree in order:

find stackblock a. in stackblock a, find kid stackblock c. in kid stackblock c, @ resultingobject. if not null, homecoming cached object.

note every step, if cannot find looking for, means not yet created, must create object , then store in tree. next time request it, available.

in case, "ac" , "ca" different objects, , tree allows store these in separate locations.

this ensure don't create object when in memory, because tree construction allows single place set specific element.

i hope in direction want?

note: old project of mine, before linq introduced. can imagine resulting code rather elegant , concise when utilize linq traversing tree. i'll spare how used it.

answer below comment

if have item "ga" , item "cga", not part of same stackblock "a". if you've cached 2 objects, tree follows:

stackblock c -> stackblock g -> stackblock -> resultingobject cga stackblock g -> stackblock -> resultingobject ga

note: you'd storing upper elements in list. list, find first element , start drilling down.

one possible point of confusion i'd address: see 2 stackblocks "g" , 2 stackblocks "a". these not same objects. every stackblock see mentioned in examples different objects (that happen have same letter).

maybe it'd improve understand if define stackblock struct instead of class. it'd work same, , you're prevented reusing same stackblock on different tiers of tree you're constructing.

resultingobject should hence not list, because there should single object phone call "cga". entire point of exercise prevent duplicate object beingness created, info construction tailored allow 1 place set cached object.

maybe helps if flesh out example, can see end up:

stackblock c -> stackblock g -> resultingobject cg -> stackblock -> resultingobject cga -> stackblock b -> resultingobject cgb stackblock g -> resultingobject g -> stackblock -> resultingobject ga -> stackblock x -> resultingobject gax -> stackblock k -> resultingobject gaxk

look @ 2 stackblocks called "g". 1 of them on top level, resultingobject g. other 1 second-level stackblock. therefore, resultingobject cg, because you have business relationship entire chain drilled down.

i hope helped clear up. it's simple concept 1 time understand it, i'm having difficulty describing why works :)

c# algorithm dictionary data-structures