Twoim zadaniem jest rozwiązanie problemu najdłuższej wspólnej sekwencji dla n ciągów o długości 1000.

Prawidłowe rozwiązanie problemu LCS przez dwa lub więcej ciągów S ₁ , S ... _n jest dowolny ciąg T maksymalnej długości tak, że znaki T pojawiają się we wszystkich S _I , w tej samej kolejności jak w T .

Zauważmy, że T nie musi być sub ciąg od S _í .

Ten problem rozwiązaliśmy już przy użyciu jak najmniejszej ilości kodu . Tym razem rozmiar nie ma znaczenia.

Przykład

Ciągi znaków axbyczi xaybzcmają 8 wspólnych podciągów o długości 3:

abc abz ayc ayz xbc xbz xyc xyz

Każde z nich stanowiłoby prawidłowe rozwiązanie problemu LCS.

Detale

Napisz pełny program, który rozwiąże problem LCS, jak wyjaśniono powyżej, przestrzegając następujących zasad:

• Dane wejściowe będą składać się z dwóch lub więcej ciągów o długości 1000, składających się ze znaków ASCII z punktami kodowymi od 0x30 do 0x3F.

• Musisz odczytać dane wejściowe ze STDIN.

  Masz dwie możliwości wyboru formatu wejściowego:

  • Po każdym łańcuchu (w tym ostatnim) znajduje się znak linii.

  • Sznurki są połączone łańcuchem, bez separatora i bez podawania linii.

• Liczba ciągów znaków zostanie przekazana do programu jako parametr wiersza polecenia.

• Musisz zapisać dane wyjściowe, tj. Dowolne z poprawnych rozwiązań LCS, STDOUT, a następnie jeden wiersz.

• Twój wybrany język musi mieć darmowy (jak w piwie) kompilator / tłumacz dla mojego systemu operacyjnego (Fedora 21).

• Jeśli potrzebujesz flag kompilatora lub konkretnego interpretera, podaj to w swoim poście.

Punktacja

Uruchomię kod z ciągami 2, 3 itd., Dopóki wydrukowanie prawidłowego rozwiązania nie zajmie więcej niż 120 sekund. Oznacza to, że masz 120 sekund na każdą wartość n .

Najwyższą liczbą ciągów, dla których kod zakończył się w czasie, jest twój wynik.

W przypadku remisu n , zgłoszenie, które rozwiązało problem n strun w jak najkrótszym czasie, zostanie ogłoszone zwycięzcą.

Wszystkie zgłoszenia będą synchronizowane na moim komputerze (Intel Core i7-3770, 16 GiB RAM, bez wymiany).

Gdy n struny (n-1) ^p testu zostanie wygenerowany przez wywołanie rand n(i odpędzenie karetki, jeśli wymagane), w którym randokreśla się, jak następuje:

rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

Klucz znajduje się 0w powyższym kodzie, ale zastrzegam sobie prawo do zmiany go na nieujawnioną wartość, jeśli podejrzewam, że ktoś (częściowo) zakodował wynik.

C, n = 3 w ~ 7 sekund

Algorytm

Algorytm jest bezpośrednim uogólnieniem standardowego rozwiązania programowania dynamicznego na nsekwencje. Dla 2 łańcuchów Ai Bstandardowa powtarzalność wygląda następująco:

L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise

Przez 3 strun A, B, Cużywam:

L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise

Kod implementuje tę logikę dla dowolnych wartości n.

Wydajność

Złożoność mojego kodu to O (s ^ n), przy sdługości łańcuchów. Na podstawie tego, co znalazłem, wygląda na to, że problem jest NP-zupełny. Tak więc, chociaż opublikowany algorytm jest bardzo nieefektywny dla większych wartości n, może nie być w stanie zrobić znacznie lepszej wydajności . Jedyne, co widziałem, to niektóre podejścia, które poprawiają wydajność małych alfabetów. Ponieważ alfabet jest tutaj umiarkowanie mały (16), może to prowadzić do poprawy. Nadal przewiduję, że nikt nie znajdzie uzasadnionego rozwiązania, które przekroczyłoby n = 42 minuty i n = 4wygląda już ambitnie.

Zmniejszyłem użycie pamięci w początkowej implementacji, aby mogła obsłużyć n = 4dany czas. Ale wytworzył tylko długość sekwencji, a nie samą sekwencję. Sprawdź historię zmian tego wpisu, aby zobaczyć ten kod.

Kod

Ponieważ pętle nad macierzami n-wymiarowymi wymagają więcej logiki niż pętle stałe, używam stałej pętli dla najniższego wymiaru i używam tylko ogólnej logiki pętli dla pozostałych wymiarów.

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

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq > N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 < nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 < lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val > maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq < nSeq && posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx >= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val > maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}

Instrukcje do biegania

Biegać:

• Zapisz kod w pliku, np lcs.c.

• Kompiluj z opcjami wysokiej optymalizacji. Użyłem:

  clang -O3 lcs.c
  

  W systemie Linux spróbowałbym:

  gcc -Ofast lcs.c
  

• Uruchom z 2 do 4 sekwencji podanymi jako argumenty wiersza poleceń:

  ./a.out axbycz xaybzc
  

  W razie potrzeby pojedynczo wpisz argumenty wiersza poleceń, ponieważ alfabet użyty w przykładach zawiera znaki specjalne powłoki.

Wyniki

test2.shi test3.shsą sekwencjami testowymi Dennisa. Nie znam poprawnych wyników, ale wyniki wydają się co najmniej wiarygodne.

$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh 
score: 391
16638018802020>3??3232270178;47240;24331395?<=;99=?;178675;866002==23?87?>978891>=9<6<9381992>>7030829?255>6804:=3>:;60<9384=081;0:?66=51?0;5090724<85?>>:2>7>3175?::<9199;5=0:494<5<:7100?=95<91>1887>33>67710==;48<<327::>?78>77<6:2:02:<7=5?:;>97<993;57=<<=:2=9:8=118563808=962473<::8<816<464<1==925<:5:22?>3;65=>=;27?7:5>==3=4>>5>:107:20575347>=48;<7971<<245<??219=3991=<96<??735698;62?<98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh 
score: 269
662:2=2::=6;738395=7:=179=96662649<<;?82?=668;2?603<74:6;2=04=>6;=6>=121>1>;3=22=3=3;=3344>0;5=7>>7:75238;559133;;392<69=<778>3?593?=>9799<1>79827??6145?7<>?389?8<;;133=505>2703>02?323>;693995:=0;;;064>62<0=<97536342603>;?92034<?7:=;2?054310176?=98;5437=;13898748==<<?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s

Ta odpowiedź jest obecnie zepsuta z powodu błędu. Naprawianie wkrótce ...

C, 2 struny w ~ 35 sekund

Jest to w dużej mierze praca w toku (o czym świadczy okropny bałagan), ale mam nadzieję, że dostarczy dobrych odpowiedzi!

Kod:

#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "time.h"

/* For the versatility */
#define MIN_CODEPOINT 0x30
#define MAX_CODEPOINT 0x3F
#define NUM_CODEPOINT (MAX_CODEPOINT - MIN_CODEPOINT + 1)
#define CTOI(c) (c - MIN_CODEPOINT)

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int LCS(char** str, int num);
int getshared(char** str, int num);
int strcount(char* str, char c);

int main(int argc, char** argv) {
    char** str = NULL;
    int num = 0;
    int need_free = 0;
    if (argc > 1) {
        str = &argv[1];
        num = argc - 1;
    }
    else {
        scanf(" %d", &num);
        str = malloc(sizeof(char*) * num);
        if (!str) {
            printf("Allocation error!\n");
            return 1;
        }

        int i;
        for (i = 0; i < num; i++) {
            /* No string will exceed 1000 characters */
            str[i] = malloc(1001);
            if (!str[i]) {
                printf("Allocation error!\n");
                return 1;
            }

            scanf(" %1000s", str[i]);

            str[i][1000] = '\0';
        }

        need_free = 1;
    }

    clock_t start = clock();

    /* The call to LCS */
    int size = LCS(str, num);

    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("Size: %d\n", size);
    printf("Elapsed time on LCS call: %lf s\n", dt);

    if (need_free) {
        int i;
        for (i = 0; i < num; i++) {
            free(str[i]);
        }
        free(str);
    }

    return 0;
}

/* Some terribly ugly global variables... */
int depth, maximum, mapsize, lenmap[999999][2];
char* (strmap[999999][20]);
char outputstr[1000];

/* Solves the LCS problem on num strings str of lengths len */
int LCS(char** str, int num) {
    /* Counting variables */
    int i, j;

    if (depth + getshared(str, num) <= maximum) {
        return 0;
    }

    char* replace[num];
    char match;
    char best_match = 0;
    int earliest_set = 0;
    int earliest[num];
    int all_late;
    int all_early;
    int future;
    int best_future = 0;
    int need_future = 1;

    for (j = 0; j < mapsize; j++) {
        for (i = 0; i < num; i++)
            if (str[i] != strmap[j][i])
                break;
        if (i == num) {
            best_match = lenmap[j][0];
            best_future = lenmap[j][1];
            need_future = 0;
            if (best_future + depth < maximum || !best_match)
                goto J;
            else {
                match = best_match;
                goto K;
            }
        }
    }

    for (match = MIN_CODEPOINT; need_future && match <= MAX_CODEPOINT; match++) {

    K:
        future = 1;
        all_late = earliest_set;
        all_early = 1;
        for (i = 0; i < num; replace[i++]++) {
            replace[i] = strchr(str[i], match);
            if (!replace[i]) {
                future = 0;
                break;
            }

            if (all_early && earliest_set && replace[i] - str[i] > earliest[i])
                all_early = 0;
            if (all_late && replace[i] - str[i] < earliest[i])
                all_late = 0;
        }
        if (all_late) {
            future = 0;
        }

    I:
        if (future) {
            if (all_early || !earliest_set) {
                for (i = 0; i < num; i++) {
                    earliest[i] = (int)(replace[i] - str[i]);
                }
            }

            /* The recursive bit */
            depth++;
            future += LCS(replace, num);
            depth--;

            best_future = future > best_future ? (best_match = match), future : best_future;
        }
    }

    if (need_future) {
        for (i = 0; i < num; i++)
            strmap[mapsize][i] = str[i];
        lenmap[mapsize][0] = best_match;
        lenmap[mapsize++][1] = best_future;
    }

J:
    if (depth + best_future >= maximum) {
        maximum = depth + best_future;
        outputstr[depth] = best_match;
    }

    if (!depth) {
        mapsize = 0;
        maximum = 0;
        puts(outputstr);
    }

    return best_future;
}

/* Return the number of characters total (not necessarily in order) that the strings all share */
int getshared(char** str, int num) {
    int c, i, tot = 0, min;
    for (c = MIN_CODEPOINT; c <= MAX_CODEPOINT; c++) {
        min = strcount(str[0], c);
        for (i = 1; i < num; i++) {
            int count = strcount(str[i], c);
            if (count < min) {
                min = count;
            }
        }
        tot += min;
    }

    return tot;
}

/* Count the number of occurrences of c in str */
int strcount(char* str, char c) {
    int tot = 0;
    while ((str = strchr(str, c))) {
        str++, tot++;
    }
    return tot;
}

Odpowiednią funkcją, która wykonuje wszystkie obliczenia LCS, jest funkcja LCS. Powyższy kod wykona własne wywołanie tej funkcji.

Zapisz jako main.ci skompiluj za pomocą:gcc -Ofast main.c -o FLCS

Kod może być uruchamiany z argumentami wiersza poleceń lub przez stdin. Podczas używania stdin oczekuje szeregu ciągów, a po nich samych ciągów.

~ Me$ ./FLCS "12345" "23456"
2345
Size: 4
Elapsed time on LCS call: 0.000056 s

Lub:

~ Me$ ./FLCS
6 
2341582491248123139182371298371239813
2348273123412983476192387461293472793
1234123948719873491234120348723412349
1234129388234888234812834881423412373
1111111112341234128469128377293477377
1234691237419274737912387476371777273
1241231212323
Size: 13
Elapsed time on LCS call: 0.001594 s

Na komputerze Mac OS X z procesorem Intel Core i7 1,7 GHz i testowym etui Dennis otrzymujemy następujące dane wyjściowe dla 2 ciągów:

16638018800200>3??32322701784=4240;24331395?<;=99=?;178675;866002==23?87?>978891>=9<66=381992>>7030829?25265804:=3>:;60<9384=081;08?66=51?0;509072488>2>924>>>3175?::<9199;330:494<51:>748571?153994<45<??20>=3991=<962508?7<2382?489
Size: 386
Elapsed time on LCS call: 33.245087 s

Podejście to jest bardzo podobne do mojego podejścia do wcześniejszego wyzwania tutaj . Oprócz poprzedniej optymalizacji sprawdzamy teraz całkowitą liczbę wspólnych znaków między łańcuchami przy każdej rekurencji i wychodzimy wcześniej, jeśli nie ma sposobu na uzyskanie dłuższego podciągu niż to, co już istnieje.

Na razie radzi sobie dobrze z 2 ciągami, ale więcej się zawiesza. Więcej ulepszeń i lepsze wyjaśnienie już wkrótce!