Często zadanie wymaga prawdziwych tablic. Weźmy na przykład zadanie zaimplementowania Befunge lub> <>. Próbowałem do tego użyć Array
modułu, ale jest to bardzo kłopotliwe, ponieważ wydaje mi się, że koduję o wiele za bardzo. Czy ktoś może mi pomóc w rozwiązywaniu takich zadań związanych z golfem mniej gadatliwym i bardziej funkcjonalnym?
11
Odpowiedzi:
Przede wszystkim polecam przyjrzeć się Data.Vector , w niektórych przypadkach ładniejszą alternatywą dla Data.Array .
Array
iVector
są idealne do niektórych przypadków zapamiętywania, jak pokazano w mojej odpowiedzi na „Znajdowanie maksymalnych ścieżek” . Jednak niektóre problemy po prostu nie są łatwe do wyrażenia w funkcjonalnym stylu. Na przykład problem 28 w projekcie Euler wymaga zsumowania liczb na przekątnych spirali. Jasne, znalezienie wzoru na te liczby powinno być dość łatwe, ale zbudowanie spirali jest trudniejsze.Data.Array.ST zapewnia zmienny typ tablicy. Jednak sytuacja typu jest bałaganem: używa klasy MArray do przeciążenia każdej z metod oprócz runSTArray . Tak więc, chyba że planujesz zwrócić niezmienną tablicę z działania zmiennej tablicy, będziesz musiał dodać jeden lub więcej podpisów typu:
Niemniej jednak moje rozwiązanie Euler 28 okazało się całkiem nieźle i nie wymagało tego podpisu, ponieważ go użyłem
runSTArray
.Używanie Data.Map jako „tablicy zmiennych”
Jeśli chcesz zaimplementować zmienny algorytm tablicowy, inną opcją jest użycie Data.Map . Kiedy używasz tablicy, żałujesz, że nie masz takiej funkcji, która zmienia pojedynczy element tablicy:
Niestety, wymagałoby to skopiowania całej tablicy, chyba że implementacja zastosowała strategię kopiowania przy zapisie, aby tego uniknąć, jeśli to możliwe.
Dobrą wiadomością jest to, że
Data.Map
ma taką funkcję, wstaw :Ponieważ
Map
jest implementowany wewnętrznie jako zrównoważone drzewo binarne,insert
zajmuje tylko O (log n) czas i przestrzeń oraz zachowuje oryginalną kopię. DlategoMap
nie tylko zapewnia nieco wydajną „zmienną tablicę”, która jest kompatybilna z funkcjonalnym modelem programowania, ale pozwala nawet „cofnąć się w czasie”, jeśli chcesz.Oto rozwiązanie Euler 28 za pomocą Data.Map:
Wzory uderzenia zapobiegają przepełnieniu stosu spowodowanemu przez to, że przedmioty akumulatorowe (kursor, liczba i mapa) nie były używane do samego końca. W przypadku większości golfów kodowych przypadki wprowadzania nie powinny być wystarczająco duże, aby potrzebować tego przepisu.
źródło
Odpowiedź glib brzmi: nie używaj tablic. Niezbyt glibowa odpowiedź brzmi: spróbuj przemyśleć swój problem, aby nie potrzebował tablic.
Często problem z niektórymi myślami można rozwiązać bez jakiejkolwiek struktury podobnej do tablicy. Na przykład oto moja odpowiedź na Euler 28:
To, co wyraża się w tym kodzie, to wzór sekwencji liczb rosnących wokół prostokątnej spirali. Nie było potrzeby przedstawiania samej macierzy liczb.
Kluczem do myślenia poza macierzami jest zastanowienie się, co tak naprawdę oznacza dany problem, a nie jak można go przedstawić jako bajty w pamięci RAM. To po prostu przychodzi z treningiem (być może powodem, dla którego tak często gram w golfa!)
Innym przykładem jest to, w jaki sposób rozwiązałem wyszukiwanie maksymalnych ścieżek golfa kodu. Tam metoda przepuszczania częściowych rozwiązań w postaci fali przez matrycę, rząd po rzędzie, jest wyrażana bezpośrednio przez operację składania. Pamiętaj: na większości procesorów nie możesz poradzić sobie z tablicą jako całością: program będzie musiał działać przez nią z czasem. Może nie potrzebować całej tablicy jednocześnie.
Oczywiście niektóre problemy są określone w taki sposób, że są z natury oparte na tablicy. Języki takie jak> <>, Befunge lub Brainfuck mają w sercu tablice. Jednak nawet tam często można zrezygnować z tablic. Na przykład zobacz moje rozwiązanie interpretacji Brainfuck , prawdziwym rdzeniem jego semantyki jest zamek błyskawiczny . Aby zacząć myśleć w ten sposób, skoncentruj się na wzorcach dostępu i strukturze bliższej znaczeniu problemu. Często nie trzeba tego zmuszać do modyfikowania tablicy.
Gdy wszystko inne zawiedzie i musisz użyć tablicy - wskazówki @ Joeya to dobry początek.
źródło