Помогите пожалуйста объективно оценить код, и квалификацию программиста который его написал. Было дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку и фунцию подсчёта поднятых битов в байте. Работа проводилась на компьютере, в 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;
}
Сам не силён, поэтому пишу сюда за объективной оценкой, что можно сказаьт о программисте который это написал?
Спасибо за внимание.
Аноним 876 пишет: > Сам не силён, поэтому пишу сюда за объективной оценкой, что можно > сказаьт о программисте который это написал?
Зачем давать задания, результат которых вы не в состоянии проверить ?
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Помогите оценить код
От:
Аноним
Дата:
27.08.07 13:18
Оценка:
MZ>Зачем давать задания, результат которых вы не в состоянии проверить ?
Отдел только создаётся. Своих программеров что бы проводить собеседование ещё нет, а людей набирать надо. Тестовые задания мы в интернете нашли, а вот с оценкой конечно тяжело Поэтому и пишу сюда.
Re: Помогите оценить код
От:
Аноним
Дата:
27.08.07 13:21
Оценка:
Добавлю свои 5 копеек в духе анонима
A>Работа проводилась на компьютере, в VC6...
А за что-нибудь более адекватное нельзя было посадить, хотя бы тот же VC7-8
Странное исключение. Если мы передали непонятно что, то кто сказал что оно выкинет (большинство ошибок тупо пропустит). А вот если человек позиционируется как 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 — во вмогих компиляторах такой тип уже есть...
Потом глюки будете искать
Аноним 876 пишет:
> Помогите пожалуйста объективно оценить код, и квалификацию программиста > который его написал. Было дано небольшое стандртное тестовое задание —
Ладно, раз уж вам так нужно....
> #include <iostream.h> > #include <string.h>
Эти заголовки давно уже не так
называются. Ну если второй еще можно (корректно)
оставлять как <string.h>, то первый по стандарту
<iostream>
Т.е. это чел либо студент (работал на старых компиляторах),
либо просто работал на старых компиляторах.
Хотя работать оно будет.
Если неправ — поправьте.
> enum ErrStat > { > OK = 0, > SomeStringError = 1000, > NotANSIString, > };
// Использовал 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>>
Перекуём баги на фичи!
Re[3]: Помогите оценить код
От:
Аноним
Дата:
27.08.07 13:37
Оценка:
Здравствуйте, Аноним, Вы писали:
MZ>>Зачем давать задания, результат которых вы не в состоянии проверить ? А>Отдел только создаётся. Своих программеров что бы проводить собеседование ещё нет, а людей набирать надо. Тестовые задания мы в интернете нашли, а вот с оценкой конечно тяжело Поэтому и пишу сюда.
Так создавайте в отделе о работе новую вакансию "Нужен человек для проверки тестовых заданий"
Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.
Re[2]: Помогите оценить код
От:
Аноним
Дата:
27.08.07 14:10
Оценка:
A>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.
Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)
A>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.
Кстати да, вопрос соотношения цена/качество как-то был упущен из виду
---=== С наилучшими пожеланиями, Phoenics ===--- _
Здравствуйте, Аноним, Вы писали:
А>Сам не силён, поэтому пишу сюда за объективной оценкой, что можно сказаьт о программисте который это написал? А>Спасибо за внимание.
1. У тестируемого наблюдается бардак в такой важной области C++ как обработка ошибок. Он намешал обработку исключений с кодами возврата. Причём и то и другое применил, во-первых, не к месту, во-вторых с недочётами. Не к месту, так как в данном случае вообще не требуется обработка ошибок. Недочёты: объявлен какой-то непонятный нигде не используемый код SomeStringError, использована конструкция catch (...), которая свидетельствует о неправильном поминании идеологии исключений.
Возможно, тестируемый хотел как-то показать, что он слышал об обработке ошибок, и даже знает о существовании двух стратегий. Но пытаясь "выпендриться", он сделал некачественный код, вместо того, чтобы просто выполнить задание. Это плохо, так как в новой команде он тоже возможно начнёт "выпендриваться" в ущерб проекта.
2. Видно, что программист видел только одну реализацию C++ (msvc). Хотя и пытается писать переносимый/обобщённый код, но это у него плохо получается (см. пост Аноним 7). Само по себе, отсутсвие опыта работы с другими реализациями C++, не так уж страшно, особенно, если нет требований к переносимости. Но это говорит об определянной ограниченности кругозора, о небольшом опыте работы с библиотеками C++. У толкового человека, осознанно работавшего с коммерческими библиотеками, наверняка бы сложилось понимание, когда нужно объявлять собственный UINT и BYTE_BIT_SIZE, а когда — нет.
3. Тестируемый неясно выражает свои мысли:
// Функция пеерворачивает символы в строке меняя их местами
Если бы я не прочитал начало поста, я бы не понял этого комментария.
>дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку
можно сделать одной строкой зная STL
std::string name = "Hello world!!!";
Здравствуйте, 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, но покажи, пожалуйста, свою реализацию», написать что-то вроде
Здравствуйте, Socket, Вы писали:
>>дано небольшое стандртное тестовое задание — написать функцию которая переворачивает строку S>можно сделать одной строкой зная STL S>std::string name = "Hello world!!!";
S>reverse(name.begin(),name.end());
В данном случае stl имеет смысл использовать, если можно сразу показать проверяющему и он скажет — достаточно этого или свою реализацию написать.
Здесь совсем другая ситуация.
Хотя наверное имеет смысл писать свою реализацию, а где-нибудь внизу указать, что "я ещё и так могу".
Здравствуйте, Аноним, Вы писали:
A>>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте.
А>Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)
Скорее всего он у вас будет нормально работать и справляться со своими задачами. Какого-то супер-кода и чёткой структуры программ ждать не приходится.
Re[4]: Помогите оценить код
От:
Аноним
Дата:
28.08.07 09:10
Оценка:
Спасибо.
Re[2]: Помогите оценить код
От:
Аноним
Дата:
28.08.07 09:32
Оценка:
Здравствуйте, MasterZiv, Вы писали:
>> catch (...){return NotANSIString;} MZ>Бред полный перехватывать тут исключения — их MZ>не будет.
В 7-ой студии это сехи ловит
Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits.
Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
Здравствуйте, Andrew S, Вы писали:
AS>Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits. 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;
}
Здравствуйте, Andrew S, Вы писали:
AS>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
AS>>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
E>ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.
Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
В общем, понятно, опять адеквата не увидим.
Этот код как минмум не быстрее приведенного мной. Например, на моем А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>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;
}
?
... причем в котором нет привязки к размерности числа
преждевременная оптимизация — корень всех зла... а приведенный мной пример ну НИКАК не тянет на преждевременную пессимизацию %)
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>Этот код как минмум не быстрее приведенного мной. Например, на моем А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
AS>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.
AS>>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.
CC>ICC 10 CC>P4 630
CC>Колво циклов увеличил до 1024^3 — бо выполняется слишком быстро
CC>15318209580 CC>8983055617
AS>>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно. CC>
Да пожалуйста, тоже увеличил.
VC6
23384774
43100993
VC7.1
17996589
20148363
Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое.
Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.
Как мы видим, тут просто развернули цикл (пачками по 4). Полагаю, IC сделал примерно то же, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).
Т.о., сравнение в данном случае получается не слишком некорректным (а точнее, вообще некорретным) — в реальном применении цикл гораздо сложнее и развернуть его таким образом не получится. Правильнее всего в смысле теста поступает VC6 — он тупо компилит то, что ему написали
AS>>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.
А>будьте любезны — уж очень хочется заценить
Что за народ пошел — все только просят привести решение, а подумать самим лень
В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно
Здравствуйте, Andrew S, Вы писали:
AS>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"
2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...
AS>В общем, понятно, опять адеквата не увидим.
В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, 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;
}
Ага, и так на каждый чих? Ну да, верно, поэтому и получаем то, что получаем — гигантские и на 99% бесполезные исполняемые модули...
RO>Мой код имеет премущество совсем в другом. По нему понятно, что он делает. Если допустить ошибку в твоем, то можно доолго ее искать. Ну, и premature optimization…
Тут я согласен. Для этих целей надо просто привести начальный (т.е. цикл со сдвигом) код в комментах функции, либо краткое описание алгоритма — он действительно очень прост.
А сампл.. Ну да, действительно, тут получалась последовательная выборка из таблица, что VC 71 заметил и "наоптимизировал".
RO>По поводу того, что мой код якобы не имеет возможностей для оптимизации компилятором:
\code skipped\
Ну, это уже совсем не весело — 256 кб пустоты для такой мелкой функции. Почему бы тогда уж 4 гб таблицу не сделать?
А по поводу результатов — для начала надо убедиться, что в данном случае сам инструмент измерений не вносит большой погрешности, как в моем варианте с VC71, когда раскручивался цикл. Т.е. смотреть нативный код — надо добиваться, чтобы _всем_ вариантам были предоставлены одинаковые условия. Например, для меня совсем не очевидно, что 256 кб таблица будет быстрее 1 кб — тут уже проблемы с кешем даже второго уровня начнутся.
А нативного кода я тут не приметил
Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).
Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно.
Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...
AS>>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно. E>1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"
Опять передергиваете. Перечитайте то, на что отвечаете, нужное выделено.
E>2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...
Да при чем тут комменты — смысл в том, что надо понимать, что это далеко не оптимальная реализация. Судя по коду (то, что например, это шаблонная функция), кандидат об этом не задумывался.
AS>>В общем, понятно, опять адеквата не увидим. E>В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...
Это вопрос не ко мне, а к топиккастеру. Хотя за ту сумму, что он озвучил, откомментировав ее как "средняя по городу вообще (а не для IT)" — думаю, вполне нормально. Хотя, конечно, задания таковы, что по ним определнно сказать что-либо сложно.
Здравствуйте, Andrew S, Вы писали:
AS>Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).
Почему компиляторы не всегда встраивают вызовы функций по одному и тому же указателю — неясно. Надеюсь, исправятся.
AS>Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно. AS>Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...
Там потому функтор, что он же должен таблицу проинициализировать.
А вообще, засунул бы функции в классы и проверил бы сам.
Вывод: твою функцию в топку, мою функцию в топку, использовать std::bitset::count, пока не выяснится, что программа проводит в ней непристойно много времени.
RO>А вообще, засунул бы функции в классы и проверил бы сам. RO>Получается интересно: RO>3872588475 — хитрые битовые операции RO>3935120400 — таблица unsigned[65536]
Ну дык я, конечно, проверил
У меня на самом деле получился твой вариант быстрее процентов на 20, чем приведенный мной. Но ввиду оверхеда на память, который он привносит, а также некоторых других "мелочей" (например, чтение сампла из памяти тоже приличный оверхед для приведенного мной алгоритма) полагаю, что по производительности они примерно равны на текущих "обычных" системах, а вот по функциональности приведенный мной вариант выигрывает _значительно_. Хочу напомнить, что это ни в коем случае не мой вариант, я лишь "разместил объяву". Авторство (а точнее, точку инстанцирования) я указал ранее.
RO>Вывод: твою функцию в топку, мою функцию в топку, использовать std::bitset::count, пока не выяснится, что программа проводит в ней непристойно много времени.
Ну... Кому что. Я работаю в области, где часто требуется эффективность, поэтому для меня подобные спички часто бывают актуальны. Впрочем, задачи, где бы требовалось подсчитать (именно подсчитать) количество единичных бит мне пока что не встречалось, так что все это имеет чисто академический интерес. Но знать о подобных алгоритмах, имхо, просто необходимо.
Например, в том же bitset::count во многих реализациях используется табличный метод (группы по 4-8 бит). Т.е. используй кандидат битсет, получил бы примерно в 2-3 раза более эффективную функцию вообще безо всяких усилий.
Здравствуйте, Andrew S, Вы писали:
AS>>>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно. E>>1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. AS>Опять передергиваете. Перечитайте то, на что отвечаете, нужное выделено.
Ну правда не важно. Важно чтобы программировать умел. А знает какой-то конкретный алгоритм или нет, да какая разница? Не знает -- узнает. А не узнает, то ничего драматического не случится, ИМХО.
AS>Да при чем тут комменты — смысл в том, что надо понимать, что это далеко не оптимальная реализация.
AS>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
AS>Судя по коду (то, что например, это шаблонная функция), кандидат об этом не задумывался.
Вообще-то говоря, какой вопрос, такой и ответ, ИМХО.
AS>Это вопрос не ко мне, а к топиккастеру.
Ну отвечал-то ты
Надеюсь, что теперь тебе понятно с чем я был согласен
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
AS>Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое. AS>Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.
Улучшить? Да он его хреново скомпилил.
Сравни:
AS>countOnes AS>
AS>Как мы видим, тут просто развернули цикл (пачками по 4). AS>Полагаю, IC сделал примерно то же
Как ты сам можешь видеть — ICC ничего не разворачивал. AS>, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).
Вообще результат компиляции countOnes вижуалкой кроме как кошмарным назвать не могу. Зачем он лишний раз читает/пишет в tv1<xxx>? И что это вообще за переменные то? В результате больше обращений к памяти чем нужно.
AS>Что за народ пошел — все только просят привести решение, а подумать самим лень
удивительная особенность человека — как только начинаешь его о чем то просить, он начинает, как бы это сказать помягче... выделываться
AS>В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно
"Назвался груздем — полезай в кузов." Вам представили универсальный работающий пример, вы же утверждаете, что знаете БОЛЕЕ эффективный...
Покажите полный законченый аналог (по работе) и превосходящий по эффективности. Все остальное — слова!
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>Я показал полный и законченый вариант. Если у Вас не хватает знаний, чтобы это оценить — это Ваши, а не мои, проблемы.
полный, законченый пример для чего? а я думал только для 32 битных значений...
AS>В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.
с каким тоном общения? на неадекватное поведение — последовал адекватный ответ.
еще раз по слогам: без полного, законченного примера все вышесказанное вами только пустая болтовня. кроме как посылать по неизвестному адресу, без каких-либо комментариев к коду (кроме "есть такая книга умная — как, а, вы не читали, учите матчасть" — это как минимум тупые комментарии).
AS>>В общем, дорогой Аноним. Еще раз и по слогам — даже не собираюсь, тем более с таким тоном общения. Если Вам это интересно — реализуйте и представьте результаты — где найти нужные знания, я уже сказал. Если же Вы просто тут для того, чтобы пофлеймить (а я в этом уверен с первого же Вашего сообщения) — для этого на rsdn есть специальные места. Подите в игнор.
E>Вообще-то задача выбора констант, вернее выбора момента с которого константы уже не нужны в CT не такая уж и тривильная, ИМХО...
?? В алгоритме количество шагов равно log(bit_count). Все константы на каждом шаге вычисляются как зависимость от номера шага, а результат на текущем шаге — это сумма резальтатов предыдущих шагов. Первые 3 шага (которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм. На последнем шаге выполняется отсечение частичной суммы предыдущего шага. А в целом — алгоритм рекурсивный, банальный бинарный спуск. Все это _реализуемо_ на шаблонах в CT, и результат будет полностью аналогичен "ручному" кодированию. Но тратить свое время запросто так, чтобы ублажить господина Анонима — не хочется. Поскольку ему нужен совсем не результат, это же очевидно
Здравствуйте, Andrew S, Вы писали:
AS>...(которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм...
Собственно я про то, что начиная с какой-то длинны целого (типа 256-битное) надо не забыть сделать &0x00FF00FF00FF00FF...00FF.
Ну и сами константы сегенрить тоже надо, кстати.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Так ловить-то оно ловит, а откуда там SEH-и будут ?
Ну если ей конечно 0x01 в качестве адреса строки дать,
оно GPF даст — да. Но если просто бесконечную строку
дать, почешет по памяти до первого '\0' и не фект что
до GPF его не найдет.
Здравствуйте, <Аноним>, Вы писали:
A>>Озвучте зарплату, на которую собеседовается человек, а то получится, что тут кандидата залажают, а окажется, что для рассматриваемой зарплаты он просто отлично пишет и другого такого вы не найдёте. А>Планировалась вилка 9-15 тыс, в нашей глубинке эта зп так скажем выше среднего (не для программистов, а вообще по городу)
Это где нонче такое? Да так, что там на такую зарплату программистов в штат набирают???
AS>>...(которые выполняются всегда, поскольку они считают суммы для полубайтов) несколько специфичны — надо учитывать возможные переполнения для частичных сумм...
E>Собственно я про то, что начиная с какой-то длинны целого (типа 256-битное) надо не забыть сделать &0x00FF00FF00FF00FF...00FF. E>Ну и сами константы сегенрить тоже надо, кстати.
Вот решение, которое полностью дублирует функционал начального кода. При 32-х битах генерируемый код — команда в команду ручная реализация pop.
Наверное, можно и красивее реализовать (особенно EnumConst, который заточен под VC6 — очевидным образом там надо const T value вместо enum использовать), но думать над этим откровенно не хочется.
Здравствуйте, MasterZiv, Вы писали:
MZ>Ладно, раз уж вам так нужно....
>> #include <iostream.h> >> #include <string.h>
MZ>Эти заголовки давно уже не так MZ>называются. Ну если второй еще можно (корректно) MZ>оставлять как <string.h>, то первый по стандарту MZ><iostream>
MZ>Т.е. это чел либо студент (работал на старых компиляторах), MZ>либо просто работал на старых компиляторах. MZ>Хотя работать оно будет. MZ>Если неправ — поправьте.
Если мне память не изменяет то в 6ой студии так и пишеться.
Поэтому и пишу сюда.
Перекуём баги на фичи!
_
