Algoritme for å hente verdier ut fra array

[bibo117]

Jeg har støtt på et lite problem og hadde vært evig takknemlig hvis noen kunne hjulpet meg litt!

 

Har deklarert en array. I arrayen ligger det verdier lastet inn fra en tekstfil. Jeg skal plukke ut forskjellige, tilfeldige verdier. Bruker en rnd-funksjon for å få til det. Problemet er at en bestemt verdi kun skal plukkes ut en gang, og ved bruk av rnd-funksjonen har jeg ingen garanti for at ikke den samme verdien blir trukket ut 2 ganger. Jeg tenkte først at jeg bare kunne opprette en ny array og føre verdiene over i den etterhvert som de blir trukket ut, men hvordan får jeg da slettet dem fra den opprinnelige arrayen? Er det eventuelt en mulighet å flytte den uttrukne verdien til bunnen av arrayen?

 

Noen tips? Eller smarte måter å gjøre dette på?

[Harald Staff]

Jeg pleier å gjøre det sånn:

1 Les inn alle verdiene og tilordne hver av dem et tilfeldig tall

2 Sorter etter disse tallene

3 Trekk ut de x første

 

HTH. Beste hilsen Harald

[bibo117]

Jeg pleier å gjøre det sånn:

1 Les inn alle verdiene og tilordne hver av dem et tilfeldig tall

2 Sorter etter disse tallene

3 Trekk ut de x første

 

HTH. Beste hilsen Harald

 

Hmm, smart!

 

Takk for svar!

[MailMan13]

Også mulig med litt Linq-magi:

var rnd = new Random();
var randomized = myList.OrderBy( x => rnd.Next());

 

Sorterings-baserte uttrekk som denne, og Harald's forslag itererer hele samlingen først (eller første gang du trekker et element med Linq), så performance-messig er det ikke bra hvis det er en stor liste og du skal trekke et lite antall elementer. Da kan det være bedre å merke "brukte" elementer, og heller trekke på nytt.

[bibo117]

Også mulig med litt Linq-magi:

var rnd = new Random();
var randomized = myList.OrderBy( x => rnd.Next());

 

Sorterings-baserte uttrekk som denne, og Harald's forslag itererer hele samlingen først (eller første gang du trekker et element med Linq), så performance-messig er det ikke bra hvis det er en stor liste og du skal trekke et lite antall elementer. Da kan det være bedre å merke "brukte" elementer, og heller trekke på nytt.

 

Hvordan kan jeg merke "brukte" elementer? Jeg er forholdsvis ny på VB og programmering, så beklager dumt spørsmål! ;P

[Harald Staff]

Samme måten, men istedetfor å tilordne et tilfeldig tall, tilordner du en boolsk False verdi som du setter til True idet du bruker verdien. Og så sjekker du om den er True for den neste du skal trekke, for i så fall trekker du en annen.

 

Det du sparer er tiden å sortere pluss litt RAM. Men ikke uvesentlig dette hvis du skal f.eks. trekke ut ti nordmenn (=sortere 5.2 mill folk først)

 

HTH. Beste hilsen Harald

[MailMan13]

En shuffle er jo linær (vanligvis iterere over array, swap hvert element med tilfeldig element med høyere index). Det kan gjøres i O(n) tid, og gjøres inkrementelt per element.

 

public static IEnumerable<T> Shuffle<T>(this T[] data)
{
   var rnd = new Random();
   var shuffled = data.ToArray();

   for(int i = 0;i<data.Length;i++)
   {
       var j = rnd.Next(data.Length - i);
       Swap(ref shuffled[i], ref shuffled[j + i]);
       yield return shuffled[i];
   }
}

 

Her kopierer jeg arrayet slik at metoden ikke skal mutere arrayet som sendes inn, utover det lages det kun en random for hver gang noen trekker et element fra Shuffle. Hvis man vil spare minne kan det utelates, men da vil orginale arrayet muteres etterhvert som trekkes elementer.

Endret 23. november 2010 av MailMan13

[GeirGrusom]

To ting bare: du burde legge ut alle slike random objekter i en static readonly variabel. Da forhindrer du at randomen genererer ikke-så-veldig-random tall.

Tror funksjonen kan ta inn IEnumerable<T> istedet for T[] også, og siden du bruker data.ToArray() regner jeg med det var meningen også