При использовании Excel меня всегда удивляло, насколько хорошо Excel выполняет следующие две операции агрегирования:
Как Excel может достичь такой производительности? Хранятся ли в них дополнительные структуры данных для сводной информации и агрегирования? Это задокументировано где-нибудь или где я могу узнать больше об этом? Я просмотрел исходный код Libreoffice, но фактический продукт даже не близок к Excel по производительности агрегации/сводки.
Было бы здорово, если бы кто-нибудь, разбирающийся в Excel, мог бы рассказать немного больше о поведении низкоуровневой агрегации или о структурах, которые Excel использует для достижения этой производительности — например, сохраняют ли они какие-либо метки дважды — один раз в собственном случае и один раз пониже для целей агрегации? Хотя я знаю, что этот вопрос слишком широк и не касается кода как такового, а является более концептуальным, я надеюсь, что ответ может послужить хорошим справочником по методам оптимизации производительности в агрегациях в стиле Excel.
Вот несколько вещей, которые я заметил на основе некоторых предложений от ARGeo:
(1) Есть два файла, связанных с Pivot Cache -- Определения (информация на уровне полей):
(2) И записи (информация об уровне строки/ячейки) --
Отсюда несколько вопросов тогда:
Struct, который Excel использует в памяти для своего сводного кэша (а не в виде различных хранимых XML-документов)?.
<cacheField name = "numEmps" numFmtId = "0"><sharedItems containsString = "0" containsBlank = "1" containsNumber = "1" containsInteger = "1" minValue = "0" maxValue = "20000"/></cacheField>
Почему сюрприз? Это программное обеспечение, предназначенное для таких вещей.
В «Замеченных вещах» вы сравниваете, как данные сериализуются на/с диска, и как структура данных работает в памяти. Они очень, очень слабо связаны между собой, поэтому практически невозможно получить представление о производительности структуры данных в памяти путем проверки сериализованных данных.
Большая сложность создания сводной таблицы из n строк данных и m строк + столбцов + фильтров составляет O (n * m). Есть некоторые крайние случаи, когда он может раздуться до O (n log n * m), но это когда вы настроили сводную таблицу иррациональным образом (добавили двойное значение в виде строки И отсортировали его). Это ДОЛЖНО быть быстрым.
@MineR, не могли бы вы поделиться базовой реализацией этого алгоритма, используя приведенные выше образцы данных (или пример того, как может быть O (n logn * m), чтобы показать базовый алгоритм создания сводной таблицы?





Производительность сводной таблицы основана на Pivot Cache. Хотя информации на эту тему очень мало (я имею в виду отсутствие официальной документации), я нашел несколько интересных постов и документацию по MS.
Определение:
Pivot Cache — специальная область памяти, в которой сохраняются записи сводной таблицы.
When you create a
Pivot Table, Excel takes a copy of the source data and stores it in thePivot Cache. ThePivot Cacheis held in Excel’s memory. You can’t see it but that’s the data the Pivot Table references when you build your Pivot Table.
This enables Excel to be very responsive to changes in the Pivot Table but it can also double the size of your file. After all, the Pivot Cache is just a duplicate of your source data so it makes sense that your file size will potentially double.
Пожалуйста, используйте этот связь и этот связь для получения дополнительной информации в качестве отправной точки.
Кроме того, вы можете прочитать сообщения Сводной кэш в Excel 101 и Сводной кэш Excel 101, чтобы узнать, что это такое и какие у него побочные эффекты.
Вот несколько фрагментов кода VB и примеры использования Объект PivotCache.
Вот код, написанный на C#, который позволяет вам создать книгу Excel с некоторыми Pivot Tables, которые, конечно же, используют Pivot Cache:
System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
using Excel = Microsoft.Office.Interop.Excel;
using System.IO;
using System.Diagnostics;
using System.Configuration;
using System.Data.SqlClient;
using System.Data;
namespace ConsoleApplication1 {
class Program {
static void Main(string[] args) {
Excel.Application objApp;
Excel.Workbook objBook;
Excel.Sheets objSheets;
Excel.Workbooks objBooks;
string command = (@"SELECT * FROM dbo.Client");
using (SqlConnection connection = new SqlConnection(GetConnectionStringByName("CubsPlus"))) {
DataTable data = new DataTable();
try {
connection.Open();
}
catch (Exception e) {
StackTrace st = new StackTrace(new StackFrame(true));
StackFrame sf = st.GetFrame(0);
Console.WriteLine (e.Message + "\n" + "Method" + sf.GetMethod().ToString() + "\n" + "Line" + sf.GetFileLineNumber().ToString());
}
try {
data = DataTools.SQLQueries.getDataTableFromQuery(connection, command);
if (data == null) {
throw new ArgumentNullException();
}
}
catch (Exception e) {
StackTrace st = new StackTrace(new StackFrame(true));
StackFrame sf = st.GetFrame(0);
Console.WriteLine (e.Message + "\n" + "Method" + sf.GetMethod().ToString() + "\n" + "Line" + sf.GetFileLineNumber().ToString());
}
objApp = new Excel.Application();
try {
objBooks = objApp.Workbooks;
objBook = objApp.Workbooks.Add(Missing.Value);
objSheets = objBook.Worksheets;
Excel.Worksheet sheet1 = (Excel.Worksheet)objSheets[1];
sheet1.Name = "ACCOUNTS";
string message = DataTools.Excel.copyDataTableToExcelSheet(data, sheet1);
if (message != null) {
Console.WriteLine("Problem importing the data to Excel");
Console.WriteLine(message);
Console.ReadLine();
}
//CREATE A PIVOT CACHE BASED ON THE EXPORTED DATA
Excel.PivotCache pivotCache = objBook.PivotCaches().Add(Excel.XlPivotTableSourceType.xlDatabase,sheet1.UsedRange);
Console.WriteLine(pivotCache.SourceData.ToString());
Console.ReadLine();
//WORKSHEET FOR NEW PIVOT TABLE
Excel.Worksheet sheet2 = (Excel.Worksheet)objSheets[2];
sheet2.Name = "PIVOT1";
//PIVOT TABLE BASED ON THE PIVOT CACHE OF EXPORTED DATA
Excel.PivotTables pivotTables = (Excel.PivotTables)sheet2.PivotTables(Missing.Value);
Excel.PivotTable pivotTable = pivotTables.Add(pivotCache, objApp.ActiveCell, "PivotTable1", Missing.Value, Missing.Value);
pivotTable.SmallGrid = false;
pivotTable.TableStyle = "PivotStyleLight1";
//ADDING PAGE FIELD
Excel.PivotField pageField = (Excel.PivotField)pivotTable.PivotFields("ParentName");
pageField.Orientation = Excel.XlPivotFieldOrientation.xlPageField;
//ADDING ROW FIELD
Excel.PivotField rowField = (Excel.PivotField)pivotTable.PivotFields("State");
rowField.Orientation = Excel.XlPivotFieldOrientation.xlRowField;
//ADDING DATA FIELD
pivotTable.AddDataField(pivotTable.PivotFields("SetupDate"), "average setup date", Excel.XlConsolidationFunction.xlAverage);
ExcelSaveAs(objApp, objBook, @"J:\WBK");
objApp.Quit();
}
catch (Exception e) {
objApp.Quit();
Console.WriteLine(e.Message);
Console.ReadLine();
}
}
}
static string ExcelSaveAs(Excel.Application objApp, Excel.Workbook objBook, string path) {
try {
objApp.DisplayAlerts = false;
objBook.SaveAs(path, Excel.XlFileFormat.xlExcel7, Missing.Value, Missing.Value, Missing.Value, Missing.Value, Excel.XlSaveAsAccessMode.xlNoChange, Missing.Value, Missing.Value, Missing.Value, Missing.Value, Missing.Value);
objApp.DisplayAlerts = true;
return null;
}
catch (Exception e) {
StackTrace st = new StackTrace(new StackFrame(true));
StackFrame sf = st.GetFrame(0);
return (e.Message + "\n" + "Method" + sf.GetMethod().ToString() + "\n" + "Line" + sf.GetFileLineNumber().ToString());
}
}
static string GetConnectionStringByName(string name) {
//ASSUME FAILURE
string returnValue = null;
//Look for the name in the connectionStrings section
ConnectionStringSettings settings = ConfigurationManager.ConnectionStrings[name];
// If found, return the connection string
if (settings != null) {
returnValue = settings.ConnectionString;
}
return returnValue;
}
}
}
А вот код, написанный на VB, который позволяет нам создать новый Pivot Cache для выбранных Pivot Table:
Sub SelPTNewCache()
Dim wsTemp As Worksheet
Dim pt As PivotTable
On Error Resume Next
Set pt = ActiveCell.PivotTable
If pt Is Nothing Then
MsgBox "Active cell is not in a pivot table"
Else
Set wsTemp = Worksheets.Add
ActiveWorkbook.PivotCaches.Create( _
SourceType:=xlDatabase, _
SourceData:=pt.SourceData).CreatePivotTable _
TableDestination:=wsTemp.Range("A3"), _
TableName: = "PivotTableTemp"
pt.CacheIndex = wsTemp.PivotTables(1).CacheIndex
Application.DisplayAlerts = False
wsTemp.Delete
Application.DisplayAlerts = True
End If
exitHandler:
Set pt = Nothing
End Sub
1. In your
asd.jsfile there are the following elements:
– s обозначает строковое значение
– n обозначает числовое значение
– d обозначает значение даты
– x обозначает значение индекса
– v указывает само значение
Итак, давайте переведем на человеческий язык данные, содержащиеся в F2 ячейке этой таблицы.:
<x v = "0"/>
Значение 0 — это zero index в массиве строк, где хранятся сокращения штатов США. Первый индекс в этом массиве извлекает для нас Arizona. Я не знаю, почему ячейка в следующей строке содержит строчные буквы az, а все остальные — прописные AZ, но я уверен, что дело не в Shared Record.
2. I haven't found any useful information on the internal C/C++ Struct that Excel uses in-memory for its pivotCache.
И, наконец:
3. Here's a LINK containing useful info regarding "helper information" in third extra question.
P.S.
Об обозначении Big O.
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (in memory or on disk) by an algorithm.
Big O notationis a measure of the complexity of your program in terms of the size of the input.
O(1) обозначает алгоритм, который всегда выполняется в одно и то же время независимо от размера набора входных данных.
O(N) обозначает алгоритм, производительность которого растет линейно и прямо пропорционально размеру набора входных данных.
O(N*N) обозначает алгоритм, производительность которого прямо пропорциональна квадрату размера набора входных данных.
T(N) = O(log N) обозначает алгоритм, производительность которого зависит от логарифмического времени. Алгоритмы, использующие логарифмическое время, обычно встречаются в операциях над бинарные деревья или при использовании бинарного поиска.
Но хорошие алгоритмы сортировки жестко O(N log N). Примером алгоритма с такой эффективностью может быть Сортировка слиянием, который разбивает массив на две половины, сортирует эти две половины, рекурсивно вызывая себя на них, а затем объединяет результат обратно в один массив.
Вот абстрактный фрагмент кода C#, показывающий, как работает алгоритм O(N log N) (примерно такой же подход можно использовать для создания сводной таблицы):
public static int[] MergeSort(int[] inputItems, int lowerBound, int upperBound) {
if (lowerBound < upperBound) {
int middle = (lowerBound + upperBound) / 2;
MergeSort(inputItems, lowerBound, middle);
MergeSort(inputItems, middle + 1, upperBound);
int[] leftArray = new int[middle - lowerBound + 1];
int[] rightArray = new int[upperBound - middle];
Array.Copy(inputItems, lowerBound, leftArray, 0, middle - lowerBound + 1);
Array.Copy(inputItems, middle + 1, rightArray, 0, upperBound - middle);
int i = 0;
int j = 0;
for (int count = lowerBound; count < upperBound + 1; count++) {
if (i == leftArray.Length) {
inputItems[count] = rightArray[j];
j++;
}
else if (j == rightArray.Length) {
inputItems[count] = leftArray[i];
i++;
}
else if (leftArray[i] <= rightArray[j]) {
inputItems[count] = leftArray[i];
i++;
}
else {
inputItems[count] = rightArray[j];
j++;
}
}
}
return inputItems;
}
спасибо за ответ. Это очень полезно и указало мне правильное направление. Вы можете увидеть, что такое фактический сводной кеш в Excel?
Дэвид, не могли бы вы сказать мне, что именно вы имеете в виду, говоря ...what the actual pivot cache is...?
конечно, позвольте мне обновить вопросы. Извиняюсь за медленное продолжение.
вау, это очень исчерпывающий и отличный ответ. Любая возможность, которую вы могли бы привести, например, очень краткий пример алгоритма сложности O(n*m) в C#, что в одном из комментариев упоминается о создании кеша сводной таблицы для завершения ответа / я бы присудил награду
Дэвид, это все, что я смог найти.
Большое спасибо, Давид! Я разрабатываю приложения для macOS, и у меня нет свободного времени для какой-либо другой работы. Спасибо за предложение.
Анатомия файла электронной таблицы
Класс PivotCache PivotCache. Когда объект сериализуется как xml, его полное имя — x:pivotCache.
Члены PivotCache (Excel) Представляет кэш памяти для Отчет сводной таблицы.
Представляет базовый класс, в котором все элементы в Офис OpenXML документ происходит от.
Спецификация OpenXML — большой и сложный зверь.
cacheField (поле PivotCache) Представляет одно поле в Сводной кэш. Это определение содержит информацию о поле, таких как его источник, тип данных и расположение на уровне или иерархия. Элемент sharedItems хранит дополнительную информацию о данных в этом поле. Если нет общих элементов, то значения хранятся непосредственно в части pivotCacheRecords.
Определяет Класс SharedItems. Когда объект сериализуется как xml, его полное имя — x:sharedItems.
Этот вопрос слишком широк для переполнения стека. Как монолитное приложение может достичь наилучшей в своем классе производительности, выполняя некоторые операции, потенциально может потребовать целой серии сообщений в блоге.