Comments 26
Подписываюсь под каждым пунктом.
Хорошая статья. Почти со всем согласен. Вот только
>> Убедись, что функции выполняются за время O(n)
ну блин, а если сложность — квадрат, или еще хуже, кубическая? Задачи-то разные бывают. К тому же для определенных вещей и линейное время тоже может быть убийственно долго. Вобщем, не понял.
>> Убедись, что функции выполняются за время O(n)
ну блин, а если сложность — квадрат, или еще хуже, кубическая? Задачи-то разные бывают. К тому же для определенных вещей и линейное время тоже может быть убийственно долго. Вобщем, не понял.
отличная статья
Очень приятная статья и перевод. Спасибо.
>Массивы лучше сложных структур данных
Совершенно не понял это утверждение, расшифруйте плиз.
Совершенно не понял это утверждение, расшифруйте плиз.
2. Не недооценивайте силу простоты
по-моему, всё очевидно
Массивы лучше деревьев, связанных списков и прочего. Там где это возможно — лучше использовать их.
Например, не нужно делать binary heap на указателях, если у вас ~50 элементов и точно не больше сотни. Массив не только будет проще, но и может получить существенный выигрыш в производительности из-за линейного доступе к памяти.
Например, не нужно делать binary heap на указателях, если у вас ~50 элементов и точно не больше сотни. Массив не только будет проще, но и может получить существенный выигрыш в производительности из-за линейного доступе к памяти.
в «Эффективном использовании STL» Мейерса есть метод как заменить map на vector.
другой вериант, это если у нас в мапе бывает немного разновидностей значений, допустим 10 из 100 (примерно, хотя на практике значения бывают больше допустим 50000 из 100000), то не нужно заводить мап чтоб их хранить и пытаться экономить на этом память, можно завести массив на все 100 элементов, и пометить есть ли он в наличии. на маленьких кусках данных это часто даже выгоднее чем заводить мап, хотя бы с точки зрения количества аллокаций, особенно если есть вероятность что в наборе появятся все варианты.
допустим в играх часто не меняется набор файлов, но при этом не менее часто нужно хранить какие-то ресурсы которые из этих файлов выгружаются. одно из решений к которому придет любой школьник, это map<filename,ressource>. более красивым решением может быть нумерация всех файлов на этапе компиляции, и использование vector<ressource> и vector<filename>, во втором мы ищем id по имени (можно при желании отсортировать и использовать бинарный поиск), в первом за O(1) получаем ресурс по ID, такой способ позволяет отказаться от указателей на ресурсы, что даст более гибкие методы управления ими (время доступа по идентификатору O(1), часто идентификатор может иметь меньший размер чем указатель, хотя это уже спички).
но если посмотреть еще, то можно заметить что vector<filename> нам не очень нужен, так как обычно имена файлов получают из других файлов либо файлов конфигураций, где какой нибудь скрипт их может заменить на ID еще в компайл тайме (в смысле на стадии сборки ресурсов), что позволит выкинуть строки и мапы вообще, получив возможность более гибко менеджить ресурсы, но ценой добавления стадии сборки ресурсов и отсутствия возможности добавлять новые файлы в уже готовую игру (немного усложняет патчинг и увеличивает размер патча, нужно это или нет уже другой вопрос).
вот так вот серия небольших размышлений которая занимает считанные дни позволяет увидеть совсем другую систему ресурсов в игре, сэкономив недели в конце проекта.
другой вериант, это если у нас в мапе бывает немного разновидностей значений, допустим 10 из 100 (примерно, хотя на практике значения бывают больше допустим 50000 из 100000), то не нужно заводить мап чтоб их хранить и пытаться экономить на этом память, можно завести массив на все 100 элементов, и пометить есть ли он в наличии. на маленьких кусках данных это часто даже выгоднее чем заводить мап, хотя бы с точки зрения количества аллокаций, особенно если есть вероятность что в наборе появятся все варианты.
допустим в играх часто не меняется набор файлов, но при этом не менее часто нужно хранить какие-то ресурсы которые из этих файлов выгружаются. одно из решений к которому придет любой школьник, это map<filename,ressource>. более красивым решением может быть нумерация всех файлов на этапе компиляции, и использование vector<ressource> и vector<filename>, во втором мы ищем id по имени (можно при желании отсортировать и использовать бинарный поиск), в первом за O(1) получаем ресурс по ID, такой способ позволяет отказаться от указателей на ресурсы, что даст более гибкие методы управления ими (время доступа по идентификатору O(1), часто идентификатор может иметь меньший размер чем указатель, хотя это уже спички).
но если посмотреть еще, то можно заметить что vector<filename> нам не очень нужен, так как обычно имена файлов получают из других файлов либо файлов конфигураций, где какой нибудь скрипт их может заменить на ID еще в компайл тайме (в смысле на стадии сборки ресурсов), что позволит выкинуть строки и мапы вообще, получив возможность более гибко менеджить ресурсы, но ценой добавления стадии сборки ресурсов и отсутствия возможности добавлять новые файлы в уже готовую игру (немного усложняет патчинг и увеличивает размер патча, нужно это или нет уже другой вопрос).
вот так вот серия небольших размышлений которая занимает считанные дни позволяет увидеть совсем другую систему ресурсов в игре, сэкономив недели в конце проекта.
Согласен со всеми пунктами, но хотелось бы добавить, что все хорошо в меру.
«Преждевременная оптимизация как преждевременная эякуляция, ничего хорошего!»
«Преждевременная оптимизация как преждевременная эякуляция, ничего хорошего!»
очень многие неправильно понимают смысл этой фразы, и считают что оптимизировать нужно в конце то что тормозит.
не потраченный час на этапе проектирования, превращается в потраченный день перед релизом (это касается не только оптимизации).
не потраченный час на этапе проектирования, превращается в потраченный день перед релизом (это касается не только оптимизации).
Основной посыл автора в том, чтобы балансировать посередине между преждевременной оптимизацией и написанием заведомо-тормозной-лажи.
Маленький классический пример на преждевременную оптимизацию:
Есть некая операция (например, получение всех классов в сборке, реализующих некий интерфейс). Она, конечно же, вынесена в отдельный метод (иначе это плохое проектирование), а может быть и в отдельный класс (если мы пуристы).
Очевидно, что операция небыстрая, и первое побуждение — написать там же рядом с этим методом (в этом классе) кэш для этой операции. И вот с этим побуждением и надо бороться. Не надо писать этот кэш сейчас — совершенно понятно, что мы можем написать его в любой момент позже, когда (и если!) мы поймем, что эта операция отнимает слишком много времени.
Не надо *сейчас* тратить на это пять минут (или полчаса, или полдня, если мы задумаемся о многопоточности и блокировках). Надо убедиться, что все работает, и пойти решать следующую бизнес-задачу. А это место оставить на рефакторинг.
Если *когда-нибудь* кто-нибудь вообще заметит, что оно медленное.
Есть некая операция (например, получение всех классов в сборке, реализующих некий интерфейс). Она, конечно же, вынесена в отдельный метод (иначе это плохое проектирование), а может быть и в отдельный класс (если мы пуристы).
Очевидно, что операция небыстрая, и первое побуждение — написать там же рядом с этим методом (в этом классе) кэш для этой операции. И вот с этим побуждением и надо бороться. Не надо писать этот кэш сейчас — совершенно понятно, что мы можем написать его в любой момент позже, когда (и если!) мы поймем, что эта операция отнимает слишком много времени.
Не надо *сейчас* тратить на это пять минут (или полчаса, или полдня, если мы задумаемся о многопоточности и блокировках). Надо убедиться, что все работает, и пойти решать следующую бизнес-задачу. А это место оставить на рефакторинг.
Если *когда-нибудь* кто-нибудь вообще заметит, что оно медленное.
По-моему автор стремится к той крайности, которая «а давайте все заранее предусмотрим и запараллелим/кешируем/что-нибудь-еще».
>Массивы лучше сложных структур данных
Весьма спорно. В плане производительности они, конечно, лучше, но записи $user[0], $user[USER_ID][] (где константу надо ещё определить заранее) и даже $user['id'] читаются, имхо, сложнее, чем $user->id (в идеале user.id).
Плюс для слаботипизированных языков (в сильнотипизированных массивы, вроде как, не допускают разнородные элементы) «сложная» структура данных позволит воспользоваться анализом кода, автодополнением и прочими плюшками, т. к. будет видно (по коду илианнотациям комментариям), что user.id может быть только числом.
Весьма спорно. В плане производительности они, конечно, лучше, но записи $user[0], $user[USER_ID][] (где константу надо ещё определить заранее) и даже $user['id'] читаются, имхо, сложнее, чем $user->id (в идеале user.id).
Плюс для слаботипизированных языков (в сильнотипизированных массивы, вроде как, не допускают разнородные элементы) «сложная» структура данных позволит воспользоваться анализом кода, автодополнением и прочими плюшками, т. к. будет видно (по коду или
Кроме PHP есть много других языков. Там где явно задан тип массива — все эти автоподстановки прекрасно работают.
Я в курсе о вашей любви предлагать не попадающие под правило примеры, но, имхо, эта статья не тот случай.
Я в курсе о вашей любви предлагать не попадающие под правило примеры, но, имхо, эта статья не тот случай.
Про подстановки в сильно или строготипизированных языках, о существовании которых я знаю и немало на которых писал, я сам указал в своём комменте. Но это лишь дополнение к основной мысли. Главное, что даже в случае однотипных (с технической точки зрения, но не с семантической) данных в каноническом массиве, что читабельней в случае, например, C/C++: a[0], a[RESOURCE_1] или a.resource_1, если размер массива фиксирован на этапе компиляции, а каждый его элемент несет разную семантическую нагрузку.
Если вам нужно записать карту локации размерами AxB в ячейках которой расположены юниты с целочисленным идентификатором от 1 до N, массив, имхо, гораздо лучше читаем чем конструкции вида Map.Point(x,y).getUnit().
Не вижу смысла спорить, любую идею можно довести до абсурда.
Не вижу смысла спорить, любую идею можно довести до абсурда.
Минус в комментарий вам за то, что даже не прочитав сообщение бросились критиковать и осуждать комментатора.
Sign up to leave a comment.
Прагматичный подход к производительности