Hi!

Da mich die Zeiten von OnlyFoo sehr beeindruckt haben, hab' ich mein Perl-Skript in C übersetzt und stell' es hier einfach mal mit ein:

Code C:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173

#include <errno.h> #include <stdio.h> #include <stdlib.h> #include <string.h>   typedef struct sweety_t sweety_t;   #define MAX_NAME_LENGTH 256   inline static sweety_t* sweety_create(const char*, unsigned, unsigned, sweety_t*);   inline static sweety_t* sweety_create_combi(const sweety_t*, const sweety_t*, sweety_t*);   static int sweety_print_name(const sweety_t*);   static void sweety_destroy(sweety_t*);   static sweety_t* calculate(sweety_t*);   inline static void candidate(sweety_t*);   static void usage(void);   struct sweety_t {     int is_combi;     union {         char *name;         struct {             const sweety_t *a;             const sweety_t *b;         } ref;     } data;     unsigned g, kcal;     sweety_t *next; };   static unsigned MAX; static sweety_t *BEST = NULL;   int main(void) {     sweety_t *sweeties = NULL, *sweety;     char name[MAX_NAME_LENGTH];     unsigned g, kcal;     if(0 >= scanf("%u", &MAX))       usage();     while(NULL != fgets(name, MAX_NAME_LENGTH, stdin))       {         if('\r' == *name || '\n' == *name)    /* Sonderbehandlung für */           continue;                           /* Windows-Input-Files  */         name[strcspn(name, "\r\n")] = '\0';   /* (CR/LF). */         if(0 >= scanf("%u %u", &g, &kcal))           usage();         if(MAX < g)           continue;         sweeties = sweety_create(name, g, kcal, sweeties);       }     if(NULL == sweeties)       usage();     calculate(sweeties);     for(sweety = sweeties; NULL != sweety; sweety = sweety->next)       candidate(sweety);     printf("Optimate Auswahl: ");     sweety_print_name(BEST);     printf("\nGewicht: %u g\nNährwert: %u kcal\n", BEST->g, BEST->kcal );     /* sweety_destroy(sweeties); */     return EXIT_SUCCESS; }   static sweety_t* calculate(sweety_t *combis) {     sweety_t *first, *current;     unsigned g;     first = combis;     if(NULL != first->next) {         combis = calculate(first->next);         for(current = combis; NULL != current; current = current->next)           {             if((g = first->g + current->g) <= MAX)               first->next = sweety_create_combi( first, current,                   first->next );           }     }     return first; }   inline static void candidate(sweety_t *combi) {     if(NULL == BEST || (BEST->kcal < combi->kcal))       BEST = combi; }   inline static sweety_t* sweety_create(const char *name, unsigned g, unsigned kcal, sweety_t *next) {     sweety_t *sweety;     size_t length = strlen(name) + 1;     sweety = malloc(length + sizeof(sweety_t));     if(NULL == sweety)       {         fprintf(stderr, "%s\n", strerror(ENOMEM));         exit(EXIT_FAILURE);       }     sweety->is_combi = 0;     sweety->data.name = (void*) sweety + sizeof(sweety_t);     memcpy(sweety->data.name, name, length);     sweety->g = g;     sweety->kcal = kcal;     sweety->next = next;     return sweety; }   inline static sweety_t* sweety_create_combi(const sweety_t *a, const sweety_t *b, sweety_t *next) {     sweety_t *sweety;     sweety = malloc(sizeof(sweety_t));     sweety->is_combi = 1;     if(NULL == sweety)       {         fprintf(stderr, "%s\n", strerror(ENOMEM));         exit(EXIT_FAILURE);       }     sweety->data.ref.a = a;     sweety->data.ref.b = b;     sweety->g = a->g + b->g;     sweety->kcal = a->kcal + b->kcal;     sweety->next = next;     return sweety; }   static int sweety_print_name(const sweety_t *sweety) {     int retval = 0;     if(0 == sweety->is_combi)       retval = fputs(sweety->data.name, stdout);     else       {         retval = sweety_print_name(sweety->data.ref.a);         retval |= fputs(", ", stdout);         retval |= sweety_print_name(sweety->data.ref.b);       }     return retval; }   static void sweety_destroy(sweety_t *sweety) {     if(NULL != sweety->next)       sweety_destroy(sweety->next);     free(sweety); }   static void usage(void) {     fputs( "Na, da stimmt wohl was mit der Eingabe nicht! "            "Schau mal hier: \nhttp://www"            ".tutorials.de/forum/diskussion/"            "357969-quiz-15-lisas-osternest.html\n", stderr );     exit(EXIT_FAILURE); }

Auf meinem Test-System komme ich damit aber immer noch nicht an OnlyFoo heran - und ich hab etliches probiert: Nicht einmal die diversen Memory-Pools und Alternativen für malloc haben geholfen (egal ob auf Basis von mmap, brk oder sbrk)! GCC Function Attributes haben ein wenig mehr Fahrtwind aufkommen lassen, allerdings nicht so viel dass es sich lohnen würde die hier mit zu präsentieren. Insofern bin ich echt auf die anderen Lösungen gespannt...

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

lenny:~/oster-quiz$ time ./a.out < 100leckereien.txt; echo Optimate Auswahl: Trüffel-Butter-Eierlikör-Ostereier, Joghurt-Trüffel-Krokant-Goldhase, Vollmilch-Eierlikör-Schokohase Gewicht: 494 g Nährwert: 3393 kcal   real    0m0.314s user    0m0.280s sys     0m0.032s   lenny:~/oster-quiz$ time ./a.out < 50leckereien.txt; echo Optimate Auswahl: Vollmilch-Krokant-Waffelhase, Marzipan-Vollmilch-Goldeier, Waffel-Joghurthase Gewicht: 494 g Nährwert: 3392 kcal   real    0m0.020s user    0m0.012s sys     0m0.008s   lenny:~/oster-quiz$ cat /proc/cpuinfo processor       : 0 vendor_id       : GenuineIntel cpu family      : 15 model           : 3 model name      : Intel(R) Pentium(R) 4 CPU 3.00GHz stepping        : 4 cpu MHz         : 2992.736 cache size      : 1024 KB fdiv_bug        : no hlt_bug         : no f00f_bug        : no coma_bug        : no fpu             : yes fpu_exception   : yes cpuid level     : 5 wp              : yes flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe constant_tsc up pebs bts pni monitor ds_cpl cid xtpr bogomips        : 5991.38 clflush size    : 64 power management:   lenny:~/oster-quiz$

Gruß
Enum