Правильная структура данных, используемая для клона Excel

Question

Скажем, я работаю над клонов Excel на C#. Моя сетка представлена ​​следующим образом:

private struct CellValue 
{ 
    private int column; 
    private int row; 
    private string text; 
} 
private List<CellValue> cellValues = new List<CellValue>(); 

Каждый раз, когда пользователь добавить текст, я просто упаковать его как CellValue и добавить его в cellValues. Учитывая тип CellValue, я могу определить его строку и столбец в O (1) раз, что отлично. Однако, учитывая столбец и строку, мне нужно пройти через все cellValues, чтобы найти, какой текст находится в этом столбце и строке, что ужасно медленно. Кроме того, учитывая текст, мне тоже нужно перебирать всю вещь. Есть ли какая-либо структура данных, в которой я могу выполнить все 3 задачи в O (1) раз?

Обновлено: Просмотрев некоторые ответы, я не думаю, что нашел тот, который мне нравится. Могу ли я:

1. Не хранить более 2 копий CellValue, чтобы избежать их синхронизации. В мире C я бы неплохо использовал указатели.
2. Динамические добавления строк и столбцов (в отличие от Excel). .

Answer 1

Учитывая, что данные 2-мерная, я бы 2D массив для хранения его в

Answer 2

Ну, вы можете хранить их в трех словарях: два Dictionary<int,CellValue> объектов для строк и столбцов, и один Dictionary<string,CellValue> для текста. Вы должны были бы держать все три тщательно в синхронизации, хотя.

Я не уверен, что я не просто идти с большой двумерный массив, хотя ...

Answer 3

Я думаю, вы должны использовать один из индексированных коллекций, чтобы сделать его работать достаточно быстро, совершенный один - KeyedCollection

Вам необходимо создать собственную коллекцию, распространяя этот класс. Таким образом, ваш объект по-прежнему будет содержать строку и столбец (так что вы ничего не потеряете), но вы сможете их искать. Вероятно, вам нужно будет создать класс, инкапсулирующий (строку, столбец) и сделать его ключом (так что сделайте его неизменным и переопределите равным и получите хеш-код)

Answer 4

Если это точный клон, то массив со списком CellValue [256]. Excel имеет 256 столбцов, но растет количество строк.

Answer 5

Я бы создать

Collection<Collection<CellValue>> rowCellValues = new Collection<Collection<CellValue>>(); 

и

Collection<Collection<CellValue>> columnCellValues = new Collection<Collection<CellValue>>(); 

Наружная коллекция имеет одну запись для каждой строки или столбца, индексированные по номер строки или столбца, внутренняя коллекция имеет все клетки в этой строке или столбце. Эти коллекции должны быть заполнены как часть процесса, который создает новые объекты CellValue.

rowCellValues[newCellValue.Row].Add(newCellValue); 
columnCellValues[newCellValue.Column].Add(newCellValue); 

Answer 6

Я бы выбрал разреженный массив (связанный список связанных списков), чтобы обеспечить максимальную гибкость при минимальном хранении.

В этом примере у вас есть связанный список строк с каждым элементом, указывающим на связанный список ячеек в этой строке (вы можете отменить ячейки и строки в зависимости от ваших потребностей).

| 
V 
+-+ +---+    +---+ 
|1| -> |1.1| ----------> |1.3| -: 
+-+ +---+    +---+ 
| 
V 
+-+    +---+ 
|7| ----------> |7.2| -: 
+-+    +---+ 
| 
= 

Каждый элемент строки имеет номер строки в нем, и каждый элемент клетка имеет указатель на его строке элемента, таким образом, чтобы получить номер строки из ячейки представляет собой О (1).

Аналогично, каждый элемент ячейки имеет номер столбца, что также делает O (1).

Нет простого способа получить O (1) для немедленного нахождения ячейки в данной строке/столбце, но разреженный массив будет таким же быстрым, как и он, если вы не предварительно распределите информацию для каждой возможной ячейки, чтобы вы может выполнять поиск по индексу по массиву - это было бы очень расточительно с точки зрения хранения.

Одна вещь, которую вы можете сделать, состоит в том, чтобы сделать одно измерение непрозрачным, например, сделать столбцы основным массивом (а не связанным списком) и ограничить их до 1000 - это приведет к индексированию столбца (быстро), затем поиск по разреженным строкам.

Я не думаю, что вы можете получить O (1) для текстового поиска просто потому, что текст можно дублировать в нескольких ячейках (в отличие от строки/столбца). Я по-прежнему считаю, что разреженный массив будет самым быстрым способом поиска текста, если вы не сохраните отсортированный индекс всех текстовых значений в другом массиве (опять же, это может сделать его быстрее, но за счет большого объема памяти).

Answer 7

Если строки и столбцы можно добавить «динамически», вы не должны хранить строку/столбец как атрибут ячейки numeric, а скорее как ссылку на объект строки или столбца.

Пример:

private struct CellValue 
{ 
    private List<CellValue> _column; 
    private List<CellValue> _row; 
    private string text; 

    public List<CellValue> column { 
    get { return _column; } 
    set { 
     if(_column!=null) { _column.Remove(this); } 
     _column = value; 
     _column.Add(this); 
     } 
    } 

    public List<CellValue> row { 
    get { return _row; } 
    set { 
     if(_row!=null) { _row.Remove(this); } 
     _row = value; 
     _row.Add(this); 
     } 
    } 
} 

private List<List<CellValue>> MyRows = new List<List<CellValue>>; 
private List<List<CellValue>> MyColumns = new List<List<CellValue>>; 

каждой строки и столбца объект реализован в виде списка объектов CellValue. Это неупорядоченный - порядок ячеек в определенном Строке не соответствует индексу столбца и наоборот.

Каждый лист имеет список строк и список столбцов в порядке листа (показаны выше как MyRows и MyColumns).

Это позволит вам изменить и вставить новые строки и столбцы без прокрутки и обновления любых ячеек.

Удаление строки должно проходить через ячейки в строке и удалять их из соответствующих столбцов перед удалением самой строки. И наоборот для столбцов.

Чтобы найти определенную строку и столбец, найдите соответствующие объекты Row и Column, а затем найдите CellValue, который они содержат вместе.

Пример:

public CellValue GetCell(int rowIndex, int colIndex) { 
    List<CellValue> row = MyRows[rowIndex]; 
    List<CellValue> col = MyColumns[colIndex]; 
    return row.Intersect(col)[0]; 
    } 

(. Я немного нечеткой на эти методы расширения в .NET 3.5, но это должно быть на стадионах)

Answer 8

Если я правильно помню, там был статья о том, как это сделала Visicalc, возможно, в журнале Byte Magazine в начале 80-х годов. Я считаю, что это был редкий массив. Но я думаю, что есть ссылки как вверх-вниз, так и слева-направо, так что любая данная ячейка имела указатель на ячейку над ней (как бы много ячеек, которые могут быть), ниже нее, слева от нее , и справа от него.

Answer 9

Это запах преждевременной оптимизации.

Тем не менее, есть несколько особенностей превосходства, которые важны при выборе хорошей структуры.

Первое, что Excel использует ячейки в умеренно нелинейном режиме. Процесс разрешения формул включает в себя перемещение электронных таблиц в эффективном случайном порядке. Структуре понадобится механизм для легкого поиска значений случайных ключей дешево, маркировка их грязная, разрешенная или неразрешимая из-за круговой ссылки. Ему также понадобится некоторый способ узнать, когда больше не осталось оставшихся ячеек, так что он может перестать работать. Любое решение, которое связано с связанным списком, вероятно, является неоптимальным для этого, поскольку для получения этих ячеек потребуется линейное сканирование.

Другая проблема заключается в том, что Excel выделяет диапазон ячеек за один раз. Это может показаться тривиальным, и в значительной степени это так, но оно, безусловно, будет идеальным, если приложение сможет вытащить все данные, необходимые для рисования диапазона ячеек за один снимок. часть этого может отслеживать высоту и ширину отображения строк и столбцов, чтобы система отображения могла перебирать диапазон до тех пор, пока не будет собрана желаемая ширина и высота ячеек. Необходимость итерации таким образом может препятствовать использованию стратегии хэширования для разреженного хранения ячеек.

Кроме того, есть некоторые недостатки репрезентативной модели электронных таблиц, которые можно было бы решать гораздо эффективнее, используя несколько иной подход.

Например, агрегаты столбцов являются неудобными. Общее количество столбцов достаточно просто для реализации в excel, но у него есть своего рода волшебное поведение, которое работает большую часть времени, но не все время. Например, если вы добавите строку в агрегированную область, дальнейшие вычисления в этой совокупности могут продолжать работать или нет, в зависимости от того, как вы ее добавили. Если вы копируете и вставляете строку (и заменяете значения), все работает нормально, но если вы вырезаете и вставляете ячейки на одну строку вниз, все не так хорошо работает.