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 axbycz
i xaybzc
mają 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 rand
okreś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ę 0
w powyższym kodzie, ale zastrzegam sobie prawo do zmiany go na nieujawnioną wartość, jeśli podejrzewam, że ktoś (częściowo) zakodował wynik.
źródło
public static void main(...)
?Odpowiedzi:
C, n = 3 w ~ 7 sekund
Algorytm
Algorytm jest bezpośrednim uogólnieniem standardowego rozwiązania programowania dynamicznego na
n
sekwencje. Dla 2 łańcuchówA
iB
standardowa powtarzalność wygląda następująco:Przez 3 strun
A
,B
,C
używam:Kod implementuje tę logikę dla dowolnych wartości
n
.Wydajność
Złożoność mojego kodu to O (s ^ n), przy
s
dł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ścin
, 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łobyn = 4
2 minuty in = 4
wygląda już ambitnie.Zmniejszyłem użycie pamięci w początkowej implementacji, aby mogła obsłużyć
n = 4
dany 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.
Instrukcje do biegania
Biegać:
lcs.c
.Kompiluj z opcjami wysokiej optymalizacji. Użyłem:
W systemie Linux spróbowałbym:
Uruchom z 2 do 4 sekwencji podanymi jako argumenty wiersza poleceń:
W razie potrzeby pojedynczo wpisz argumenty wiersza poleceń, ponieważ alfabet użyty w przykładach zawiera znaki specjalne powłoki.
Wyniki
test2.sh
itest3.sh
są sekwencjami testowymi Dennisa. Nie znam poprawnych wyników, ale wyniki wydają się co najmniej wiarygodne.źródło
N_MAX
jako makro i dodać flagę kompilatora,-std=c99
aby skompilować kod za pomocą GCC.Ta odpowiedź jest obecnie zepsuta z powodu błędu. Naprawianie wkrótce ...
C, 2 struny w ~ 35 sekundJest to w dużej mierze praca w toku (o czym świadczy okropny bałagan), ale mam nadzieję, że dostarczy dobrych odpowiedzi!
Kod:
Odpowiednią funkcją, która wykonuje wszystkie obliczenia LCS, jest funkcja
LCS
. Powyższy kod wykona własne wywołanie tej funkcji.Zapisz jako
main.c
i 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.
Lub:
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:
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!
źródło