Структура данных сводной таблицы
Какой тип структуры данных (или структур данных?) можно использовать для хранения сводной таблицы из двух измерений, где данные могут быть доступны? Например, возьмем следующее, скопированное из Excel:
Если бы все данные были в одномерной иерархии, то есть группа > продукт > год > стоимость, мы могли бы сделать что-то вроде:
{
"Electronics": {
"(all)": {
"Year": {
"2018": 2,
"2019": 1,
"Grand Total": 3
}
},
"Computer": {
"Year": {
"2018": 1,
"2019": 0,
"Grand Total": 1
}
},
"Phone": {
"Year": {
"2018": 1,
"2019": 1,
"Grand Total": 2
}
}
}
}
И тогда я мог бы получить доступ к значению в разделе «Электроника»> «Компьютер»> 2018, выполнив:
obj["Electronics"]['Computer']['Year']
// {2018: 1, 2019: 0, Grand Total: 1}
obj["Electronics"]['Computer']['Year'][2018]
// 1
Но я не могу представить, как это можно было бы поместить в двумерную структуру данных за пределами двумерного многомерного массива, который действительно не имел бы никакого использования, кроме возможности получить значение в определенной позиции (и Мне нужно было бы хранить тонны метаданных, чтобы знать, что хранится в каком месте).
Какая будет подходящая структура данных для этого? Я отметил это Java, C, C++ — подойдет любой язык, меня больше интересует фактическая структура данных.
Люди будут собирать ответы здесь из-за щедрости. Но я сомневаюсь, что какой-то из них будет действительно полезен для вас. Рекомендую еще раз прочитать Как спросить. Я понимаю, что у вас достаточно репутации, чтобы иметь некоторое представление о том, как задать хороший вопрос (прямо или косвенно), но, чтобы не тратить щедрость впустую, сделать его более легким для ответа, вероятно, будет мудрым шагом. Так что, пожалуйста, извините меня за то, что я снова упоминаю об этом.
У меня складывается впечатление, что первая строка на картинке имеет избыточные данные, которые можно было бы определить по остальным. Или в этом суть вашего вопроса? Пожалуйста, рассмотрите возможность определения своего понимания «сводной таблицы», возможно, сославшись на контекст, в котором вы ее узнали; например «МС Эксель».
@Yunnosch обязательно добавлю некоторые детали.
Если данные представлены в формате ввода, который вы показываете (выглядит как JSON), рассмотрите возможность предоставления минимального воспроизводимого примера того, как вы их читаете, сохраняете и выводите как есть. Это покажет структуры данных, механизмы ввода/вывода и формат вывода. В этом «механизме вывода» также может быть что-то вроде структуры данных, которая должна быть заполнена желаемым результатом для заданного входного образца. т.е. у вас есть первая треть нужной программы и третья треть. Заполнение пропущенной второй трети в качестве ответа было бы намного проще и, скорее всего, полезным для вас. Для этого вы, вероятно, захотите выбрать язык.
Существуют различные способы хранения данных, например, в виде простой таблицы базовых данных фактов. Чтобы ответить на ваш вопрос, нам нужно знать, что вы хотите делать с данными. Нужен ли вам, например, быстрый доступ к итоговым значениям или достаточно вычислять их по запросу?
@ jon-hanson любой из них на самом деле хорош, но я полагаю, что если бы мне пришлось сказать одно или другое, я бы сказал (1) в зависимости от того, что проще; и (2) если это не имеет значения, то да, материализуйте итоги.
Ответы 2
В Python иерархическое индексирование используется для реализации сводных таблиц. Например, сводные таблицы python pandas представляют собой мультииндексные кадры данных. Реализация фрейма данных находится в https://github.com/pandas-dev/pandas/blob/v0.22.0/pandas/core/frame.py#L236-L6142. MultiIndex реализован в pandas.core.indexes.multi.py
Для C++ и Java также существуют иерархические библиотеки индексации, т.е. boost::multi_index, здесь в stackoverflow multi-index имеет свой тег.
Возможно, проверьте boost::multi_index примеры: https://www.boost.org/doc/libs/1_62_0/libs/multi_index/doc/examples.html
Мультииндексация в Java: Есть ли где-нибудь аналог boost::multi_index для Java?
В https://www.scss.tcd.ie/Owen.Conlan/4d2/4D2-9&10_Multi-Level_Indexes_v1.02.pdf , https://www.cs.uct.ac.za/mit_notes/ база данных/htmls/chp11.html#многоуровневые индексы и http://theteacher.info/index.php/architecture-data-comms-and-applications-unit-5/4-organisation-and-structure-of -data/all-topics/3940-multi-level-indexes анализ мультииндексации в файлах (структура файловой системы) и алгоритм поиска
Команды, используемые в python для обработки многоуровневых индексов, т.е. stack и unstack :
Я бы хранил данные в табличной форме, т.е.:
+---------------------------------------+
| Sector | Device | Year | Count |
+---------------------------------------+
| Electronics | Computer | 2018 | 1 |
| Electronics | Phone | 2018 | 1 |
| Electronics | Phone | 2019 | 1 |
+---------------------------------------+
Сводная таблица — это просто визуальный способ представления вышеуказанных данных.
Вы можете использовать столбчатую таблицу представления (т. е. хранить данные по столбцам, а не по строкам), чтобы оптимизировать представление для быстрых запросов. Как правило, столбцы сначала упорядочиваются по наиболее часто используемым, сортируются данные в каждом столбце и сохраняются позиции, чтобы отметить, где начинается каждый набор различных значений в столбце.
Столбчатые представления включают Apache Arrow для данных в памяти и Apache Parquet для данных, хранящихся на диске.
Для приведенных выше данных это может выглядеть примерно так:
+-------------+
| Electronics |
| Electronics |
| Electronics |
+-------------+
| Computer |
| Phone |
| Phone |
+-------------+
| 2018 |
| 2018 |
| 2019 |
+-------------+
| 1 |
| 1 |
| 1 |
+-------------+
конечно, но вам также понадобятся все промежуточные итоги, верно? (Как насчет чего-то вроде отдельного подсчета, когда вы не можете суммировать подзаписи?)
Промежуточные итоги могут быть вычислены путем запроса данных и сохранения результата. Если значения в кубе нестатичны, вам, конечно, понадобится совершенно другая структура данных - возможно, ориентированный граф зависимостей. Отсюда мой вопрос: «Что вы хотите делать с данными?». Невозможно ответить на ваш вопрос, если вы не предоставите эту информацию заранее.
Вопрос действительно слишком открытый, чтобы подходить для переполнения стека. Тем не менее, «сводная таблица» — это, по сути, конкретная конфигурация группировки и агрегации простого старого набора данных. Вы должны сосредоточиться на трех частях отдельно: самой базе данных (будь то фактическая БД или просто таблица в памяти или что-то еще), запрос(ы) для получения желаемых агрегированных результатов и, наконец, визуальное представление этих агрегированных результатов. .