Комментарии 7
Вы оптимизировали хэш-функцию под какой-то свой набор данных и какое-то своё применение. Итого, результат вашего труда бесполезен для всех остальных (кроме функции вычисления CRC через специальную инструкцию – странно, кстати, что этого нет в стандартной библиотеке).
Да и для вас – под вопросом. Сколько времени вы затратили на оптимизацию? А сколько раз будет запущена оптимизированная программа? В общем, можно по приколу посчитать экономический эффект: цена рабочего времени против цены энергии, которую сожрёт неоптимальное хэширование. Поэтому, собственно, и есть некие стандартные хэш-функции, которые годятся почти всегда.
ЗЫ: для курсовой – отлично, поиграли с хэшированием, разобрались, как оптимизировать и вообще интересно провели время, поздравляю!
И это не считая того что можно использовать генерально оптимизированные таблицы типа hasbrown
Вы оптимизировали хэш-функцию под какой-то свой набор данных и какое-то своё применение.
А очень часто так и бывает - приходится оптимизировать алгоритм под конкретную задачу с учетом ее особенностей. Просто потому, что универсальные решения "не пролазят" под поставленные требования.
А сколько раз будет запущена оптимизированная программа? В общем, можно по приколу посчитать экономический эффект: цена рабочего времени против цены энергии, которую сожрёт неоптимальное хэширование.
Вот именно - надо считать. Представьте, что в постановке указаны жесткие рамки по эффективности использования ресурсов, требования по быстродействию... И задача не считается решенной до тех пор, пока вы в эти рамки не уложитесь.
И что будет с "ценой рабочего времени" когда вы сделаете все на "стандартных" решениях, но вам завернут на нагрузочном тестировании с требованием все переделать?
Поэтому, собственно, и есть некие стандартные хэш-функции, которые годятся почти всегда.
"Почти всегда" - это когда нет особо жестких требований. Ну работает оно полторы секунды (вместо трех совсем без хешей) и ладно. А если требования 150мс? И никакие "стандартные хеши" в это время не укладываются?
для курсовой – отлично, поиграли с хэшированием, разобрались, как оптимизировать
Именно так. Заодно научились понимать, что не всегда можно обойтись стандартными решениями - иногда приходится включить мозг и поработать ручками.
Следующий этап - научиться понимать где и когда достаточно стандартных решений и можно сэкономить время на разработку, а где и когда не надо тратить время на попытку решить задачу универсальными средствами, но сразу сосредоточиться на оптимизации с учетом конкретики задачи.
И да. Хеши не всегда подходят в принципе. Как способ "свертки" длинного ключа - да. Но если длина ключа сравнима с длиной хеша, то возможно не стоит тратить время на его вычисление, а работать с ключом напрямую и заняться оптимизацией алгоритма поиска с учетом специфики структуры ключа. Тут все от задачи идет. Иногда не стоит переусложнять решение в погоне за концептуальностью.
Ны не подумайте чего - я сам всегда "за все хорошее против всего плохого" :-) Но что-то часто в последнее время стали приходить на доработку "дефекты производительности". Задачи, которые когда-то были решены "стандартными способами" и до какого-то момента все устраивало. А с какого-то момента (объем данных растет постоянно) стандартное решение перестало укладываться в отведенное для задачи временное окно и возникла потребность переработки алгоритма с целью его ускорения. И в >80% случаев приходится просто выкидывать старое решение и разрабатывать новое с нуля.
Вы всё правильно пишете.
И курсовая у ребят отличная, препод им дал "потрогать руками" оптимизацию.
Просто описание одного конкретного случая оптимизации, да ещё без анализа, нужна ли она вообще – не очень полезно (а для новичков, которые могут решить, что это пример для подражания – даже вредно). Грубо говоря, хотелось бы видеть на Хабре не отчёт по выполненной курсовой, а методичку, по которой она делалась.
А вот тут соглашусь. Вы правы - хотелось бы услышать предпосылки к такой вот "ручной" оптимизации - почему и зачем именно так, а не стандартными способами.
Какие особенности данных и как использовались.
Сравнение - какой выигрыш по сравнению со стандартными подходами получен в данном конкретном случае.
да нет это не только для курсовой НЕ удовлетворительно, это для преподавателя и/или для целой специальности которая позволяет формулировать такие псевдо научные исследования оценка ДВА и подтверждение полной некомпетентности.
Реализация хеш-функций базируется на теоремах-аксиомах дискретной математики. Это строгая математическая база не просто проигнорирована в такой постановке задаче, фундаментальные основы подменили и извратили, чтобы, как бы, сформулировать какую то "новую" задачу.
Бредовость этой "новой" задачи подтверждается результатами ее решения:
У компилятора есть строгие рамки при оптимизации, за пределы которых он не выйдет
Уход от более свободных рамок к более строгим может дать значимый прирост производительности
Не все проблемы решаются ассемблерными оптимизациями
Тот кто сомневается в справедливости этих утверждений и принимает их как результаты исследования не должен преподавать.
И тоже верно. Оптимизация начинается с выбора наиболее подходящего в данном случае алгоритма. Точнее даже с определения что именно не устраивает в текущей реализации. Или определения требований к реализации.
Т.е. ответов на вопросы - что, зачем и почему будем оптимизировать. Определяем требования, узкие места. И только потом думаем как именно.
Вот пример. Прилетает письмо от сопровождения:
"Коллеги, сервис *** за последние 5 недель увеличил потребление процессорных ресурсов в 3 раза!!! Он уже является 2-м по величине сервисом после *****.
В качестве альтернативы мы рассматриваем перенос запуска сервиса на резервный сервер, но там есть лаг по отставанию до 10 мин.
Заказчикам сервиса это может не понравиться :(
"Сервис" в данном случае есть тонкая прослойка между внешним миром и изолированным сервером на котором крутится вся бизнес-логика, реализованная в виде вебсервиса. На стороне сервера каждому сервису соответствует т.н. "сервис-модуль", вызываемый сервисом за заданным набором параметров и возвращающий результат. Собственно, задача вебсервиса - предоставить внешний интерфейс и обеспечить преобразование типов параметров и возвращаемого результата.
Т.о. все проблемы производительности упираются в проблемы сервис-модуля.
С первого взгляда задачка казалась несложной. Ну неделя. Вместе с аналитикой.
Но... Хочешь рассмешить бога - поведай ему о своих планах.
Первый подход к снаряду не дал ожидаемого результата.
Сначала выявились тонкости в алгоритме.
Потом первое нагрузочное тестирование не показало желаемого улучшения. Уперлись в некоторые ограничения, накладываемые форматом БД где хранятся нужные данные. Ломали голову как обойти. Придумали. Реализовали. Стало лучше.
Потом еще увидели что при определенных вызовах есть оверкод в части лишних проверок того, что уже проверялось при прошлых вызовах. Добавили кеширование всего чего только можно. Фактически просто переписали все заново. С нуля. Так, что не осталось ни одного лишнего обращения к БД - если полезли в таблицу, сразу выгребаем все что потребуется и сейчас и потом и прихораниваем в кеше.
Результат (опять от сопровождения):
Спасибо!
Уже утром видим очень хороший результат!!!
Доработка сокращает потребление процессорных ресурсов почти в 10 раз!
При этом, ни одной "ассемблерной вставки" (на нашей платформе вообще ассемблера нет, точнее, он наверное есть, но для прикладного разработчика недоступен, только для разработчиков самой ОС на самых нижних, закрытых для пользователя, слоях). Все исключительно алгоритмизацией. Но главное - предварительная аналитика с выявлением узких мест, оверкода, избыточных обращений к таблицам БД, неоптимальных запросов и т.д. и т.п.
В практике есть куча других примеров - в силу невозможности закупки нового адекватного железа приходится оптимизировать старые модули (благо, там возможностей для оптимизации более чем достаточно - много писалось давно, писалось "в лоб" и удовлетворяло когда объемы данных были кратно меньше).
Из статьи же непонятно что именно оптимизировали? Зачем? Почему хеши? Может там проще какой-то другой алгоритм использовать? Самобалансирующиеся деревья, SkipList тот же? Какие там объемы данных? Какова плотность вызовов? Много вопросов...
Исследование возможностей оптимизации ПО на примере хеш-таблицы