efficiency improvements in my code

[jamesfarrow]

Hi everyone. I have written the code below, its just a daft lottery simulator. Is there a way to make it more efficient. Like using pointers or references in the function calls - stuff like that!

Thanks in advance.

  #include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>


std::vector<int> GetNumbers();

std::vector< std::vector<int> > StoreGetNumbersInVector();


int main(int argc, const char * argv[]) {
    
    srand(static_cast<unsigned int>(time(NULL))); // randomise seed
    
    std::vector< std::vector<int> > StoredNumbers;
    std::vector<int> LottoDraw;
    bool LottoWin = false;
    int count = 0;
    
    
    do{
    StoredNumbers = StoreGetNumbersInVector();
    
    LottoDraw = GetNumbers();
        
    for(const auto &line : StoredNumbers){
        if(LottoDraw == line){
                LottoWin = true;
            }
            count++;
            if(count % 1000000 == 0){
                std::cout << count << std::endl;
            }
        }
    }while(!LottoWin);
    
    std::cout << "Draw number: " << count << std::endl;
    std::cout << "Winning line" << std::endl;
    for(const auto numbers : LottoDraw){
        std::cout << numbers << " ";
    }
    std::cout << std::endl;
    
    
    std::cout << "Lotto Card" << std::endl;
    for(const auto &line : StoredNumbers){
        for(const auto &numbers : line){
            std::cout << numbers << " ";
        }
        std::cout << std::endl;
    }
    
    

    

    return 0;
}


std::vector<int> GetNumbers(){
    
    int numberofballs = 60; // 60 to account for off by 1 error
    int line = 0; //number of balls in a line set to one and inc to 6
    
    
    std::vector<int> lotterynumbers(numberofballs, 0);
    std::vector<int> LottoLine;
    
    
    //generate 6 random numbers and set that element to the random number
    while(line < 6) {
        int RandomNum = 1 + rand() % 59;
        if (lotterynumbers[RandomNum] == 0){
            lotterynumbers[RandomNum] = RandomNum;
            ++line; //increment for stop condition of loop
        }
    }
    
    for( const auto numbers : lotterynumbers){
        if( numbers != 0){
            LottoLine.push_back(numbers);
        }
    }
    
    return LottoLine;
    
}

std::vector< std::vector<int> > StoreGetNumbersInVector(){
    
    std::vector< std::vector<int> > VectorOfVectors;
    
    
    for(int i = 0; i < 6; i++){
        VectorOfVectors.push_back(GetNumbers());
    }

    
    return VectorOfVectors;
}

[JLBorges]

> Is there a way to make it more efficient. Like using pointers or references in the function calls

No. Using value semantics (return the vector as a prvalue) is the most efficient way.

Every compiler implements NRVO

If a function returns a class type by value, and the return statement's expression is the name of a non-volatile object with automatic storage duration, which isn't the function parameter, or a catch clause parameter, and which has the same type (ignoring top-level cv-qualification) as the return type of the function, then copy/move (since C++11) is omitted. When that local object is constructed, it is constructed directly in the storage where the function's return value would otherwise be moved or copied to. This variant of copy elision is known as NRVO, "named return value optimization".
http://en.cppreference.com/w/cpp/language/copy_elision

[jamesfarrow]

Thanks! At the moment my code is as optimised as it can be? Is there a 'better way' to help it to run quicker...!

[jonnin]

lotterynumbers[RandomNum] = RandomNum;
^^ This concerns me. The index equals the value, so could lotterynumbers be of type bool and instead, do this
lotterynumbers[RandomNum] = true;

Also,

how big is this loop:

for(const auto &line : StoredNumbers){

if this is looping over a LOT of values, there may be some tweaks inside it. It looks like it may be comparing too much stuff, but I can't tell just by looking. You have a small winning combination pool, and a lot of tickets, generally. For very large inputs, you can do something cheezy like keep a sum of the winning combo and ticket selected numbers. If that matches, then you can do the full comparison of 60 values. If not, they didn't match.

[jamesfarrow]

I tried using bool but I couldn't get the range based loop to work properly on a true? It is interpreted as a '1', it seemed easier to set the vector to zero and do it that way?

[jonnin]

I am not sure. Lets back up on that... bear with me, I am glancing at this between waiting on something to run at work and can't study it in depth right now.

What exactly is your big comparison loop actually doing. It looks like there is a brute force lurking in it, but I am not 100% sure. I suspect there is a better way to do something in there. Are you looking for 100% winner tickets, or do you count partial match / lesser wins like a real lotto, or do you plan to do that?

[jamesfarrow]

Yes its a brute force comparison, and at the moment I'm only checking for jackpot winning line.
It is the do while statement where it all happens. A ticket of 6 lines in generated and each 1 in turn is compared against the draw line.

[jlb]

Have you thought about using some of the standard algorithms to aid in producing your random numbers?

const size_t Num_Picks = 6;

std::vector<int> GetNumbers()
{
    std::vector<int> v{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
                              16,17,16,19,20,21,22,23,24,25,26,27,28,29,30,
                              31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,
                              46,47,48,49,50,51,52,53,54,55,56,57,58,59};

    std::random_device rd;
    std::mt19937 g(rd());

    std::shuffle(v.begin(), v.end(), g);

    return{v.begin(), v.begin() + Num_Picks};
}

[jonnin]

Ok. This screams bucket sort.

define a ticket as (typedef might work here, whatever)
char ticket[60] = {0};
..
for the ticket, for each number...
generate number from 0-59. **INCREMENT bs[number].

for all tickets
memcmp bs vs ticket. Pass/fail result is fine for jackpot comparison.

you can do the same thing with vectors and algorithms if you prefer; this is simple enough that POD array and mem function will eat it alive.

you could squeeze a ticket into a 64 bit int if the tickets can only have 1 instance of a given number. If they can have the same number more than once, you can't.

[JLBorges]

Note: compile with optimisations enabled

#include <iostream>
#include <random>
#include <ctime>
#include <array>
#include <bitset>
#include <numeric>
#include <algorithm>

constexpr std::size_t N = 59 ; // total #numbers
constexpr std::size_t NUMBERS_PER_LINE = 6 ; // #balls in one line
constexpr std::size_t LINES_PER_DRAW = 6 ; // #balls in one line

#define USE_BITSET // comment out this line to use std::array instead of a bitset
                   // (try both; either one may be faster on a particular implementation)

#ifdef USE_BITSET
    using line = std::bitset<N> ; // line[i] is set if number i is in present
#else // use array
    using line = std::array<bool,N> ; // line[i] is set if number i is present
#endif // USE_BITSET

using card = std::array< line, LINES_PER_DRAW > ; // all lines in a card

std::array<std::size_t,N> all_numbers() { // 0, 1, ... N-1

    std::array<std::size_t,N> numbers ;
    std::iota( std::begin(numbers), std::end(numbers), 0 ) ; // fill with 0 .. N-1
    return numbers ;
}

line random_line() {

    static std::array<std::size_t,N> numbers = all_numbers() ;
    static std::mt19937 rng( std::time(nullptr) );

    // shuffle the numbers and pick the first NUMBERS_PER_LINE numbers
    // note: the twister would be slower than the crude std::rand()
    // however, the pseudo-randomness of the generated numbers would be a lot better
    std::shuffle( std::begin(numbers), std::end(numbers), rng ) ;
    line ln {} ;
    for( std::size_t i = 0 ; i < NUMBERS_PER_LINE ; ++i ) ln[ numbers[i] ] = true ;
    return ln ;
}

card random_card() {

    card crd ;
    for( line& ln : crd ) ln = random_line() ;
    return crd ;
}

bool check_win( const card& crd, const line& ln ) {

    return std::find( std::begin(crd), std::end(crd), ln ) != std::end(crd) ;
}

void print_line( const line& ln ) {

    for( std::size_t i = 0 ; i < ln.size() ; ++i )
        if( ln[i] ) std::cout << i+1 << ' ' ;
    std::cout << '\n' ;
}

void print_card( const card& crd ) {

    std::cout << "lotto card\n----------\n" ;
    for( const line& ln : crd ) print_line(ln) ;
    std::cout << '\n' ;
}

int main() {

    const card lotto_card = random_card() ;
    print_card(lotto_card) ;

    long long draw_number = 1 ;
    line ln ;
    while( !check_win( lotto_card, ln = random_line() ) ) {

        constexpr long long million = 1'000'000 ;

        if( draw_number % million == 0 )
            std::cout << draw_number/million << "M ... " << std::flush ;

        ++draw_number ;
    }

    std::cout << "\n\ndraw number: " << draw_number << "\nwinning line: " ;
    print_line(ln) ;
}

[JLBorges]

This may be faster (binary search instead of linear search):

#include <iostream>
#include <random>
#include <ctime>
#include <array>
#include <bitset>
#include <numeric>
#include <algorithm>

constexpr std::size_t N = 59 ; // total #numbers
constexpr std::size_t NUMBERS_PER_LINE = 6 ; // #balls in one line
constexpr std::size_t LINES_PER_DRAW = 6 ; // #lines in one card

using line = std::bitset<N> ; // line[i] is set if number i is present

using card = std::array< line, LINES_PER_DRAW > ; // all lines in a card

std::array<std::size_t,N> all_numbers() { // 0, 1, ... N-1

    std::array<std::size_t,N> numbers ;
    std::iota( std::begin(numbers), std::end(numbers), 0 ) ; // fill with 0 .. N-1
    return numbers ;
}

line random_line() {

    static std::array<std::size_t,N> numbers = all_numbers() ;
    static std::mt19937 rng( std::time(nullptr) );

    // shuffle the numbers and pick the first NUMBERS_PER_LINE numbers
    // note: the twister would be slower than the crude std::rand()
    // however, the pseudo-randomness of the generated numbers would be a lot better
    std::shuffle( std::begin(numbers), std::end(numbers), rng ) ;
    line ln {} ;
    for( std::size_t i = 0 ; i < NUMBERS_PER_LINE ; ++i ) ln[ numbers[i] ] = true ;
    return ln ;
}

card random_card() {

    card crd ;
    for( line& ln : crd ) ln = random_line() ;
    return crd ;
}

bool check_win( std::array< unsigned long long, LINES_PER_DRAW >& crd, const line& ln ) { // values in crd are ordered

    return std::binary_search( std::begin(crd), std::end(crd), ln.to_ullong() ) ;
}

void print_line( const line& ln ) {

    for( std::size_t i = 0 ; i < ln.size() ; ++i )
        if( ln[i] ) std::cout << i+1 << ' ' ;
    std::cout << '\n' ;
}

void print_card( const card& crd ) {

    std::cout << "lotto card\n----------\n" ;
    for( const line& ln : crd ) print_line(ln) ;
    std::cout << '\n' ;
}

int main() {

    const card lotto_card = random_card() ;
    print_card(lotto_card) ;

    std::array< unsigned long long, lotto_card.size() > number_values ;
    for( std::size_t i = 0 ; i < lotto_card.size() ; ++i )
        number_values[i] = lotto_card[i].to_ullong() ;
    std::sort( std::begin(number_values), std::end(number_values) ) ; // sort the lines

    long long draw_number = 1 ;
    line ln ;
    while( !check_win( number_values, ln = random_line() ) ) {

        constexpr long long million = 1'000'000 ;

        if( draw_number % million == 0 )
            std::cout << draw_number/million << "M ... " << std::flush ;

        ++draw_number ;
    }

    std::cout << "\n\ndraw number: " << draw_number << "\nwinning line: " ;
    print_line(ln) ;
}