Was sind die Datenstrukturen hinter einer Tabelle?

35

Ich möchte verstehen, wie eine Tabelle (eine Gruppe benannter oder auf andere Weise identifizierter Zellen, die Werte oder Formeln enthalten, die auf andere Zellen verweisen) gelöst wird. Ich habe versucht, vorhandene Projekte zu betrachten, aber es war so viel los mit der GUI, der Serialisierung, Ereignissen usw., dass ich die Tabelle nicht finden konnte.

Am einfachsten wie funktioniert es?

hildred
quelle
1
Wenn Sie sich eine Tabellenkalkulationsimplementierung ansehen möchten, die eine sehr minimale Benutzeroberfläche (und damit weniger Ablenkung vom eigentlichen Problem) aufweist, lesen
Sie

Antworten:

21

Im Kern ist eine Kalkulationstabelle eine funktionale Sprache mit dynamischer Typisierung, und jede Funktion oder jeder Wert kann als Zelle in der Matrix referenziert werden.

Anstelle von Dingen wie wird (defn some-name ...)das some-nameTeil in einer Zelle selbst platziert.

Wenn Sie zu einer dynamisch aktualisierten Funktionssprache wechseln (z. B. lighttable für clojure), sehen Sie einen Großteil derselben Funktionalität wie bei einer Tabellenkalkulation. Binden Sie einen Wert an einen Namen, schreiben Sie eine Funktion, die diesen Wert verwendet, ändern Sie den Wert und die Ausgabe der Funktion ändert sich sofort. Dies ist dasselbe, als würde man etwas =A1 + B2an der Stelle von C3in Excel schreiben .

So schreiben funktionale Programmierer oft Tabellenkalkulationen als Spielzeugprogramme ... und auch das Thema von Forschungsarbeiten. (Ja, es tut mir leid, sie stehen alle hinter einer ACM.org-Paywall.)

  • Tabellenkalkulationsprogrammierung

    Die Community für funktionale Programmierung hat ein gewisses Interesse an Arbeitsblättern gezeigt, aber überraschenderweise scheint niemand darüber nachgedacht zu haben, ein Standard-Arbeitsblatt wie Excel mit einer Standardsprache für funktionale Programmierung wie Haskell arbeiten zu lassen. In diesem Artikel zeigen wir einen Weg, wie dies getan werden kann. Wir hoffen, dass wir auf diese Weise Tabellenkalkulationsprogrammierer dazu bringen, die funktionale Programmierung auszuprobieren.

  • Forms / 3: Eine visuelle Sprache erster Ordnung, um die Grenzen des Tabellenkalkulationsparadigmas zu erkunden

    Obwohl Kritiker der funktionalen Programmierung manchmal behaupten, dass die funktionale Programmierung für die meisten Programmierer zu schwierig oder nicht intuitiv zu verstehen und zu verwenden ist, kann anhand der Popularität von Tabellen das Gegenteil nachgewiesen werden. Das Spreadsheet-Paradigma, eine Untermenge erster Ordnung des funktionalen Programmierparadigmas, hat sowohl bei Programmierern als auch bei Endbenutzern breite Akzeptanz gefunden. Dennoch gibt es bei den meisten Tabellenkalkulationssystemen viele Einschränkungen. In diesem Artikel werden Sprachmerkmale erörtert, mit denen einige dieser Einschränkungen beseitigt werden, ohne vom deklarativen Bewertungsmodell erster Ordnung abzuweichen.

  • Implementieren von Funktionskalkulationen

    Ein großer Teil der Endbenutzerentwicklung wird mit Tabellenkalkulationen durchgeführt. Die Tabellenkalkulationsmetapher ist attraktiv, weil sie visuell ist und interaktives Experimentieren ermöglicht, aber wie von Peyton Jones, Blackwell und Burnett beobachtet, lässt die Tabellenkalkulationsmetapher nicht einmal die grundlegendste Abstraktion zu: die Umwandlung eines Ausdrucks in eine benannte Funktion. Daher schlugen sie eine Möglichkeit vor, eine Funktion in Form eines Arbeitsblatts mit festgelegten Eingabe- und Ausgabezellen zu definieren. wir werden es ein Funktionsblatt nennen.


Der Start von Spreadsheet bei Wikipedia gibt einige Hinweise zur Implementierung:

Eine Tabelle ist ein interaktives Computeranwendungsprogramm zur Organisation und Analyse von Daten in Tabellenform. Tabellenkalkulationen wurden als computergestützte Simulationen von Papierbuchhaltungs-Arbeitsblättern entwickelt. Das Programm verarbeitet Daten, die als Zellen eines Arrays dargestellt werden und in Zeilen und Spalten angeordnet sind. Jede Zelle des Arrays ist ein Model-View-Controller-Element, das entweder numerische oder Textdaten oder die Ergebnisse von Formeln enthalten kann, die automatisch einen Wert basierend auf dem Inhalt anderer Zellen berechnen und anzeigen.

Aufbauend auf dem in den Java-Bibliotheken zum Ausdruck gebrachten Modell-View-Controller-Paradigma . Der Autor erwähnt weiterhin Applets (ein bisschen veraltet, sie wurden zwischen '93 und '96 geschrieben) und erwähnt seine Webseite, die zu http://csis.pace.edu/~bergin/Java/applets.htm (yes) führt , Applets) für den entsprechenden Tabellenkalkulationscode http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Ich werde darauf hinweisen, dass die Gesamtheit der Tabelle in diesem Applet 570 Zeilen einschließlich Dokumentation nicht so groß ist.

Das heißt, je nach Sprache könnten Sie wahrscheinlich alles mit nur Funktionszeigern in einem spärlichen Array tun.


quelle
32

Konzeptionell ist jede Zelle ein Knoten eines gerichteten azyklischen Diagramms , und Verweise auf andere Zellen erzeugen Kanten in diesem Diagramm. Wenn Sie eine Zelle ändern, erhalten Sie durch eine topologische Sortierung aller Knoten, die von der geänderten Zelle aus erreichbar sind, die Reihenfolge, in der Sie die Zellen auswerten müssen. Sobald Sie die richtige Reihenfolge festgelegt haben, wird nur noch das Parsing von Standardausdrücken durchgeführt.

Karl Bielefeldt
quelle
3
Rufen Sie mich an, aber es gibt keine Garantie dafür, dass Sie keine Zyklen in einer Tabelle erstellen können. Tatsächlich habe ich das gerade mit Excel getestet und eine Warnung erhalten, aber wenn ich sie ignoriere, kann ich leicht eine zyklische Referenz erstellen.
Doc Brown
1
@DocBrown Um nicht in der Schleife hängen zu bleiben und das Programm einzufrieren, wird es wahrscheinlich bei der letzten Verknüpfung unterbrochen, die es verursachen würde.
Izkata
1
Guter Punkt, @DocBrown. Sie müssen den Zyklus immer noch erkennen und für die Zwecke der Berechnungsreihenfolge wie eine DAG behandeln, auch wenn Sie die Rekursion zulassen. Sie gehen diese Bestellung einfach mehrmals durch.
Karl Bielefeldt
Welche Datenstrukturen könnten verwendet werden, um diese Art von DAG-Abhängigkeiten zu simulieren? Ich habe die Adjazenzmatrix überprüft, aber mit einem * n-Array konnten wir Knoten und Kanten keine Attribute zuordnen. Zum Beispiel Formel auf der Zelle wäre eines der Attribute
Andy Dufresne
6

Wie bereits erwähnt, kann eine Tabelle leicht als DAG (Directed Acyclic Graph) implementiert werden, die in einem einfachen Hash oder Dictionary gespeichert ist. Ein einfacher Code zum Spielen ist wahrscheinlich der einfachste Weg, ihn zu verstehen:

Eine sehr einfache Python-Version: http://code.activestate.com/recipes/355045-spreadsheet/

Dies wurde in diesem Blog-Beitrag erklärt und ausgearbeitet: http://ralsina.me/weblog/posts/BB585.html

Es gibt auch eine einfache JavaScript-Version mit einer GUI hier: http://jsfiddle.net/ondras/hYfN3/

Tom
quelle
0

Ich habe ein Python-Paket programmiert, mit dem Sie die Zielfunktionszellenstruktur einer MS Excel-Datei in Python konvertieren können. XL2py

Zellwerte werden analysiert, und an ein Objekt vom Typ dict () werden ihre Werte angehängt. Zellen mit Verweisen auf andere Zellen durch Formeln umfassen Knoten. Knoten beziehen sich auf eine Zelle, deren Wert durch ihre Formel definiert wird. Aus jeder Knotenformel wird eine Abhängigkeitsstruktur definiert, um zu definieren, ob Zirkelverweise vorhanden sind oder nicht. Knotenberechnungsreihenfolgen werden unter Berücksichtigung der beteiligten Zellenabhängigkeitsstrukturen definiert.

Ab der E / A-Baumstruktur können Sie jeden Minimierungsalgorithmus verwenden, der in Python implementiert ist.

Ich würde vorschlagen, dass Sie einen Blick auf https://github.com/gusmaogabriels/XL2py werfen

Viele Grüße, Gabriel

Gabriel S. Gusmão
quelle