Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

Länka ihop förälder och barn från en lista

1
Skriv svar
Permalänk
Medlem
●

Länka ihop förälder och barn från en lista

Tjo!

Antag att vi har en blandad lista med element som bland annat innehåller ett id och id på föräldern (om den har någon). Nu skulle jag vilja länka ihop dom så att varje barn har en referens till sin förälder.

Vad finns det för olika algoritmlösningar för att lösa det effektivast?

Min första tanke att angripa det hela var att göra en iterering igenom hela listan och spara alla element och dess id i en associativ array/map/hash och sedan göra en iterering till igenom hela listan och göra en lookup från mappen.

Är det den smidigaste lösningen att lösa det på eller finns det några andra smarta sätt att göra det på?

Scenariot är ett normalt program på en normal dator så det är ingen som behöver tokoptimeras för minimal minnesanvändning (eller några andra extremfall).

//C

Redigera
Citera flera Citera
Permalänk
Medlem
●

varför vill du spara allt i samma lista?

Visa signatur

In order to understand recursion, one must first understand recursion

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av pkzlol:

varför vill du spara allt i samma lista?

Gå till inlägget

Vill och vill, det är så jag har posterna. Det är inget ovanligt att man får poster i en lista/sekvens. Det kan till exempel vara ett (web)service-anrop som returnerar en lista med prylar eller så är posterna lagrade i en sql-tabell t.ex.

//C

Redigera
Citera flera Citera
Permalänk
Medlem
●

Vilket programmeringsspråk använder du dig av? Om det är C# så skulle jag rekommendera att du använder sig utav en Dictonary för att sammanfoga listorna.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Krass:

Vilket programmeringsspråk använder du dig av? Om det är C# så skulle jag rekommendera att du använder sig utav en Dictonary för att sammanfoga listorna.

Gå till inlägget

Jag är främst ute efter det generella resonemanget runt det hela. Det var förvisso en grej i Java jag skrev när jag tänkte på det hela.

Det du föreslår blir väl ändå samma sak som jag nämnde i första inlägget? Det vill säga en loop för att stoppa in alla i Dictionaryn och sedan en loop med ett dictionary-uppslag per post.

Sugen att höra om någon tänker på något annat sätt.

//C

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Skrivet av conio:

Jag är främst ute efter det generella resonemanget runt det hela. Det var förvisso en grej i Java jag skrev när jag tänkte på det hela.

Det du föreslår blir väl ändå samma sak som jag nämnde i första inlägget? Det vill säga en loop för att stoppa in alla i Dictionaryn och sedan en loop med ett dictionary-uppslag per post.

Sugen att höra om någon tänker på något annat sätt.

//C

Gå till inlägget

Det är alltid kul att optimera och försöka tänka på ett annat sätt!

Att det just är en blandad lista är väl det som verkligen ställer till det.
Barn X som ska vara ihopkopplat med Förälder Y kan ligga Z positioner ifrån varandra.
Hade det varit ett resultat från en SQL-query så kan man ju garantera att objekten är på samma rad i och med att man joinar osv.

Om vi tar det jobbiga exemplet där det är helt slumpat. Jag tror att jag hade gjort en variant av lösningen som du har.
Loopa igenom "resultatet" av barn och föräldrar.
Stöter du på ett barn så stoppar du in det i en List<Barn> om barnet har en förälderid-referens.
Stöter du på en förälder så stoppar du in det i en Dictionary<förälderid,Förälder>
Sen loopar du igenom Barn-listan och hämtar referensen till föräldern baserat på barnets förelderid.

Detta blir då en optimering så att man får ett ett-till-många-flöde istället för många-till-många. Då får du färre iterationer (eftersom vi inte loopar ALLT igen) och mindre hash (bara föräldrarna är med i den). Men denna skillnaden gör nog inte mycket (jämfört mot många-till-många) skulle jag säga.

Visa signatur

ηλί, ηλί, λαμά σαβαχθανί!?

Redigera
Citera flera Citera
Permalänk
Medlem
●

Du har en lista, vilken innehåller barn och föräldrar blandat. Oavsett om det är ett barn eller en förälder så har elementet ett ID. Ett barn har dessutom ett till ID, vilket är en referens till föräldern (om barnet har någon förälder).

Skrivet av conio:

Nu skulle jag vilja länka ihop dom så att varje barn har en referens till sin förälder.

Gå till inlägget

Antingen trasslar mig hjärna sig när jag läser din problem formulering, eller är den skriven knasigt.
Förtydliga gärna hur dina data strukturer ser ut

Visa signatur

In order to understand recursion, one must first understand recursion

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Leedow:

Det är alltid kul att optimera och försöka tänka på ett annat sätt!
...

Detta blir då en optimering så att man får ett ett-till-många-flöde istället för många-till-många. Då får du färre iterationer (eftersom vi inte loopar ALLT igen) och mindre hash (bara föräldrarna är med i den). Men denna skillnaden gör nog inte mycket (jämfört mot många-till-många) skulle jag säga.

Gå till inlägget

Kul att fler vill vara med och tänka Tyvärr håller inte ditt resonemang då man inte vet vilka element som är föräldrar. Det enda man vet är vilka som är barn (de har ett förälderid satt) men även barn kan vara föräldrar. Så då slutar det med samma variant som jag beskrev i början.

Skrivet av pkzlol:

Antingen trasslar mig hjärna sig när jag läser din problem formulering, eller är den skriven knasigt.
Förtydliga gärna hur dina data strukturer ser ut

Gå till inlägget

Det kan nog vara antingen det ena eller andra eller båda Jag har en tendens att vara lite otydlig ibland också.

Förenklat ser strukturen ut så här när jag får tillgång till den

public class Element {
   public int id;
   public Integer parentId; //Kan vara null/osatt
}

Sedan vill jag koppla ihop barnen med föräldern, dvs något i stil med följande:

public class Element {
   public int id;
   public Integer parentId; //Kan vara null/osatt
   public Element parent; //Kan vara null/osatt
}

Observera att jag är ute efter det generella resonemanget, inte någon kodlösning i något språk.

//C

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara