ComputerBase Menü
Aktuelles

C++ Wie kann man effizient 10 % aus einer List mit vielen Elementen ziehen?

firespot schrieb:
Und über das letzte bißchen an Performancen sollte man sich nur Gedanken machen nachdem gezieltes
Zum Vergrößern anklicken....
Naja, der Code von Kali-Hi den ich bei mir compiliert habe war auch nach Stunden noch nicht fertig :-)
Das "letzte bißchen an Performance" fühlt sich leicht anders an :-)
 
  • Gefällt mir
Reaktionen: Piktogramm
foofoobar schrieb:
war auch nach Stunden noch nicht fertig
Zum Vergrößern anklicken....
lag dann aber am Testfall ;) die Laufzeit wächst mit jeder "Runde" superpolynomial. Man kann den Test auch einfacher machen.
 
foofoobar schrieb:
der Code [...] war auch nach Stunden noch nicht fertig
Zum Vergrößern anklicken....
C++: 
#include <iostream>
#include <vector>
#include <ranges>
#include <random>
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <format>
#include <locale>

using namespace std;

template < typename E >
    void select_n_elements_a(const vector < E > & in, vector < E > & out,
        const uint32_t n) {
        static auto gen = default_random_engine {
            random_device {}()
        };
        vector < uint32_t > indexes(in.size());
        iota(begin(indexes), end(indexes), 0);
        ranges::shuffle(indexes, gen);
        sort(indexes.begin(), indexes.begin() + n);
        for (auto it = indexes.begin(); it != indexes.begin() + n; it++) {
            out.push_back(in [ * it]);
        }
    }

template < typename E >
    void select_n_elements_b(const vector < E > & in, vector < E > & out,
        const uint32_t n) {
        static auto gen = default_random_engine {
            random_device {}()
        };
        ranges::sample(in, back_inserter(out), n, gen);
    }

int main() {
        const uint32_t n = 100'000;
        vector < int > out1 = {};
        vector < int > out2 = {};
        vector < int > out3 = {};
        vector < int > out4 = {};
        // fill
        auto start = chrono::system_clock::now();
        vector<int> values;
        values.reserve(100'000'000);
        for (int i : ranges::views::iota(0, static_cast<int>(100'000'000)))
          values.push_back(i);

        auto end = chrono::system_clock::now();
        chrono::duration < double > elapsed = end - start;
        cout << "filling initial vector n=" << 100'000'000 << ":  " << elapsed.count() << endl;




        start = chrono::system_clock::now();
        select_n_elements_a(values, out1, n);
        end = chrono::system_clock::now();
        elapsed = end - start;
        cout << "select_n_elements_a 1. n=" << n << ":  " << elapsed.count() << endl;

        start = chrono::system_clock::now();
        select_n_elements_a(values, out2, n);
        end = chrono::system_clock::now();
        elapsed = end - start;
        cout << "select_n_elements_a 2. n=" << n << ":  " << elapsed.count() << endl;

        start = chrono::system_clock::now();
        select_n_elements_b(values, out3, n);
        end = chrono::system_clock::now();
        elapsed = end - start;
        cout << "select_n_elements_b 1. n=" << n << ":  " << elapsed.count() << endl;

        start = chrono::system_clock::now();
        select_n_elements_b(values, out4, n);
        end = chrono::system_clock::now();
        elapsed = end - start;
        cout << "select_n_elements_b 2. n=" << n << ":  " << elapsed.count() << endl;

        cout << endl;
        cout << "done";
    // }
}

2 Durchläufe muss gut genug sein bei großen Elementzahlen.
Code: 
filling initial vector n=100000000:  0.891856
select_n_elements_a 1. n=100000:  11.271
select_n_elements_a 2. n=100000:  11.29
select_n_elements_b 1. n=100000:  1.12709
select_n_elements_b 2. n=100000:  1.1194

done


Edit: Zur Frage, welcher Verteilung die Abstände der Indizes bei einer gleichverteilten Zufallsstichprobe folgen: Keine Ahnung. Es wird schon was Ähnliches sein wie eine Normalverteilung um den mittleren Abstand herum, aber es kann ja allein schon offensichtlich nicht negativ werden.
 
  • Gefällt mir
Reaktionen: kali-hi
  1. 100 Millionen Elemente gefüllt mit Strings hoch zählender Zahlen in einem gewöhnlichen Pointer Array. (Creator)
  2. Der Shaker ist Fisher-Yates. ( https://de.wikipedia.org/wiki/Zufällige_Permutation#Fisher-Yates-Verfahren )
  3. Das Sampling ist das ziehen von Elementen an einem zufälligen Index.
  4. Das Sampling könnte man noch bzgl. der Speichernutzung (evtl. auch CPU) optimieren in dem man das MSB von den Pointern nutzt um bereits gezogende Elemente zu markieren :-)
  5. Zufall ist Mersenne-Twister von Wikipedia mit festen Seed.
Conclusion: Ab dem Ziehen von mehr als ~2/3 Elementen ist der Shaker schneller.

Disclaimer: Ich bin ein wenig aus der Übung was C angeht.
Bugs: MANY! (Please report or fix it)
Speed: Make it faster!

Code: 
$ lscpu | grep "^Model n"
Model name:                           AMD Ryzen 7 7700 8-Core Processor
$ CFLAGS=-O3 make m
cc -O3    m.c   -o m
$ ./m
Start Creator
End Creator, Time required = 4.57157 seconds

99999999
mult: 0.023283

Start Pointer Copy (800 Megabytes)
End Pointer Copy, Time required = 0.04994 seconds


Start Shaker
End Shaker, Time required = 2.22900 seconds

0: 54146917, 1: 15112755, 2: 48826822, 3: 90161046, 4: 10923243,
99999999: 54148343, 99999998: 52793713, 99999997: 68249870, 99999996: 17562227,

Start sampling (5 Percent) (5000000 count)
End Sampling Time required = 0.12274 seconds
0: 82482960, 1: 47175951, 2: 37191809, 3: 41093301, 4: 55602759,

Start sampling (10 Percent) (10000000 count)
End Sampling Time required = 0.24817 seconds
0: 78543114, 1: 4953348, 2: 96917277, 3: 57940122, 4: 68840531,

Start sampling (15 Percent) (15000000 count)
End Sampling Time required = 0.37811 seconds
0: 71401878, 1: 71245615, 2: 28743191, 3: 81102185, 4: 49441787,

Start sampling (20 Percent) (20000000 count)
End Sampling Time required = 0.51284 seconds
0: 51449520, 1: 54203948, 2: 48830793, 3: 38648269, 4: 2932325,

Start sampling (25 Percent) (25000000 count)
End Sampling Time required = 0.65101 seconds
0: 13677937, 1: 38751965, 2: 28455323, 3: 40211532, 4: 77048749,

Start sampling (30 Percent) (30000000 count)
End Sampling Time required = 0.79616 seconds
0: 19157634, 1: 86224120, 2: 21237978, 3: 44600371, 4: 72549474,

Start sampling (35 Percent) (35000000 count)
End Sampling Time required = 0.94841 seconds
0: 78075291, 1: 23268388, 2: 4078930, 3: 12950136, 4: 35845025,

Start sampling (40 Percent) (40000000 count)
End Sampling Time required = 1.11407 seconds
0: 9685732, 1: 76826284, 2: 21667725, 3: 64293081, 4: 4223722,

Start sampling (45 Percent) (45000000 count)
End Sampling Time required = 1.29862 seconds
0: 4422140, 1: 37975280, 2: 20967172, 3: 52639719, 4: 55117114,

Start sampling (50 Percent) (50000000 count)
End Sampling Time required = 1.50990 seconds
0: 38379790, 1: 99657310, 2: 11661422, 3: 60556903, 4: 56984284,

Start sampling (55 Percent) (55000000 count)
End Sampling Time required = 1.77024 seconds
0: 90483048, 1: 28992318, 2: 43425535, 3: 26784200, 4: 29736220,

Start sampling (60 Percent) (60000000 count)
End Sampling Time required = 2.08957 seconds
0: 8162742, 1: 75658173, 2: 6369056, 3: 66982369, 4: 29892973,

Start sampling (65 Percent) (65000000 count)
End Sampling Time required = 2.45925 seconds
0: 49468421, 1: 16180629, 2: 25248074, 3: 97352443, 4: 99277901,

Start sampling (70 Percent) (70000000 count)
End Sampling Time required = 2.87456 seconds
0: 17534114, 1: 16463428, 2: 85334151, 3: 31573731, 4: 93497949,

Start sampling (75 Percent) (75000000 count)
End Sampling Time required = 3.32572 seconds
0: 11736580, 1: 98481698, 2: 73895709, 3: 35632777, 4: 53114223,

Start sampling (80 Percent) (80000000 count)
End Sampling Time required = 3.80037 seconds
0: 41698599, 1: 31345766, 2: 80130064, 3: 82786614, 4: 74684718,

Start sampling (85 Percent) (85000000 count)
End Sampling Time required = 4.30775 seconds
0: 55397316, 1: 13262261, 2: 21874730, 3: 72380467, 4: 48686991,

Start sampling (90 Percent) (90000000 count)
End Sampling Time required = 4.86745 seconds
0: 33692799, 1: 66840080, 2: 12800394, 3: 10943696, 4: 79676488,

Start sampling (95 Percent) (95000000 count)
End Sampling Time required = 5.67329 seconds
0: 38726026, 1: 74504358, 2: 91645937, 3: 47024247, 4: 59864699,

$ cat m.c
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define mw_state_n 624

// Version 0.1 (Bugs: many :-)
// Use "ulimit -s" for alloca !!!!! If ulimit is not availible substitute alloa with malloc (#define alloca malloc)

#define myrand ((int) ((double) random_uint32(&rnd_state) * mult));

typedef struct {
    uint32_t state_array[mw_state_n];    // the array for the state vector
    int state_index;            // index into state vector array, 0 <= state_index <= n-1   always
} mt_state;

void initialize_state(mt_state* state, uint32_t seed);
uint32_t random_uint32(mt_state* state);

int main(int argc, char** argv)
{
//    int i, ElementsCnt = 100;
//    int i, ElementsCnt = 65535;
    int i, ElementsCnt = 100000000;
    int percent;
    char **Elements, **Elements_copy;
    char *issampled;
    struct timespec begin, end;
    double mult;
    mt_state rnd_state;

    printf("%s\n", "Start Creator"); clock_gettime(CLOCK_MONOTONIC, &begin);
    Elements = alloca(ElementsCnt * sizeof(char*));                    // TODO check
    for (i = 0; i <= ElementsCnt; i++) {
        char buff[100];
        snprintf(buff, 100, "%d", i);
        if (!(Elements[i] = alloca(strlen(buff) + 1))) { puts("mem"); exit(1); }
        strcpy(Elements[i], buff);
    }
    clock_gettime(CLOCK_MONOTONIC, &end); printf("End Creator, Time required = %.5f seconds\n\n", ((double) end.tv_sec + 1.0e-9 * end.tv_nsec) - ((double) begin.tv_sec + 1.0e-9 * begin.tv_nsec));
    puts(Elements[ElementsCnt - 1]);

    initialize_state(&rnd_state, 19650218UL);
    mult = (double) (ElementsCnt ) / UINT32_MAX;
//    mult = (double) (ElementsCnt ) / (UINT32_MAX & 0x0000ffff);
    printf("mult: %f\n", mult);

//    for (i = 0; 1 ; i++) {
//        printf("%d rand: %u\n", i, (int) ((double) (random_uint32(&rnd_state) & 0x0000ffff) * mult));
//        printf("%d rand: %d %d\n", i, (int) ((double) random_uint32(&rnd_state) * mult), ElementsCnt);
//    }
    Elements_copy = alloca(ElementsCnt * sizeof(char*)); printf("\nStart Pointer Copy (%ld Megabytes)\n", ElementsCnt * sizeof(char*) / 1000000);    // TODO check

    clock_gettime(CLOCK_MONOTONIC, &begin);
    memcpy(Elements_copy, Elements, ElementsCnt * sizeof(char*)); clock_gettime(CLOCK_MONOTONIC, &end);
    printf("End Pointer Copy, Time required = %.5f seconds\n\n", ((double) end.tv_sec + 1.0e-9 * end.tv_nsec) - ((double) begin.tv_sec + 1.0e-9 * begin.tv_nsec));

    printf("\n%s\n", "Start Shaker"); clock_gettime(CLOCK_MONOTONIC, &begin);
    for (i = 0; i <= ElementsCnt; i++) {
        char* tmp_Element;
        int rand;

        rand = myrand;
        tmp_Element = Elements[i];
        Elements[i] = Elements[rand];
        Elements[rand] = tmp_Element;
    }
    clock_gettime(CLOCK_MONOTONIC, &end); printf("End Shaker, Time required = %.5f seconds\n\n", ((double) end.tv_sec + 1.0e-9 * end.tv_nsec) - ((double) begin.tv_sec + 1.0e-9 * begin.tv_nsec));

    for (i = 0; i <= 4; i++) {
        printf("%d: %s, ", i, Elements[i]);
    }
    puts("");
    for (i = ElementsCnt -1; i >= ElementsCnt - 4; i--) {
        printf("%d: %s, ", i, Elements[i]);
    }
    puts(""); puts("");

    memcpy(Elements, Elements_copy, ElementsCnt * sizeof(char*));        // deshake for sampling

#define inc_with_wrap(foo) (foo < ElementsCnt ? foo + 1 : 0)

    issampled = alloca(ElementsCnt);                    // TODO check
    for (percent = 5; percent <= 95; percent += 5) {
        int cnt, tmp, run, rand, runner = 0;

        bzero(Elements_copy, ElementsCnt * sizeof(char*));
        bzero (issampled,ElementsCnt);
        cnt = (int) (ElementsCnt * ((double) percent / 100));
        printf("Start sampling (%d Percent) (%d count)\n", percent, cnt); clock_gettime(CLOCK_MONOTONIC, &begin);

        for (i = 0; i <= cnt; i++) {
            rand = myrand;
            if (!issampled[rand]) {                        // Element was free;
                Elements_copy[runner++] = Elements[rand]; issampled[rand]++;
            } else {                            // Element was sampled before
                tmp = rand;
                tmp = inc_with_wrap(tmp);
                while (rand != tmp && issampled[tmp]) {            // Search for Empty Element
                    tmp = inc_with_wrap(tmp);
                }
                if (rand == tmp) {
                    puts("Infinite Loop stopped");
                    exit(1);
                }
                Elements_copy[runner++] = Elements[tmp]; issampled[tmp]++;
            }
        }
        clock_gettime(CLOCK_MONOTONIC, &end); printf("End Sampling Time required = %.5f seconds\n", ((double) end.tv_sec + 1.0e-9 * end.tv_nsec) - ((double) begin.tv_sec + 1.0e-9 * begin.tv_nsec));

        for (run = 0; run <= 4; run++) {
            printf("%d: %s, ", run, Elements_copy[run] ? Elements_copy[run] : "NULL");
        }
        puts(""); puts("");
    }
    exit (0);
}

// https://en.wikipedia.org/wiki/Mersenne_Twister

// replaced by mw_state_n
// #define n 624

#define m 397
#define w 32
#define r 31
#define UMASK (0xffffffffUL << r)
#define LMASK (0xffffffffUL >> (w-r))
#define a 0x9908b0dfUL
#define u 11
#define s 7
#define t 15
#define l 18
#define b 0x9d2c5680UL
#define c 0xefc60000UL
#define f 1812433253UL

void initialize_state(mt_state* state, uint32_t seed)
{
    uint32_t* state_array = &(state->state_array[0]);
 
    state_array[0] = seed;                          // suggested initial seed = 19650218UL
 
    for (int i=1; i<mw_state_n; i++)
    {
        seed = f * (seed ^ (seed >> (w-2))) + i;    // Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
        state_array[i] = seed;
    }
 
    state->state_index = 0;
}


uint32_t random_uint32(mt_state* state)
{
    uint32_t* state_array = &(state->state_array[0]);
 
    int k = state->state_index;      // point to current state location
                                     // 0 <= state_index <= n-1   always
 
//  int k = k - n;                   // point to state n iterations before
//  if (k < 0) k += n;               // modulo n circular indexing
                                     // the previous 2 lines actually do nothing
                                     //  for illustration only
 
    int j = k - (mw_state_n-1);               // point to state n-1 iterations before
    if (j < 0) j += mw_state_n;               // modulo n circular indexing

    uint32_t x = (state_array[k] & UMASK) | (state_array[j] & LMASK);
 
    uint32_t xA = x >> 1;
    if (x & 0x00000001UL) xA ^= a;
 
    j = k - (mw_state_n-m);                   // point to state n-m iterations before
    if (j < 0) j += mw_state_n;               // modulo n circular indexing
 
    x = state_array[j] ^ xA;         // compute next value in the state
    state_array[k++] = x;            // update new state value
 
    if (k >= mw_state_n) k = 0;               // modulo n circular indexing
    state->state_index = k;
 
    uint32_t y = x ^ (x >> u);       // tempering
             y = y ^ ((y << s) & b);
             y = y ^ ((y << t) & c);
    uint32_t z = y ^ (y >> l);
 
    return z;
}
$
 
Zuletzt bearbeitet:
  • Gefällt mir
Reaktionen: kali-hi
foofoobar schrieb:
Ab dem Ziehen von mehr als ~2/3 Elementen
Zum Vergrößern anklicken....
Das kann ich bestätigen, wenn (ziemlich) genau 66 % der Elemente ausgewählt werden sollen, dann haben beide Verfahren in etwa die gleiche Laufzeit (oder sind sich am ähnlichsten...)

C++: 
#include <cstdint>
#include <cmath>
#include <chrono>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

template < typename E >
    void select_n_elements_a(const vector < E > & in, vector < E > & out,
        const uint32_t n) {
        static auto gen = default_random_engine {
            random_device {}()
        };
        vector < uint32_t > indexes(in.size());
        iota(begin(indexes), end(indexes), 0);
        shuffle(indexes.begin(), indexes.end(), gen);
        sort(indexes.begin(), indexes.begin() + n);
        for (auto it = indexes.begin(); it != indexes.begin() + n; it++) {
            out.push_back(in [ * it]);
        }
    }

template < typename E >
    void select_n_elements_b(const vector < E > & in, vector < E > & out,
        const uint32_t n) {
        static auto gen = default_random_engine {
            random_device {}()
        };
        ranges::sample(in, back_inserter(out), n, gen);
    }

// test until the first match
template < typename T >
    void test1(T select_n_elements,
        const uint32_t n,
            const uint32_t type) {
        vector < int > in(n);
        iota(begin(in), end(in), 0);
        for (int i = 0; i < in.size();) {
            vector < int > out = {};
            select_n_elements(in, out, type == 0 ? 1 : n - 1);

            if (type == 0 && out[0] == i || type == 1 && find(out.begin(), out.end(), i) == out.end()) {
                i++;
            }
        }
    }

template < typename T >
    chrono::duration < double > time1(T select_n_elements,
        const uint32_t n1,
            const uint32_t n2) {
        vector < int > in(n1);
        iota(begin(in), end(in), 0);
        vector < int > out = {};
        auto start = chrono::system_clock::now();
        select_n_elements(in, out, n2);
        auto end = chrono::system_clock::now();
        return end - start;
    }

int main() {
    const uint32_t n1 = 1'000'000;
    uint32_t n2 = 0;
    uint32_t delta = n1 / 2;
    double dist = 100;
    for (int i = 1; i <= 50; i++) {
        cout << "i=" << i << "  n2=" << n2 << "  dist=" << dist << endl;
        auto t1 = time1(select_n_elements_a < int > , n1, n2);
        auto t2 = time1(select_n_elements_b < int > , n1, n2);
        auto d = (t1 - t2) / t1;
        cout << "New dist:  " << d << endl;
        if (d < dist) {
            n2 += delta;
        } else if (d > dist) {
            n2 -= delta;
        }
        delta -= delta / 5;
        dist = d;
    }
}

Den Test kann jeder selber probieren und sollte nur ein paar Sekunden dauern.
 
  • Gefällt mir
Reaktionen: simpsonsfan
kali-hi schrieb:
wenn (ziemlich) genau 66 % der Elemente ausgewählt werden sollen, dann haben beide Verfahren in etwa die gleiche Laufzeit (oder sind sich am ähnlichsten...)
Zum Vergrößern anklicken....
Also die gleich Laufzeit kann ich nicht bestätigen, die Anzahl auch nicht.
Hab es mal lokal (g++) und auf onlinegdb.com (also auch g++) laufen lassen.
Das Laufzeitverhältnis konvergiert gegen 0.9, sprich select_elements_b benötigt dann 10% der Laufzeit von a. Die Anzahl der Elemente n variiert, beim Onlinecompiler kam eher etwas mehr raus, lokal etwas weniger. Und das unterschiedlich bei mehreren Aufrufen. Aber es war so im Bereich n=70 000 bis n=85 000.

Code: 
g++ lokal
i=50  n2=727345  dist=0.892362
New dist:  0.891293

onlinegdb:
i=50  n2=841125  dist=0.895698
New dist:  0.899537

Verschiedene Compiler können dabei natürlich unterschiedliche PRNGs als default verwenden, hab an dem Code nix geändert.
 
  • Gefällt mir
Reaktionen: kali-hi
Wie meinst das? Ich hatte nur std::ranges::shuffle durch std::shuffle ersetzt...

Als Zeitberechnung hatte ich Zeit A minus Zeit B, geteilt durch Zeit A genommen, also die Differenz, aber noch einmal geteilt durch die längere Ausführungszeit der beiden.

Beispiel:
A=10s B=2s ergibt 4/5 (also 0.8)
A=1s B=0.2s ergibt auch 4/5 (also 0.8)

Mich interessiert also nur der relative Zeitabstand.
 
simpsonsfan schrieb:
Verschiedene Compiler können dabei natürlich unterschiedliche PRNGs als default verwenden, hab an dem Code nix geändert.
Zum Vergrößern anklicken....
Oder die Compiler bringen unterschiedliche Implementierungen von shuffle oder ranges mit.
 
  • Gefällt mir
Reaktionen: simpsonsfan
kali-hi schrieb:
auto d = (t1 - t2) / t1;
Zum Vergrößern anklicken....

Ich glaube, auto d = (t1 - t2) / (t1 + t2); wäre richtiger.

simpsonsfan schrieb:
Verschiedene Compiler können dabei natürlich unterschiedliche PRNGs als default verwenden, hab an dem Code nix geändert.
Zum Vergrößern anklicken....
Habe bislang immer nur online getestet. 1 2
 
kali-hi schrieb:
Ich glaube, auto d = (t1 - t2) / (t1 + t2); wäre richtiger.
Zum Vergrößern anklicken....
Variablen schlau und sprechend zu benennen hat Vorteile :-)
kali-hi schrieb:
Habe bislang immer nur online getestet. 1 2
Zum Vergrößern anklicken....
Sind Cygwin, WSL, Live-CDs oder andere freie Compiler4WIN sind keine Alternative für dich?
Löhnware ist nicht zwingend besser.
 
foofoobar schrieb:
Löhnware ist nicht zwingend besser.
Zum Vergrößern anklicken....
Bin dort ja nicht angemeldet...

foofoobar schrieb:
Sind Cygwin, WSL, Live-CDs oder andere freie Compiler4WIN
Zum Vergrößern anklicken....
Es gäbe auch noch Docker-Container (obwohl die teils auf WSL setzen)... aber so ist es einfacher

Ich mache C++ nicht professionell
 
foofoobar schrieb:
[...] 100 Millionen Elemente gefüllt mit Strings hoch zählender Zahlen in einem gewöhnlichen Pointer Array.
Zum Vergrößern anklicken....
Ich hab mal auf meiner Hardware (Ryzen 5 7600, leider nur halb so schnell wie bei dir) deinen Code und die C++ sample Variante getestet. Du hast hier ja (soweit ich sehe) noch keinen Vergeich zu den C++ STL Varianten gepostet. Jeweils 100 000 000 Elemente. Bei dir das Pointer-Array auf Strings, In C++ ein std::vector<int>.
Davon dann 5% (5 000 000) ziehen:

foofoobar Pointer Array C
Code: 
End Shaker, Time required = 4.38791 seconds
Start sampling (5 Percent) (5000000 count)
End Sampling Time required = 0.24441 seconds

C++ STL vector<int> sample
Code: 
select_n_elements_a (
ranges::shuffle ohne sort) n=5000000:  11.6454
ranges::shuffle und sort) n=5000000:  12.7247
select_n_elements_b (ranges::sample) n=5000000:  1.20672

Also, Applaus! So viel zum Thema Performance.

@kali-hi Kann dir nur zu Cygwin raten. Bringt auch ne Bash mit, die sich sich mittlerweile sehr schön in den Windows-Terminal integrieren lässt. Und auch wenn es Geschmacksache ist, sind wir mal ehrlich, bash > Powershell.
 
simpsonsfan schrieb:
Ich hab mal auf meiner Hardware (Ryzen 5 7600, leider nur halb so schnell wie bei dir) deinen Code und die C++ sample Variante getestet.
Zum Vergrößern anklicken....
Danke, dann brauch ich das nicht selber machen. (Ich mag einfach diesen Zen4 mit 65 Watt, der lief während der Tests mit ~5,4 GHz)
Ich vermute das mein Code fast komplett an der RAM-Bandbreite hängt, und da bin ich voll auf JEDEC, innerhalb der offiziellen AMD-Specs und mit ECC unterwegs. Also am alleruntersten Ende unterwegs.

Deswegen habe ich für Vergleiche auch die Laufzeit der (zu kurzen) "Pointer Copy" mit ausgegeben.
Für ernsthafte Vergleiche müßte man noch eine Loop drumbauen.
simpsonsfan schrieb:
Du hast hier ja (soweit ich sehe) noch keinen Vergeich zu den C++ STL Varianten gepostet. Jeweils 100 000 000 Elemente. Bei dir das Pointer-Array auf Strings, In C++ ein std::vector<int>.
Zum Vergrößern anklicken....
Sollte keinen Unterschied machen solange man nur mit den Pointern rummacht.
simpsonsfan schrieb:
Davon dann 5% (5 000 000) ziehen:

foofoobar Pointer Array C
Code: 
End Shaker, Time required = 4.38791 seconds
Start sampling (5 Percent) (5000000 count)
End Sampling Time required = 0.24441 seconds

C++ STL vector<int> sample
Code: 
select_n_elements_a (
ranges::shuffle ohne sort) n=5000000:  11.6454
ranges::shuffle und sort) n=5000000:  12.7247
select_n_elements_b (ranges::sample) n=5000000:  1.20672

Also, Applaus! So viel zum Thema Performance.
Zum Vergrößern anklicken....
Faktor ~2,6 und ~3,6 schneller zeigt gut den Overhead den man sich durch die Nutzung ungeeigneter Datenstrukturen und ggf. unnötiger Abstraktionen einfängt.

Hier der passende Rant dazu: http://www.fefe.de/dietlibc/kleinesoftware.pdf

BTW: Mersenne-Twister gibt es auch mit SIMD: https://www.google.com/search?q=mersenne+twister+simd
 
Zuletzt bearbeitet:
  • Gefällt mir
Reaktionen: Piktogramm
So, damit wir auf die gleiche Basis kommen, macht mal bitte Folgendes:

Main.cpp:

C++: 
#include <cstdint>
#include <cmath>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

template <typename E>
void select_n_elements_a(const vector<E> &in, vector<E> &out,
                         const uint32_t n)
{
    static auto gen = default_random_engine{
        random_device{}()};
    vector<uint32_t> indexes(in.size());
    iota(begin(indexes), end(indexes), 0);
    shuffle(indexes.begin(), indexes.end(), gen);
    sort(indexes.begin(), indexes.begin() + n);
    for (auto it = indexes.begin(); it != indexes.begin() + n; it++)
    {
        out.push_back(in[*it]);
    }
}

template <typename E>
void select_n_elements_b(const vector<E> &in, vector<E> &out,
                         const uint32_t n)
{
    static auto gen = default_random_engine{random_device{}()};
    sample(in.begin(), in.end(), back_inserter(out), n, gen);
}

// test until the first match
template <typename T>
void test1(T select_n_elements,
           const uint32_t n,
           const uint32_t type)
{
    vector<int> in(n);
    iota(begin(in), end(in), 0);
    for (int i = 0; i < in.size();)
    {
        vector<int> out = {};
        select_n_elements(in, out, type == 0 ? 1 : n - 1);

        if (type == 0 && out[0] == i || type == 1 && find(out.begin(), out.end(), i) == out.end())
        {
            i++;
        }
    }
}

template <typename T>
chrono::duration<double> time1(T select_n_elements,
                               const uint32_t n1,
                               const uint32_t n2)
{
    vector<int> in(n1);
    iota(begin(in), end(in), 0);
    vector<int> out = {};
    auto start = chrono::system_clock::now();
    select_n_elements(in, out, n2);
    auto end = chrono::system_clock::now();
    return end - start;
}

int main()
{
    const uint32_t n1 = 1000000; // 1 million
    uint32_t n2 = 0;
    uint32_t delta = n1 / 2;
    double dist = 100;
    cout << setprecision(4);
    for (int i = 1; i <= 55; i++)
    {
        auto t1 = time1(select_n_elements_a<int>, n1, n2);
        auto t2 = time1(select_n_elements_b<int>, n1, n2);
        auto d = (t1 - t2) / t1 * 100.0;
        cout << "i=" << i << "\tn2=" << n2 << "\told_dist=" << dist << "\tnew_dist=" << d << "\tdelta=" << delta << endl;

        if (d < dist)
        {
            n2 += delta;
        }
        else if (d > dist)
        {
            n2 -= delta;
        }
        delta -= delta / 5;
        dist = d;
    }
    cout << "Final n2: " << n2 << endl;

    const uint32_t n11 = n1 * 100; // 100 million
    const uint32_t n21 = n2 * 100;
    auto t1 = time1(select_n_elements_a<int>, n11, n21);
    auto t2 = time1(select_n_elements_b<int>, n11, n21);
    auto diff_percent = (t1 - t2) / t1 * 100.0;
    cout << "Final test with n1=" << n11 << " n2=" << n21 << " t1=" << t1.count() << " t2=" << t2.count() << " diff_percent=" << diff_percent << "%" << endl;
    return 0;
}

PowerShell: 
docker run --rm -it -v ${pwd}:/app -w /app lazypanda07/ubuntu_cxx20:24.04 g++ -std=c++17 -Wall -Wextra -Werror Main.cpp -o a.out
docker run --rm -it -v ${pwd}:/app -w /app lazypanda07/ubuntu_cxx20:24.04 bash -c "chmod +x a.out && ./a.out"

(valgrind ginge hier auch ...)

Und dann ist die Ausgabe bei mir:

Code: 
i=1     n2=0    old_dist=100    new_dist=99.99  delta=500000
i=2     n2=500000       old_dist=99.99  new_dist=85.49  delta=400000
i=3     n2=900000       old_dist=85.49  new_dist=89.91  delta=320000
i=4     n2=580000       old_dist=89.91  new_dist=84.39  delta=256000
i=5     n2=836000       old_dist=84.39  new_dist=88.28  delta=204800
i=6     n2=631200       old_dist=88.28  new_dist=84.93  delta=163840
i=7     n2=795040       old_dist=84.93  new_dist=87.61  delta=131072
i=8     n2=663968       old_dist=87.61  new_dist=85.64  delta=104858
i=9     n2=768826       old_dist=85.64  new_dist=86.51  delta=83887
i=10    n2=684939       old_dist=86.51  new_dist=86.17  delta=67110
i=11    n2=752049       old_dist=86.17  new_dist=87.06  delta=53688
i=12    n2=698361       old_dist=87.06  new_dist=86.17  delta=42951
i=13    n2=741312       old_dist=86.17  new_dist=87.17  delta=34361
i=14    n2=706951       old_dist=87.17  new_dist=86.19  delta=27489
i=15    n2=734440       old_dist=86.19  new_dist=86.83  delta=21992
i=16    n2=712448       old_dist=86.83  new_dist=86.47  delta=17594
i=17    n2=730042       old_dist=86.47  new_dist=86.8   delta=14076
i=18    n2=715966       old_dist=86.8   new_dist=86.54  delta=11261
i=19    n2=727227       old_dist=86.54  new_dist=86.68  delta=9009
i=20    n2=718218       old_dist=86.68  new_dist=86.49  delta=7208
i=21    n2=725426       old_dist=86.49  new_dist=86.51  delta=5767
i=22    n2=719659       old_dist=86.51  new_dist=86.71  delta=4614
i=23    n2=715045       old_dist=86.71  new_dist=86.58  delta=3692
i=24    n2=718737       old_dist=86.58  new_dist=86.69  delta=2954
i=25    n2=715783       old_dist=86.69  new_dist=86.13  delta=2364
i=26    n2=718147       old_dist=86.13  new_dist=86.67  delta=1892
i=27    n2=716255       old_dist=86.67  new_dist=86.47  delta=1514
i=28    n2=717769       old_dist=86.47  new_dist=86.55  delta=1212
i=29    n2=716557       old_dist=86.55  new_dist=86.72  delta=970
i=30    n2=715587       old_dist=86.72  new_dist=86.65  delta=776
i=31    n2=716363       old_dist=86.65  new_dist=86.48  delta=621
i=32    n2=716984       old_dist=86.48  new_dist=86.17  delta=497
i=33    n2=717481       old_dist=86.17  new_dist=86.55  delta=398
i=34    n2=717083       old_dist=86.55  new_dist=86.55  delta=319
i=35    n2=717402       old_dist=86.55  new_dist=86.54  delta=256
i=36    n2=717658       old_dist=86.54  new_dist=87.99  delta=205
i=37    n2=717453       old_dist=87.99  new_dist=86.71  delta=164
i=38    n2=717617       old_dist=86.71  new_dist=86.81  delta=132
i=39    n2=717485       old_dist=86.81  new_dist=86.67  delta=106
i=40    n2=717591       old_dist=86.67  new_dist=86.68  delta=85
i=41    n2=717506       old_dist=86.68  new_dist=86.67  delta=68
i=42    n2=717574       old_dist=86.67  new_dist=86.62  delta=55
i=43    n2=717629       old_dist=86.62  new_dist=86.6   delta=44
i=44    n2=717673       old_dist=86.6   new_dist=86.78  delta=36
i=45    n2=717637       old_dist=86.78  new_dist=86.67  delta=29
i=46    n2=717666       old_dist=86.67  new_dist=86.43  delta=24
i=47    n2=717690       old_dist=86.43  new_dist=86.61  delta=20
i=48    n2=717670       old_dist=86.61  new_dist=86.47  delta=16
i=49    n2=717686       old_dist=86.47  new_dist=86.46  delta=13
i=50    n2=717699       old_dist=86.46  new_dist=86.76  delta=11
i=51    n2=717688       old_dist=86.76  new_dist=86.59  delta=9
i=52    n2=717697       old_dist=86.59  new_dist=86.59  delta=8
i=53    n2=717705       old_dist=86.59  new_dist=86.59  delta=7
i=54    n2=717698       old_dist=86.59  new_dist=86.76  delta=6
i=55    n2=717692       old_dist=86.76  new_dist=86.69  delta=5
Final n2: 717697
Final test with n1=100000000 n2=71769700 t1=40.24 t2=3.916 diff_percent=90.27%

Das heißt ... die std::sample-Variante ist bei mir im Vergleich im worst case noch ca. 90 % schneller als meine Variante.

Richtig?
Ergänzung ()

foofoobar schrieb:
durch die Nutzung ungeeigneter Datenstrukturen
Zum Vergrößern anklicken....
Das liegt hier nicht an der Datenstruktur (std::vector), sondern an einer anderen Algorithmenkomplexität.
 
  • Gefällt mir
Reaktionen: kuddlmuddl
kali-hi schrieb:
PowerShell: 
docker run --rm -it -v ${pwd}:/app -w /app lazypanda07/ubuntu_cxx20:24.04 g++ -std=c++17 -Wall -Wextra -Werror Main.cpp -o a.out
docker run --rm -it -v ${pwd}:/app -w /app lazypanda07/ubuntu_cxx20:24.04 bash -c "chmod +x a.out && ./a.out"
Zum Vergrößern anklicken....
Warum tut man sich diesen docker-bloat an ?
kali-hi schrieb:
Das liegt hier nicht an der Datenstruktur (std::vector), sondern an einer anderen Algorithmenkomplexität.
Zum Vergrößern anklicken....
Welche Anforderung erfüllt mein Code nicht?
Was habe ich falsch verstanden?
 
foofoobar schrieb:
Welche Anforderung erfüllt mein Code nicht?
Zum Vergrößern anklicken....
Kannst du vielleicht noch mal den Beitrag nennen ... verliere hier langsam dem Überblick.

foofoobar schrieb:
Was habe ich falsch verstanden?
Zum Vergrößern anklicken....
Ich weiß jetzt nicht, wo genau du dich darauf beziehst ... womöglich liegt gar kein Missverständnis vor, ich habe ja nicht behauptet, meine Variante sei schneller als std::sample, wenn du das meintest. Meine Variante ist langsamer, weil sich die Herangehensweisen bzw. Algorithmen unterscheiden - jedoch nicht die Datenstrukturen.
 
kali-hi schrieb:
Kannst du vielleicht noch mal den Beitrag nennen ... verliere hier langsam dem Überblick.
Zum Vergrößern anklicken....
Es sind doch deine Anforderungen, hast du die vergessen?
kali-hi schrieb:
Ich weiß jetzt nicht, wo genau du dich darauf beziehst ... womöglich liegt gar kein Missverständnis vor, ich habe ja nicht behauptet, meine Variante sei schneller als std::sample, wenn du das meintest. Meine Variante ist langsamer, weil sich die Herangehensweisen bzw. Algorithmen unterscheiden - jedoch nicht die Datenstrukturen.
Zum Vergrößern anklicken....
Alles mit realloc() und memcpy() ist teuer.
https://en.cppreference.com/w/cpp/container/vector.html
 
  • Gefällt mir
Reaktionen: Piktogramm
Btw. ... für unsere Bevölkerungsanzahl wären beide Varianten noch vertretbar (oder praktikabel) ... aber für die Chinesen (oder gar die gesamte Weltbevölkerung) würde es (also die Problemgröße) zu einem zeitlichen Problem werden - ich wäre da für einen Durchlauf schon bei towards 10 Minuten.
Ergänzung ()

foofoobar schrieb:
Alles mit realloc() und memcpy() ist teuer.
Zum Vergrößern anklicken....
Aber wo genau siehst du hier eine der beiden genannten Methoden?
 
kali-hi schrieb:
Btw. ... für unsere Bevölkerungsanzahl wären beide Varianten noch vertretbar (oder praktikabel) ... aber für die Chinesen (oder gar die gesamte Weltbevölkerung) würde es (also die Problemgröße) zu einem zeitlichen Problem werden - ich wäre da für einen Durchlauf schon bei towards 10 Minuten.
Zum Vergrößern anklicken....
Willst du die Weltbevölkerung dezimieren?
kali-hi schrieb:
Aber wo genau siehst du hier eine der beiden genannten Methoden?
Zum Vergrößern anklicken....
Schau dir die Implementierung von std::vector an, der Link aus #98 liefert ja schon die entsprechenden Hinweise. Die Bequemlichkeit davon ist eben nicht for free.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben

Willkommen auf ComputerBase!

Mit Werbung weiterlesen

Besuche ComputerBase wie gewohnt mit Werbung und Tracking. Die Zustimmung ist jederzeit widerrufbar.

Details im Privacy Center und in der Liste unserer Partner. Ein Widerruf ist möglich in der Datenschutzerklärung.

… oder ComputerBase Pro bestellen

Nutze ComputerBase ohne Werbebanner, Video-Ads und Werbetracking schon für 4 €/Monat oder 36 €/Jahr.

Mehr zu ComputerBase Pro

Bereits Pro-Nutzer? Hier anmelden.

Tracking: Wir und unsere 171 Partner verarbeiten personenbezogene Daten, indem wir mit auf Ihrem Gerät gespeicherten Informationen (z. B. eindeutige Kennungen in Cookies) ein Nutzungsprofil erstellen, um z. B. Anzeigen zu personalisieren. Verarbeitungszwecke: Genaue Standortdaten und Abfrage von Geräteeigenschaften zur Identifikation, Informationen auf einem Gerät speichern und/oder abrufen, Personalisierte Anzeigen und Inhalte, Anzeigen- und Inhaltsmessungen, Erkenntnisse über Zielgruppen und Produktentwicklungen.

Impressum Kontakt Datenschutz