Jakie struktury danych kryją się za arkuszem kalkulacyjnym?


35

Chciałbym zrozumieć, w jaki sposób rozwiązany jest arkusz kalkulacyjny (grupa nazwanych lub w inny sposób zidentyfikowanych komórek zawierających wartości lub formuły odnoszące się do innych komórek). Próbowałem przyjrzeć się istniejącym projektom, ale z GUI, serializacją, wydarzeniami itp. Działo się tyle rzeczy, że nie mogłem znaleźć arkusza kalkulacyjnego.

Najprościej jak to działa?


1
Jeśli chcesz spojrzeć na implementację arkusza kalkulacyjnego, która ma bardzo minimalne GUI (a tym samym mniej rozprasza od sedna
— itsbruce

Odpowiedzi:


21

Zasadniczo arkusz kalkulacyjny jest językiem funkcjonalnym z dynamicznym pisaniem, a każdą funkcję lub wartość można określić jako komórkę w macierzy.

Zamiast rzeczy jak (defn some-name ...)w some-nameczęści umieszcza się w samej komórce.

Jeśli przejdziesz do dynamicznie aktualizowanego ideowego języka funkcjonalnego (takiego jak lighttable for clojure), zobaczysz wiele takich samych funkcji jak arkusz kalkulacyjny. Powiąż wartość z nazwą, napisz funkcję, która korzysta z tej wartości, zmień wartość, a wynik funkcji zmieni się natychmiast. To jest tak samo jak robienie czegoś takiego jak pisanie =A1 + B2w lokalizacji C3excel.

W związku z tym programiści funkcjonalni często lubią pisać arkusze kalkulacyjne jako programy zabawkowe ... i także temat prac naukowych. (Tak, przepraszam, wszystkie stoją za paywallem ACM.org)

  • Programowanie funkcjonalne arkusza kalkulacyjnego

    Społeczność programistów funkcjonalnych wykazała pewne zainteresowanie arkuszami kalkulacyjnymi, ale nieoczekiwanie nikt nie pomyślał o stworzeniu standardowego arkusza kalkulacyjnego, takiego jak Excel, do pracy ze standardowym funkcjonalnym językiem programowania, takim jak Haskell. W tym artykule pokazujemy jeden ze sposobów, w jaki można to zrobić. Mamy nadzieję, że robiąc to, możemy poprosić programistów arkuszy kalkulacyjnych, aby spróbowali programowania funkcjonalnego.

  • Forms / 3: Język wizualny pierwszego rzędu do eksploracji granic paradygmatu arkusza kalkulacyjnego

    Chociaż krytycy programowania funkcjonalnego czasami twierdzą, że programowanie funkcjonalne jest zbyt trudne lub sprzeczne z intuicją, aby większość programistów mogła je zrozumieć i używać, dowody przeciwne można znaleźć, patrząc na popularność arkuszy kalkulacyjnych. Paradygmat arkusza kalkulacyjnego, podzbiór pierwszego rzędu funkcjonalnego paradygmatu programowania, zyskał szeroką akceptację zarówno wśród programistów, jak i użytkowników końcowych. Istnieje jednak wiele ograniczeń w większości systemów arkuszy kalkulacyjnych. W tym artykule omawiamy funkcje językowe, które eliminują kilka z tych ograniczeń bez odchodzenia od deklaratywnego modelu oceny pierwszego rzędu.

  • Wdrażanie arkuszy kalkulacyjnych funkcji

    Arkusze kalkulacyjne wymagają dużej liczby prac rozwojowych użytkowników końcowych. Metafora arkusza kalkulacyjnego jest atrakcyjna, ponieważ jest wizualna i umożliwia interaktywne eksperymenty, ale jak zaobserwowali Peyton Jones, Blackwell i Burnett, metafora arkusza kalkulacyjnego nie przyjmuje nawet najbardziej podstawowej abstrakcji: przekształcenia wyrażenia w nazwaną funkcję. Dlatego zaproponowali sposób zdefiniowania funkcji w kategoriach arkusza roboczego z wyznaczonymi komórkami wejściowymi i wyjściowymi; nazywamy to arkuszem funkcji.


Początek arkusza kalkulacyjnego w Wikipedii zawiera kilka wskazówek, jak go wdrożyć:

Arkusz kalkulacyjny to interaktywny program komputerowy do organizacji i analizy danych w formie tabelarycznej. Arkusze kalkulacyjne opracowane jako skomputeryzowane symulacje papierowych arkuszy kalkulacyjnych. Program działa na danych reprezentowanych jako komórki tablicy uporządkowane w wierszach i kolumnach. Każda komórka tablicy jest elementem kontrolującym widok modelu, który może zawierać dane liczbowe lub tekstowe albo wyniki formuł, które automatycznie obliczają i wyświetlają wartość na podstawie zawartości innych komórek.

Opierając się na tym z paradygmatu Zarys modelu Model-Widok-Kontroler wyrażonego w bibliotekach Java . Autor wspomina o apletach (nieco datowanych, napisano w latach 93–96) i wspomina o swojej stronie internetowej, która prowadzi pod adresem http://csis.pace.edu/~bergin/Java/applets.htm (tak , aplety) dla odpowiedniego kodu arkusza kalkulacyjnego http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Zwrócę uwagę, że cały arkusz kalkulacyjny nie jest aż tak duży w tym aplecie 570 linii łącznie z dokumentacją.

To powiedziawszy, w zależności od języka, prawdopodobnie możesz to wszystko zrobić za pomocą wskaźników funkcji w rzadkiej tablicy.


32

Koncepcyjnie, każda komórka jest węzłem ukierunkowanego wykresu acyklicznego , a odniesienia do innych komórek tworzą krawędzie na tym wykresie. Po zmianie komórki topologiczne sortowanie wszystkich węzłów dostępnych z komórki, którą zmieniłeś, da ci kolejność potrzebną do oceny komórek. Po ustaleniu prawidłowej kolejności jest to po prostu standardowa analiza wyrażeń.


3
Zadzwoń do mnie, ale nie ma gwarancji, że nie możesz utworzyć żadnych cykli w arkuszu kalkulacyjnym. W rzeczywistości właśnie przetestowałem to w programie Excel, otrzymując ostrzeżenie, ale ignorując to, mogłem łatwo utworzyć cykliczne odwołanie.
— Doc Brown,

1
@DocBrown Aby uniknąć złapania się w pętlę i zawieszenia programu, najprawdopodobniej zostanie odcięty przy ostatnim łączu, tym, który go spowodował.
— Izkata

1
Dobra uwaga, @DocBrown. Nadal musisz wykryć cykl i traktować go jak DAG do celów kolejności obliczeń, nawet jeśli zdecydujesz się na rekursję. Po prostu przechodzisz przez to zamówienie wiele razy.
— Karl Bielefeldt,

Jakie struktury danych można wykorzystać do symulacji tego rodzaju zależności DAG? Sprawdzałem macierz przylegania, ale z tablicą * n nie mogliśmy powiązać atrybutów z węzłami i krawędziami. Na przykład formuła na komórce byłaby jednym z atrybutów
— Andy Dufresne

6

Jak już wspomniano, arkusz kalkulacyjny można łatwo zaimplementować jako DAG (ukierunkowany wykres acykliczny) przechowywany w prostym haszu lub słowniku. Prosty kod do zabawy jest prawdopodobnie najłatwiejszym sposobem na jego zrozumienie:

Bardzo prosta wersja Pythona: http://code.activestate.com/recipes/355045-spreadsheet/

Zostało to wyjaśnione i opracowane w tym poście na blogu: http://ralsina.me/weblog/posts/BB585.html

Dostępna jest również prosta wersja JavaScript z graficznym interfejsem użytkownika: http://jsfiddle.net/ondras/hYfN3/


0

Zakodowałem pakiet Pythona, który umożliwia konwersję struktury komórek funkcji celu pliku MS Excel do Pythona. XL2py

Wartości komórek są analizowane do obiektu typu dict () dołączającego ich wartości. Komórki z odniesieniami do innych komórek według wzorów zawierają węzły. Węzły odnoszą się do komórki, której wartość jest zdefiniowana przez jej formułę. Z każdej formuły węzła definiuje się strukturę zależności, aby określić, czy istnieją odwołania cykliczne. Kolejności obliczania węzłów są definiowane z uwzględnieniem struktur zależności zaangażowanych komórek.

W strukturze drzewa We / Wy możesz używać dowolnego algorytmu minimalizacji w Pythonie do woli.

Proponuję rzucić okiem na https://github.com/gusmaogabriels/XL2py

Pozdrawiam, Gabriel

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.