1. C++ / Говнокод #9681

    +1002

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    8. 8
    9. 9
    template<class _CharType>
    bool check_arith(const _CharType* str)
    {
       for(; *str ; ++str)
          for(unsigned long long j = 0x6165696F7579ull; j; j >>= 8)
            if(((j & 0xFF) | 0x20) == (*str | 0x20))
               return true;
       return false; 
    }

    Функция, которая проверяет, есть ли в слове гласные буквы латинского алфавита с учетом регистра.

    Запостил: gooseim, 15 Марта 2012

    Комментарии (48) RSS

    • шо за дьявольская константа?
      Ответить
      • Коды гласных букв, видать. По байту на букву.
        Ответить
        • это оч.классно согласуется с _CharType
          Ответить
          • ну как раз _CharType тут вполне терпимо

            но во первых такие вещи надо делать как функцию isvowel, которую затем было бы удобно применить к тому же std::find

            и во вторых я бы 100 раз подумал, стоит ли быть умнее компилятора в оптимизации
            может быть в лоб { c |= 0x20; return (c == 'a' || c == 'e' || ... ); } не так уж и плохо получилось бы, а если уж настолько важна скорость, то статическая таблица была бы лучше решения в топике
            Ответить
            • Какая-то херовая оптимизация вышла.
              Я сначала подумал, они сделали аналог паскалевского set, завели 32-байтный массив, символизирующий множество из элементов типа из 256 значений, а тут перебор в лоб.
              Тупо.
              Ответить
              • На сколько я знаю, в паскале такой же перебор лоб. Только ход не сдвигу битов, а по массиву. Или я ошибаюсь?
                Ответить
                • Откуда ты это знаешь? Ёбни по голове того, кто тебе это сказал (или прокрестел).

                  На самом деле там если множество константа и оно просто устроено (что можно 4 сравнениями обойтись), то там таки перебор.
                  Ответить
                  • Дошло до меня про множество, там массив, который содержит нули и единицы и проверка на принадлежность проверяется по индексу массива = проверяемому значению.
                    Но здесь такой трюк не пройдет, потому что может быть не char, а еще и wchar_t и даже теоретически еще что-то большее.
                    Ответить
                    • Если нужные символы находятся в небольшом подынтервале wchar_t, то двумя сравнениями проверяем попадание в интервал (можно и одним, dcc умеет), а потом проверяем для множества, составленного для интервала.
                      Ответить
                    • специализация для <char> тривиальна - через статическую таблицу из 256 значений - думаю, будет быстрее 1-2 битовых операций и бранча
                      для всего остального - мастеркард return (arg < 'z' ? isvowel<char>(arg) : false);
                      Ответить
                      • предлагаю минуснувшему обосновать
                        Ответить
                        • предупреждаю, что не минусовал
                          мой комментарий не к этому относится
                          Ответить
                      • Придумать то можно конечно много вариантов, я имею ввиду, что паскалевский вариант в чистом виде не подойдет. На его основе можно конечно сделать хороший код.
                        Точнее плохой. Потому что хороший код это std::string::find_first_of и тому подобное.
                        Ответить
                        • Подойдёт, подойдёт. Там, где значения вылазят за 255, на помощь приходит умный case:
                          case c of
                          'A', 'B', ...
                          ну ты понял. И пофиг, какой там тип, компилятор это чётко расчехлит.

                          Ну и минусовать при культурном споре - это говнотон.
                          Ответить
                          • Не совсем понял. Как case относится к set? Я говорил число про операцию множества.
                            Про минусовку - согласен. Если минусовать, то надо объяснять хотя бы почему ты это сделал.
                            Ответить
                            • Чтобы определить, относится ли элемент перечислимого типа к множеству, удобно делать так:
                              var S: WideChar;
                              case S of
                              'a', 'b', '0'..'9': writeln('относится');
                              else writeln('не относится');
                              end;
                              При этом внутренности этого case будут скомпилированы в как можно более оптимальный код, с таблицами или бинарными деревьями, в зависимости от ситуации.
                              Ответить
                              • И в отличие от set, это работает даже тогда, когда нужные элементы не укладываются в диапазон длины 256
                                Ответить
                                • значит так
                                  провёл тест
                                  сейчас покажу результаты
                                  Ответить
                                • Ты меня не понял. Я говорил только про set. Как я уже писал, хороших алгоритмов можно написать много и на разных языках.
                                  Ответить
                                  • Внутренности этого case представляют собой продвинутый алгоритм, который всяко лучше той фигни, что в данном ГК.
                                    И там тоже есть хитрая битовая таблица.
                                    Ответить
                                    • Ладно. Я понимаю что мы на разных волнах. На счет ГК - я его не ставлю в пример хорошего кода, иначе бы сюда его не помещал.
                                      Ответить
                                • http://pastebin.com/CZ7jqzw1
                                  Ответить
                                  • Хороший тест.
                                    Всё как и ожидалось: битовая таблица - православна, сишный кейс - говно.
                                    Приведенный в топике код - полное говно.
                                    Ответить
                          • >на помощь приходит умный case: ..., ну ты понял.
                            Я не понял. Объясни пожалуйста.
                            Ответить
                  • >прокрестел
                    Lol'd hardly.
                    >завели 32-байтный массив, символизирующий множество из элементов типа из 256 значений
                    Всё правильно - проставить при инициализации единицы где нужно и возвращать бит по адресу.
                    Ответить
            • > и во вторых я бы 100 раз подумал,
              > стоит ли быть умнее компилятора в оптимизации

              Иногда - стоит... На днях ковырял код видеоплеера - переписал красивый и понятный цикл в жуткое говнополотно с дублированием кода (избегал делений), стало работать примерно в 4 раза быстрее (инфа от VTune Amplifier).

              Но ЗДЕСЬ?.. Что это за проект, в котором проверка гласных букв требует обязательной оптимизации? :)
              Ответить
              • А как раскрытие цикла позволяет избежать делений, можно пример?
                Ответить
                • Там не совсем раскрытие, цикл остался. Проблема была в том, что он был двойным и делал проход одновременно по трём массивам-"плоскостям". Из них две имеют размер вдвое меньший, чем третья (subsampling), так что деления (целочисленные на 2 + взятие остатка) постоянно использовались для пересчёта между сквозным индексом в выходном буфере и условными x,y в трёх исходных. Хоть компилятор и умеет заменять деление на 2 сдвигом, лишнего всё равно делалось дофига, причём постоянно.

                  После переписывания никаких пересчётов индексов нет вообще, зато появилась куча вспомогательных переменных и 90% дублирование кода внутренних циклов.

                  Пример мог бы запостить, но длинновато выйдет.
                  Ответить
                  • Думаю, можно было через подпрограммы убрать дублирование.
                    Ответить
                    • Возможно. Если вдруг не окажется, что их вызовы дают заметный дополнительный оверхед. Но мне 4-кратного прироста пока и так хватило, тем более, что искомые протормозы в итоге оказались вообще в другом месте. :) Оптимизацией ради самой оптимизации не очень увлекаюсь.
                      Ответить
                      • Вызовы инлайнятся
                        Ответить
                        • Только если компилятор так захочет. Ну или всякие непортабельные форсинлайны.
                          Ответить
                  • >Из них две имеют размер вдвое меньший, чем третья (subsampling)
                    I bet it was YV12.
                    Ответить
                    • YCbCr, вроде так. Но я в теорию сильно не вникал, благо всё было написано до меня и работало. Только медленно.
                      Ответить
                      • Просто в YV12 или YUV420.
                        >две имеют размер вдвое меньший
                        Это chroma то есть цветовые компоненты.
                        >чем третья
                        это luma - яркость.
                        Так вот цветовые компоненты обычно пакуют в одну переменную и обрабатываются их пачками ибо так быстрее.
                        Ответить
                        • > chroma, luma

                          Да, оно и есть. Только почему-то libtheora (декодируем ogv) их никуда не пакует, а возвращает в раздельных буферах. Вот и приходится по обоим гулять.

                          Ну или я опять чего-то недопонял.
                          Ответить
                          • >а возвращает в раздельных буферах
                            Так может там вызов такой. Стопудов можно задать output colorspace.
                            libavcodec (который хавает всё что угодно) куда угодно конверт (ибо там есть специальный модуль), хоть в RGB, хоть обратно в YUV.

                            Рекомендую взглянуть на libswscale http://svn.perian.org/ffmpeg/doc/swscale.txt
                            Ответить
                            • Спасибо, покопаю, когда в следующий раз станет актуальным.
                              Ответить
                • Собственно, вот оригинальный цикл. Я таки немного соврал - он не был двойным, а стал двойным после переписывания, но работает быстрее.

                  for (int i = 0; i < buffer.y_width * buffer.y_height; ++i)
                  {
                  int row = i / buffer.y_width;
                  int col = i % buffer.y_width;

                  int yShift = buffer.y_stride * row;
                  int uvShift = buffer.uv_stride * (row / 2);

                  uint8 y_ = *(buffer.y_ + yShift + col);
                  int8 u = 128 ^ *(buffer.u + uvShift + (col / 2));
                  int8 v = 128 ^ *(buffer.v + uvShift + (col / 2));

                  int r = y_ + ((175 * v) / 128);
                  int g = y_ - ((89 * v + 43 * u) / 128);
                  int b = y_ + ((222 * u) / 128);

                  frame_[4 * i + 0] = clampToUInt8(b);
                  frame_[4 * i + 1] = clampToUInt8(g);
                  frame_[4 * i + 2] = clampToUInt8(r);
                  }
                  Ответить
                  • Ну очевидно, что его надо делать двойным, чтобы не считать row и col.
                    И ещё у меня никогда в подобных циклах скорость не упиралась в деление на два. У меня всё упиралось в запись в память (которое frame_).
                    Видимо дело было в одинарном цикле и делении кадый пиксел.
                    Ответить
                    • Да, насколько помню, VTune указывал именно первые две строчки внутри цикла как самые тяжёлые. Ну а раз всё равно переписывать - то и от деления на два уходить по-любому.
                      Ответить
                      • > Да, насколько помню, VTune указывал именно первые две строчки внутри цикла как самые тяжёлые.

                        А после них - память. А сдвиг - 1%. Так что ты зря наговнокодил.
                        Ответить
                  • а еще бы я не считал 4 * i и (col / 2) по нескольку раз
                    Ответить
    • А теперь пример хорошего кода. Не очень производительного, зато понятного. Решение той же задачи с добавлением поддержки поиска любых заданных символов.
      template<class _Elem, class _Traits, class _Ax>
      	inline bool findic(const std::basic_string<_Elem, _Traits, _Ax>& where, const std::basic_string<_Elem, _Traits, _Ax>& what, const std::locale & Loc = std::locale())
      	{
      		return boost::algorithm::to_lower_copy(where).find_first_of(boost::algorithm::to_lower_copy(what)) != std::basic_string<_Elem, _Traits, _Ax>::npos;
      	}
      Ответить
      • не очень хороший код...
        1) Loc то передали, а попользоваться забыли
        2) привязка к std::basic_string, хотя алгоритм спокойно принимает Sequence
        3) многовато to_lower_copy - наверняка с what можно пооптимальней
        Ответить
        • 1) согласен, я написал об этом, но в меня опередили, не увидел
          2) нельзя, т.к. find_first_of исключительно метод класса std::basic_string
          3) ваш вариант в студию
          Ответить
      • забыл только для to_lower_copy передать локаль
        Ответить

    Добавить комментарий