Najszybsza najdłuższa wspólna wyszukiwarka sekwencji

11

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 1 , 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.

Dennis
źródło
Czy możemy rzucać wyjątki?
HyperNeutrino,
@JamesSmith Dopóki dane wyjściowe są prawidłowe, na pewno.
Dennis
Skoro czytam z buforowanym czytnikiem, czy mogę wyrzucić ioexception public static void main(...)?
HyperNeutrino,
@JamesSmith Naprawdę nie znam Java, więc nie wiem, co to jest, ale nie martw się o wyjątki.
Dennis,
4
@JamesSmith Ponieważ długość kodu nie ma znaczenia dla tego wyzwania, nie możesz po prostu złapać wyjątków?
Reto Koradi,

Odpowiedzi:

5

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
Reto Koradi
źródło
Przepraszamy, jeśli nie było to jasne, ale musisz wydrukować LCS, a nie tylko jego długość.
Dennis
@Dennis Rozumiem. Niektóre moje optymalizacje poszły na marne. Będę musiał wrócić do wersji, która przechowuje pełną macierz, aby móc zrekonstruować ciąg. To nie będzie w stanie działać dla n = 4, ale powinno nadal kończyć się poniżej 10 sekund dla n = 3. Myślę, że miałem około 6-7 sekund, kiedy jeszcze miałem pełną matrycę.
Reto Koradi
Jeszcze raz przepraszam. Pytanie nie było bardzo jasne na ten temat ... Kiedy opublikujesz swój wynik, będę mógł go porównać do BrainSteel. Długość zgłaszana przez program przekracza długość jego wyniku o 5 dla n = 2. Nawiasem mówiąc, musiałem zdefiniować N_MAXjako makro i dodać flagę kompilatora, -std=c99aby skompilować kod za pomocą GCC.
Dennis
@Dennis Nie ma problemu. Stwierdzono, że rozwiązanie „jest łańcuchem”, więc powinno to być wystarczająco jasne. Prawie wyłącznie używam C ++, więc nigdy nie jestem pewien, co jest dozwolone w C. Ten kod zaczął się jako C ++, ale kiedy zdałem sobie sprawę, że tak naprawdę nie używam żadnych funkcji C ++, zmieniłem go na C. clang na moim Macu był z niego zadowolony, ale prawdopodobnie domyślnie używa innej wersji C lub jest po prostu łagodniejszy.
Reto Koradi
1
@Dennis Ok, dodałem logikę śledzenia, aby móc wygenerować ciąg. Zajmuje teraz około 7 sekund dla n = 3.
Reto Koradi,
3

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!

BrainSteel
źródło
1
Myślę, że coś przeoczyłem. Czy przy 2 ciągach nie jest to klasyczny problem z programowaniem dynamicznym, który należy wykonać w około 1000 ^ 2 krokach? Innymi słowy, ułamek sekundy.
@Lembik Tak, powinno. Ta metoda została zbudowana do obsługi wielu więcej niż 2 łańcuchów, ale zakończyła się zbyt słabym skalowaniem przy długości łańcucha, aby uzyskać dobre wyniki. Mam w zanadrzu wiele innych sztuczek i jeśli któryś z nich rzeczywiście działa ... Rzeczy powinny się znacznie poprawić.
BrainSteel,
Wydaje się, że gdzieś jest problem. @ Kod RetoKoradi znajduje prawidłowy wspólny podciąg o długości 391 dla n = 2, podczas gdy twój kod zgłasza długość 386 i wypisuje ciąg o długości 229.
Dennis
@Dennis Umm ... Tak, tak to robi ... Och kochanie. Cóż, to jest zawstydzające. Pracuję nad tym :) Wyedytuję odpowiedź, aby odzwierciedlić błąd.
BrainSteel,