betrag-maximum suchen ...

volkard

ich würde mich morgen an der suche nach der schnellsten funktion beteiligen. und hab eigentlich nur lust auf die schnelle funktion und nicht drauf, vorher ein langes prog zu bauen, was mißt.

RockNix

ach so, doch klar - hier ist meine kleine testroutine, die schnellere von beiden wird dann wieder in das "grosse" project zurückwandern.

#include <windows.h>
#include <stdio.h>
#include <math.h>

#define AVG_SIZE 1
float m_rightAvg[AVG_SIZE];
float m_leftAvg[AVG_SIZE];
UINT m_uAvgIndex = 0;

/////////////////////////////////////////////////////////////////////////////////////
int peak_abs( const float* dest, DWORD size)
{
    DWORD iSearchLength = size/2-2;
    float f = 0.0;

    m_leftAvg[ m_uAvgIndex] = fabs( dest[0]);

    // find left max
    for( x=2;  x<iSearchLength; x=x+2)
    {
        if( m_leftAvg[ m_uAvgIndex] < fabs(dest[x]))
            m_leftAvg[ m_uAvgIndex] = fabs(dest[x]);
    }

    m_rightAvg[ m_uAvgIndex] = fabs( dest[1]);

    // find right max
    for( x=3;  x<iSearchLength; x=x+2)
    {
        if( m_rightAvg[ m_uAvgIndex] < fabs(dest[x]))
            m_rightAvg[ m_uAvgIndex] = fabs(dest[x]);
    }

    m_uAvgIndex++;

    if(m_uAvgIndex==AVG_SIZE)
            m_uAvgIndex = 0;

    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////

int peak_if( const float* dest, DWORD size)
{
    DWORD iSearchLength = size/2-2;

    float* pTemp = new float[size];

    // make unsigned
    for( DWORD x=0; x<size; x++)
    {
        if( dest[x]<0.0)
            pTemp[x] = -dest[x];
        else
            pTemp[x] = dest[x];
    }

    m_leftAvg[ m_uAvgIndex] = pTemp[0];
    // find left max
    for( x=2;  x<iSearchLength; x=x+2)
    {
        if( m_leftAvg[ m_uAvgIndex]<pTemp[x])
            m_leftAvg[ m_uAvgIndex] = pTemp[x];
    }

    m_rightAvg[ m_uAvgIndex] = pTemp[1];
    // find right max
    for( x=3;  x<iSearchLength; x=x+2)
    {
        if( m_rightAvg[ m_uAvgIndex]<pTemp[x])
            m_rightAvg[ m_uAvgIndex]=pTemp[x];
    }

    m_uAvgIndex++;

    if(m_uAvgIndex==AVG_SIZE)
            m_uAvgIndex = 0;

    delete pTemp;

    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////

int main()
{
    int x=0;
    float data[4096];

    ZeroMemory( data, 4096*sizeof(float));

    data[2] = 1.0;
    data[3] = -1.0;

    for( x=0; x<100; x++)
        peak_if( data, 4096);

    for( x=0; x<100; x++)
        peak_abs( data, 4096);

    return 0;
}

so far ... rocknix ///

ps: vielleicht ist es sogar möglich, den rechten und linken kanal in einer schleife durchzuarbeiten, who knows ...

[ Dieser Beitrag wurde am 30.04.2003 um 16:50 Uhr von RockNix editiert. ]

volkard

ok, ich fang jetzt an.
aber dein test-prog geht nicht. ich bau doch ein eigenes. ich nehm bashars prototyp dazu und zufallszahlen drin. umbauen auf dein prob wirste dann selber müssen.

volkard

frage: wurde das array kurz vorher gebaut oder gelesen, daß es noch im cache liegt?

volkard

ich teste hiermit (MSVC60):

#include <iostream>
#include <cmath>
using namespace std;

float max(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

float test(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

void fill(float array[4096])
{
    srand(0);
    for(int i=0;i<4096;++i)
    {
        array[i]=rand()/10.0;
    }
}

typedef unsigned __int64 u64;

#pragma warning(push)
#pragma warning(disable:4035)//warning C4035: 'rdtsc' : Kein Rueckgabewert
inline u64 rdtsc()
{
    __asm rdtsc;
}
#pragma warning(pop)

int main()
{
    float array[4096];
    {
        fill(array);
        float m1=max(array);
        fill(array);
        float m2=test(array);
        if(m1!=m2)
        {
            cout<<"fehler!"<<endl;
            return 1;
        }
    }

    int left=1000;
    u64 mintime=-1;
    float sum=0;
    while(left)
    {
        --left;
        fill(array);
        u64 start=rdtsc();
        sum+=test(array);
        u64 stop=rdtsc();
        u64 time=stop-start;
        if(time<mintime)
        {
            mintime=time;
            left=1000;
            cout<<int(mintime)<<" takte"<<endl;
        }
    }
    cout<<sum<<endl;
    return 0;
}

zur zeit bei mir 123151 takte.

Mr. N

hier die portierte version:

#include <iostream>
#include <cmath>
using namespace std;

float max(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

float test(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

void fill(float array[4096])
{
    srand(0);
    for(int i=0;i<4096;++i)
    {
        array[i]=rand()/10.0;
    }
}

#ifdef _MSC_VER
typedef unsigned __int64 u64;

#pragma warning(push)
#pragma warning(disable:4035)//warning C4035: 'rdtsc' : Kein Rueckgabewert
inline u64 rdtsc()
{
    __asm rdtsc;
}
#pragma warning(pop)
#else // gcc
typedef unsigned long long u64;
#define _rdtsc(low) __asm__ __volatile__ ("rdtsc" : "=a" (low) : : "edx")
inline u64 rdtsc() {
    int a;
    _rdtsc(a);
    return a;
}
#endif

int main()
{
    float array[4096];
    {
        fill(array);
        float m1=max(array);
        fill(array);
        float m2=test(array);
        if(m1!=m2)
        {
            cout<<"fehler!"<<endl;
            return 1;
        }
    }

    int left=1000;
    u64 mintime=-1;
    float sum=0;
    while(left)
    {
        --left;
        fill(array);
        u64 start=rdtsc();
        sum+=test(array);
        u64 stop=rdtsc();
        u64 time=stop-start;
        if(time<mintime)
        {
            mintime=time;
            left=1000;
            cout<<int(mintime)<<" takte"<<endl;
        }
    }
    cout<<sum<<endl;
    return 0;
}

volkard

nix neues. nur bashars version kleiner.

float test(float array[4096]) 
{
    float result = fabs(array[0]);
    for (int i = 1; i < 4096; ++i) 
    {
        if (array[i] > result) 
        {
            result = array[i];
        }
    }
    return result;
}

hat bei mir 25% gespart.

volkard

meine meinung:
bashars lösung ist an sich optimal. ein paar prozemzt kannste mit den üblichen tricks rauskitzenl. nicht viel. mach variablen lokal! dene globalen variablen stören den optimierer.

und danach:
brauchte wirklich en maximalwerte aller samples? oder reicht einer, der echt hoch ist? kannst leicht bei 4096 samples nur jeden achten nehmen und keine sau hört den unterschied. es ist hochwahrscheinlich, daß du den maximalwert oder einen, der minstestens 98% davon hat, erwischt hast. noch sauberer und genausi billig (also auchg glatt faktor ist es, in 8-er-schriten voranzum*****ieren, und bei jeder neulernung des maxwertes (ist ja selten) mal schnell die 8 oder 15 nbachbarwerte anzugucken und evtl die als neuwert zu nehmen).

[ Dieser Beitrag wurde am 01.05.2003 um 03:37 Uhr von volkard editiert. ]

Mr. N

@volkard: ich verstehe irgendwie nicht, wieso die verbesserte variante überhaupt funktioniert. szenario:
array[0]=-1
=> result=1
array[1]=-2
=> result=1 bleibt wahr, soll es aber nicht

volkard

Original erstellt von Mr. N:
@volkard: ich verstehe irgendwie nicht, wieso die verbesserte variante überhaupt funktioniert. szenario:
array[0]=-1
=> result=1
array[1]=-2
=> result=1 bleibt wahr, soll es aber nicht

haha. hab doch in der tat das fabs vergessen.
mit fabs isses wieder genau so schnell wie bashars variante.

[ Dieser Beitrag wurde am 01.05.2003 um 14:20 Uhr von volkard editiert. ]