Структура данных для таблицы?

Question

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

 
    | column 1 | column 2 | column 3| 
a | asd  | awd  | asfc | 
b | asgf  | aasf  | asgfc | 

у меня есть:

 
String a = "column 1" 
String b = "b" 
String c = find(a,b); 

В конце значение в c должно быть asgf.

Answer 1

Вы должны использовать ассоциативные массивы (так называемые словари) на основе хеш-таблиц. Средняя временная сложность для поиска - O (1 + n/k) и O (n) в худшем случае. Вы должны упорядочить таблицу как словарь столбцов (с именами столбцов в качестве ключа). И Колонка должна быть словарь значений (с названиями строк в качестве ключа)

Подробнее:

http://en.wikipedia.org/wiki/Dictionary_(data_structure) http://en.wikipedia.org/wiki/Hash_table

Пример в C#:

using System; 
using System.Collections; 
using System.Collections.Generic; 

namespace Test { 
    public class Test 
    { 
     class Table { 
      class Column { 
       public Dictionary<string, string> cells; 

       public Column() { 
        cells = new Dictionary<string, string>(); 
       } 

       public string Find(string rowName) { 
        string resultValue; 
        if (cells.TryGetValue(rowName, out resultValue)) 
         return resultValue; 
        else 
         throw new Exception("oops, no such cell"); 
       } 
      } 

      Dictionary<string, Column> columns; 
      List<string> rowNames; 

      public Table() { 
       columns = new Dictionary<string, Column>(); 
       rowNames = new List<string>(); 
      } 

      public void AddColumn(string columnName, params string[] values) { 
       Column column = new Column(); 
       columns.Add(columnName, column); 

       // fill new cells 
       int counter = 0; 
       foreach (string rowName in rowNames) { 
        if (counter < values.Length) 
         column.cells.Add(rowName, values[counter]); 
        else 
         column.cells.Add(rowName, ""); 
        counter++; 
       } 
      } 

      public void AddRow(string rowName, params string[] values) { 
       rowNames.Add(rowName); 

       // fill new cells 
       int counter = 0; 
       foreach (KeyValuePair<string, Column> columnPair in columns) { 
        Column column = columnPair.Value; 
        if (counter < values.Length) 
         column.cells.Add(rowName, values[counter]); 
        else 
         column.cells.Add(rowName, ""); 
        counter++; 
       } 
      } 

      public string Find(string columnName, string rowName) { 
       Column resultColumn; 
       if (columns.TryGetValue(columnName, out resultColumn)) 
        return resultColumn.Find(rowName); 
       else 
        throw new Exception("oops, no such cell"); 
      } 
     } 

     public static void Main() 
     { 
      Table table = new Table(); 
      table.AddRow("a"); 
      table.AddRow("b"); 
      table.AddColumn("column 1", "asd", "asgf"); 
      table.AddColumn("column 2", "awd", "aasf"); 
      table.AddColumn("column 3", "asfc", "asgfc"); 
      Console.WriteLine(table.Find("column 1", "b")); 
     } 
    } 
}