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?

Hildred
źródło
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.


źródło
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ń.

Karl Bielefeldt
źródło
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/

Tomek
źródło
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

Gabriel S. Gusmão
źródło