U
DocShoe schrieb:
Es gibt die Funktion next_permutation in der STL, wirf da mal einen Blick drauf.
die erfüllt aber nicht die anforderungen (zum lottozahlen ziehen kann man sie relativ schlecht gebrauchen ;))
ich hab mich mal dran versucht. ist zwar relativ einfach zu benutzen, aber vrmtl so doof geschrieben, dass der compiler vieles nicht wegoptimieren kann. habs jetzt gerad mal gemessen. war dann aber zu faul, noch zu gucken, was man verbessern müsste, weil ich froh war, als es endlich lief^^ vermutlich aber vor allem, die zahlen in-place vertauschen. wollts aber auch mal so versuchen.
nur zum lotto zahlen durchprobieren läuft es schon 34sec bei höchster optimierungsstufe@msvc / core2duo E8400@3.0GHz:
#pragma once
#pragma warning(push)
#pragma warning(disable:4996)
#include <algorithm>
#include <cassert>
#include <iterator>
#include <ostream>
template <class T, class S = typename T::size_type>
class sorted_selection
{
public:
typedef typename T::value_type value_type;
typedef typename T::const_iterator const_iter_type;
typedef S size_type;
static sorted_selection make(const T& set, size_type count)
{
return sorted_selection(set, count);
}
static sorted_selection end()
{
return sorted_selection();
}
sorted_selection(const sorted_selection& rhs)
: set_(rhs.set_), count_(rhs.count_)
{
elements_ = nullptr;
if(count_ == size_type(0))
return;
elements_ = new const_iter_type[count_];
std::copy(rhs.elements_, rhs.elements_+count_, elements_);
}
~sorted_selection()
{
delete[] elements_;
}
sorted_selection& operator=(const sorted_selection& rhs)
{
sorted_selection(rhs).swap(*this);
return *this;
}
void swap(sorted_selection& rhs)
{
using std::swap;
swap(set_, rhs.set_);
swap(count_, rhs.count_);
swap(elements_, rhs.elements_);
}
std::ostream& operator<<(std::ostream& s) const
{
assert(!is_end());
for(auto i(elements_), e(elements_+count_); i != e; ++i)
s << **i << ' ';
return s;
}
bool is_end() const
{
return elements_ == nullptr;
}
sorted_selection next()
{
if(is_last())
return end();
sorted_selection ret_val(*this);
ret_val.set_to_next();
return ret_val;
}
private:
T const* set_;
size_type count_;
const_iter_type* elements_;
sorted_selection()
: set_(nullptr), count_(0), elements_(nullptr)
{}
sorted_selection(const T& set, size_type count)
: set_(&set), count_(count), elements_(new const_iter_type[count_])
{
assert(set.size() >= count_ && count_ > 0);
const_iter_type first = set_->begin();
for(size_type i(0); i != count_; ++i, ++first)
elements_[i] = first;
}
void set_to_next()
{
for(size_type i(count_); i != 0; --i)
{
if(position_less_than_max(i-1))
{
add_one_to_pos(i-1);
return;
}
for(; position_got_maximum(i-1); --i)
/* skip all max states - no need to test for index bounds*/;
// v----- (i-1)
// ... 23 24 98 99 {max = 99}
auto& pos_before_max_state = elements_[i-1];
++pos_before_max_state;
for(size_type j(i); j != count_; ++j)
{
//(j-1)----v
// ... 23 25 98 99 {max = 99}
// ^---- (j)
elements_[j] = elements_[j-1];
++elements_[j];
}
// ... 23 25 26 27 {max = 99}
return;
}
}
bool position_less_than_max(size_type at) const
{
auto& selection_position = elements_[at];
auto& max_set_position_for_selection_position = get_set_iter(set_->size()-count_+at);
return selection_position != max_set_position_for_selection_position;
}
bool position_got_maximum(size_type at) const
{
return !position_less_than_max(at);
}
void add_one_to_pos(size_type at)
{
auto& selection_position = elements_[at];
++selection_position;
}
const_iter_type get_set_iter(size_type at) const
{
const_iter_type first = set_->begin();
using std::advance;
advance(first, at);
return first;
}
bool is_last() const
{
assert(!is_end());
auto first_selected = get_set_iter(set_->size()-count_);
auto largest_available_state = elements_[0];
return first_selected == largest_available_state;
}
};
template <class T, class S>
std::ostream& operator<<(std::ostream& s, const sorted_selection<T, S>& these)
{
return these.operator<<(s);
}
template <class T, class S>
void swap(sorted_selection<T, S>& lhs, sorted_selection<T, S>& rhs)
{
lhs.swap(rhs);
}
#pragma warning(pop)
#include <iostream>
#include <vector>
int main()
{
const int min = 1;
const int max = 49;
const int pool_size = 7;
std::vector<int> pool;
for(int i(min), e(max+1); i != e; ++i)
pool.push_back(i);
timer_t time;
unsigned long long count = 0;
for(auto selection = sorted_selection<std::vector<int>>::make(pool, pool_size); !selection.is_end(); selection = selection.next())
++count;
time.stop();
std::cout << time.get_seconds() << " sec / " << count << std::endl;
}
+ timer:
#pragma once
#include "windows.h"
#include <cassert>
#include <stdexcept>
struct large_integer_t
{
typedef __int64 integral_type;
operator float() const
{
return static_cast<float>( static_cast<integral_type>(*this) );
}
operator integral_type() const
{
return data.QuadPart;
}
operator integral_type()
{
return data.QuadPart;
}
large_integer_t()
: data(LARGE_INTEGER())
{}
large_integer_t(const LARGE_INTEGER& data)
: data(data)
{}
large_integer_t& operator-= (const large_integer_t& other)
{
data.QuadPart -= other.data.QuadPart;
return *this;
}
private:
LARGE_INTEGER data;
};
large_integer_t operator- (const large_integer_t& lhs, const large_integer_t& rhs)
{
large_integer_t tmp(lhs);
tmp -= rhs;
return tmp;
}
class timer_t
{
public:
typedef float second_t;
timer_t()
: begin(get_timestamp())
#if !defined (NDEBUG)
, stopped(false)
#endif //#if !defined (_NDEBUG)
{
end = begin;
}
void stop()
{
#if !defined (NDEBUG)
stopped = true;
#endif //#if !defined (_NDEBUG)
end = get_timestamp();
}
second_t get_seconds() const
{
assert(stopped);
return (end-begin)/static_cast<second_t>(get_frequency());
}
private:
#if !defined (NDEBUG)
bool stopped;
#endif //#if !defined (_NDEBUG)
static large_integer_t get_frequency()
{
LARGE_INTEGER ret_val;
BOOL succeed = QueryPerformanceFrequency(&ret_val);
if(!succeed)
throw std::runtime_error("calling QueryPerformanceFrequency failed");
return ret_val;
}
static large_integer_t get_timestamp()
{
LARGE_INTEGER ret_val;
BOOL succeed = QueryPerformanceCounter(&ret_val);
if(!succeed)
throw std::runtime_error("calling QueryPerformanceCounter failed");
return ret_val;
}
large_integer_t begin;
large_integer_t end;
};
bb
edit: ok: inplace bringts doch ne ganze menge
void next_inplace()
{
if(is_last())
*this = end();
set_to_next();
}
<1sec
const int max = 65;
const int pool_size = 8;
<50sec
außerdem muss das array nicht vorsortiert sein, sondern man kann wahrscheinlichere zahlen/buchstaben vorn ranschreiben. schöner kann ichs jetzt aber nicht mehr reden^^
