3. pruefen, ob alle werte 'wert' haben

pruefen, ob alle werte 'wert' haben

  • ?

    Einfachste Möglichkeit wohl

    #include <valarray>

// ...

if(std::valarray<bool>(array, &array[arraylen]) == true) {
  // alles true
}

    Ist grad ungetestet, aber ich denke, dass es so gehen müsste. Die Performance hängt dabei natürlich von der Qualität der valarray-Implementierung ab, und liegt im Zweifel wegen des Kopierens im Konstruktor unter der des Vergleichens des Arrays von Hand, aber wenns dir um die Notation geht...

    Ne andere Möglichkeit wäre

    #include <set>

// ...

std::set<bool> tmp_set(array, &array[arraylen]);
if(tmp_set.find(false) == tmp_set.end()) {
  // alles true
}

    performancetechnisch gilt da aber das gleiche wie für valarray.

    0
  • V

    smasher1985 schrieb:

    Nehmt mal bitte Stellung 😉

    ok. ich hab mit MinGW compiliert.

    Messen ist sauschwer. Aber ich dachte mir schon, daß da was nicht stimmen kann.
    Ich messe dies:

    #include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;//garantier, daß nix wegoptimiert wird
}

int main() 
{ 
	int const NUM=1000000;
    bool array[100];
    for (int j=0; j<100; ++j) 
        array[j] = (rdtsc()!=0); //garantier, daß der compiler nachher nix wegoptimiert
	u64 time;

    /// CAMPERS METHODE 1 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            bool allTrue; 
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; ); 
            if (allTrue) foo(); 
        } 

    } 
    time+=rdtsc();
    cout <<"Camper1 "<<time<< endl; 

    /// CAMPERS METHODE 2 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
			int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
            for (; bool( array[ i ] ) && ++i < 100; ); 
            if (i >= 100) { 
                foo(); 
            } 
        }
    } 
    time+=rdtsc();
    cout <<"Camper2 "<<time<< endl; 

    /// VOLKARDS METHODE (leicht verändert) 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            if(areAllTrue(array,100)) {    
                foo(); 
            } 
        } 
    } 
    time+=rdtsc();
    cout <<"Volkard "<<time<< endl; 

	cout<<'('<<g<<')'<<endl;
}

    ausgabe:
    Camper1 461972848
    Camper2 646757321
    Volkard 494893179
    (3000000)

    jo, so sind deine messungen.
    jetzt lege ich meinen code mal an den anfang, wo unser prozess noch
    hohe priorität hat und nicht als langrechner abgestuft wurde.

    #include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;
}

int main() 
{ 
	int const NUM=1000000;
    bool array[100];
    for (int j=0; j<100; ++j) 
        array[j] = (rdtsc()!=0); 
	u64 time;

    /// VOLKARDS METHODE (leicht verändert) 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            if(areAllTrue(array,100)) {    
                foo(); 
            } 
        } 
    } 
    time+=rdtsc();
    cout <<"Volkard "<<time<< endl; 

    /// CAMPERS METHODE 1 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            bool allTrue; 
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; ); 
            if (allTrue) foo(); 
        } 

    } 
    time+=rdtsc();
    cout <<"Camper1 "<<time<< endl; 

    /// CAMPERS METHODE 2 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
			int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
            for (; bool( array[ i ] ) && ++i < 100; ); 
            if (i >= 100) { 
                foo(); 
            } 
        }
    } 
    time+=rdtsc();
    cout <<"Camper2 "<<time<< endl; 

	cout<<'('<<g<<')'<<endl;
}

    ausgabe:
    Volkard 397708167
    Camper1 423422744
    Camper2 549747252
    (3000000)

    merke: nur durch erhöhen der anzahl der mesungen erreicht man nicht unbeding eine steigerung
    der genauigkeit.

    am genauesten wird generell gemessen, wenn man von sehr vielen messungen den kleinsten messwert nimmt. denn schneller als ohne störenden fremden einfluss gehts nicht. aber störende einflüsse können auf modernen maschinen so mannigfaltig viele sein, daß man sie beim messen einfach immer mal drin hat.

    das führt direkt zu diesem code (bin auf dieses messverfahren sehr stolz):

    #include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;
}

void volkard(bool array[10000]){
	if(areAllTrue(array,10000))
		foo();
}

void camper1(bool array[10000]){
	bool allTrue; 
	for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 10000; ); 
	if (allTrue) foo(); 
}

void camper2(bool array[10000]){
	int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
	for (; bool( array[ i ] ) && ++i < 10000; ); 
	if (i >= 10000) { 
		foo(); 
	} 
}

u64 measure(void(*f)(bool[10000])){
    bool array[10000];
    for (int j=0; j<10000; ++j) 
        array[j] = (rdtsc()!=0); 

	u64 minTime=u64(-1);
	int left=10000;
	while(left--){
		u64 time=-rdtsc();
		(*f)(array);
		time+=rdtsc();
		if(time<minTime){
			minTime=time;
			left=10000;
		}
    } 
	return minTime;
}

int main() 
{ 
    cout <<"Volkard "<<measure(&volkard)<< endl; 
    cout <<"camper1 "<<measure(&camper1)<< endl; 
    cout <<"camper2 "<<measure(&camper2)<< endl; 
	cout<<'('<<g<<')'<<endl;
}

    ausgabe:
    Volkard 26404
    camper1 26404
    camper2 26404
    (30008)

    dann bin ich ins netz gegangen und hab noch ein paarmal gemessen:
    Volkard 26389
    camper1 26394
    camper2 26394
    (39654)

    Volkard 26394
    camper1 26394
    camper2 26389
    (48521)

    Volkard 26389
    camper1 26394
    camper2 26389
    (63805)

    wir stellen fest: ich kann sachen mit so grossen laufzeiten nicht auf den takt genau messen. aber den fehler und 1% riegt man schon.
    und im rahmen der messgenauigkeit sind alle drei lösungen identisch.

    0
  • C
    Mod

    interessante lösung - wenns recht ist, benutz ich die in zukunft auch 🙂
    das ganze nochmal mit vc++7.1 (mal zusätzlich mit der assemblervariante - die ist allerdings nicht ganz optimal)
    Volkard 30112
    VolkardAsm 6636
    camper1 30112
    camper2 30112
    (30006)

    nichts besonders ... ganz im gegensatz zu icl 8.1
    Volkard 30108
    VolkardAsm 6632
    camper1 20088
    camper2 16788
    (37531)
    soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

    edit: es muss übrigens #ifdef _MSC_VER heissen

    0
  • G

    volkard schrieb:

    alleTrue &&= array[i];

    Sollte das ein Gag sein? 🙂

    0
  • V

    camper schrieb:

    nichts besonders ... ganz im gegensatz zu icl 8.1
    Volkard 30108
    VolkardAsm 6632
    camper1 20088
    camper2 16788
    (37531)
    soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

    ka. mag dem argument aber nicht folgen. warum sollten schleifenabbrüche was anderes als if sein? bringt umsortieren wieder was? dann wär's fiesmal schlechtes function alignment.

    den faktor 5 für die asm-lösung hab ich mit c++ auch.

    inline bool areAllTrueOpt(bool* array,int arrayend){
	while(arrayend%8)
		if(array[--arrayend]) return false;
	while(reinterpret_cast<size_t>(array)&3)
		if(!*array++) return false;
	for(int i=0;i<arrayend/8;++i){
		if(((long long*)array)[i++]!=0x0101010101010101ULL) return false;
	}
	return true;
}

    be mir bringen dir 8-er-schritte aber keinen hauch mehr als 4-er-schritte. hab mal 8-er genommen, falls du nen 64-bittigen prozessor hast.

    0
  • C
    Mod

    volkard schrieb:

    camper schrieb:

    nichts besonders ... ganz im gegensatz zu icl 8.1
    Volkard 30108
    VolkardAsm 6632
    camper1 20088
    camper2 16788
    (37531)
    soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

    ka. mag dem argument aber nicht folgen. warum sollten schleifenabbrüche was anderes als if sein? bringt umsortieren wieder was? dann wär's fiesmal schlechtes function alignment.

    den faktor 5 für die asm-lösung hab ich mit c++ auch.

    inline bool areAllTrueOpt(bool* array,int arrayend){
	while(arrayend%8)
		if(array[--arrayend]) return false;
	while(reinterpret_cast<size_t>(array)&3)
		if(!*array++) return false;
	for(int i=0;i<arrayend/8;++i){
		if(((long long*)array)[i++]!=0x0101010101010101ULL) return false;
	}
	return true;
}

    be mir bringen dir 8-er-schritte aber keinen hauch mehr als 4-er-schritte. hab mal 8-er genommen, falls du nen 64-bittigen prozessor hast.

    so gehts nat. auch. die 8er schritte waren den mmx befehlen geschuldet, die ja gleich 8byte mit einem mal aufnehmen. sonst sind 4er schritte im allgemeinen eusreichend. die sache mit der vektorisierung - ich hab nat. zuerst den assemblertext angeschaut, bevor ich das behauptet habe. sicherlich ist das if dem schleifenabbruch in der schleifenbedingung im grunde equivalent. allerdings für den compiler anhand von formalen kriteren kaum zu erkennen. möglich das sich das in späteren versionen ändert.

    0
  • S

    Das schöne ist: nur volkards Version lässt sich so optimieren, da es eben eine Funktion ist 🙂 Bei campers Variante müsste man die Stellen im Code suchen und dort Copy&Pasten...

    0
  • ?

    Je nach Compiler könnte das hier ne portablere Variante von Volkards MEthode sein:

    #include <cstring>

using namespace std;

bool all_are_true(bool *arr, int arraylen) {
  static bool true_arr[8] = { true, true, true, true,
                                       true, true, true, true };

  if(memcmp(arr, true_arr, arraylen % 8))
    return false;
  arr += arraylen % 8;
  for(int i = 0; i < arraylen / 8; ++i) {
    if(memcmp(arr, true_arr, 8))
      return false;
    arr += 8;
  }
  return true;
}

    Der gcc zum Beispiel implementiert die Funktion intrinsic, als dürfte da kein Geschwindigkeitsverlust entstehen. Glaube ich...

    0
Anmelden zum Antworten