Return to Answer

added 1105 characters in body

Source Link

edited Sep 7, 2014 at 14:27

user52292

I ask the author to make this clear in the question. With this assumption, we have algorithm that works for count < int.MaxValue, but gets very slow for count close to that value, but that would mean eating nearly 8GB memory (2G*4B). We can try to make it faster for count greater than some threshold, e.g. 20 (subject to benchmarking), throw expectionexception for some ridiculous count and rewrite it like this:

The do..while may seem ugly, but is separated by two empty lines (in original code), thus makes it sufficient but still subject to further rethinking regarding to who may be maintaining the code. I will not address this furteher, because it depends on how many people may maintain the code and programmer's preferences (I will not address code-style while I see one). I am not that strict in this and for me, two empty lines (one before and one after) is enought to signal it needs more thinking when encountered and I will never touch a code that works and is optimal. Comments can help to describe the intent, code is to be reviewed when there is something wrong (does not work or is slow). The following may look better by using {}, more end-of-lines and few comments:

public static List<int> GetRandomNumbers(int count) {
//  eating too much memory is not desired
    if(count > int.MaxValue/8)
        throw new MyException("count too big");
    
    List<int> randomNumbers = new List<int>(count);
    if(count < 20) {
    //  list is fast enough for small count
        for (int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (randomNumbers.Contains(number));
            randomNumbers.Add(number);
        }
    } else {
    //  but HashSet is faster for longer sequence
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}

I ask the author to make this clear in the question. With this assumption, we have algorithm that works for count < int.MaxValue, but gets very slow for count close to that value, but that would mean eating nearly 8GB memory (2G*4B). We can try to make it faster for count greater than some threshold, e.g. 20 (subject to benchmarking), throw expection for some ridiculous count and rewrite it like this:

I ask the author to make this clear in the question. With this assumption, we have algorithm that works for count < int.MaxValue, but gets very slow for count close to that value, but that would mean eating nearly 8GB memory (2G*4B). We can try to make it faster for count greater than some threshold, e.g. 20 (subject to benchmarking), throw exception for some ridiculous count and rewrite it like this:

public static List<int> GetRandomNumbers(int count) {
//  eating too much memory is not desired
    if(count > int.MaxValue/8)
        throw new MyException("count too big");
    
    List<int> randomNumbers = new List<int>(count);
    if(count < 20) {
    //  list is fast enough for small count
        for (int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (randomNumbers.Contains(number));
            randomNumbers.Add(number);
        }
    } else {
    //  but HashSet is faster for longer sequence
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}

Source Link

answered Sep 6, 2014 at 20:13

user52292

First of all, there is one unspecified variable random and my best bet would be to assume it is System.Random and the Next method returns

A 32-bit signed integer greater than or equal to zero and less than MaxValue.

I ask the author to make this clear in the question. With this assumption, we have algorithm that works for count < int.MaxValue, but gets very slow for count close to that value, but that would mean eating nearly 8GB memory (2G*4B). We can try to make it faster for count greater than some threshold, e.g. 20 (subject to benchmarking), throw expection for some ridiculous count and rewrite it like this:

public static List<int> GetRandomNumbers(int count) {
    if(count > int.MaxValue/8)
        throw new MyException("count too big");
    
    List<int> randomNumbers = new List<int>(count); 
    if(count < 20) for (int i=0; i<count; i++) {
        int number; do number = random.Next(); // I will address the 'uglyness' later
        while (randomNumbers.Contains(number));
        randomNumbers.Add(number);
    } else {
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number; do number = random.Next();
            while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}