Vinderen af XBoxen
Jeg gør dette kort fordi jeg gerne vil holde weekend!
Sagen er den at jeg har fået rigtig mange gode bud på opgaven fra igår. Men der er et bud der slår dem alle sammen. Desværre kommer budet fra en Microsoft ansat, og da det ikke er første gang andre har fået ondt i deres jantelov, så må jeg hellere lade være med at give ham den Xbox. Mark du har ellers fortjent den!
Mark Seemann indsendte som en af de første dette knivskarpe bud:
Random r = new Random();
int[] numbers = Enumerable.Range(1, 1000).
Select(i => new { I = i, Key = r.Next() }).
OrderBy(a => a.Key).
Select(a => a.I).ToArray();
Men den går som sagt ikke...med mindre i andre synes at han skal vinde ?
Lad os se på hvad der ellers ligger i bunken.
Søren Larsen kom med et bud i VB.NET:
Function ArrayOfInts() As Integer()
Dim ArrayItems As New List(Of KeyValuePair(Of Integer, Integer))
Randomize()
For C = 1 To 1000
ArrayItems.Add(New KeyValuePair(Of Integer, Integer)(Rnd() * 20000, C))
Next
Return (From entity In ArrayItems Order By entity.Key Select entity.Value).ToArray
End Function
Og Brian har selvfølgelig også været på banen med dette:
public static int[] GetRandomNumbers() {
var numbers = Enumerable.Range(1, 1000).ToList();
var random = new Random();
numbers.Sort((l, r) => l == r ? 0 : random.Next(3) - 1 );
return numbers.ToArray();
}
Jeg har faktisk modtaget rigtig mange forslag der stort er ens. Se f.eks dette eksempel af Christian Dalager:
public List<int> Get1000Ints()
{
const int max = 1000;
var result = new List<int>(max);
var rand = new Random();
var intSrc = Enumerable.Range(1, 1000).ToList();
for (var i = max - 1; i >= 0; i--)
{
var index = i == 0 ? 0 : rand.Next(i - 1);
result.Add(intSrc[index]);
intSrc.RemoveAt(index);
}
return result;
}
Den sidste jeg vil bede jer om at tage med op til overvejelse er følgende:
public static int[] GenerateUsingHybridLinq(int arrayLength)
{
var random = new Random();
// Use PLINQ if we're above the "very scientific" limit of 3000.
if(arrayLength >= 3000)
{
return (from i in ParallelEnumerable.Range(1, arrayLength)
orderby random.Next()
select i).ToArray();
}
return (from i in Enumerable.Range(1, arrayLength)
orderby random.Next()
select i).ToArray();
}
I har indtil Mandag til at stemme på disse forslag. Der er i alt 5 kode eksempler, og i skal bare skrive jeres navn og tallet fra 1 - 5! I må kun stemme en gang.
Xboxen bliver sendt ud efter jul!
Comments
Anonymous
December 19, 2008
PingBack from http://blog.a-foton.ru/index.php/2008/12/19/vinderen-af-xboxen/Anonymous
December 19, 2008
Marks løsning er super-elegant (men har han overhovedet et TV til xbox'en? :-)). Desværre synes jeg, at Marks forslag (og alle de andre, der benytter LINQ) har den fejl, at de sorterer resultatet. Det dræber performance fuldstændigt! Jeg har lavet en lille test, hvor jeg sammenligner Marks forslag med mit eget forslag, som er den "traditionelle" løsning til random permutations (og derfor ikke specielt originalt - forslaget er ikke engang med på Daniels kandidatliste :-)). Marks forslag kører 5-6 gange langsommere, og jeg vil tro, at de 3 andre LINQ løsninger har samme problem! Jeg har pastet testkoden ind forneden. Men - reglerne siger ikke noget om, at løsningen skal give god performance, eller at man ikke må være ansat hos MS, så giv da Mark præmien for pokker :-) Kode: class Program { static void Main(string[] args) { Test(CreateRandomPermutation); Test(CreateRandomPermutation2); } delegate int[] PermutationHandler(); static void Test(PermutationHandler func) { DateTime start = DateTime.Now; for (int i = 0; i < 100000; ++i) { func(); } Console.WriteLine((DateTime.Now - start).Ticks.ToString("N")); } static int[] CreateRandomPermutation() { Random rand = new Random(); int[] ret = new int[1000]; for (int i = 0; i < ret.Length; ++i) ret[i] = i + 1; for (int i = 0; i < (ret.Length - 1); ++i) { int tmp = ret[i]; int idx = rand.Next(i, ret.Length); ret[i] = ret[idx]; ret[idx] = tmp; } return ret; } static int[] CreateRandomPermutation2() { Random r = new Random(); return Enumerable.Range(1, 1000).Select(i => new { I = i, Key = r.Next() }).OrderBy(a => a.Key).Select(a => a.I).ToArray(); } }Anonymous
December 19, 2008
Jeg stemmer på Sørens forslag!!!Anonymous
December 19, 2008
Når du nu spørger, så synes jeg, at det vil være upassende at lade præmien går til en Microsoft-mand - der må trods alt være nogle fordele ved ikke at være en del af biksen :) Jeg synes dog også, du skulle have afklaret dette inden og ikke lade den slags være op til os at bestemme. Det er underligt, at du fremhæver Marks bidrag og så kommer med den slags. Mht performance synes jeg, det er et underligt sted at slå ned. Daniel har jo udtaget to bidrag, der end ikke overholder de regler, han satte op. Christians bidrag returnerer List<int> i stedet for en array og Mark har slet ikke lavet en metode. Så hvorvidt en metode, der aldrig skal bruges i praksis kører hurtigere eller langsommere, er vel mindre vigtig.Anonymous
December 19, 2008
Jeg stemmer på Brians forslag :)Anonymous
December 19, 2008
The comment has been removedAnonymous
December 19, 2008
@ Jesper Hvis man benytter Random's default constructor bliver den seeded med tid (current ticks). Derfor er det problem du omtaler kun problematisk hvis man fx laver en ny Random for hver tal man skal bruge, da disse så vil have samme seed og derfor lave samme sekvens (og vigtigere endnu - samme start værdi).Anonymous
December 19, 2008
Nr. 5 er forresten min :-) Jeg ved ikke helt om det er fair at den kom med, eftersom jeg sendte en replacement løsning senere på aftenen - men det må være op til dem der stemmer :-) Jeg har tillad mig at skrive en lille blog-post om de løsninger jeg fandt på problemet, inklusiv den sidste jeg så kom frem til, hvis nogen er interesserede :-) http://www.rasmuskl.dk/post/Evolution-of-Solutions-and-Perceived-Performance.aspxAnonymous
December 19, 2008
@Rasmus Ja lige præscis det er sådan det er - tak for reminderen - det er ikke godt at være glemsom med det store .NET Framework :)Anonymous
December 19, 2008
For en god ordens skyld må jeg hellere lige understrege, at jeg explicit skrev til Daniel, at jeg som Microsoft-ansat naturligivs ikke deltager i konkurrencen om Xboxen - jeg syntes bare at opgaven var så sjov at jeg ikke kunne dy mig for at give mit bud. Jakob har i øvrigt helt ret i at jeg ikke har TV, så den ville være spildt på mig under alle omstændigheder :) Mht. performace er løsningen i sig selv muligvis ikke optimal, men det er interessant at bemærke, at grundet dens deklarative natur er den meget lettere for en kompiler at optimere end mere imparativ kode. Dette er en af hovedpointerne bag PLINQ, og nu har jeg godt nok ikke prøvet det af, men det skulle slet ikke overraske mig, hvis man kunne få en væsentlig forbedring næsten gratis ved at benytte PLINQ og en maskine med flere CPU'er (jeg vil hermed lade dette være en øvelse for den interesserede læser). Men som flere har gjort opmærksom på, var performance ikke et krav :)Anonymous
December 20, 2008
Jeg stemmer på Brians forslag.Anonymous
December 20, 2008
Jeg stemmer på sidste forslag.Anonymous
December 21, 2008
@Brian Det ser ud til, at der er en fejl i din kode. I enkelte tilfælde vil Sort funktionen kaste en ArgumentException, så der er et eller andet galt med din Comparison lambda-funktion. Kan det passe, at der er et krav om, at Comparison skal være deterministisk? Hvis Mark er ude, stemmer jeg på nummer 5 (Rasmus).Anonymous
December 21, 2008
Uden at have testet Brians kode ser det ud som om det måske kan være et problem med: (l, r) => l == r ? 0 : random.Next(3) - 1 Den kan give 0 selvom de to er forskellige - (random.Next(3) - 1 giver [-1, 0, 1]). l == r ? 0 : (random.next(2) == 0 ? -1 : 1) ville nok give det korrekte resultat - medmindre der er krav om at comparison skal være deterministisk som Jakob skrev.Anonymous
December 21, 2008
Jeg stemmer på Rasmus. Jeg kan ikke stemme på Mark eller Christian, da de ikke opfylder opgaveformuleringen. I øvrigt er det mega fesent at svar bliver udeladt, når man nu bruger tid på det. Mit svar var dette: def nisseDans(): import random, array nisser = range(0,1000) for i in nisser: snaps = random.randint(0,i) nisser[i], nisser[snaps] = nisser[snaps], nisser[i] return array.array("i", [nisse+1 for nisse in nisser]) Sproget er i øvrigt Python.Anonymous
December 21, 2008
@Rasmus Den version har jeg prøvet, og det giver også fejl. Det var derfor, jeg gættede på det med det deterministiske.Anonymous
December 21, 2008
@Jakob - dumme mig, jeg troede, det var nok, at bare læse dokumentationen. Her står der, at ArgumentException smides, hvis x ikke returnerer 0 ved sammenligning med x. Det tager jeg jo eksplicit højde for i min kode. Det er desværre ikke nok. Desværre forudsætter den underliggende QuickSort-implementering at Comparer-implementeringen er konsekvent. I langt de fleste tilfælde har det dog ingen effekt (hvilket forklarer, at man kan køre min kode mange, mange gange uden at få fejlen). Fejlen opstår, fordi de interne tællere tælles op/ned på baggrund af, hvad Compareren returnerer. Det kan i enkelte tilfælde resulterer i en IndexOutOfRangeException, der efterfølgende bliver pakket ind i førnævnte ArgumentException. Jeg debuggede problemet med WinDbg, hvor jeg ved selvsyn kunne konstatere IndexOutOfRange og spurgte for en sikkerheds skyld efter yderligere input på SO. Daniel, hvis du virkelig vil diskvalificere mig på jeres manglende dokumentation, må jeg jo leve med det :) Jeg synes, som nævnt ikke at Mark bør være med i konkurrencen, men hvis Daniel alligevel lader ham deltage, går min stemme i så fald til ham. Hvis både Mark og jeg er ude, går min stemme til Rasmus, selvom jeg synes, PLINQ er ret fjollet her.Anonymous
December 21, 2008
@Rasmus: Det er desværre ikke nok. Hvis man ser på implementeringen af QuickSort, vil man se, at et indeks tælles ned afhængig af hvad Compare returnerer. Hvis Compare-metoden ikke er konsekvent kan det resultere i IndexOutOfRange.