Re[9]: Помогите оценить код - C/C++

Здравствуйте, <Аноним>, Вы писали:

Эх, понеслась!

// Использовал legacy iostream не из STL. Наверно, до того много писал на TurboC++ / BorlandC++ <=5
А>#include <iostream.h>
А>#include <string.h>

// Если уж так хочет использовать _правильные_ типы, то для StrRevTest должен был брать size_t
// А для наколенных решений можно было и int взять.
// Разница вылезет только на huge моделях памяти, где int < ptrdiff_t (x86 huge, ia64 и т.п.)
// Ну так по-любому unsigned int для длины строки там неадекватен.
// Итого: перебдел на ровном месте
А>typedef unsigned int UINT;

// Забавный набор кодов ошибки
А>enum ErrStat
А>{
А>    OK = 0,
А>    SomeStringError = 1000, // почему-то начинающийся с 1000, и кстати, не использующийся
А>    NotANSIString,
А>};

А>//
А>// Функция пеерворачивает символы в строке меняя их местами
А>//
А>ErrStat StrRevTest(char * str)
А>{
А>    char temp = '\0';
А>    UINT StrLen = 0;

// Ловля ошибки защиты памяти плюсовым исключением - ну-ну.
// Проще было включить в контракт этой функции условие о валидности строки
// и умыть руки от юзерских глупостей
// (а вдруг на данной платформе вообще нет защиты памяти?)
А>    try
А>    {
А>        StrLen = strlen(str); // здесь ловится только ошибка чтения
А>    }
А>    catch (...){return NotANSIString;}
А>    UINT StrLenMinOne = StrLen-1; // единичку вычесть - это мы кэшируем,
А>    for (UINT i=0; i<StrLen/2; i++) // а на два делить - это уже нет
А>    {
А>        temp = str[i];
А>        str[i] = str[StrLenMinOne-i]; // а здесь не ловится ошибка записи (строка-константа?)
А>        str[StrLenMinOne-i] = temp;
А>    }
А>    return OK;
А>}
// Выводы:
// 1) недоперебдел с защитой памяти
// 2) заложился на волю компилятора и рантайма (трансляцию signal/SEH на исключения)
// 3) недоперебдел с оптимизацией (привет Дейкстре, кстати - premature и далее по тексту)

// Не знает о стандартной константе CHAR_BIT
// Кстати говоря, её явное использование может помочь лишь для раскрутки цикла
// а можно было написать код, не зависящий от неё
А>#define BYTE_BIT_SIZE 8

А>template <typename T>
А>UINT CalcNumOfBits(T Data)
А>{
А>    UINT Result=0;
// Для популярных платформ - целочисленные типы занимают всю доступную разрядную сетку.
// Но для мифической БЭСМ-6 это уже не так. Можно случайно посчитать биты в мусоре.
// Корректнее было использовать numeric_limits<T>, а кроме того, тем самым мы бы отфильтровали
// использование этой функции на нечисловых типах
А>    for (UINT i=0; i<BYTE_BIT_SIZE*sizeof(T); i++)
А>    {
А>        Result += Data & 0x1;
А>        Data = Data>>1; // как насчёт оператора >>=
// Да, кстати! он осознаёт, как эта штука будет вести себя на знаковых типах?
// На дополнительном коде, в заполненной разрядной сетке, с априорным количеством итераций
// здесь всё работает правильно.
// Убери любое из упомянутых условий - поломается.
А>    }
А>    return Result;
А>}

А>int main (void) // привет голому Си! (void)
А>{
// По поводу AV на строках: предложи заменить char str1[] на char* str1 ;)
А>    char str1[] = "abcdef";
А>    char str2[] = "abcdefg";
А>    StrRevTest(str1);
А>    StrRevTest(str2);
А>    cout<<str1<<endl<<str2<<endl;

// Уж извольте: или UINT, или int. Иначе зачем было городить огород?
А>    int num = CalcNumOfBits(0);
А>    num = CalcNumOfBits(1);
А>    num = CalcNumOfBits(2);
А>    num = CalcNumOfBits(3);
А>    num = CalcNumOfBits(4);
А>    num = CalcNumOfBits(5);
// посчитать посчитали, а вывести забыли :)
А>    int pause;
    cin>>>pause;
А>    return 0;
А>}

Резюме: товарищ не имеет практики программирования.
Он излишне сосредоточился на ненужных вещах, и к тому же сделал их неграмотно. В то же время, упустил вещи нужные.

Под опытным руководством — наверное, научится.
Хотя всё упирается в вопрос: насколько крепко он будет держаться за свой опыт программирования для бормана.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Andrew S, Вы писали:

AS>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"
2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...

AS>В общем, понятно, опять адеквата не увидим.
В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...

AS>>Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits.
AS>>Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

А>не нужно слов — покажите на примере!

Генри Уоррен Младший, страницы 75-76. Учите матчасть.

int pop (unsigned X)
{
    X = X - ( (X >> 1) & 0x55555555);
    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
    X = (X + (X >> 4)) & 0x0F0F0F0F;
    X = X + (X >> 8) ;
    X = X + (X>> 16) ;
    return X & 0x0000003F;
}

Уважаемые форумчане!

Помогите пожалуйста объективно оценить код, и квалификацию программиста который его написал. Было дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку и фунцию подсчёта поднятых битов в байте. Работа проводилась на компьютере, в VC6 примерно 15-20 минут он возился.

#include <iostream.h>
#include <string.h>

typedef unsigned int UINT;
enum ErrStat
{
    OK = 0,
    SomeStringError = 1000,
    NotANSIString,
};

//
// Функция пеерворачивает символы в строке меняя их местами
//
ErrStat StrRevTest(char * str)
{
    char temp = '\0';
    UINT StrLen = 0;
    try
    {
        StrLen = strlen(str);
    }
    catch (...){return NotANSIString;}
    UINT StrLenMinOne = StrLen-1;
    for (UINT i=0; i<StrLen/2; i++)
    {
        temp = str[i];
        str[i] = str[StrLenMinOne-i];
        str[StrLenMinOne-i] = temp;
    }
    return OK;
}

#define BYTE_BIT_SIZE 8

template <typename T>
UINT CalcNumOfBits(T Data)
{
    UINT Result=0;
    for (UINT i=0; i<BYTE_BIT_SIZE*sizeof(T); i++)
    {
        Result += Data & 0x1;
        Data = Data>>1;
    }
    return Result;
}

int main (void)
{
    char str1[] = "abcdef";
    char str2[] = "abcdefg";
    StrRevTest(str1);
    StrRevTest(str2);
    cout<<str1<<endl<<str2<<endl;
    int num = CalcNumOfBits(0);
    num = CalcNumOfBits(1);
    num = CalcNumOfBits(2);
    num = CalcNumOfBits(3);
    num = CalcNumOfBits(4);
    num = CalcNumOfBits(5);
    int pause;
    cin>>pause;
    return 0;
}

Сам не силён, поэтому пишу сюда за объективной оценкой, что можно сказаьт о программисте который это написал?
Спасибо за внимание.

AS>>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.

А>будьте любезны — уж очень хочется заценить

Что за народ пошел — все только просят привести решение, а подумать самим лень

В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно

Здравствуйте, Аноним, Вы писали:

Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.

Здравствуйте, Socket, Вы писали:

>>дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку
S>можно сделать одной строкой зная STL
S>std::string name = "Hello world!!!";

S>reverse(name.begin(),name.end());

Это уже обсуждалось. За reverse двойка тебе — первым делом нужно раскрыть тему std::reverse_iterator (std::string::rbegin, std::string::rend), потом, когда скажут «а разверни-ка эту строку на месте», упомянуть std::reverse, а потом уже, после «+1, но покажи, пожалуйста, свою реализацию», написать что-то вроде

template <class BidirectionalIterator>
void bicycleReverse(BidirectionalIterator first, BidirectionalIterator last)
{
    return implBicycleReverse(first, last, std::iterator_traits<Iter>::iterator_category());
}

template <class RandomAccessIterator>
void implBicycleReverse(RandomAccessIterator first, RandomAccessIterator last, std::random_access_iterator_tag)
{
    while(first < last)
    {
        std::iter_swap(first++, --last);
    }
}

template <class BidirectionalIterator>
void implBicycleReverse(BidirectionalIterator first, BidirectionalIterator last, std::bidirectional_iterator_tag)
{
    while(first != last && first != --last)
    {
        std::iter_swap(first++, last);
    }
}

Здравствуйте, Andrew S, Вы писали:

AS>Генри Уоррен Младший, страницы 75-76. Учите матчасть.

AS>

AS>int pop (unsigned X)
AS>{
AS>    X = X - ( (X >> 1) & 0x55555555);
AS>    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS>    X = (X + (X >> 4)) & 0x0F0F0F0F;
AS>    X = X + (X >> 8) ;
AS>    X = X + (X>> 16) ;
AS>    return X & 0x0000003F;
AS>}
AS>

Ужас.

unsigned char const ones[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, . . . };

unsigned countOnes(uint32_t x)
{
    return 0
        + ones[(x >>  0) & 0xFF]
        + ones[(x >>  8) & 0xFF]
        + ones[(x >> 16) & 0xFF]
        + ones[(x >> 24) & 0xFF]
    ;
}

Здравствуйте, MasterZiv, Вы писали:

MZ>Ладно, раз уж вам так нужно....

>> #include <iostream.h>
>> #include <string.h>

MZ>Эти заголовки давно уже не так
MZ>называются. Ну если второй еще можно (корректно)
MZ>оставлять как <string.h>, то первый по стандарту
MZ><iostream>

MZ>Т.е. это чел либо студент (работал на старых компиляторах),
MZ>либо просто работал на старых компиляторах.
MZ>Хотя работать оно будет.
MZ>Если неправ — поправьте.

Если мне память не изменяет то в 6ой студии так и пишеться.

Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits.
Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

Здравствуйте, Andrew S, Вы писали:

AS>Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits.
AS>Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

не нужно слов — покажите на примере!

Здравствуйте, Andrew S, Вы писали:

AS>>>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
E>>1) ИМХО, не важно знает ли кандидат такой алгоритм или нет.
AS>Опять передергиваете. Перечитайте то, на что отвечаете, нужное выделено.
Ну правда не важно. Важно чтобы программировать умел. А знает какой-то конкретный алгоритм или нет, да какая разница? Не знает -- узнает. А не узнает, то ничего драматического не случится, ИМХО.

AS>Да при чем тут комменты — смысл в том, что надо понимать, что это далеко не оптимальная реализация.

AS>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

AS>Судя по коду (то, что например, это шаблонная функция), кандидат об этом не задумывался.
Вообще-то говоря, какой вопрос, такой и ответ, ИМХО.

AS>Это вопрос не ко мне, а к топиккастеру.
Ну отвечал-то ты

Надеюсь, что теперь тебе понятно с чем я был согласен

Здравствуйте, Andrew S, Вы писали:

AS>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.

AS>>Генри Уоррен Младший, страницы 75-76. Учите матчасть.
AS>>

AS>>int pop (unsigned X)
AS>>{
AS>>    X = X - ( (X >> 1) & 0x55555555);
AS>>    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS>>    X = (X + (X >> 4)) & 0x0F0F0F0F;
AS>>    X = X + (X >> 8) ;
AS>>    X = X + (X>> 16) ;
AS>>    return X & 0x0000003F;
AS>>}
AS>>

RO>Ужас.

Нет. Ужас то, что привели вы, почему — см. ниже. Хотя даже если был бы приведен такой вариант — уже значительно лучше цикла.
RO>

RO>unsigned char const ones[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, . . . };

RO>unsigned countOnes(uint32_t x)
RO>{
RO>    return 0
RO>        + ones[(x >>  0) & 0xFF]
RO>        + ones[(x >>  8) & 0xFF]
RO>        + ones[(x >> 16) & 0xFF]
RO>        + ones[(x >> 24) & 0xFF]
RO>    ;
RO>}
RO>

Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.

        LONGLONG l = QueryPerformanceCounter();
        for (unsigned i = 0; i < 1024*1024;++i)
        {
            pop(i);
        }
        LONGLONG l1 = QueryPerformanceCounter() - l;
        l = QueryPerformanceCounter();
        for (unsigned j = 0; j < 1024*1024;++j)
        {
            countOnes(j);
        }
        LONGLONG l2 = QueryPerformanceCounter() - l;
        cout << (unsigned)l1 << endl;
        cout << (unsigned)l2 << endl;        
// output
23065
42916

Не говоря уже требовании наличия инициализированного не нулями массива (что как минимум увеличивает размер бинарника). Ваш код можно ускорить, если выбирать не char, а unsigned, примерно в 1.5 раза. Но и в этом случае лучше приведенного мной варианта он не стант, а памяти потребует еще больше.
В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.

AS>>

AS>>int pop (unsigned X)
AS>>{
AS>>    X = X - ( (X >> 1) & 0x55555555);
AS>>    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS>>    X = (X + (X >> 4)) & 0x0F0F0F0F;
AS>>    X = X + (X >> 8) ;
AS>>    X = X + (X>> 16) ;
AS>>    return X & 0x0000003F;
AS>>}
AS>>

А>и что, действительно будет быстрее чем обычный цикл вроде
А>

А>template <typename T>
А>unsigned int Bits(T value)
А>{
А>    unsigned int bits = 0;
А>    for (; value > 0; value >>= 1)
А>        bits += (value & 0x1);
А>        return bits;
А>}
А>

А>?

Да. В 5 раз, для unsigned 32 bit.

22866        // pop
42549        // countones
106870       // bits

А>... причем в котором нет привязки к размерности числа

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

А>преждевременная оптимизация — корень всех зла... а приведенный мной пример ну НИКАК не тянет на преждевременную пессимизацию %)

Да-да, это любимая фраза всех лентяев и бездельников

В данном случае существует уже _готовые_ алгоритмы, которые надо просто применить — т.е. стоимость r&d == 0. Так что это именно преждевременная пессимизация.

Здравствуйте, Andrew S, Вы писали:

AS>Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).

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

AS>Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно.
AS>Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...

Там потому функтор, что он же должен таблицу проинициализировать.

А вообще, засунул бы функции в классы и проверил бы сам.

Получается интересно:
3872588475 — хитрые битовые операции
3935120400 — таблица unsigned[65536]

Вывод: твою функцию в топку, мою функцию в топку, использовать std::bitset::count, пока не выяснится, что программа проводит в ней непристойно много времени.

AS>Что за народ пошел — все только просят привести решение, а подумать самим лень

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

AS>В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно

"Назвался груздем — полезай в кузов." Вам представили универсальный работающий пример, вы же утверждаете, что знаете БОЛЕЕ эффективный...
Покажите полный законченый аналог (по работе) и превосходящий по эффективности. Все остальное — слова!

AS>Я показал полный и законченый вариант. Если у Вас не хватает знаний, чтобы это оценить — это Ваши, а не мои, проблемы.
полный, законченый пример для чего? а я думал только для 32 битных значений...

AS>В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.
с каким тоном общения? на неадекватное поведение — последовал адекватный ответ.
еще раз по слогам: без полного, законченного примера все вышесказанное вами только пустая болтовня. кроме как посылать по неизвестному адресу, без каких-либо комментариев к коду (кроме "есть такая книга умная — как, а, вы не читали, учите матчасть" — это как минимум тупые комментарии).

MZ>Зачем давать задания, результат которых вы не в состоянии проверить ?

Отдел только создаётся. Своих программеров что бы проводить собеседование ещё нет, а людей набирать надо. Тестовые задания мы в интернете нашли, а вот с оценкой конечно тяжело

Поэтому и пишу сюда.

Добавлю свои 5 копеек в духе анонима

A>Работа проводилась на компьютере, в VC6...
А за что-нибудь более адекватное нельзя было посадить, хотя бы тот же VC7-8

    try
    {
        StrLen = strlen(str);
    }
    catch (...){return NotANSIString;}

Странное исключение. Если мы передали непонятно что, то кто сказал что оно выкинет (большинство ошибок тупо пропустит). А вот если человек позиционируется как C++ программист (а вывод то потоковый), то строки разумно хранить в std::string, тогда и проверок таких делать не надо, если конечно же иное не было оговорено заданием

#define BYTE_BIT_SIZE 8

Излишнее. Конечно показать что ты заботишься о кроссплатформнности хорошо, но ибо:

template <typename T>
UINT CalcNumOfBits(T Data)
{
    UINT Result=0;
    for (UINT i=0; i<BYTE_BIT_SIZE*sizeof(T); i++)
    {
        Result += Data & 0x1;
        Data = Data>>1;
    }
    return Result;
}

Это конечно замахиывется на работу со сложными типами, да вот

Data & 0x1;

всё выдаёт, уж лучше

while(data)
{
Result += Data & 0x1;
Data = Data>>1;}
}

А вообще если надо было посчитать именно в байте, то для этого есть

unsigned NumOfBitts(char data)
{
   int cnt = 0;
   while(data)
   {
    cnt += data%2;
    data /= 2;
   }
   return cnt;
}

IMHO человек не должен показывать что он знает исключения и шаблоны, а всего лишь наиболее точно выполнять поставленные задачи.

Да, ещё я против любителей UINT и DWORD, но это уже личное

Здравствуйте, <Аноним>, Вы писали:
функция strlen имеет тип size_t. Человек объявил свой тип. стандарт гарантирует, что size_t сможет вместить размер строки, а вот unsigned int. Вполне может быть, что на некоторых платформах эти типы не совпадут.
С другой стороны зачем было вообще в данном случае обявлять свой тип да ещё с именем UINT — во вмогих компиляторах такой тип уже есть...
Потом глюки будете искать

... << RSDN@Home 1.2.0 alpha rev. 727>>

Здравствуйте, Аноним, Вы писали:

[]

А>

А>unsigned NumOfBitts(char data)
А>{
А>   int cnt = 0;
А>   while(data)
А>   {
А>    cnt += data%2;
А>    data /= 2;
А>   }
А>   return cnt;
А>}
А>

а если это проверить так:

NumOfBitts(-1)

Аноним 876 пишет:

> Помогите пожалуйста объективно оценить код, и квалификацию программиста
> который его написал. Было дано небольшое стандртное тестовое задание —

Ладно, раз уж вам так нужно....

> #include <iostream.h>
> #include <string.h>

Эти заголовки давно уже не так
называются. Ну если второй еще можно (корректно)
оставлять как <string.h>, то первый по стандарту
<iostream>

Т.е. это чел либо студент (работал на старых компиляторах),
либо просто работал на старых компиляторах.
Хотя работать оно будет.
Если неправ — поправьте.

> enum ErrStat
> {
> OK = 0,
> SomeStringError = 1000,
> NotANSIString,
> };

> ErrStat StrRevTest(char * str)
> {
> char temp = '\0';
> UINT StrLen = 0;
> try
> {
> StrLen = strlen(str);
> }
> catch (...){return NotANSIString;}

Бред полный перехватывать тут исключения — их
не будет.

> UINT StrLenMinOne = StrLen-1;
> for (UINT i=0; i<StrLen/2; i++)
> {
> temp = str[i];
> str[i] = str[StrLenMinOne-i];
> str[StrLenMinOne-i] = temp;
> }
> return OK;
> }

Но алгоритмы-то он нормально написал. По-моему это главное.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, Аноним, Вы писали:

MZ>>Зачем давать задания, результат которых вы не в состоянии проверить ?
А>Отдел только создаётся. Своих программеров что бы проводить собеседование ещё нет, а людей набирать надо. Тестовые задания мы в интернете нашли, а вот с оценкой конечно тяжело

Поэтому и пишу сюда.
Так создавайте в отделе о работе новую вакансию "Нужен человек для проверки тестовых заданий"

A>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.

Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)

A>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.

Кстати да, вопрос соотношения цена/качество как-то был упущен из виду

Здравствуйте, <Аноним>, Вы писали:

А>Так создавайте в отделе о работе новую вакансию "Нужен человек для проверки тестовых заданий"

А его кто будет тестировать? RSDN DDos Team?

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Аноним, Вы писали:

А>Сам не силён, поэтому пишу сюда за объективной оценкой, что можно сказаьт о программисте который это написал?
А>Спасибо за внимание.
1. У тестируемого наблюдается бардак в такой важной области C++ как обработка ошибок. Он намешал обработку исключений с кодами возврата. Причём и то и другое применил, во-первых, не к месту, во-вторых с недочётами. Не к месту, так как в данном случае вообще не требуется обработка ошибок. Недочёты: объявлен какой-то непонятный нигде не используемый код SomeStringError, использована конструкция catch (...), которая свидетельствует о неправильном поминании идеологии исключений.
Возможно, тестируемый хотел как-то показать, что он слышал об обработке ошибок, и даже знает о существовании двух стратегий. Но пытаясь "выпендриться", он сделал некачественный код, вместо того, чтобы просто выполнить задание. Это плохо, так как в новой команде он тоже возможно начнёт "выпендриваться" в ущерб проекта.
2. Видно, что программист видел только одну реализацию C++ (msvc). Хотя и пытается писать переносимый/обобщённый код, но это у него плохо получается (см. пост Аноним 7). Само по себе, отсутсвие опыта работы с другими реализациями C++, не так уж страшно, особенно, если нет требований к переносимости. Но это говорит об определянной ограниченности кругозора, о небольшом опыте работы с библиотеками C++. У толкового человека, осознанно работавшего с коммерческими библиотеками, наверняка бы сложилось понимание, когда нужно объявлять собственный UINT и BYTE_BIT_SIZE, а когда — нет.
3. Тестируемый неясно выражает свои мысли:
// Функция пеерворачивает символы в строке меняя их местами
Если бы я не прочитал начало поста, я бы не понял этого комментария.

Диагноз: junior developer.

>дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку
можно сделать одной строкой зная STL
std::string name = "Hello world!!!";

reverse(name.begin(),name.end());

Здравствуйте, Socket, Вы писали:

>>дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку
S>можно сделать одной строкой зная STL
S>std::string name = "Hello world!!!";

S>reverse(name.begin(),name.end());

В данном случае stl имеет смысл использовать, если можно сразу показать проверяющему и он скажет — достаточно этого или свою реализацию написать.
Здесь совсем другая ситуация.
Хотя наверное имеет смысл писать свою реализацию, а где-нибудь внизу указать, что "я ещё и так могу".

Здравствуйте, Аноним, Вы писали:

A>>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.

А>Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)

Скорее всего он у вас будет нормально работать и справляться со своими задачами. Какого-то супер-кода и чёткой структуры программ ждать не приходится.

Здравствуйте, MasterZiv, Вы писали:

>> catch (...){return NotANSIString;}
MZ>Бред полный перехватывать тут исключения — их
MZ>не будет.
В 7-ой студии это сехи ловит

Здравствуйте, <Аноним>, Вы писали:

А>В 7-ой студии это сехи ловит

... если ключик указать. И в любой другой, если потанцевать с бубном.

... << RSDN@Home 1.2.0 alpha rev. 655>>

А Егор-то с чем не согласен, или просто так, пнуть из принципа? А может, демонстрируем незнание простейших bittricks?

AS>>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.

E>ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.

Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
В общем, понятно, опять адеквата не увидим.

AS>

AS>int pop (unsigned X)
AS>{
AS>    X = X - ( (X >> 1) & 0x55555555);
AS>    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS>    X = (X + (X >> 4)) & 0x0F0F0F0F;
AS>    X = X + (X >> 8) ;
AS>    X = X + (X>> 16) ;
AS>    return X & 0x0000003F;
AS>}
AS>

и что, действительно будет быстрее чем обычный цикл вроде

template <typename T>
unsigned int Bits(T value)
{
    unsigned int bits = 0;
    for (; value > 0; value >>= 1)
        bits += (value & 0x1);
        return bits;
}

... причем в котором нет привязки к размерности числа

преждевременная оптимизация — корень всех зла... а приведенный мной пример ну НИКАК не тянет на преждевременную пессимизацию %)

Здравствуйте, Andrew S, Вы писали:

AS>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.

ICC 10
P4 630

Колво циклов увеличил до 1024^3 — бо выполняется слишком быстро

15318209580
8983055617

AS>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.

pop

  00031 8b ee            mov ebp, esi                           ;.\test.cpp:39.6
  00033 d1 ed            shr ebp, 1                             ;.\test.cpp:39.6
  00035 81 e5 55 55 55 
        55               and ebp, 1431655765                    ;.\test.cpp:39.6
$LN9:
  0003b f7 dd            neg ebp                                ;.\test.cpp:39.10
  0003d 03 ee            add ebp, esi                           ;.\test.cpp:39.10
$LN11:
  0003f 8b c5            mov eax, ebp                           ;.\test.cpp:39.6
  00041 25 33 33 33 33   and eax, 858993459                     ;.\test.cpp:39.6
  00046 c1 ed 02         shr ebp, 2                             ;.\test.cpp:39.6
  00049 81 e5 33 33 33 
        33               and ebp, 858993459                     ;.\test.cpp:39.6
  0004f 03 c5            add eax, ebp                           ;.\test.cpp:39.6
  00051 8b f8            mov edi, eax                           ;.\test.cpp:39.6
  00053 c1 ef 04         shr edi, 4                             ;.\test.cpp:39.6
  00056 03 c7            add eax, edi                           ;.\test.cpp:39.6
  00058 25 0f 0f 0f 0f   and eax, 252645135                     ;.\test.cpp:39.6
  0005d 8b e8            mov ebp, eax                           ;.\test.cpp:39.6
  0005f c1 ed 08         shr ebp, 8                             ;.\test.cpp:39.6
  00062 03 c5            add eax, ebp                           ;.\test.cpp:39.6
  00064 8b e8            mov ebp, eax                           ;.\test.cpp:39.6
  00066 c1 ed 10         shr ebp, 16                            ;.\test.cpp:39.6
  00069 03 c5            add eax, ebp                           ;.\test.cpp:39.6
  0006b 83 e0 3f         and eax, 63                            ;.\test.cpp:39.6

countOnes

  0009a 0f b6 e8         movzx ebp, al                          ;.\test.cpp:48.6
  0009d 0f b6 95 00 00 
        00 00            movzx edx, BYTE PTR ?ones$0@@4QBEB[ebp] ;.\test.cpp:48.6
  000a4 8b e8            mov ebp, eax                           ;.\test.cpp:48.6
  000a6 c1 ed 08         shr ebp, 8                             ;.\test.cpp:48.6
  000a9 81 e5 ff 00 00 
        00               and ebp, 255                           ;.\test.cpp:48.6
  000af 0f b6 ad 00 00 
        00 00            movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp] ;.\test.cpp:48.6
$LN37:
  000b6 03 d5            add edx, ebp                           ;.\test.cpp:48.3
$LN39:
  000b8 8b e8            mov ebp, eax                           ;.\test.cpp:48.6
  000ba c1 ed 10         shr ebp, 16                            ;.\test.cpp:48.6
  000bd 81 e5 ff 00 00 
        00               and ebp, 255                           ;.\test.cpp:48.6
  000c3 0f b6 ad 00 00 
        00 00            movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp] ;.\test.cpp:48.6
  000ca 03 d5            add edx, ebp                           ;.\test.cpp:48.6
  000cc 8b e8            mov ebp, eax                           ;.\test.cpp:48.6
  000ce c1 ed 18         shr ebp, 24                            ;.\test.cpp:48.6
  000d1 0f b6 ad 00 00 
        00 00            movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp] ;.\test.cpp:48.6
  000da 8d 1c 2a         lea ebx, DWORD PTR [edx+ebp]           ;.\test.cpp:48.6

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

AS>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.

будьте любезны — уж очень хочется заценить

AS>>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.

CC>ICC 10
CC>P4 630

CC>Колво циклов увеличил до 1024^3 — бо выполняется слишком быстро

CC>15318209580
CC>8983055617

AS>>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.
CC>

Да пожалуйста, тоже увеличил.

Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое.
Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.

А это мои, VC 7.1
Pop

    mov    ecx, edx
    shr    ecx, 1
    and    ecx, 1431655765                ; 55555555H
    mov    eax, edx
    sub    eax, ecx
    mov    ecx, eax
    shr    ecx, 2
    and    ecx, 858993459                ; 33333333H
    and    eax, 858993459                ; 33333333H
    add    ecx, eax
    mov    eax, ecx
    shr    eax, 4
    add    eax, ecx
    and    eax, 252645135                ; 0f0f0f0fH
    mov    ecx, eax
    shr    ecx, 8
    add    eax, ecx
    mov    ecx, eax
    shr    ecx, 16                    ; 00000010H
    add    ecx, eax
    and    ecx, 63                    ; 0000003fH

countOnes

    lea    edx, DWORD PTR [eax-1]
    mov    ebx, edx
    shr    ebx, 24                    ; 00000018H
    movzx    ebx, BYTE PTR _ones[ebx]
    lea    esi, DWORD PTR [eax-2]
    mov    DWORD PTR tv1199[esp+48], esi
    shr    esi, 24                    ; 00000018H
    movzx    esi, BYTE PTR _ones[esi]
    add    esi, ebx
    lea    ecx, DWORD PTR [eax+1]
    mov    ebx, ecx
    shr    ebx, 24                    ; 00000018H
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    lea    ebx, DWORD PTR [eax-2]
    and    ebx, 255                ; 000000ffH
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    lea    ebx, DWORD PTR [eax-1]
    and    ebx, 255                ; 000000ffH
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    mov    ebx, eax
    shr    ebx, 24                    ; 00000018H
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    movzx    ebx, ah
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    movzx    ebx, BYTE PTR tv1023[esp+50]
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    movzx    ebx, ch
    movzx    ebx, BYTE PTR _ones[ebx]
    mov    DWORD PTR tv1192[esp+48], edx
    add    esi, ebx
    movzx    edx, dh
    movzx    edx, BYTE PTR _ones[edx]
    mov    DWORD PTR tv1180[esp+48], ecx
    movzx    ebx, BYTE PTR tv1180[esp+50]
    movzx    ebx, BYTE PTR _ones[ebx]
    add    esi, ebx
    add    esi, edx
    movzx    edx, BYTE PTR tv1192[esp+50]
    movzx    edx, BYTE PTR _ones[edx]
    add    esi, edx
    movzx    edx, BYTE PTR tv1199[esp+49]
    movzx    edx, BYTE PTR _ones[edx]
    add    esi, edx
    movzx    edx, BYTE PTR tv1199[esp+50]
    movzx    edx, BYTE PTR _ones[edx]
    and    ecx, 255                ; 000000ffH
    movzx    ecx, BYTE PTR _ones[ecx]
    add    esi, edx
    mov    edx, eax
    add    esi, ecx
    and    edx, 255                ; 000000ffH
    movzx    ecx, BYTE PTR _ones[edx]

Как мы видим, тут просто развернули цикл (пачками по 4). Полагаю, IC сделал примерно то же, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).
Т.о., сравнение в данном случае получается не слишком некорректным (а точнее, вообще некорретным) — в реальном применении цикл гораздо сложнее и развернуть его таким образом не получится. Правильнее всего в смысле теста поступает VC6 — он тупо компилит то, что ему написали

Здравствуйте, Andrew S, Вы писали:

AS>>>Генри Уоррен Младший, страницы 75-76. Учите матчасть.
RO>>Ужас.
AS>Нет. Ужас то, что привели вы, почему — см. ниже. Хотя даже если был бы приведен такой вариант — уже значительно лучше цикла.
RO>>unsigned char const ones[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, . . . };

AS>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.

AS>// output
AS>23065
AS>42916
AS>Не говоря уже требовании наличия инициализированного не нулями массива (что как минимум увеличивает размер бинарника). Ваш код можно ускорить, если выбирать не char, а unsigned, примерно в 1.5 раза. Но и в этом случае лучше приведенного мной варианта он не стант, а памяти потребует еще больше.
AS>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.

О ужас! 256 байт.

Мой код имеет премущество совсем в другом. По нему понятно, что он делает. Если допустить ошибку в твоем, то можно доолго ее искать. Ну, и premature optimization…

По поводу того, что мой код якобы не имеет возможностей для оптимизации компилятором:

unsigned countOnesSmartly(unsigned X)
{
    X = X - ( (X >> 1) & 0x55555555);
    X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
    X = (X + (X >> 4)) & 0x0F0F0F0F;
    X = X + (X >> 8) ;
    X = X + (X>> 16) ;
    return X & 0x0000003F;
}

unsigned countOnesLamely(unsigned x)
{
    unsigned res = 0;
    while(x)
    {
        x &= x - 1;
        ++res;
    }
    return res;
}

class OnesCounter
{
public:
    OnesCounter()
    {
        for(unsigned i = 0; i < 65536; ++i)
        {
            table[i] = countOnesLamely(i);
        }
    }

    unsigned operator()(unsigned x) const
    {
        return table[x & 0xFFFF] + table[x >> 16];
    }

private:
    unsigned table[65536];
};


template <class F>
inline LONGLONG getLargeInt(F func)
{
    LARGE_INTEGER tmp;
    func(&tmp);
    return tmp.QuadPart;
}

template <class It, class F>
LONGLONG benchmark(It first, It last, F f, unsigned& dummy)
{
    LONGLONG const t1 = getLargeInt(QueryPerformanceCounter);
    while(first != last)
    {
        dummy += f(*first++);
    }
    LONGLONG const t2 = getLargeInt(QueryPerformanceCounter);

    return t2 - t1;
}

int main()
{
    unsigned const sampleSize = 0x08000000;
    std::vector<unsigned> data(sampleSize);

    // Ваши с CreatorCray варианты дают мне поблажку, позволяя менеджеру кеша загружать таблицу по частям.
    std::generate(data.begin(), data.end(), boost::bind(boost::uniform_int<unsigned>(0u, 0xFFFFFFFFu), boost::mt19937()));

    unsigned dummy = 0;

    LONGLONG const tLame  = benchmark(data.begin(), data.end(), countOnesLamely, dummy);
    LONGLONG const tSmart = benchmark(data.begin(), data.end(), countOnesSmartly, dummy);
    LONGLONG const tTable = benchmark(data.begin(), data.end(), OnesCounter(), dummy);

    std::cout << tLame  << std::endl;
    std::cout << tSmart << std::endl;
    std::cout << tTable << std::endl;

    std::cout << (dummy == 42 ? ' ' : '\t') << std::endl;
}

VC8 -Oxb2:
16433597970
5235748897
3936869895

MinGW 3.4.2 -O3:
14762037345
4396007865
2606004375

RO>О ужас! 256 байт.

Ага, и так на каждый чих? Ну да, верно, поэтому и получаем то, что получаем — гигантские и на 99% бесполезные исполняемые модули...

RO>Мой код имеет премущество совсем в другом. По нему понятно, что он делает. Если допустить ошибку в твоем, то можно доолго ее искать. Ну, и premature optimization…

Тут я согласен. Для этих целей надо просто привести начальный (т.е. цикл со сдвигом) код в комментах функции, либо краткое описание алгоритма — он действительно очень прост.
А сампл.. Ну да, действительно, тут получалась последовательная выборка из таблица, что VC 71 заметил и "наоптимизировал".

RO>По поводу того, что мой код якобы не имеет возможностей для оптимизации компилятором:

\code skipped\

Ну, это уже совсем не весело — 256 кб пустоты для такой мелкой функции. Почему бы тогда уж 4 гб таблицу не сделать?

А по поводу результатов — для начала надо убедиться, что в данном случае сам инструмент измерений не вносит большой погрешности, как в моем варианте с VC71, когда раскручивался цикл. Т.е. смотреть нативный код — надо добиваться, чтобы _всем_ вариантам были предоставлены одинаковые условия. Например, для меня совсем не очевидно, что 256 кб таблица будет быстрее 1 кб — тут уже проблемы с кешем даже второго уровня начнутся.
А нативного кода я тут не приметил

Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).

Вот, что получается с OnesCounter.

??$benchmark@Viterator@?$vector@IV?$allocator@I@std@@@std@@VOnesCounter >::iterator,OnesCounter>, COMDAT

; 318  : {

    sub    esp, 16                    ; 00000010H
    push    esi
    push    edi

; 319  :     LONGLONG const t1 = getLargeInt(QueryPerformanceCounter);

    mov    edi, DWORD PTR __imp__QueryPerformanceCounter@4
    lea    eax, DWORD PTR _tmp$74373[esp+24]
    push    eax
    call    edi

; 320  :     while(first != last)

    mov    ecx, DWORD PTR _first$[esp+20]
    mov    esi, DWORD PTR _last$[esp+20]
    cmp    ecx, esi
    je    SHORT $L71530
    mov    edx, DWORD PTR _dummy$[esp+20]
    push    ebx
    push    ebp
$L71529:

; 321  :     {
; 322  :         dummy += f(*first++);

    mov    eax, ecx
    mov    eax, DWORD PTR [eax]
    mov    ebx, eax
    and    eax, 65535                ; 0000ffffH
    mov    ebp, DWORD PTR _f$[esp+eax*4+28]
    mov    eax, DWORD PTR [edx]
    shr    ebx, 16                    ; 00000010H
    mov    ebx, DWORD PTR _f$[esp+ebx*4+28]
    add    ebx, ebp
    add    ecx, 4
    add    eax, ebx
    cmp    ecx, esi
    mov    DWORD PTR [edx], eax
    jne    SHORT $L71529
    pop    ebp
    pop    ebx
$L71530:

; 323  :     }
; 324  :     LONGLONG const t2 = getLargeInt(QueryPerformanceCounter);

    lea    ecx, DWORD PTR _tmp$74407[esp+24]
    push    ecx
    call    edi

; 325  : 
; 326  :     return t2 - t1;

    mov    edx, DWORD PTR _tmp$74373[esp+24]
    mov    eax, DWORD PTR _tmp$74407[esp+24]
    mov    ecx, DWORD PTR _tmp$74373[esp+28]
    sub    eax, edx
    mov    edx, DWORD PTR _tmp$74407[esp+28]
    pop    edi
    sbb    edx, ecx
    pop    esi

; 327  : }

    add    esp, 16                    ; 00000010H
    ret    0
??$benchmark@Viterator@?$vector@IV?$allocator@I@std@@@std@@VOnesCounter>::iterator,OnesCounter>

а вот что с остальными измерениями:

??$benchmark@Viterator@?$vector@IV?$allocator@I@std@@@std@@P6AII@Z(__cdecl*)(unsigned int)>, COMDAT

; 318  : {

    sub    esp, 16                    ; 00000010H
    push    ebx
    push    esi

; 319  :     LONGLONG const t1 = getLargeInt(QueryPerformanceCounter);

    lea    eax, DWORD PTR _tmp$74333[esp+24]
    push    eax
    call    DWORD PTR __imp__QueryPerformanceCounter@4

; 320  :     while(first != last)

    mov    esi, DWORD PTR _first$[esp+20]
    mov    ebx, DWORD PTR _last$[esp+20]
    cmp    esi, ebx
    je    SHORT $L71523
    push    ebp
    mov    ebp, DWORD PTR _f$[esp+24]
    push    edi
    mov    edi, DWORD PTR _dummy$[esp+28]
$L71522:

; 321  :     {
; 322  :         dummy += f(*first++);

    mov    eax, esi
    mov    ecx, DWORD PTR [eax]
    push    ecx
    add    esi, 4
    call    ebp
    mov    ecx, DWORD PTR [edi]
    add    ecx, eax
    add    esp, 4
    cmp    esi, ebx
    mov    DWORD PTR [edi], ecx
    jne    SHORT $L71522
    pop    edi
    pop    ebp
$L71523:

; 323  :     }
; 324  :     LONGLONG const t2 = getLargeInt(QueryPerformanceCounter);

    lea    edx, DWORD PTR _tmp$74363[esp+24]
    push    edx
    call    DWORD PTR __imp__QueryPerformanceCounter@4

; 325  : 
; 326  :     return t2 - t1;

    mov    edx, DWORD PTR _tmp$74333[esp+24]
    mov    eax, DWORD PTR _tmp$74363[esp+24]
    mov    ecx, DWORD PTR _tmp$74333[esp+28]
    sub    eax, edx
    mov    edx, DWORD PTR _tmp$74363[esp+28]
    pop    esi
    sbb    edx, ecx
    pop    ebx

; 327  : }

    add    esp, 16                    ; 00000010H
    ret    0
??$benchmark@Viterator@?$vector@IV?$allocator@I@std@@@std@@P6AII@Z(__cdecl*)(unsigned int)>

Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно.
Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...

AS>>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
E>1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"

Опять передергиваете. Перечитайте то, на что отвечаете, нужное выделено.

E>2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...

Да при чем тут комменты — смысл в том, что надо понимать, что это далеко не оптимальная реализация. Судя по коду (то, что например, это шаблонная функция), кандидат об этом не задумывался.

AS>>В общем, понятно, опять адеквата не увидим.
E>В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...

Это вопрос не ко мне, а к топиккастеру. Хотя за ту сумму, что он озвучил, откомментировав ее как "средняя по городу вообще (а не для IT)" — думаю, вполне нормально. Хотя, конечно, задания таковы, что по ним определнно сказать что-либо сложно.

RO>А вообще, засунул бы функции в классы и проверил бы сам.
RO>Получается интересно:
RO>3872588475 — хитрые битовые операции
RO>3935120400 — таблица unsigned[65536]

Ну дык я, конечно, проверил

У меня на самом деле получился твой вариант быстрее процентов на 20, чем приведенный мной. Но ввиду оверхеда на память, который он привносит, а также некоторых других "мелочей" (например, чтение сампла из памяти тоже приличный оверхед для приведенного мной алгоритма) полагаю, что по производительности они примерно равны на текущих "обычных" системах, а вот по функциональности приведенный мной вариант выигрывает _значительно_. Хочу напомнить, что это ни в коем случае не мой вариант, я лишь "разместил объяву". Авторство (а точнее, точку инстанцирования) я указал ранее.

RO>Вывод: твою функцию в топку, мою функцию в топку, использовать std::bitset::count, пока не выяснится, что программа проводит в ней непристойно много времени.

Ну... Кому что. Я работаю в области, где часто требуется эффективность, поэтому для меня подобные спички часто бывают актуальны. Впрочем, задачи, где бы требовалось подсчитать (именно подсчитать) количество единичных бит мне пока что не встречалось, так что все это имеет чисто академический интерес. Но знать о подобных алгоритмах, имхо, просто необходимо.
Например, в том же bitset::count во многих реализациях используется табличный метод (группы по 4-8 бит). Т.е. используй кандидат битсет, получил бы примерно в 2-3 раза более эффективную функцию вообще безо всяких усилий.

Здравствуйте, Andrew S, Вы писали:

AS>Да пожалуйста, тоже увеличил.
AS>

AS>VC6
AS>23384774
AS>43100993
AS>VC7.1
AS>17996589
AS>20148363
AS>

AS>Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое.
AS>Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.
Улучшить? Да он его хреново скомпилил.
Сравни:

AS>countOnes
AS>

AS>    lea    edx, DWORD PTR [eax-1]
AS>    mov    ebx, edx
AS>    shr    ebx, 24                    ; 00000018H
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    lea    esi, DWORD PTR [eax-2]
AS>    mov    DWORD PTR tv1199[esp+48], esi
AS>    shr    esi, 24                    ; 00000018H
AS>    movzx    esi, BYTE PTR _ones[esi]
AS>    add    esi, ebx
AS>    lea    ecx, DWORD PTR [eax+1]
AS>    mov    ebx, ecx
AS>    shr    ebx, 24                    ; 00000018H
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    lea    ebx, DWORD PTR [eax-2]
AS>    and    ebx, 255                ; 000000ffH
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    lea    ebx, DWORD PTR [eax-1]
AS>    and    ebx, 255                ; 000000ffH
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    mov    ebx, eax
AS>    shr    ebx, 24                    ; 00000018H
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    movzx    ebx, ah
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    movzx    ebx, BYTE PTR tv1023[esp+50]
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    movzx    ebx, ch
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    mov    DWORD PTR tv1192[esp+48], edx
AS>    add    esi, ebx
AS>    movzx    edx, dh
AS>    movzx    edx, BYTE PTR _ones[edx]
AS>    mov    DWORD PTR tv1180[esp+48], ecx
AS>    movzx    ebx, BYTE PTR tv1180[esp+50]
AS>    movzx    ebx, BYTE PTR _ones[ebx]
AS>    add    esi, ebx
AS>    add    esi, edx
AS>    movzx    edx, BYTE PTR tv1192[esp+50]
AS>    movzx    edx, BYTE PTR _ones[edx]
AS>    add    esi, edx
AS>    movzx    edx, BYTE PTR tv1199[esp+49]
AS>    movzx    edx, BYTE PTR _ones[edx]
AS>    add    esi, edx
AS>    movzx    edx, BYTE PTR tv1199[esp+50]
AS>    movzx    edx, BYTE PTR _ones[edx]
AS>    and    ecx, 255                ; 000000ffH
AS>    movzx    ecx, BYTE PTR _ones[ecx]
AS>    add    esi, edx
AS>    mov    edx, eax
AS>    add    esi, ecx
AS>    and    edx, 255                ; 000000ffH
AS>    movzx    ecx, BYTE PTR _ones[edx]
AS>

movzx ebp, al
movzx edx, BYTE PTR ?ones$0@@4QBEB[ebp]
mov ebp, eax
shr ebp, 8
and ebp, 255
movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp]
add edx, ebp
mov ebp, eax
shr ebp, 16
and ebp, 255
movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp]
add edx, ebp
mov ebp, eax
shr ebp, 24
movzx ebp, BYTE PTR ?ones$0@@4QBEB[ebp]
lea ebx, DWORD PTR [edx+ebp]

AS>Как мы видим, тут просто развернули цикл (пачками по 4).
AS>Полагаю, IC сделал примерно то же
Как ты сам можешь видеть — ICC ничего не разворачивал.
AS>, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).

Вообще результат компиляции countOnes вижуалкой кроме как кошмарным назвать не могу. Зачем он лишний раз читает/пишет в tv1<xxx>? И что это вообще за переменные то? В результате больше обращений к памяти чем нужно.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

AS>>В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно

А>"Назвался груздем — полезай в кузов." Вам представили универсальный работающий пример, вы же утверждаете, что знаете БОЛЕЕ эффективный...
А>Покажите полный законченый аналог (по работе) и превосходящий по эффективности. Все остальное — слова!

Я показал полный и законченый вариант. Если у Вас не хватает знаний, чтобы это оценить — это Ваши, а не мои, проблемы.

В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.

AS>>Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое.
AS>>Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.
CC>Улучшить? Да он его хреново скомпилил.

Именно _улучшить_. Там пачки по 4, внимательно изучите код.

AS>>Как мы видим, тут просто развернули цикл (пачками по 4).
AS>>Полагаю, IC сделал примерно то же
CC>Как ты сам можешь видеть — ICC ничего не разворачивал.
AS>>, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).

CC>Вообще результат компиляции countOnes вижуалкой кроме как кошмарным назвать не могу. Зачем он лишний раз читает/пишет в tv1<xxx>? И что это вообще за переменные то? В результате больше обращений к памяти чем нужно.

Это временные переменные, в которых он собирает часть результата. На самом деле, операции со стеком в последних процессорах оптимизированы (по моим тестам, проигрыш с такими обращениями даже в основном цикле получается небольшой — порядка 7-10 процентов). К сожалению, ic у меня нет, поэтому проверить, как работает его вариант на нормальных платформах (а P4 считать за нормальную платформу сложно) я не могу. Если, конечно, бинарник кто-нибудь не выложит

Ну и опять же — варианту Романа в данном тесте, как он сам и заметил, предоставляются "тепличные" условия — упорядоченное чтение. Лучше бы вы попробовали сампл Романа, заменив функции на функторы — там получается несколько правильнее.

Здравствуйте, Andrew S, Вы писали:

AS>В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.

Вообще-то задача выбора констант, вернее выбора момента с которого константы уже не нужны в CT не такая уж и тривильная, ИМХО...
Хотя наверное можно как-то извратиться

В конце концов протабулировать всё до 2048-битных чисел, например

AS>>В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.

E>Вообще-то задача выбора констант, вернее выбора момента с которого константы уже не нужны в CT не такая уж и тривильная, ИМХО...

?? В алгоритме количество шагов равно log(bit_count). Все константы на каждом шаге вычисляются как зависимость от номера шага, а результат на текущем шаге — это сумма резальтатов предыдущих шагов. Первые 3 шага (которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм. На последнем шаге выполняется отсечение частичной суммы предыдущего шага. А в целом — алгоритм рекурсивный, банальный бинарный спуск. Все это _реализуемо_ на шаблонах в CT, и результат будет полностью аналогичен "ручному" кодированию. Но тратить свое время запросто так, чтобы ублажить господина Анонима — не хочется. Поскольку ему нужен совсем не результат, это же очевидно

Здравствуйте, Andrew S, Вы писали:

AS>...(которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм...

Собственно я про то, что начиная с какой-то длинны целого (типа 256-битное) надо не забыть сделать &0x00FF00FF00FF00FF...00FF.
Ну и сами константы сегенрить тоже надо, кстати.

Аноним 617 пишет:
> В 7-ой студии это сехи ловит

Так ловить-то оно ловит, а откуда там SEH-и будут ?
Ну если ей конечно 0x01 в качестве адреса строки дать,
оно GPF даст — да. Но если просто бесконечную строку
дать, почешет по памяти до первого '\0' и не фект что
до GPF его не найдет.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, <Аноним>, Вы писали:

A>>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.
А>Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)

Это где нонче такое? Да так, что там на такую зарплату программистов в штат набирают???

С Уважением, Andir!

using( RSDN@Home 1.2.0 alpha rev. 717 ) { /* Работаем */ }

AS>>...(которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм...

E>Собственно я про то, что начиная с какой-то длинны целого (типа 256-битное) надо не забыть сделать &0x00FF00FF00FF00FF...00FF.
E>Ну и сами константы сегенрить тоже надо, кстати.

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

template <int nCount>
struct EnumConstHelper
{
    template <class T>
    struct Dummy
    {
        enum {value = T::value};
    };
};

template <>
struct EnumConstHelper<0>
{
    template <class T>
    struct Dummy
    {
        enum {value = 0};
    };
};


template <class T, int nVal>
struct EnumConst
{
    template <int nCount>
    struct EnumConstImpl
    {
        enum {value = ((nVal << ((nCount - 1)*CHAR_BIT)) | EnumConstHelper<nCount-1>::Dummy<EnumConstImpl<nCount - 1> >::value)};
    };
    enum {value = EnumConstImpl<sizeof(T)>::value};
};


template <int iLevel>
struct CountBitsImpl
{
    template <class T>
    static unsigned DoCount(T X)
    {
        X = CountBitsImpl<iLevel - 1>::DoCount(X);
        return X + (X >> (1 << (iLevel))) ;
    }
};


template <>
struct CountBitsImpl<0>
{
    template <class T>
    static unsigned DoCount(T X)
    {
        return X - ( (X >> 1) & EnumConst<T, 0x55>::value);
    }
};

template <>
struct CountBitsImpl<1>
{
    template <class T>
    static unsigned DoCount(T X)
    {
        X = CountBitsImpl<0>::DoCount(X);
        return (X & EnumConst<T, 0x33>::value) + ((X >> 2) & EnumConst<T, 0x33>::value);
    }
};

template <>
struct CountBitsImpl<2>
{
    template <class T>
    static unsigned DoCount(T X)
    {
        X = CountBitsImpl<1>::DoCount(X);
        return (X + (X >> 4)) & EnumConst<T, 0x0F>::value;
    }
};


template <int nVal>
struct CountLevelImpl
{
    enum {value = CountLevelImpl<nVal/2>::value + 1};
};

template <>
struct CountLevelImpl<0>
{
    enum {value = 0};
};

template <int nVal>
struct CountLevel
{
    enum {value = CountLevelImpl<nVal>::value  - 1};
};

template <>
struct CountLevel<0>
{
};


template <class T>
unsigned CountBits(T X)
{
    return CountBitsImpl<CountLevel<sizeof(T)*CHAR_BIT>::value - 1>::DoCount(X) & (((unsigned)-1) >> (sizeof(int)*CHAR_BIT - CountLevel<sizeof(LONGLONG)*CHAR_BIT>::value));
};

Наверное, можно и красивее реализовать (особенно EnumConst, который заточен под VC6 — очевидным образом там надо const T value вместо enum использовать), но думать над этим откровенно не хочется.

	От:	MasterZiv
	Дата:	27.08.07 13:05
	Оценка:	1 (1) +6

	От:	Кодт
	Дата:	27.08.07 13:37
	Оценка:	3 (3) +1

	От:	Erop
	Дата:	28.08.07 18:34
	Оценка:	2 (2) +2

От:	Andrew S	http://alchemy-lab.com
Дата:	28.08.07 12:11
Оценка:	9 (2)

	От:	Аноним
	Дата:	27.08.07 12:33
	Оценка:

	От:	Roman Odaisky
	Дата:	28.08.07 08:01
	Оценка:	4 (2)

	От:	__SPIRIT__
	Дата:	06.09.07 15:01
	Оценка:	1 (1) +1

От:	Phoenics	https://sourceforge.net/projects/phengine
Дата:	27.08.07 14:28
Оценка:

От:	Socket	http://www.samborsky.com
Дата:	28.08.07 05:55
Оценка:

От:	Andir	http://twitter.com/AndirNotes
Дата:	29.08.07 10:40
Оценка: