Какова самая сложная структура данных, которую вы использовали в практической ситуации? [закрыто]

17

Зародыш этого вопроса возник из обсуждения, которое я вел с парой коллег-разработчиков из отрасли.

Оказывается, что во многих местах руководители проектов настороженно относятся к сложным структурам данных и обычно настаивают на том, что существует "из коробки" из стандартной библиотеки / пакетов. Общая идея, похоже, состоит в том, чтобы использовать комбинацию из того, что уже доступно, если производительность серьезно не ограничена. Это помогает сохранять простоту кодовой базы, что для недипломатического означало бы: «у нас высокий уровень истощения, а новые, которые мы нанимаем, могут быть не такими уж хорошими».

Так что нет никакого фильтра Блума, пропускающих списков или сплайнов для вас. Итак, вот вопрос (снова): Какова самая сложная структура данных, которую вы делали или использовали в офисе?

Помогает понять, насколько хорошее / сложное программное обеспечение реального мира.

data-structures Fanatic23
источник
Написано другими или самими собой?
Моим первоначальным замыслом было то, что я сам разработал, но я думаю, что это добавляет интересное измерение к вопросу. Отредактированный оригинальный вопрос.
Fanatic23
Делать это сложно не значит, что это сложно. Проще = лучше всегда
tp1
Самые сложные были всегда доступны от STL. Сложность обычно происходит от вложенных структур данных, а не от их типа. Простая структура = хорошо, если профайлер не жалуется.
Кодер
-1 для ненужной оценки стоимости. Я мог бы точно так же сказать: в эти дни, если вы внедряете структуры данных самостоятельно, вы глупы и упрямы. Не будьте следующим умным ребенком, который думает, что он может реализовать структуру данных неверным способом.
Питер Б

Ответы:

7

Использовать пропустить списки для поиска. Там, где я работаю, есть стандартная реализация, и всем рекомендуется ее использовать. Использовали попытки Патриции для эффективного хранения и извлечения IP-адресов. Снова реализация уже присутствовала.

aufather
источник
7

Я разработчик Java. Java Collection Framework может решить мои 90% проблем со структурой данных, остальные 10% требуют усилий. Я думаю, что если вы действительно понимаете сложную стандартную библиотеку, написанную экспертами, вы найдете, что они помогают в большинстве случаев.

Сложные структуры данных трудно поддерживать в реальном мире. Чтобы не испортить код, я разделю проблему на несколько меньших. Каждая небольшая проблема может быть решена с помощью Java Collection Framework . Возможно, решение не самое умное (оно требует больше памяти и медленнее), но оно работает и легко обслуживается. Это компромисс.

Если мне нужно написать сложную структуру данных, я заберу учебник :)

远 声 远 Shengyuan Lu
источник
4

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

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

Отсутствие общих знаний CompSci в отрасли является серьезной проблемой. Например, я потерял счет количества знакомых мне разработчиков программного обеспечения, которые не понимают таких выражений, как! (A! = 5 && b! = 3) и a == 5 || b == 3 логически эквивалентны. Любой, кто знает, как применять теорему Деморгана, может признать, что эти выражения логически эквивалентны. Большинство не выпускников CompSci никогда не слышали о теореме Деморгана. Если кто-то просматривает какую-либо существенную кодовую базу, он найдет много вхождений выражений, которые отрицают отрицательные логические подвыражения. Читаемость кода, содержащего отрицательные логические подвыражения, почти всегда улучшается путем преобразования этих выражений в их неотрицательную форму.

бит-бездельник
источник
5
Я советую любому, кто проголосует «за», добавить комментарий, объясняющий, почему он «проголосовал». Я могу справиться с кем-то другого мнения. Однако я не могу справиться с трусостью.
bit-twiddler
2
@ bit-twiddler Я изучил теорему де Моргана в своей философии. Сейчас я делаю CS, это не было упомянуто. Честно говоря, я вижу такие вещи как сокращение, которое лучше всего приходит с опытом. Вы действительно должны помнить правила (и по имени!), Которые вы используете при факторинге уравнения? Я не знаю о вас, но я решаю это на основе того, что передо мной, а не наизусть. То же самое касается модификации логических выражений.
Руперт Мэдден-Эбботт
2
@Rupert: Теорема де Моргана обычно рассматривается в дискретной математике и компьютерной организации (обе из которых являются обязательными для студентов в США). Я сконцентрировался на компьютерной архитектуре / системном программном обеспечении как студент. Теорема де Моргана широко используется в дизайне цифровой логики. В разработке программного обеспечения низкого уровня есть области, где знание теоремы Де Моргана становится критическим. Например, существуют компьютеры с минимальным набором команд, которые не содержат полный набор логических инструкций; следовательно, нужно иметь возможность вывести одну булеву операцию из другой.
bit-twiddler
1
(продолжение) Вот тест, который показывает, что большинство выпускников, не относящихся к информатике / компьютерной инженерии / электротехнике (концентрация компьютерных технологий), либо терпят неудачу сразу, либо для ответа на них требуется очень много времени. Учитывая только операцию NAND (отрицательную), выведите следующие логические операции: NOT, AND, OR, NOR, XOR и XNOR. Знание теоремы де Моргана значительно упрощает вывод этих шести логических операций. Теорема де Моргана, безусловно, является самой важной теоремой в дизайне цифровой логики.
bit-twiddler
1
..... хотя, если быть честным, в отрасли, где МНОГИЕ работы сводятся к написанию недоделанных приложений RoR для какого-то малого бизнеса, в 1000000000, возможно, потребуется примерно 1 раз, когда вам даже понадобится услышать Понятие логических ворот и булевой алгебры, вместо того, чтобы просто знать значение английских слов «или» и «и». Нельзя сказать, что эти вещи не имеют значения, чтобы знать, выполняете ли вы работу с CS, сложные алгоритмы или оптимизации или низкоуровневое программирование, но для большинства людей, работающих программистами, это своего рода бесполезные мелочи.
Сара
2

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

Я также выпустил продукт, который содержал конечный автомат с примерно 80000 состояниями - код для его генерации был, по меньшей мере, немного сложным.

Питер Тейлор
источник
2

Давным-давно, в галактике ... Работал в команде, которая использовала "буфферы дружбы" Кнута в ОСРВ на ассемблере.

Кроме того, Игра жизни Конвея с 256 поколениями для мира 1024 x 1024.

dbasnett
источник
1

На самом деле ничего особенного не использовалось, с нуля это был бы двусвязный список .

Не очень интересно, я использовал другие структуры. Но твой вопрос ответил с нуля.


источник
в C ++ это так std::list, и в этом нет ничего сложного: / я считаю, что красно-черное дерево / дерево AVL намного сложнее, со всеми этими условиями восстановления баланса!
Матье М.
@Mathieu std :: map, и вы, скорее всего, получите RB-дерево.
aufather
1

Дерево хеш-таблиц, содержащих общие списки финансовых данных - даже не спрашивайте. Иногда я хотел бы быть ковбоем. Ах, простая жизнь под звездами ...

Скудный Роджер
источник
снимает очки "Дорогой Бог".
Лен Джозеф
1

Мне пришлось с нуля написать кольцевую структуру двойного связанного списка для алгоритма « Танцующие ссылки» для решателя судоку. Это было похоже на разработку кубика Рубика. Вся структура представляла собой список списков - каждый узел указывал на четыре других.

ProdigySim
источник
1
Это звучит как перебор для решателя судоку, поскольку алгоритм обратного отслеживания методом грубой силы решает задачу быстрее, чем вы можете ввести данные.
Кевин Клайн
3
@kevin, танцующие ссылки - это алгоритм обратного отслеживания методом грубой силы, но с вероятной эвристикой.
Питер Тейлор
Вам нужна эвристика, если вы собираетесь делать такие вещи, как перечисление общего количества решений и утверждение, что у Sudoku есть только 1 уникальное решение.
ProdigySim
1

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

TMN
источник
0

Если подумать, то самая «сложная» структура данных, которую я сделал с нуля, - это моделирование сети элементов, основанной на двусвязных списках. Но это было годы назад, когда я занимался программированием на системном уровне.

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

Я лично считаю, что стоящая перед нами задача определяет средства. Зачем стремиться использовать какую-то экзотическую структуру данных, если она бесполезна? И если я могу сказать, что в большинстве практических прикладных программ нет необходимости изобретать велосипед.


источник
Моим намерением было не форсировать какую-то экзотическую структуру данных. Но это печальная ситуация, когда вам нужно что-то из коробки и приходится иметь дело с тем, что уже доступно, только потому, что так диктует корпоративная политика.
Fanatic23
0

Считается ли приоритетная очередь? Это встречается практически в каждом приложении, написанном в реальном времени. Только недавно она стала частью стандартной библиотеки Java (Java 1.5).

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

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

Old Pro
источник