Алгоритм сортировки для непредсказуемых данных

Question

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

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

Даже для встроенного кодирования существуют ли какие-либо обстоятельства, когда такой вид реализации будет иметь место, учитывая тот факт, что для использования доступны boost, SQLite и другие библиотеки? Другими словами, стоит ли думать о способах оптимизации таких алгоритмов?

Answer 1

Как встроенный программист, я бы сказал, что все сводится к проблеме и системным ограничениям. В частности, на микропроцессоре вам может не понадобиться/нужно втягивать Boost, и SQLite может все еще быть слишком тяжелым для данной проблемы. Как вы нарезываете проблемы, выглядит иначе, если вы говорите, 2 КБ ОЗУ - но это определенно крайность.

Так, например, вы, вероятно, не хотите переписывать код для красно-черного дерева самостоятельно, потому что, как вы указали, вы, скорее всего, получите очень неоптимизированный код. Но в стремлении к повторному использованию абстракция часто добавляет слои косвенности коду. Таким образом, вы можете в конечном итоге переопределить по крайней мере более простые «разрешенные» проблемы, где вы можете сделать лучше, чем встроенная библиотека для определенных случаев в нише. Недавно я написал специализированную версию связанных списков, используя пулы разделяемой памяти для распределения по спискам, например. Я сравнивал с списком STL, и он просто не сокращал его из-за добавленных слоев абстракции. Мой код хорош? Нет, наверное, нет. Но я более легко мог специализироваться на конкретных случаях использования, так что это получилось лучше.

Так что, я думаю, я хотел бы остановиться на нескольких вещах со своего поста: -Почему компании все еще спрашивают о запуске большого времени? Я видел, что даже очень хорошие инженеры делают плохой выбор в отношении структур данных, потому что они не очень тщательно рассуждали о времени выполнения O(). Квадратичная или линейная или линейная или постоянная работа - это болезненный урок, когда вы ошибаетесь. (ах, голос опыта)

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

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

Answer 2

Если вы предлагаете использовать SQLite на Arduino на 2 kB, вы можете услышать много смеха.

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

Answer 3

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