Lokal minima

Jeg forstår ikke spørgsmålet.

At finde mindste element blandt elementerne 77000 til 77010 bør
ikke tage lang tid.

Og vi har følge array

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,-1,1,1,1,1,1

Jeg ønsker at at vide at der på plads 16 og 27 er et lokalt minima

(O:

Det jeg mener med et område på 10 element er følgende.

2,2,2,2,1,2,2,0,2,2,2,2,2,2
Her vil der være et lokalt minima hvis der ses på et område med størrelse 10 og to minimA hvis der ses på et område med størrelse 2

Så er du vel nødt til at løbe arrayet (eller en relevant del af det)
igennem og finde alle elementer som er mindre end både det foregående
og det næste element.

Det bør ikke tage lang tid.

Og jeg kan ikke se nogle alternativer.

OK nu ser jeg jeg pointen.

Du har et stort array med N elementer og du vil finde elementer som
er minima indenfor +/- M elementer hvor M er relativt lille.

Det jeg gør nu er at undersøge bare et at de ti omkringlæggende elementer er mindre en det element jeg står med nu. Dette gør jeg for alle mine elementer.  Dette betyder at jeg i gennemsnit laver ca. 4*N sammenligninger.
Hvilket formentligt ikke er optimalt.

jep til "OK nu ser jeg jeg pointen.

Du har et stort array med N elementer og du vil finde elementer som
er minima indenfor +/- M elementer hvor M er relativt lille."

Vil det være et minima hvis der er 10 ens tal ?

Nej.

Med mindre du har en god hurtig løsning hvor dette antages

Så må det gælde at nogle regler:

hvis a[i] ikke er et minima så må a[i+1]=a[i] være nok til at afvise
at a[i+1] er et minima og det må kunne gøre at du kan nøjes med en sammenligning
i de fleste tilfælde

ja dette er korrekt. Jeg arbejder desværre med billeder med en del variation i. Dvs at der meget sjældent  optræder ens værdier.

Det må også gælde at hvis a[i] er minima og der ikke er nogle
a[j] j=i+1..i+5 hvor a[j]=a[i] så kan man godt hoppe fra i til
i+6 i testen.

Ja Korrekt.

Den behøver faktisk ikke engang være minima.

Når du har behandlet element i kan du generelt gå til enten i+6 eller
det i < j < i+6 hvor a[j] <= a[i].

Måske kan du nøjes med 1 sammenligning for en del increments.

Men jeg tror ikke at det er meget du kan vinde.

Det vigtigste er at der er nok RAM til at hele arrayet kan
ligge i memeory.

Ja bestemt. Det kan det også.

Jeg sidder lige og leger med noget test kode.

Stay tuned.

Lyder godt (O:

#include <stdio.h>
#include <stdlib.h>

#define N 10000000

int standard(int *a)
{
    int i, j, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        for (j = (i - 5); j <= (i + 5); j++)
        {
            if (a[j] < a[i])
            {
                minima = 0;
                break;
            }
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int unrolled(int *a)
{
    int i, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        if (a[i - 5] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 5] < a[i])
        {
            minima = 0;
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int main()
{
    int *a, i, n1, n2, t1a, t1b, t2a, t2b;
    a = (int *)malloc(N*sizeof(int));
    srand(12345);
    for (i = 0; i < N; i++) {
        a[i] = rand() % 1000;
    }
    t1a = clock();
    n1 = standard(a);
    t1b = clock();
    printf("%d %d\n",n1,(t1b - t1a));
    t2a = clock();
    n2 = unrolled(a);
    t2b = clock();
    printf("%d %d\n",n2,(t2b - t2a));
    return 0;
}

C:\>gcc -O6 minima.c -o minima.exe

C:\>minima
914298 234
914298 141

Den unrolled version er noget hurtigere.

Ja ok, jeg prøver lige at smide den ind i min kode og se om der giver noget. Jeg vender tilbage I overmorgen. Eller i morgen hvis jeg kan komme til en mail

#include <stdio.h>
#include <stdlib.h>

#define N 10000000

int standard(int *a)
{
    int i, j, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        for (j = (i - 5); j <= (i + 5); j++)
        {
            if (a[j] < a[i])
            {
                minima = 0;
                break;
            }
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int unrolled(int *a)
{
    int i, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        if (a[i - 5] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 5] < a[i])
        {
            minima = 0;
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int smart(int *a)
{
    int i, j, res, minima;
    res = 0;
    i = 5;
    while (i < (N - 5))
    {
        minima = 1;
        for (j = (i - 5); j <= (i + 5); j++)
        {
            if (a[j] < a[i])
            {
                minima = 0;
                break;
            }
        }
        if (minima)
        {
            res++;
        }
        j = i + 1;
        while((j < (i + 5)) && (a[j] > a[i])) j++;
        i = j;
    }
    return res;
}

int smartunrolled(int *a)
{
    int i, j, res, minima;
    res = 0;
    i = 5;
    while (i < (N - 5))
    {
        minima = 1;
        if (a[i - 5] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 5] < a[i])
        {
            minima = 0;
        }
        if (minima)
        {
            res++;
        }
        j = i + 1;
        while((j < (i + 5)) && (a[j] > a[i])) j++;
        i = j;
    }
    return res;
}

int main()
{
    int *a, i, n1, n2, n3, n4;
    int t1a, t1b, t2a, t2b, t3a, t3b, t4a, t4b;
    a = (int *)malloc(N*sizeof(int));
    srand(12345);
    for (i = 0; i < N; i++) {
        a[i] = rand() % 1000;
    }
    for (i = 0; i < 3; i++)
    {
        t1a = clock();
        n1 = standard(a);
        t1b = clock();
        printf("standard %d %d\n",n1,(t1b - t1a));
        t2a = clock();
        n2 = unrolled(a);
        t2b = clock();
        printf("unrolled %d %d\n",n2,(t2b - t2a));
        t3a = clock();
        n3 = smart(a);
        t3b = clock();
        printf("smart %d %d\n",n3,(t3b - t3a));
        t4a = clock();
        n4 = smartunrolled(a);
        t4b = clock();
        printf("smart unrolled %d %d\n",n4,(t4b - t4a));
    }
    return 0;
}

C:\>gcc -O6 minima.c -o minima.exe

C:\>minima
standard 914298 234
unrolled 914298 141
smart 914298 125
smart unrolled 914298 109
standard 914298 250
unrolled 914298 125
smart 914298 125
smart unrolled 914298 125
standard 914298 219
unrolled 914298 141
smart 914298 125
smart unrolled 914298 109

Det ser ud til at "smart unrolled" teknikken er hurtigst.

Men muligvis kan den forbedres yderligere.

Bemærk at jeg er sprunget meget nemt over "start og slut problemerne".

Og så vil jeg tillade mig at ligge et svar.

ok, her er en ide. Jeg ved ikke om det vil være hurtigt.
Man løber sit array igennem og indsætter alle lokale minima hvor følgende gælder i et nyt array. a[i-1]>a[i]<a[i+1] hvis dette er Sandt  => I[n]=i
Herefter løbes det meget minde I[] igennem og hvis a[I[n-1]]>a[I[n]]<a[I[n+1]] og I[n]-I[n-1]>5 && I[n]-I[n+1]>5 må I[n] være et lokalt minima

Ja, ok. Det var nu ikke helt det jeg søgte. Men ok. Jeg prøver lige det ovenstående

Du skal huske at tage højde for:

4 1 4 3 4 2 4 3 4 1 4

2 er mindre end 3 men ikke mindre end 1

Men derfor kan teknikken godt være en forbedring.

Det ser nu ikke for lovende ud.

#include <stdio.h>
#include <stdlib.h>

#define N 10000000

int standard(int *a)
{
    int i, j, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        for (j = (i - 5); j <= (i + 5); j++)
        {
            if (a[j] < a[i])
            {
                minima = 0;
                break;
            }
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int unrolled(int *a)
{
    int i, res, minima;
    res = 0;
    for (i = 5; i < (N - 5); i++)
    {
        minima = 1;
        if (a[i - 5] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 5] < a[i])
        {
            minima = 0;
        }
        if (minima)
        {
            res++;
        }
    }
    return res;
}

int smart(int *a)
{
    int i, j, res, minima;
    res = 0;
    i = 5;
    while (i < (N - 5))
    {
        minima = 1;
        for (j = (i - 5); j <= (i + 5); j++)
        {
            if (a[j] < a[i])
            {
                minima = 0;
                break;
            }
        }
        if (minima)
        {
            res++;
        }
        j = i + 1;
        while((j < (i + 5)) && (a[j] > a[i])) j++;
        i = j;
    }
    return res;
}

int smartunrolled(int *a)
{
    int i, j, res, minima;
    res = 0;
    i = 5;
    while (i < (N - 5))
    {
        minima = 1;
        if (a[i - 5] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i - 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 1] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 2] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 3] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 4] < a[i])
        {
            minima = 0;
        }
        else if (a[i + 5] < a[i])
        {
            minima = 0;
        }
        if (minima)
        {
            res++;
        }
        j = i + 1;
        while((j < (i + 5)) && (a[j] > a[i])) j++;
        i = j;
    }
    return res;
}

int doublearray(int *a)
{
    int *a2,n,i,res;
    a2 = (int *)malloc(N/2*sizeof(int));
    n = 0;
    for (i = 1; i < (N - 1); i++)
    {
        if((a[i - 1] > a[i]) && (a[i] < a[i + 1]))
        {
            a2[n] = i;
            n++;
        }
    }
    res = 0;
    for (i = 1; i < (n - 1); i++)
    {
        if(((a2[i-1] < (a2[i] - 5)) || (a[a2[i]] < a[a2[i-1]])) && (((a2[i] + 5) < a2[i+1]) || (a[a2[i]] < a[a2[i+1]])))
        {
            res++;
        }
    }
    return res;
}

int main()
{
    int *a, i, n1, n2, n3, n4, n5;
    int t1a, t1b, t2a, t2b, t3a, t3b, t4a, t4b, t5a, t5b;
    a = (int *)malloc(N*sizeof(int));
    srand(12345);
    for (i = 0; i < N; i++) {
        a[i] = rand() % 1000;
    }
    for (i = 0; i < 3; i++)
    {
        t1a = clock();
        n1 = standard(a);
        t1b = clock();
        printf("standard %d %d\n",n1,(t1b - t1a));
        t2a = clock();
        n2 = unrolled(a);
        t2b = clock();
        printf("unrolled %d %d\n",n2,(t2b - t2a));
        t3a = clock();
        n3 = smart(a);
        t3b = clock();
        printf("smart %d %d\n",n3,(t3b - t3a));
        t4a = clock();
        n4 = smartunrolled(a);
        t4b = clock();
        printf("smart unrolled %d %d\n",n4,(t4b - t4a));
        t5a = clock();
        n5 = doublearray(a);
        t5b = clock();
        printf("double array %d %d\n",n5,(t5b - t5a));
    }
    return 0;
}

C:\>minima
standard 914298 234
unrolled 914298 141
smart 914298 125
smart unrolled 914298 109
double array 1134563 188
standard 914298 218
unrolled 914298 141
smart 914298 109
smart unrolled 914298 125
double array 1134563 188
standard 914298 234
unrolled 914298 125
smart 914298 125
smart unrolled 914298 125
double array 1134563 188

Fejlen i antal må skyldes det jeg har beskrever.

Og selv uden test for det så er den langsommere.