Wo so ein Generator aufhören muss, kann man ja von aussen zum Beispiel mit `itertools.islice()` bestimmen. Die interessante Frage ist eher der Algoritmus die x. lexikografische Kombination direkt aus einem gegebenen x zu erzeugen kann, damit man diesen Startpunkt hat. Das geht auf jeden Fall, ich kann mich da dunkel an eine Vorlesung zu dem Thema erinnern. Muss mal in meinen Unterlagen suchen.
Bei 4 Sekunden mit PyPy lohnt sich der Aufwand das zu parallelisieren ja eigentlich kaum noch.
Ich habe hier einen Athlon64 X2 (Dual Core, 2,7 Ghz) allerdings mit 32-Bit-Betriebssystem. Da dauert ein sehr ähnliches Programm 11.635s.
Meinen zweiten Ansatz — sich die Kombinationen im ersten Durchlauf zu den entsprechenden Summen zu merken um nur noch die im zweiten Durchlauf zu testen wo Summe mal Anzahl gross genug ist — habe ich auch mal in C probiert. Das hat zwar nicht so eine katastrophale Laufzeit wie der Python-Versuch, ist aber trotzdem ≈5× langsamer als der „brute force” Ansatz bei dem einfach zweimal alle Kombinationen generiert werden. Ich dachte ja es lag bei Python an den dynamisch wachsenden Listen und dass ich das Problem in C umgehen kann, in dem ich einmal ein entsprechend grosses Array mit allen Kombinationen + Listenzeiger erzeuge und im Histogram einen Zeiger auf eine Kombination zu jeder Summe speichere und die Kombinationen dann über ihre Zeiger eine verkettete Liste bilden. Das ist Konstanter Aufwand pro Kombination. Das bisschen verketten ist aber anscheinend deutlich teurer als einfach die Kombinationen noch einmal zu generieren.
lotto_02.c:
Code: Alles auswählen
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#define N 49
#define K 6
#define MAX_SUM (279 + 1) /* = N + N-1 + N-2 + N-3 + N-4 + N-5 + 1*/
typedef struct Combination {
uint8_t numbers[K];
struct Combination *next;
} Combination;
typedef struct {
uint32_t length;
Combination *items;
} Combinations;
typedef struct {
uint32_t count;
Combination *head;
} HistogramEntry;
HistogramEntry histogram[MAX_SUM];
Combinations combinations;
uint32_t number_of_combinations(uint8_t n, uint8_t k)
{
uint32_t result = 1;
uint8_t i, max;
max = (k < n - k) ? k : n - k;
for (i = 0; i < max; ++i) {
result = (result * (n - i)) / (i + 1);
}
return result;
}
void Combination_init(Combination *combination)
{
uint8_t i;
for (i = 0; i < K; ++i) {
combination->numbers[i] = i + 1;
}
combination->next = NULL;
}
_Bool Combination_next(Combination *combination)
{
int8_t i;
uint8_t n;
for (i = K - 1, n = N - 1; i >= 0 && combination->numbers[i] > n; --i, --n);
if (i < 0) return false;
++combination->numbers[i];
for (i = ++i; i < K; ++i) {
combination->numbers[i] = combination->numbers[i - 1] + 1;
}
return true;
}
uint16_t Combination_sum(Combination *combination)
{
uint8_t i;
uint16_t result = 0;
for (i = 0; i < K; ++i) {
result += combination->numbers[i];
}
return result;
}
uint32_t Combination_product(Combination *combination)
{
uint8_t i;
uint32_t result = 1;
for (i = 0; i < K; ++i) {
result *= combination->numbers[i];
}
return result;
}
void Combination_print(Combination *combination)
{
uint8_t i;
for (i = 0; i < K; ++i) {
printf("%2d ", combination->numbers[i]);
}
putchar('\n');
}
void Combinations_init(void)
{
uint32_t i;
Combination combination;
combinations.length = number_of_combinations(N, K);
combinations.items = malloc(
combinations.length * sizeof(*combinations.items)
);
i = 0;
Combination_init(&combination);
do {
memcpy(&combinations.items[i++], &combination, sizeof(combination));
} while(Combination_next(&combination));
assert(i == combinations.length);
}
void Combinations_destroy(void)
{
combinations.length = 0;
free(combinations.items);
}
void calculate_histogram()
{
Combination *combination;
HistogramEntry *entry;
uint32_t i;
memset(histogram, 0, sizeof(histogram));
for (
i = 0, combination = combinations.items;
i < combinations.length;
++i, ++combination
) {
entry = &histogram[Combination_sum(combination)];
++entry->count;
combination->next = entry->head;
entry->head = combination;
}
}
void search_combination(void)
{
Combination *combination;
uint16_t i;
uint32_t x;
for (i = 0; i < MAX_SUM; ++i) {
x = i * histogram[i].count;
if (x > 2000000) {
combination = histogram[i].head;
while (combination) {
if (x == Combination_product(combination)) {
Combination_print(combination);
}
combination = combination->next;
}
}
}
}
int main(void)
{
Combinations_init();
calculate_histogram();
search_combination();
Combinations_destroy();
return 0;
}Code: Alles auswählen
Filename Impl. Runtime Factor
============== ====== ========= ===========
lotto_02.py python 6m41.216s -7.24
lotto_01.py python 34.144s 1.00
lotto_02.py pypy 21.054s 1.62
lotto_01.py pypy 11.635s 2.93
lotto_02.c 1.316s 25.95 (Neu)
lotto_01.c 0.267s 127.88
