Пример принципа "интеллектуальных структур данных" Эрика Раймонда

Ответ 1

Здесь один для вас из MaNGOS:

#if defined( __GNUC__ )
#pragma pack(1)
#else
#pragma pack(push,1)
#endif

typedef struct AUTH_LOGON_CHALLENGE_C
{
    uint8   cmd;
    uint8   error;
    uint16  size;
    uint8   gamename[4];
    uint8   version1;
    uint8   version2;
    uint8   version3;
    uint16  build;
    uint8   platform[4];
    uint8   os[4];
    uint8   country[4];
    uint32  timezone_bias;
    uint32  ip;
    uint8   I_len;
    uint8   I[1];
} sAuthLogonChallenge_C;

Это TCP-пакет. Просто взглянув на это, вы расскажете о всех алгоритмах, которые вам понадобятся для отправки и приема хорошо сформированных пакетов. Вам все равно нужно знать допустимые значения для каждого поля, но они одинаково определены в одном файле.

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

Ответ 2

Хорошим примером этого является С++ STL.

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

Ответ 3

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

В двусвязном списке (с манекеном node, чтобы список всегда имел хотя бы один node), вы можете удалить node только с ссылкой на node:

node.Prev.Next = node.Next;
node.Next.Prev = node.Prev;

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

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

Из Википедии:

Для двух связанных списков требуется больше места на node (если только не используется xor-linking), а их элементарные операции более дороги; но их часто легче манипулировать, поскольку они обеспечивают последовательный доступ к списку в обоих направлениях. В частности, можно вставлять или удалять node в постоянное число операций, учитывая только этот адрес node. Чтобы сделать то же самое в односвязном списке, нужно иметь предыдущий адрес node. Некоторые алгоритмы требуют доступа в обоих направлениях. С другой стороны, они не разрешают совместное использование ключей и не могут использоваться в качестве постоянных структур данных.

Ответ 4

Это, вероятно, не то, что вы имеете в виду, а вот идея.

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

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

http://www.joelonsoftware.com/items/2006/08/01.html

Ответ 5

@Rob на правильном пути здесь для хорошего примера. Взгляните на объекты коллекций, найденные на С# или Java.

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

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

while there are items in the bag list
     remove the next item from the bag
     put away the item

введите что-то еще code-ish

while (item = bag.NextItem())
{
   bag.Remove(item);
   robot.PutAway(item);
}

Теперь вам все равно, как реализован список предметов в сумке? Нет, совсем нет. Вам просто нужно, чтобы вы могли найти следующий предмет и вытащить его из сумки. Является ли сумка двойным связанным списком, единственным связанным списком, независимо от того, что это не имеет значения.

Итак, разработчик, пишущий этот отвратительный алгоритм PutAway, не заботится о том, как они находят элементы, им просто нужно, чтобы у них был элемент. Мешок не волнует, что происходит с предметами, он просто заботится о том, чтобы он мог удерживать их какое-то время, а затем их отбирают. И этот разработчик возвращается домой на выходные.:)

Конечно, это очень простой пример, там есть много дыр, которые вы можете высунуть в него.

Ответ 6

Приведенное вами предложение приходит сразу после хорошего примера:

Первое серьезное изменение, которое я сделал, это добавить поддержку IMAP. Я сделал это, перестроив протокольные машины в общий драйвер и три таблицы методов (для POP2, POP3 и IMAP).