Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Стартап Hola платит 500 $ всем, кто решит задачку по программированию на языке С. Лучшим предлагает удаленную работу на прекрасных условиях. Условия тут hola.org/jobs_ru.html
Коментар порушує правила спільноти і видалений модераторами.
Коментар порушує правила спільноти і видалений модераторами.
Добрый день!
Хотела сказать, что пока Hola не готова выложить правильный ответ, поскольку конкурс решили продолжить. Раздали 14 призов (включая
Призовой фонд еще есть, так что продолжаем ждать правильных ответов.
Спасибо за понимание:))))
Поучаствовал и у меня создалось впечатление, что эти товарищи с присущей их древнему народу смекалкой решили устроить крупномасштабный мозговой штурм на халяву.
Даже если так, смысл в чем? Тут полфорума могут написать вполне нормально эти 2 нещасные функции (если подумают конечно не 15 минут).
Пиар стартапа?Во много раз правдоподобнее.
И получить их стандартную отписку с предложением подумать еще, уже за полцены
я думаю, что Билл Гейтс и Папа Римский уже выграли по 500$, попробуйте еще раз :-)
Они кстате по видимому саллоцировали еще бабла — до 40 тыщ.
Получил. Согласен, мое предположение бессмысленно. Это так, первая реакция. Моя реализация работала вдвое-втрое быстрее библиотечных, но похоже, этого никто и не проверял. Абыдна, да!
Получил.Вчера? ;)
Моя реализация работала вдвое-втрое быстрее библиотечных, но похоже, этого никто и не проверял.Зато сколько памяти небось переводит зря ;)
В течение уже вот более года? Нет, всё проще — это пиар вакансии и пиар, надо признать, удачный.
Тем, кто не входит в их целевую аудиторию, присылают стандартную отписку, с остальными наводят мосты.
Стандартные отписки посылают только тем, кто решил задачу неверно:)))
Спасибо. Ждём на хабре подробный пост-разбор верного решения :)
Дык, челендж продлили до марта, и еще бабла подкинули.
Пока не ждите — мы еще не все деньги раздали. Вот сейчас платим двоим решившим и еще двоим — за то, что привели победителей. Но все равно деньги пока есть и работники пока требуются.
Надеюсь в конце этого мероприятия организаторы выложать каноническое решение, что бы мы смогли оценить глубину мысли гуру?
Просто решение, ответа никакого думаю не даст. А вот если бы знать четко контекстик применения кода — тут уже можно оценивать глубины.
Если есть некий тайный контекст который не удосужились сообщить собеседуемым, то эта задача из разряда «угадай что у меня в кармане»
Если есть некий тайный контекст который не удосужились сообщить собеседуемым, то эта задача из разряда «угадай что у меня в кармане»Не совсем так. Просто есть люди, которые видят проблему также как и они, и им ничего объяснять не нужно. Остальных — отсеять. Они где то писали что хотят избавиться от гемора собеседований с помощью этого челенджа. Имхо, проблему контекста они уже достаточно ясно излагают в своих отписках.
Ну вот хотелось бы увидеть ответ, что бы определить, это действительно вопрос видения, или совместимости маразма
Ну вот хотелось бы увидеть ответ, что бы определить, это действительно вопрос видения, или совместимости маразмаЕсли ответом будут 14 строк кода, то полюбасу найдутся такие, кто считает решение неправильным. Слишком большая разница, где будет этот код крутиться, в космической орбитальной станции или в каком-нибудь андроиде.
Сергей Волошин, я вас прошу удалить комментарий dou.ua/...ic/8356/#403483 . Это просто несправедливо, что люди себя так ведут. Олимпиада ведь продолжается.
Ещё вот эти, пожалуйста:
dou.ua/...=comment#384769
dou.ua/...=comment#386250
Проще удалить одного юзера.
Почему думаете, что это лохотрон? Не только ли из-за того что ваша телега не прошла?
Почему думаете, что это лохотрон?Я думаю, что вы странный тип, только и всего.
Не только ли из-за того что ваша телега не прошла?Я ничего никуда не посылал. Мне претят задания такого типа.
void str_cpy(char **dst, const char *src)
{
if(!src || !dst || (*dst == src))
return;
int src_len = strlen(src);
(*dst) = realloc((*dst), src_len + 1);
if(*dst)
{
memmove((*dst), src, src_len + 1);
}
}
// У меня вот такое получилось, для str_cpy ...
Почему вы не делаете проверку if(!(src=(char *)666) || (!(dst == (char **)777))) ?
... глупый коммент.
Я ошибся, извини. Я имел ввиду
if(src==(char *)666 || dst == (char **)777)
return;
По логике вашей валидации нужно еще и такую проверку делать.
(*dst) = realloc((*dst), src_len + 1);А что дают скобки? Серьезно не знаю.
Здесь скобки лишь для наглядности. Вот стиль у меня такой.
Уже какбы говорили, что лишнии токены не приветствуются ...
Оверлаааааааааааааааап! Ну и пересечение тоже.
Пару месяцев уже корплю над задачкой.
Пишут, что «There are still 2 typical use-cases where your code return incorrect results.»
Вот тесты, которыми покрываю код: codepad.org/SHWcjRWJ. Может, кто-нибудь подскажет, каких тесткейсов ещё нету?
Потерял пароль к почте — создал новый аккаунт.
Пишут, что «There are still 2 typical use-cases where your code return incorrect results.»Да, твой код возвращает 2 раза char** в двух разных функциях. Зачем? Абы вернуть?
Попробуй str_cat(&s, str_cpy(&d, “Some string”));
Да, твой код возвращает 2 раза char** в двух разных функциях. Зачем? Абы вернуть?Уже отправлял варианты с void, char* и size_t. После char** перестали ругаться на «non-useful return value» вроде, так и оставил. Плюс такого решения в том, что можно результат вызова str_xxx передавать снова в качестве первого аргумента другого вызова.
size_t str_len(const char *str);
А это зачем?
Просто вынес повторяющуюся два раза строчку кода в отдельную функцию. Это не проблема, свои функции можно вводить.
Это не проблема, свои функции можно вводить.С чего взяли? Таким макаром ведь можно каждую функцию в одну строчку разрулить ...
Дык длина функций не самоцель. Цель — library quality. Критерии более-менее формализованы и даны.
После char** перестали ругаться на «non-useful return value» вроде, так и оставил.Мне вообще прислали список озаглавленный
Мне говорят, что самая важная проблема осталась — это два непокрытых юз-кейса, причём они достаточно широкоиспользуемые, чуть ли не у K&R описаны. Полистал книжку, ничего не нашел. Почитал тесты <string> в glibc, там тоже ничего интересного.
Что под руку попадётся, то и ide. Этот код писан в VS2012 и vim. Как это относится к теме?
Как это относится к теме?dou.ua/...ic/8356/#386716
И чо?)
Уже ниже написал, что
Память тоже нигде не убежала.Валгринд гонял. Таки, при чём тут иде?
Там внутри src изменяеться/копируется из правильного места, если произошло реаллоцирование?
Валгринд гонял. Таки, при чём тут иде?Подозреваю, что в вижуалстудио, икскоде, и.т.д. такое не заметишь (память при этом нигде не течет):
str_cat(str_cpy(&s, «Hola »), *str_cpy(&d, «World»))Ради интереса, попробуй заменить символ d на s, и запустить под валгриндом
В этом случае, после одного из вызовов str_cpy (порядок следования не определён) s инвалидируется, и произойдёт обращение к недоступной памяти.
Судя по выводу valgrind ( codepad.org/AODPuR4E ), инвалидировался второй указатель, который src для str_cat (т.к. было инвалидное только чтение, а не запись).
Кстати, ты в тестах кастуешь, то что возвращается каллоком. Есть подозрение что тоже самое ты делаешь и в функциях. Типа редундант код.))
Спасибо, нет. В функциях редундант код вычищен )
Кинул взгляд на тесты еще раз, нигде не увидел что то типа
str_cpy(&s, «„);
str_cat(&s, s);
str_cat(&s, s);
str_cpy(&s, “»);
Может на границе что то умирает?
Тесты 4,6,11,13 об этом. Последовательное применение таких вызовов тоже работает, сейчас проверил. Память тоже нигде не убежала.
Возможно для них является полным неадекватом:
1. Когда стринга создается стркатом.
2. Когда из нуллового соурса выходит что-то путевое.
Имхо, оба варианта нелогичны.
Вообще говоря, garbage in — garbage out. Но разве я, как разработчик библиотеки, не могу подстраховать пользователя и выдать что-то наименее вредное в случае неадекватного вызова? Какой результат, по твоему, был бы логичнее?
Вообще говоря, garbage in — garbage out.Надо определиться сперва, что такое гарбедж. (char *)1 ? или может (char *)777 ? или (char *) 0.
Какой результат, по твоему, был бы логичнее?сегфолт при стрлен, потому что в упор не вижу разницы между NULL и (char *)1 в качестве src или dst.
Но разве я, как разработчик библиотеки, не могу подстраховать пользователя и выдать что-то наименее вредное в случае неадекватного вызова?Опять таки, попробуй подстраховать когда str_cpy((char **)1, (char *)666)
А зачем себя подстраховывать в этом случае?
А зачем себя подстраховывать в случае str_cpy(NULL, NULL) ?
Я не кажу що потрібно :). Як на мене, і у випадку str_cpy(&s, s — 1) теж не потрібно
Вадим! Поздравляю с правильным решением и призом:)))
спасибо за интересную задачу!
Поздравляю, тоже! С первого раза решили?
У меня вот, с первого раза не получилось, а второй я еще не отсылал. Задачка действительно сильно зацепила )). Очень надеюсь, что вы не выложите решение в сеть )
Вирішив не з першого.
За правилами рішення викладати не можу, а то ще приз попросять повернути :)
Вирішив не з першого.Да чорт с тем призом )) Это подло просто было бы, имхо.
За правилами рішення викладати не можу, а то ще приз попросять повернути :)
Ну теперь то мы во всяком случае знаем, что нифига не фэйк, не развод и все такое.
Коли читав усі коментарі тут, і на інших просторах, теж думав що фейк. Та цікавість перемогла і я все таки спробував, витратив багато часу, набагато більше 20 хв. В кінці кінців рішення вийшло невеликим і зрозумілим. Приз отримав.
Кстати, а вы собеседовались в этой конторе? Судя по вашему тайтлу и месту работы, это был бы серьезный шаг вперед. Да что уж таить, для меня это был бы тоже шаг вперед — после 7ми лет клепания формочек в дотнете...
Стараемся:))) В воскресенье еще два собеседования — претенденты почти дорешали, осталось что-то мелкое. Предполагается, что на собеседовани и решат. Надеюсь, что справятся.
Кстати, господа недоверчивые спорщики, которые все еще не верят, что я не робот. А нет ли среди вас тех, кто программирует на JavaScript и (или) для Android? У нас есть вакансии. Никаких задач:))) Просто просим работы посмотреть, и приглашаем (или нет) на собеседование.
Я уже устал ждать ответ :) У вас же там нет Нового Года.
Странно, как только я вам отправил «идеальное» решение — вы сразу растворились. Я конечно не буду выкладывать в интернет свое решение или ваши отписки, но зато вполне могу указать ссылку на уже готовое решение в сорцах одного известного продукта.
Лариса, через сколько вы обычно отвечаете? В первый раз — это было 3 дня, но сейчас уже прошло 10!!! Я начал плохо спать, и мне уже начинает ГОРЕТЬ разболтать всему сообществу в чем суть.
расскажите, всем интересно.Если вскоре не получу ответ, то расскажу. А вообще все будут разочарованы, я так думаю.
У вас тоже остались только «Invalid results» и вы раскопали в чем там дело?
Я считаю, да. И даже реализовать за полчасика оказалось вполне реально. И даже статьи в инете есть об «этом». И сорцы кое-какие тоже просвящают. Сложновато просто заставить человека мыслить таким образом (непонятно почему). Лично я просто наткнулся на эти дополнительные юзкейсы — решил их — а потом погуглил, и тут началось ... Вобщем лучше чем здесь dou.ua/...ic/8356/#388916 и не скажешь. :)
Тот товарисч вверху, который писал тесты и делал кастомный str_len, вероятно настолько запутался в жизни, что начал лобать для вайд чарактеров. Хотя возможно я ошибаюсь — иначе нахрен ему str_len? :)
мне отвечали раз в неделю, а когда было уже правильно тоже долго не отвечали, но потом ответили. А сейчас, тем более, много не рабочих дней было, так что ответят ...
Тут уж пардоньте, но 1 и 666 — вполне себе валидные адреса, в отличие от NULL. В каком-нибудь embedded ничего не мешает куче аллоцироваться там, например.
К тому же, моя реализация str_len не сегфолтится от NULL.
garbage — это (1)передача неаллоцированного указателя, (2)передача указателя на аллоцированную строку, но без нуль-терминации, или (3)передача пустого указателя.
Если первые два случая я никак не могу обнаружить без хуков аллокатора, то третий легко обнаруживается и может быть использован для повышения универсальности библиотеки.
Не смогу вас наверное отговорить. Я вижу проверку на нулл всего лишь маленькой частностью.
В любом случае, это не относится к делу. Отписка от Ноама такая:
These are ’valid & reasonable’ use-cases, in the sense they involve valid inputТо есть, не работает что-то с бесспорно вполне валидными входными данными.
and standard string manipulation methods/scenarios. Some of these use-cases are
very common in C programming, and are even demonstrated in K&R “The C
Programming Language” book. In fact, they are common enough in C that there are
standard C (ANSI and POSIX) APIs that generate the type of strings that will
cause your code to fail!
memmove. иначе тесты с оверлапами (5,12) не всегда проходили бы, а тесты они смотрели, и говорят, что нужно расширить набор )
Пожалуйста, попросите админов удалить комент. Это несправедливо по отношению к hola. Один тут уже начал верещать they are fake и все такое.
Учите С++, на чистом С далеко не уедете только нервы испортите себе и другим. ;-)
Задачка на 500 фунтов от Миши Собина
Валяйте, щас разберем по косточкам
Мишу уже давно разобрали по косточкам.
Уважаемые участники спора! Официально от имени Hola сообщаю вам, что мы НЕ даем призов за коллективное творчество. Поэтому все, кто выставляет здесь свои варианты решения, не могут претендовать на вознаграждение.
Мне кажется, это вполне справедливо.
За то, что они тут выкладывают, надо не приз давать, а путёвку в тайгу на лесоповал.
Путевок нет:))) НО есть призы, и за коллективное творчество их давать не положено. Еще есть работа, но ее дают все равно только после собеседования, так что коллективно никак не получится одолеть:)))
Официально от своего имени сообщаю, что для меня компания Hola не является карьерной целью, мне просто интересно обсудить предложенную задачу с коллегами. Свой потенциальный приз я передаю в фонд Организации Освобождения Палестины.
Неполиткорректно.
Тем не менее, мне интересно это обсуждение.
Передаю свой потенциальный приз в фонд повышения девичьей самооценки.
Джастаутофкуриосити, Ноам заплатит 2 тыщи если свести количество строк кода до
См. выше, мы все уже на карандаше у Мосгаза.
Не заплатят, так шо показывай уже, не томи.
Все хочу куда-нибудь вклиниться и довести до сведения спорящих письмо Ноама:))) Правда, на английском — на русском он не пишет. Итак, спич о том, почему условия задачи нечеткие:
“A substantial part of the challenge is to make the correct assumptions and best
design decisions, in order to produce a perfect library-quality code. To help
you make these decisions, we provide the example main() - which hints at how the
library should be used and some use-cases. Your challenge is to fill-in the gaps
and try to make the best decisions, to create the most robust and useful,
library quality code.
I’m sorry I can’t be any more specific than that — or the challenge wouldn’t be
a challenge at all...”
Андрей Катруша
Ievgen
Андрей Катруша
Larisa Zimina
anonymous
marko dou
Nobody
reality_hacker
Mike Gorchak
ScorpZ Lapshov
Alexander Mihailov
Ivan D
Vlad Svitlychnyi
Nobody
void str_cpy(char **dst, char *src)
{
if (!src || !dst)
return;
int src_len = strlen(src);
if (src_len)
{
if ((*dst = (char*)realloc(*dst, src_len + 1)) == 0)
return;
memmove(*dst, src, src_len + 1);
}
}
void str_cat(char **dst, char *src)
{
if (!src || !dst)
return;
int src_len = strlen(src);
int dst_len = strlen(*dst);
if (src_len)
{
if ((*dst = (char*)realloc(*dst, dst_len + src_len + 1)) == 0)
return;
memmove(*dst + dst_len, src, src_len + 1);
}
}
Можыте лашыть.А зачем memmove(), если realloc() вполне успешно закрешит выполнение кода парой строчек ранее, если передали один и тот же выделенный регион памяти в качестве src и dst?
char* dst;
dst+=5;
str_cpy(&dst, dst-5);
чорд, придётся без реаллок.
тогда в семь строк ну никак не уместиться.
чорд, придётся без реаллок.Еще как можно.
тогда в семь строк ну никак не уместиться.
Еще как можно.я понял, сёдня поужинать не получицца.
всё ещё ждем Вашего кода... непременно в семь строк, да ещё и не сбойного.
str_cpy(&dst, dst-5);Кстати в таком случае мы вообще не можем делать free(*dst) внутри функций.
Ну да :) Это я специально :)
та хто б сомневался :)
тогда мы типа не озабочиваемся внутри функций ёмкостью буфера, если нам передан ненулевой указатель, так что ли? пишем, что дОлжно и будь что будет?
Если не делать свой аллокатор, я ниже про это писал, то да. dou.ua/...ic/8356/#370057
Походу от соискателей хотят проверить dst на нуль, если нуль — выделить память по длине источника и «свести задачу к предыдущей» :)
if ((*dst = (char*)realloc(*dst, src_len + 1)) == 0)Это конечно работает как-то (согласен). Но представим на секундочку, что произойдет здесь при оверлапе строк str_cpy(&s, s+5); , если имплементация реаллока отдает память ядру?
str_cpy() по условиям задачи должна корректно справляться с ситуацией, когда память, на которую указывают dst и src, перекрывается. См. второй вызов к ней в main().
Таким образом, str_cpy() реализована некорректно.
Совет: напишите тестовое приложение, скопируйте оригинальную main() туда, и погоняйте свои функции на ней.
напишите тестовое приложение,танунах, тут всё «на листике» разруливается
Вы же сами видите, что не всегда разруливается...
*dst == src -> crash
*dst == NULL -> crash
возвращение void -> нонсенс.
Дальше читать лениво, мне пора менять очки на линзы и бежать в клуб прикидываться дурочкой. Димлом — не скоро))))
Чего и вам желаю, не засиживайтесь на месте;) Только не притворяйтесь дурочкой — парням это не к лицу)))
*dst == src -> crashВо всех трёх каментах выше уже ткнули носом. Смысл повторяться?
void str_cpy(char **dst, char *src)
{
if (!src || !dst)
return;
int src_len = strlen(src);
char* new_dst = (char*)malloc(src_len + 1);
if (new_dst)
{
memmove(new_dst, src, src_len + 1);
free(*dst);
*dst = new_dst;
}
}
void str_cat(char **dst, char *src)
{
if (!src || !dst)
return;
int src_len = strlen(src);
int dst_len = *dst ? strlen(*dst) : 0;
char* new_dst = (char*)malloc(dst_len + src_len + 1);
if (new_dst)
{
if (*dst)
memmove(new_dst, *dst, dst_len);
memmove(new_dst + dst_len, src, src_len + 1);
free(*dst);
*dst = new_dst;
}
}
v.2, после комментов благодарных читателей.Разрази мою пьяную голову, Саттер — вы же по колено в коде!
realloc — не осилили? Думайте.
1 char** str_cpy(char **dst, char *src)
2 {
3 if (!src || !dst) return NULL;
4 int src_len = strlen(src);
5 int diff = *dst && (src - *dst < strlen(*dst)) ? (src - *dst) : -1;
6
7 if ( (*dst = (char*)realloc(*dst, src_len + 1)) != NULL )
8 memmove(*dst, diff > 0 ? *dst + diff : src, src_len+1);
9
10 return dst;
11 }
10 строк всего, из них 2 пустых, 2 скобки, и два объявления переменных могут быть перенесены на одну строку по желанию. Итого: 6 строк кода сейчас, 5 строк кода возможно.
В отличие от вашего кода, моя ласточка не делает лишних перераспределений.
Хотя, это лишь ваш исправленный код — я сделала иначе, но публиковать пока не буду.
msvs, eclipse, qtcreator.
В данном случае это был vim, «:set invnumber» не делался для удобства подсчета строк вами.
Будем надеятсо, что ваша ласточка работает получше «исправленного кода».
А есличо — валгринд в помощь, а то эти современные иде такие современные.
Обижаете. Валгринд рецензировал мой код первым.
Да и вообще я гамнокожу только с дичайших бодунов в институтском общежитии.
Коментар порушує правила спільноти і видалений модераторами.
Ладно. Задам вопрос прямо. Вы вот это dou.ua/...ic/8356/#386639 проверяли валгриндом?
Мигать-колотить, вот оно протрезвение! Пардоньте, мужики, щас все будет чики-пики — и в дамки. Я по колено в коде.
Пардоньте, мужики, щас все будет чики-пики — и в дамки. Я по колено в коде.Да ради Бога! Абы ласточка не хромала на ту же ногу.
Готово.
К счастью, фикс тривиальный и не влияет отрицательно ни на число строк, ни на эффективность
Фикс:
1 char** str_cpy(char **dst, char *src)
2 {
3 if (!src || !dst) return NULL;
4 int src_len = strlen(src);
5 int diff = *dst && ((src - *dst) < strlen(*dst)) ? src - *dst : -1;
6
7 if ( diff >= 0 || (*dst = (char*)realloc(*dst, src_len + 1)) != NULL )
8 memmove(*dst, src, src_len+1);
9
10 return dst;
11 }
Дабы не пугать вас просто так:
% rm test
% cat test.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char** str_cpy(char **dst, char *src)
{
if (!src || !dst) return NULL;
int src_len = strlen(src);
int diff = *dst && ((src - *dst) < strlen(*dst)) ? src - *dst : -1;
if ( diff >= 0 || (*dst = (char*)realloc(*dst, src_len + 1)) != NULL )
memmove(*dst, src, src_len+1);
return dst;
}
int main()
{
char *s = NULL;
str_cpy(&s, "hello World");
str_cpy(&s, s+6);
printf("mew - '%s'\n\n", s);
free(s);
return 0;
}
% gcc -g -Wall -o test test.c && ./test && valgrind --leak-check=full ./test
mew - 'World'
==83313== Memcheck, a memory error detector
==83313== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==83313== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==83313== Command: ./test
==83313==
mew - 'World'
==83313==
==83313== HEAP SUMMARY:
==83313== in use at exit: 4,096 bytes in 1 blocks
==83313== total heap usage: 2 allocs, 1 frees, 4,108 bytes allocated
==83313==
==83313== LEAK SUMMARY:
==83313== definitely lost: 0 bytes in 0 blocks
==83313== indirectly lost: 0 bytes in 0 blocks
==83313== possibly lost: 0 bytes in 0 blocks
==83313== still reachable: 4,096 bytes in 1 blocks
==83313== suppressed: 0 bytes in 0 blocks
==83313== Reachable blocks (those to which a pointer was found) are not shown.
==83313== To see them, rerun with: --leak-check=full --show-reachable=yes
==83313==
==83313== For counts of detected and suppressed errors, rerun with: -v
==83313== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Прошу идентичный скрин, только уберите
free(s);в main.
Похоже, вы таки дунули ;)
Ну уберу я free(s) из main(), ладно. Согласно условию изначальной задачи напишу вместо него str_free(&s);
Догадаетесь сами, как реализовать str_free?
Прошу идентичный скрин, только уберитеfree(s);
в main.
Чтобы исправить «reachable» можно в main написать «free(s); s=NULL;»
Всё, лишь бы вы не расстраивались. Хотите — поцелую?
% rm ./test
% cat test.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char** str_cpy(char **dst, char *src)
{
if (!src || !dst) return NULL;
int src_len = strlen(src);
int diff = *dst && ((src - *dst) < strlen(*dst)) ? src - *dst : -1;
if ( diff >= 0 || (*dst = (char*)realloc(*dst, src_len + 1)) != NULL )
memmove(*dst, src, src_len+1);
return dst;
}
void str_free(char** s)
{
free(s ? *s : NULL);
}
int main()
{
char *s = NULL;
str_cpy(&s, "hello World");
str_cpy(&s, s+6);
printf("mew - '%s'\n\n", s);
str_free(&s);
return 0;
}
% gcc -g -Wall -o test test.c && ./test && valgrind --leak-check=full ./test
mew - 'World'
==83492== Memcheck, a memory error detector
==83492== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==83492== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==83492== Command: ./test
==83492==
mew - 'World'
==83492==
==83492== HEAP SUMMARY:
==83492== in use at exit: 4,096 bytes in 1 blocks
==83492== total heap usage: 2 allocs, 1 frees, 4,108 bytes allocated
==83492==
==83492== LEAK SUMMARY:
==83492== definitely lost: 0 bytes in 0 blocks
==83492== indirectly lost: 0 bytes in 0 blocks
==83492== possibly lost: 0 bytes in 0 blocks
==83492== still reachable: 4,096 bytes in 1 blocks
==83492== suppressed: 0 bytes in 0 blocks
==83492== Reachable blocks (those to which a pointer was found) are not shown.
==83492== To see them, rerun with: --leak-check=full --show-reachable=yes
==83492==
==83492== For counts of detected and suppressed errors, rerun with: -v
==83492== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Не не не :))) Задача предельно проста. В этом dou.ua/...ic/8356/#386879 необходимо убрать free(s) в функции main. Запустить и прислать скрин.
Кто вам такую задачу поставил?
У вас нет задачи вставить в конец system("sudo reboot"); или убрать из main() str_cpy() ? :)
Моя задача — исправить изначальный str_cpy() одного из коллег так, чтобы он перестал дурно пахнуть и был применим в условиях, приведенных компанией-организатором:
int main(int argc, char *argv[])
{
char *s = NULL;
str_cpy(&s, "Hola Hola");
str_cpy(&s, s+5);
str_cat(&s, " World");
str_printf(&s, "%s!", s);
puts(s); /* result: "Hola World!" */
str_free(&s);
return 0;
}
Удалив всё, что мной не реализовано, а именно: str_cat() и str_printf() вы легко убедитесь в том, что мое решение корректно в этом случае.
Если у вас есть конструктивная критика — валяйте.
Если нет — не валяйте дурака.
Вы уже накрапали 3 огромных комента в ответ. А я вас прошу сделать лишь одно dou.ua/...ic/8356/#386926
Попытаюсь пояснить понятнее, что я хочу от вас: здесь dou.ua/...ic/8356/#386879 сотрите фри, запустите и пришлите скрин :) Это ведь не сложно?
В качестве намека на адекватность вашей просьбы я вас прошу запостить сюда своё фото с дуршлагом на голове в носках и вьетнамках.
Ваша просьба не адеквана, вы таки упороты.
Хотите, я еще сотру realloc(), запущу и пришлю вам скрин?
Только давайте переместим это обсуждение куда-нибудь отсюдова, потому что это флуд и скоро нас отлупят банхаммером и потрут сообщения.
Хотите, я еще сотру realloc(), запущу и пришлю вам скрин?Это ж жесть просто. Нет, не надо вовсе удалять реаллок. только одну функцию (фри©;) и все.
Противный.
==83856== Memcheck, a memory error detector ==83856== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al. ==83856== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info ==83856== Command: ./test ==83856== mew - 'World' ==83856== ==83856== HEAP SUMMARY: ==83856== in use at exit: 4,108 bytes in 2 blocks ==83856== total heap usage: 2 allocs, 0 frees, 4,108 bytes allocated ==83856== ==83856== 12 bytes in 1 blocks are definitely lost in loss record 1 of 2 ==83856== at 0x2594BB: malloc (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so) ==83856== by 0x259604: realloc (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so) ==83856== by 0x40070B: str_cpy (test.c:11) ==83856== by 0x40076D: main (test.c:20) ==83856== ==83856== LEAK SUMMARY: ==83856== definitely lost: 12 bytes in 1 blocks ==83856== indirectly lost: 0 bytes in 0 blocks ==83856== possibly lost: 0 bytes in 0 blocks ==83856== still reachable: 4,096 bytes in 1 blocks ==83856== suppressed: 0 bytes in 0 blocks ==83856== Reachable blocks (those to which a pointer was found) are not shown. ==83856== To see them, rerun with: --leak-check=full --show-reachable=yes ==83856== ==83856== For counts of detected and suppressed errors, rerun with: -v ==83856== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Доволен? Кончай флудить, ты не ту задачу решаешь.
Доволен? Кончай флудить, ты не ту задачу решаешь.Фух. Наконец. Благодарю.
Удовлетворите, пожалуйста, мою просьбу
То есть не смущает что в памяти остался висеть
Двухгигабайтового куска нет. Давай пруф.
Бажный код сделан по твоей просьбе — в нормальном коде приведенном выше этого нет. Если считаешь, что есть — пруф или небыло.
str_cpy(&s, «два гектара трэша включая ноль-символ компилятора»);
str_cpy(&s, s + 2 * 1024 * 1024 * 1024 — 2);
----валгринд та та та ----------
итого: прое.балось 2 гб
Ну коль руки из задницы — то неудивительно. Я не буду больше рассматривать случаи долбоепизма вроде ваших просьб выше «давайте так же, но без освобождения памяти» и «опа, теперь память не осводобилась».
Тут или полное непонимание друг друга или нежелание. Лично мне хочется попользовать эти 2 гб — 2 байта после вызова
str_cpy(&s, s + 2 * 1024 * 1024 * 1024 — 2);
Скорее и то, и другое вместе взятое. Имеем компромисс между скоростью и краткостью с одной стороны, и простотой использования в приведённом случае.
Хочется? Пользуйтесь:
str_cpy(&new_s, s + 2 * 1024 * 1024 * 1024 — 2); str_free(&s);
Конечно, такое поведение должно быть документировано в объявлении функции.
Кстати, интересно покритиковать ваш вариант. Сможете избавиться от недостатков моего кода, не растеряв преимуществ?
Кстати, интересно покритиковать ваш вариант. Сможете избавиться от недостатков моего кода, не растеряв преимуществ?Тремя разными способами — но это еще не значит, что будет приемлемый для Ноама перфоманс. А кровавые эмбеддеры типа горчака или ноубади просто потешаюцца над нами, или вы еще не поняли?
А кровавые эмбеддерыЯ аж порвал от неожиданности пачку сотенных купюр с пятнами крови. Ни один приличный дон не возьмёт себе прозвище где есть слова кровь или смерть. И да, я не эмбеддер, если что, хотя умею и, говорят, неплохо.
Ну если уж «Developer в QNX» — не эмбеддер, тогда я и подавно формошлёп.
Эмбеддеры — это те, кто его использует :)
Коментар порушує правила спільноти і видалений модераторами.
Всё, лишь бы вы не расстраивались. Хотите — поцелую?Катя, это у вас своей дури хватает или что-то внешнее принимаете?
Всё своё) Потому и не принимаю ничего внешнего.
Мне жаль, что я серьёзно отнеслась к словам этого товарища.
Какой ваш взгляд на разыгравшуюся драму?
Какой ваш взгляд на разыгравшуюся драму?Когда я смотрю на эту драму мой взгляд мутный.
Коментар порушує правила спільноти і видалений модераторами.
По жизни — да. Что касаетсо конкретной задачи — врядле.
Тут везде вызывается free как будто заранее известно, что *dst был выделен alloc’ом. А вдруг там просто был константный указатель?
facepalm.jpeg
Если в качестве параметра-назначения (dest) любой из функций вида str_cpy, strcpy и иже с ними был передан указатель на константную память — то написавшего это программиста уже не должно волновать что будет с кодом, потому что с большой долей вероятности к нему придет тимлид и совершит с программистом что-нибудь противоестественное в целях стимуляции кровообращения в тех местах, которыми бедолага думал при написании кода.
Это не проблема разработчика str_ библиотеки.
Мне кажется, если функция не обрабатывает все возможные ситуации (даже просто ничего не делая в этом случае, но как минимум не вызывая падение) то это проблема все-таки функции.
Предложите вариант решения (можно безотносительно данной задачи) на стандартном Си. Выберем лучший.
На чистом си кроме как переписать функции выделения/освобождения и учитывать все указатели на выделенные блоки с ходу в голову ничего не приходит. Не сложно, но при большом количестве выделенных блоков будет медленно.
Или мы еще free() в стандартной библиотеке перепишем, дабы никто не отстрелил себе пипку по неосторожности?
Ну конечно, и выделение и освобождение. Чтоб если код не работает то можно было бы быть уверенным, что ошибка на стороне пользователя функций. Это же прекрасно — сделать, забыть как устроено и просто пользоваться.
Открою секрет, это уже сделано до нас: ru.wikipedia.org/wiki/Python
Ну, я как бы в курсе, что много чего в мире существует. Речь же о чистом си, вдруг это задача для какого-то контроллера стиральной машины?
Для контроллера стиральной машины, а точнее, его эмулятора было бы логичнее один раз сделать отладочную версию libc с нужными проверками во free и не морочить голову
вот так наделают отладочных версий в эмуляторе, пересоберут, засунут в контроллер, а потом у них тойоты людей давят
Толсто. Отладочные версии не должны менять поведение. Даже точнее — отладочный код не должен менять поведение, он должен просто обрушить всё моментально при попытке некорректного использования.
а еще люди должны любить друг друга, хотя это уже флуд пошел
Любовь к ближнему непосредственно не влияет на качество кода. А неправильное понимание что такое «отладочная libc» — влияет.
Тогда тойоты будут глохнуть у разработчиков и никого не будут давить у пользователей.
В крайнем случае, можно вставить отладочные проверки в assert() или под #define, но это выходит за рамки поставленной задачи.
мгм, мы уже.
dou.ua/...ic/8356/#386401 и далее.
походу никакого перераспределения памяти внутри функций быть вообще не должно, только выделение при нулевом входном буфере. И надо отдать должное авторам, этот кейс с нулевым буфером вкупе с мантрами про «качественное и эффективое» меня сбил с толку :)
P.S.
константный указательимелся в виду наверное всё же указатель на стеке?
В комментарии/мануале должно быть указано, что эти функции — не для буфферов на стеке. А не то будет что-нибудь противоестественное.
да, имелось в виду, что не alloc/malloc/calloc. по стандарту free в этом случае должен удивить программиста
Вставлю свои 5 копеек.
Если уж в 4й строке вызываем — strlen(*dst),
то неплохо бы было перед этим *dst на NULL проверять.
например -
int dst_len = ((*dst) == 0 ? 0 : strlen(*dst));
Спорно. Как по мне — пусть падает. А вот убрать
if (!src || !dst)
return;
это точняк.
Сам клюнул на эту хрень. Но польстился на предлагаемую работу, а не на приз. Хотя в первом письме от этой ларисы был именно упор на работу. А задачу посчитал, что это прелюдия для собеседования. Хотя сразу нужно было остановиться и послать их подальше , потому как в main() были уже спрятаны “подводные камни” с указателями. Поэтому не вникая в нюансы, наваял минут за двадцать код в VC, что бы усе уложилось в 7 строк.
void str_cpy(char** strD, char* strS)
{
int len = strlen(strS);
if (!len) return;
char *str = (char*)malloc(len + 1);
strcpy(str, strS);
if (*strD) free(*strD);
*strD = str;
}
void str_cat(char** strD, char* strS)
{
if (!strS) return;
if (*strD == NULL ) return;
char* str = (char*)malloc(strlen(*strD) + strlen(strS) + 1);
strcpy(str, *strD);
strcat(str, strS);
free(*strD);
*strD = str;
}
Ответ пришел сразу от некого Ноама, со стандартными ответами на ошибки
— Your code creates incorrect results on some reasonable use cases —
hola.org/...correct_results
— Your code’s performance is significantly slower than a good implementation —
hola.org/c?performance
— str_cat’s performance is significantly slower than a good implementation —
hola.org/...perf_no_realloc
— Your argument validation is inconsistent/incomplete/illogical —
www.hola.org/c?inconsistent_arg_validation
— Your code may be simplified by using better suited functions —
hola.org/...uited_functions
— Your code includes redundant tokens— hola.org/...dant_tokens_cpp
— Inconsistent coding conventions — hola.org/...ing_conventions
— Your use of free() is not optimal — hola.org/c?free
— Clarification: Are you sure about choosing to not handle the case of
out-of-memory failure in your implementation? —
hola.org/...ailure_handling
Вопросы спорные, потому как задача была составлена, как контракт из МТС — нужно вчитываться во всякие нюансы .
Далее он говорит, что прайс будет поделен на двое и я может быть встречусь с ним. Т.е уклон уже переведен на бабки, а не на работу.
Ладно, хотите быстро, сделал код по другому, потратил уже НЕ 15 минут
#define MALLOC_CHECK_ 2
char*
str_cpy(char **str_dst, char *str_src)
{
int len_src = 0, len = 0;
char *str = NULL, *str_tmp = NULL;
/* Argument validation */
if (!str_src ||
!(len_src = strlen(str_src)) ||
!(str = (char*)malloc(len_src + 1)))
return NULL;
/* Release of memcpy(str, str_src, len_src) */
len = len_src;
str_tmp = str;
while (len—)
*str_tmp++ = *str_src++;
/* End of string and reallocation memory */
*(str + len_src) = 0×00;
free(*str_dst);
*str_dst = str;
return *str_dst;
}
char*
str_cat(char **str_dst, char *str_src)
{
int len_src = 0, len_dst = 0, len = 0;
char *str_tmp = NULL;
/* Argument validation */
if(!str_src || !(len_src = strlen(str_src)))
return !*str_dst ? NULL : *str_dst;
if (!*str_dst) {
*str_dst = str_src;
return str_src;
}
/* Allocation memory */
len_dst = strlen(*str_dst);
len = len_src + len_dst;
if(!(*str_dst = (char*)realloc(*str_dst, len + 1)))
return NULL;
/* Release of memcpy(*str_dst + len_dst, str_src, len_src); */
str_tmp = *str_dst + len_dst;
while (len_src—)
*str_tmp++ = *str_src++;
/* End of string */
*(*str_dst + len) = 0×00;
return *str_dst;
}
Ответ был, что и следовало ожидать — я не прошел тест, но я еще могу, что то заработать если найду им еще таких лохов, как я.
А с чем конкретно вы не согласны, что вам выслал Ноам?
вот я не согласен с этим:
— Your use of free() is not optimal — hola.org/c?freeНа той страничке автор советует прочитать man 3 free.
Скорей всего он имел в виду допустимость free(NULL);
увы... здесь, кажется, нету шансов попасть в ситуацию, когда нужно делать free(NULL)
Важно другое. «Ответы» подобраны так, что любое толковое решение можно подвергнуть сомнению... в стиле «вы не использовали возможность делать free(NULL)»
/* Release of memcpy(*str_dst + len_dst, str_src, len_src); */Хоть бы посмотрел как оно у ровных пацанчиков github.com/...cpy.c?source=cc
str_tmp = *str_dst + len_dst;
while (len_src—)
*str_tmp++ = *str_src++;
/* End of string */
*(*str_dst + len) = 0×00;
У ровных пацанчиков (и чотких дам) там memove();
Не те нынче рыцари пошли, не те :(
Стесняетесь оверлапа? Тю. Либце не стесняется, а вы стесняетесь?
И шо? Стесняюсь, в стандарте за memcpy написано «нельзя», значит нельзя. Замучаетесь гембели выискивать потом при переходе на другое Це.
У самых правильных там идёт такой код:
inline void* memcpy(void* b, const void* a, size_t n)
{
char* s1 = b;
const char* s2 = a;
for(; 0<n; --n)
{
*s1++ = *s2++;
}
return b;
}
А самые умные могут пояснить почему.
Как вы думаете, будет ли компилятор использовать SIMD в таком коде?
Безусловно.
Мозга не хватает. Но кажется здесь замешано лучшее предсказание процессором условных переходов.
Если target при компиляции установлен на SSE2 (а ставить меньше сегодня нужно только в единичных случаях), то gcc/icc/msvc превратят такой код в:
movdqu (%esi,%edx), %xmm0 movdqu %xmm0, (%eax,%edx)
и будут копировать по 16 байт за раз.
Вообще побайтовый мемкопи это жесть !
Насколько помню в нормальных системах должно быть примерно так ...
inline __asm memcopy(void *a, void *b, size_t n)
{
LEA ESI, B
LEA EDI, A
MOV CX, N
SHR CX,2
REP MOVSD /* x4 Собственно трансфер */
...
MOVSW /* x2 Если остаток больше > 1 */
...
MOVSB /* x1 Если остаток больше > 0 */
}
Кстати данный алгоритм был актуален до
через MOVSQ делать ...
В том-то и дело, что по-байтовый memcpy превратится во что угодно, а жёстко прописанные типы это уже конечный продукт.
Код тех ровных пацанчиков не вызывается с вероятностью 99.999%, а работает gcc’шный вариант. А у vicul код открыт для сериализации (и векторизации), gcc такой паттерн распознает.
Тот еще треш. Сударь, я бы постеснялась такое слать:
1. Копирование строк — пьяный угар;
2. realloc таки да, таки рулит;
3. зачем str_tmp? И вообще это —
len = len_src;курам на смех;
str_tmp = str;
Мадам, там еще товарищ внизу жалуется. Поясните ему.
Предпочитаю более точное «мадемуазель» или «мисс».
Нажмите CTRL-F, «Киса, куку», [ENTER]
Стартап Hola платит 500 $ всем, кто решит задачку по программированию на языке С. Лучшим предлагает удаленную работу на прекрасных условиях. Условия тут hola.org/jobs_ru.htmlи сколько уже набрали?
Из программистов, говорящих на русском (с начала сентября) заплатили 4 приза и троих приглашаем на работу (но только двое из призеров и один просто хорошо прошел интервью, но задачу не решил).
Well, guys, they are fake!
I sent him an answer... Below is what I got:
------------------------------------------------
Hi ***,
Thanks for your solution to the Hola challenge.
Although your answer basically works, it is not “perfect” — hola.org/...library_quality
I believe that you can provide a perfect answer. I’ve put together the issues that I’d like you to work on:
— Your code creates incorrect results on some reasonable use cases — hola.org/...correct_results
— Your code’s performance is significantly slower than a good implementation — hola.org/c?performance
— str_cat’s performance is significantly slower than a good implementation — hola.org/...perf_no_realloc
— Your implementation has a non-useful return value — hola.org/...ul_return_value
— Inappropriate handling of out-of-memory failure — hola.org/...?malloc_failure
— Your argument validation is inconsistent/incomplete/illogical — www.hola.org/c?inconsistent_arg_validation
— Your code may be simplified by using better suited functions — hola.org/...uited_functions
— Your code includes redundant tokens— hola.org/...dant_tokens_cpp
— Your use of free() is not optimal — hola.org/c?free
Please visit the links for guidelines on how to fix.
So, your answer is good, and when you resolve these issues it will be perfect. I will then be glad to see you get the prize and possibly meet you in person.
Best regards, ****
----------------------------------------------------
Please note: no links to the actual solution, their suggestions are inappropriate (not related to the code at all), requirements are not equal to original (they didn’t specified to rewrite “main”), and so on...
So, guys, don’t waste your time, don’t share your e-mails.
Админы, потрите этот трэш ради Бога. Тут же очевидно, что какой то школьник соскочил с сишарпа на цэ и обосрался по нормальному зделать две функции. И таки да — это задачка далеко не на 15 минут.
Судя по всему там сидят школьники: hola.org/...perf_no_realloc
Такой бред может написать только школьник, который ни разу не открывал стандарт C.
Не знаю. Я согласен с ними с точки зрения перфоманса. На маленьких строках должно работать особенно быстро. Если это сильно уж очень не срывает пелену с глаз, то поясни, что вы имели ввиду
Такой бред может написать только школьник, который ни разу не открывал стандарт C.Это относиться только к hola.org/...perf_no_realloc ?
Не знаю. Я согласен с ними с точки зрения перфоманса. На маленьких строках должно работать особенно быстро. Если это сильно уж очень не срывает пелену с глаз, то поясни, что вы имели ввидуС какого бодуна оно должно работать быстрее? Открываем C99 стандарт и читаем.
Это относиться только к hola.org/...perf_no_realloc ?Да, первое, что бросилось в глаза.
С какого бодуна оно должно работать быстрее? Открываем C99 стандарт и читаем.Это имеешь ввиду?
Насколько я понимаю, с того бодуна, что реаллок не всегда деаллоцирует старый обьект и аллоцирует новый.
Насколько я понимаю, с того бодуна, что реаллок не всегда деаллоцирует старый обьект и аллоцирует новый.
2 The realloc function deallocates the old object pointed to by ptr and returns a pointer to a new object that has the size specified by size.
маллок и реаллок у себя внутри выделяют чанки памяти поболее чем запрашивает пользователь и когда мы реаллоцируем уже что-то существующее, что не вылезает, грубо говоря, за размеры такого чанка, то операция реаллоцирования будет сравнительно быстрой.
Зачем выделять пустой памяти по-более? Я видел выделение неиспользуемой памяти только для выравнивания, но там копейки. А malloc маленьких размеров приводит к сумасшедшему overhead’у хипа.
Или вы говорите про какой-то определённый аллокатор?
Лень гуглить, но сейчас кажеться большинство стандартных реализаций аллокаторов выделяют память с запасом.
Вы наверное спутали постраничное выделение памяти хипа и больших кусков постранично с выделением памяти внтури хипа.
В любом случае указанное замечание
hola.org/...perf_no_realloc слишком implementation dependant и не соответствует даже древнему С99.
Вы наверное спутали постраничное выделение памяти хипа и больших кусков постранично с выделением памяти внтури хипа.Я скорее имел ввиду постраничное выделение памяти хипа.
больших кусков постранично с выделением памяти внтури хипа.Вот тут я даже не знаю, занимаються ли таким аллокаторы, и много ли из них.
void * realloc ( void * ptr, size_t size );
ptr: Pointer to a memory block previously allocated with malloc, calloc or realloc, or a null pointer (to allocate a new block)
size: New size for the memory block, in bytes
Realloc increases the size of the memory block pointed by ptr. If the current address of the memory block doesn’t has “size” free bytes after it. Realloc allocates a completely new memory block at a different location. So, realloc may move the memory block to a different address, so you might get a different ptr in return.
When the ptr is NULL, realloc exactly behaves like malloc. It allocated a memory block of size bytes long.
Не хочется нарушать накал профессиональной беседы, но вот уже 4 приза мы заплатили:))) И первого человека приняли на работу:))) — Виктора из Харькова
Это все здорово. Но все-же хотелось бы чтобы вы хоть как-то отреагировали на комментарий Александра Наумова (если это он конечно).
А как я могу отреагировать? Человек, который придумал задачу, сказал, что ему нужен тот, кто поймет без дополнительных объяснений. «Если нужно говорить, то не нужно говорить». Он так уже много лет людей нанимает (начал в прежней фирме Jango, и продал ее за 107 млн. долларов). И такие, судя по выплаченным призам и договорам о найме, есть. А я недостаточно понимаю в вопросе, чтобы лезть в дискуссию.
Рада:))) На самом деле если есть вопросы по процедуре, то это ко мне, а если к задаче — то я ничего не понимаю в программировании:))) Но еще раз говорю: 3 человека получили приз, один подписал уже договор о работе. Долго его убеждала, что мы не шутим:)))
Вот тут я даже не знаю, занимаються ли таким аллокаторы, и много ли из них.Ваш упомянутый glibc был в этом замечен.
Я просто думаю, что если взять банальный гну либцэ и запилить оба варианта реализации задачи на маленьких строках, реаллок победит.Жду бенчмарка в виде
void* tptr=NULL;
void* tptr2=NULL;
for (int it=1; it<1024*1024; it++)
{
tptr=realloc(tptr, it);
if (tptr2!=NULL)
{
free(tptr2);
}
tptr2=malloc(4095+it);
}
С другой стороны, если аллокатор использует заданное заранее количество poweroftwo блоков для мелких маллоков, то после их быстрого исчерпания, начнутся точно такие же тормоза. Т.е. если аллокатор использует блоки 32, 64, 128, 256 байт для мелких аллокаций, то при выделении 129 байт будет заюзан блок 256, который будет раздроблен на 1×129, 1×64, 1×32 и 31 байт свободных будут приписаны к 129. Но вы меня извините, если размер будет программером увеличиваться по нескольку байт, то тогда realloc будет неэффективен и медлен по сравнению с другими вариантами увеличения размера выделенной памяти (следующий абзац), если увеличение будет на большой размер, то realloc будет иметь такую же эффективность, что и malloc/free. Профита нет.
Т.е. хорошая реализация кода может увеличивать размеры выделенной памяти, допустим, кусками сразу по 64 байта за одно перевыделение, но это убъёт весь выигрышь от realloc()’а уже на 4 увеличении (а выигрыша и так не будет, т.к. будут выделяться каждый раз другие куски памяти большего размера). Т.е. в любом случае их замечание про realloc() бестолковое.
Не разбирался во всем что вы написали пока.
Жду бенчмарка в видеvoid* tptr=NULL;
void* tptr2=NULL;for (int it=1; it<1024*1024; it++)
{
tptr=realloc(tptr, it);
if (tptr2!=NULL)
{
free(tptr2);
}
tptr2=malloc(4095+it);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define BILLION 1E9
int main(int argc, const char * argv[]) {
struct timespec start, end;
double diff;
void *tptr = NULL;
void *tptr2 = NULL;
int it = 0;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for (it = 1; it < 1024 * 1024; it++) {
tptr = realloc(tptr, it);
/*
if(tptr2 != NULL) {
free(tptr2);
}
tptr2 = malloc(4095 + it);
*/
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
diff = (end.tv_sec — start.tv_sec) + (double)(end.tv_nsec — start.tv_nsec ) / BILLION;
printf("%f", diff);
return 0;
}
Конкретные числа ответа никакого не дадут, но скорость незакоментированной части быстрее закоментированной приблизительно в
Нет, нет, нет, оно должно быть раскомментировано для теста realloc(). Иначе это не настоящий тест.
Можете скинуть 2 разных тела цикла, а то я вас немного недопонимаю? Не понял просто что с чем вы хотите сравнить.
Это я привел полный пример для realloc() бенчмарка, не надо там ничего комментировать ;) Естественно, если делать realloc() последнему выделению, то всё будет быстро, но неествественно, в дикой природе такое будет встречаться очень редко.
Хорошо. Выходит мы всегда выигрываем в дикой природе.
Но в реальном мире реаллок за нас делает выделение новой памяти, копирование из старой области в новую и освобождение старой памяти. Вы же предлагаете в str_cat делать всегда malloc-memcpy, memcpy-free, как я понял, что то же самое что и realloc-memcpy.
Я предлагаю в str_cat делать malloc/realloc только если (newsize + 0×3F) & ~(0×3F) > (oldsize + 0×3F) & ~(0×3F), таким образом уменьшается количество вызовов функций в 64 раза. Если учесть, что в среднем сферическом аллокаторе в вакууме на 32 байта выделенной памяти приходится практически столько же оверхеда, то увеличение блоками по 64 байта не сильно увеличит расход памяти, как кажется на первый взгляд, всего лишь в 1,5 раза вместо двух. В этом же случае накладные расходы на вызов realloc или malloc+copy будут незначительными.
Тоже самое у них непонятное мне неадекватное замечание, что нужно вызывать free(NULL) без проверки указателя на NULL. И это в свете того, что они борятся за оптимальный код. Лучше один branch чем безусловный вызов функции.
Уважаемый, обозвавший меня школьником — может, предложите свой вариант решения?
Уважаемый, обозвавший меня школьником — может, предложите свой вариант решения?Естественно. Но только после того как отправлю и получу ответ.
Админы, потрите этот трэш ради Бога. Тут же очевидно, что какой то школьник соскочил с сишарпа на цэ и обосрался по нормальному зделать две функции.
Если будете писать дальше в таком стиле, придется стереть вас.
Сергей! Компания Hola убедительно просит Вас убрать из обсуждений решение задачи Александра Наумова и цитату из ответа ему Ноама. Дело в том, что конкурс продолжается, и это — прямые подсказки тем, кто может в нем участвовать. Спасибо заранее.
Сергей! Компания Hola убедительно просит Вас убрать из обсуждений решение задачи Александра Наумова и цитату из ответа ему Ноама. Дело в том, что конкурс продолжается, и это — прямые подсказки тем, кто может в нем участвовать. Спасибо заранее.Вот именно. Поэтому я и отреагировал так dou.ua/...ic/8356/#384948 .
Коментар порушує правила спільноти і видалений модераторами.
Сергей! Компания Hola убедительно просит Вас убрать из обсуждений решение задачи Александра Наумова и цитату из ответа ему Ноама. Дело в том, что конкурс продолжается, и это — прямые подсказки тем, кто может в нем участвовать. Спасибо заранее.Вот именно. Поэтому я и отреагировал так dou.ua/...ic/8356/#384948 .
решение задачи Александра Наумоване. трэшачок с войдами можно оставить :)
Коментар порушує правила спільноти і видалений модераторами.
забавно... меня уже лет двадцать никто школьником не обзывал...
Я для этого *хама* приведу моё решение.
flyman
void str_cpy(char **dst, char *src)
{
char *new_dst;
if (!dst) return;
if (!(new_dst = (char *)malloc(strlen(src) + 1))) return;
strcpy(new_dst, src);
free(*dst);
*dst = new_dst;
}
voidstr_cat(char **dst, char *src)
{
char *new_dst;
if (!dst) return;
if (!(new_dst = (char *)malloc((*dst ? strlen(*dst) : 0) + strlen(src) + 1))) return;
if (*dst) strcpy(new_dst, *dst);
strcat(new_dst, src);
free(*dst);
*dst = new_dst;
}
и напомню, что задача была — уместиться в 7 линий кода.
А теперь, уважаемый (ли ?) марко, прокомментируй. А лучше — предолжи своё решение, если не засц***
И еще. Я готов заплатить $10 каждому, кто найдёт ошибки в коде (в рамках постановки задачи!). Я серьезно.
У вас ошибка в самой постановке задачи, линий кода должно быть 8, или 10, в крайнем случае 6, но никак ни 7 ...
Это не у меня!! Это в их чудо-фейк-конторе ошибка
На правах наброса:
char* foo = NULL;
str_cpy(&foo, «Hello»); // Ok, by design
char* bar = NULL;
str_cat(&bar, «World»); // Undefined behaviour в строке ’strcat(new_dst, src)’
По аналогии с str_cpy в условии задачи можно сделать вывод, что такой вариант использования допустим.
P.S. $10 не хочу, интересно исключительно из любви к искусству.
Я полагаю: коль скоро в тексте main() такого use-case не было, то это не ошибка. Да, по-хорошему стоило бы проверять и в str_cat()...
patch:
-if (*dst) strcpy(new_dst, *dst);
+strcpy(new_dst, *dst ? *dst : "");
А вы пришлите нам код, и Ноам найдет вам ошибки за зарплату:)))
Sorry, probably you missed something.
I already sent the code, got an answer and even placed it here!
Unfortunately, Noam answered so generic so I suspect it’s a bot’ answers. Also, since Noam is an “awesome Javascripter” (as it said on some website), I think he easily implemented such “answer machine” to collect specific e-mails.
Hope you understand :)
And, please believe me, if Noam knows C and once he finds at least one error in my code (in terms of “main” function from the task), I will pay $10.
Напрасно вы так:((( Это похоже на «сам дурак»:))) Хотя по степени концентрации Ноам и правда похож на компьютер: за время, что я его знаю, он ни разу ни в чем не ошибся:)))
Да, хотела спросить: может быть, кто-то здесь программирует на JavaScript и Android Java? Мы ищем сотрудников:)))
Прикинь сам, а для чего в твоем коде str_free?
Probably str_free() would be more complex than free(). To use str_free() instead of free() isn’t effective solution, believe me.
Probably str_free() would be more complex than free().Да 100%.
To use str_free() instead of free() isn’t effective solution, believe me.Да я может и согласен, но деваться некуда. Из майна его не выкинешь же просто так.
But it’s not required to use str_free() inside str_cpy() or str_cat().
Instead, there is an suggestion to use functions declared in included headers.
But it’s not required to use str_free() inside str_cpy() or str_cat().А я и не спорю. Полностью согласен с этим утверждением.
No way.
In terms of their “main()”, it’s not explicitly desired to know. Both functions should never crash :)
Other side. Imagine you pass non-NULL although invalid argument as pointer to string. For example,
char *p = (char*)1; str_cpy(&p, “oops!”);
Do you think I should protect str_cpy against such cases? Well, probably it will take more than 7 lines of code as they suggest.
Надо признать, что ваше решение изящней оного у Викули (vicul). Но — не фонтан. Слашала я такие оговорки про «в терминах main()», когда разговор шёл о сексе.
Для Вас код не фонтан? Очень прошу, приведите свой пример, или укажите где плохо.
И, если не затруднит, дайте ссылку на «оного у Викули (vicul)», я не нашёл.
Если вы не счастливый обладатель ноутбука от одной фруктовой компании — нажмите CTRL-F, vicul, F3, F3. Серьёзный дядька в возрасте, а капризничаете как я. На маке не знаю, как.
Здрасьте вам через окно! Делали-делали, и недоделали!
if (!(new_dst = (char *)malloc(strlen(src) + 1))) return;
strcpy(new_dst, src);
free(*dst);
*dst = new_dst;
if (!(new_dst = (char *)malloc(strlen(src) + 1))) return; free(*dst); *dst = strcpy(new_dst, src);Более по-человечески, не находите?
да, нахожу. Впрочем, эта «оптимизация» влияет более на читаемость, нежели на производительность.
Не в качестве оправдания (а в борьбе за здравый смысл) — зачем strcpy() возвращает указатель? почему я должен использовать именно возвращаемое значение? неужели лишь для экономии линий кода?
Представьте, что я — junior, читающий такой код. Не помня назначения и сигнатуры strcpy(), я мог бы подумать, что эта функция возвращает что-то, отличное от new_dst... но постойте, я же только что выделил под new_dst память... и что же с ней стало? может, освободить её?..
... короче, *dst = strcpy(new_dst, src); — менее понятный способ, хотя и лаконичный.
Джуниор идет в гугл. Более опытный коллега пишет strcat(strcpy(str, «hello»), «world»);
И да,
> if (!dst) return;
> if (!(new_dst = (char *)malloc(strlen(src) + 1))) return;
if ( dst && (new_dst = (char *)malloc(strlen(src) + 1)) )
{
...
}Выглядит лучше и строк меньше. Никто адекватный скобки за строки считать не будет.присваивать значение переменной внутри if — плохой стиль, значительно ухудшающий читаемость.
Я за то, чтобы каждая строка кода была использована разумно... if — для проверки условий, а не для того, чтобы внутри что-то присваивать. Не ровён час, добьётесь забавных эффектов.
Полностью поддерживаю, я за это не одни джунские руки отбил.
Товарищ Александр Наумов тоже джуниор?
Раб странных требований.
И я вообще не понимаю, почему народ стесняется сделать один большой one-liner. Там можно и не делать присваивание в условиях и т.п.
Я уже напоминала про оператор запятая. Вот где сила!
Согласна. Особенно забавно это звучит в контексте того, что это самое присваивание внутри if я скопипастила прямо из вашего кода ;) где это выглядело как:
if (!(new_dst = (char *)malloc((*dst ? strlen(*dst) : 0) + strlen(src) + 1))) return;
Похоже, вы так эмоционировали от того, что ваши ошибки критикует студентка, что забыли, что писали двумя экранами выше)))) Не забыли, как вас зовут?
Привет,
во-первых, я такое присвоение написал, пожалуй, впервые в жизни — и только ради того, чтобы уместиться в 7 строк. В реале — отобью руки за такой код.
Во-вторых, откуда мне знать, студентка ли Вы. Что реагирую эмоционально — да, такую фамильярную критику близко к сердцу принимаю.
В-третьих, да, я и правда забыл как меня зовут! Чуть не впервые в жизни меня занесло в соц.сеть, а тут такое... и школьником обозвали, и студентка покритиковала, и в джуниорах заподозрили... танунах, лучше пойду напишу драйверок.
Вам дико повезло, что не обозвали кровавым драйверописателем.
когда Вы будете в отладчике, на вот такой строке
if ( dst && (new_dst = (char *)malloc(strlen(src) + 1)))
легко ли Вы сообразите, почему не попали внутрь?
а если строк будет две, у Вас есть шанс увидеть, или это dst нулевой, или malloc вернул нуль.
Тогда я наберу в консоли отладчика «dv» или даже «print dst» и всё станет ясно, как божий день.
Рискуя показаться занудой я еще замечу, что «dv» после неудачного if-a отработает нормально. А после return; в вашем коде — не отработает.
Ребята, ну в 3й строке ф-ции str_cpy, src на NULL не проверяем и суем ее в strlen...
Не могу писать фамилию, но нет, Вы не угадали. Но могу, наверное, сказать что он из Харькова:))) И еще один уже есть — Максим. Тоже Украина. Вот так:)))
Ну вот, есть первый победитель с Украины — Виктор. И он получил предложение о работе:)))
Федорович небось?)
Они хотят «Код, написанный вами, должен соответствовать по качеству библиотечному коду, как в хорошей реализации libc.» а в задаче:
int main(int argc, char *argv[])
{
char *s = NULL;
str_cpy(&s, «Hola Hola»);
str_cpy(&s, s+5);
str_cat(&s, " World«);
str_printf(&s, «%s!», s);
puts(s); /* result: «Hola World!» */
str_free(&s);
return 0;
}
-------
тость str_cpy каким-то образом прячет выделение памяти, а если ей передатся не нул, то освободжает память и заново выделяет ее, а еще есть str_cat ? это и близко не путь libc, это гавнокод для сишника-самоубийцы который работу с памятью и строками свалил в одну кучу.
тость str_cpy каким-то образом прячет выделение памяти, а если ей передатся не нул, то освободжает память и заново выделяет ее,Я так понимаю, что они ещё хотят свой аллокатор, ведь неизвестно сколько памяти может использовать str_cpy по переданному указателю. Т.е. выделять size+sizeof(size), в *ptr хранить этот самый size, а юзеру возращать сдвинутый указатель ptr+sizeof(size). Ну а свой подобный аллокатор — это бомба замедленного действия, особенно если кто-то сделает free(ptr) вместо free(ptr-4).
ой ... как то это совсем грустно
Такую задачу лучше делать на собеседовании чтобы иметь возможность задавать уточняющие вопросы. Проверяющие нормальную реализацию, но несоответствующую их пожеланиям по поведению функций, могут запросто отфутболить. Может проверяют реакцию на неполное описание задачи. Но разделение на «идеальное» и «неидеальное» явно натянуто с такой расплывчатой формулировкой
фразу «Очень высокая зарплата» любой хр говорит (пишет) 30 раз на дню
Там требования сильно расплывчатые, фраза «как в хорошей реализации libc» отпугивает почему-то, т.е придраться можно ко всему. Например, если указать, что основные элементы поведения взяты у POSIX strcpy/strcat, то будет гораздо меньше недомолвок. Т.е. можно смело передавать NULL в качестве всех аргументов, использовать buffer overflow и overlapped regions (использовать ли memcpy или memmove или использовать компиляторную векторную сериализацию a la memcpy) и чхать на поведение функции. С другой стороны они могут посчитать реализацию, которая чекает все входные параметры неэффективной. Непонятно, что функции должны возвращать, str_cat можно/нужно реализовать через str_cpy() и т.д. и т.п. Т.е. $250 скостить нефиг делать, что они, собственно, и делают, даже отписки одинаковые %)
Ну а потом, чтобы забрать деньги, надо будет что-то ещё написать, пройти собеседование, а дальше ждёт настощий аццкий ад на работе, судя по отзывам работавших там и те $250 будут прокляты триста раз :)
Кстати, вы же крутой перец, небось разрулили задачу уже? ))
Такие задачи приходится решать каждый день, вот только у меня свои критерии идеальности и они явно не совпадают с их критериями.
Угу — судя по простоте задачи, типичная обманка: ищут не решение задачи, а соответствие заранее утаённым критериям стиля.
Ну тут как бы рецепт простой — пишем решение, отправляем, смотрим что именно ответили. Меня к примеру остановила не разоговры о качестве а размытость требований, я совсем не с первого разу вьехал в то что же они хотят. Если получу ответ-поделюсь впечатлениями
Ну а потом, чтобы забрать деньги, надо будет что-то ещё написать, пройти собеседование
У меня друг туда на удаленку устроился. Ни про какие такие ужасы не рассказывал.
Он хоть и живет в стране северного сияния и летних ужинов в свитере, но работает вполне себе в Израиле. Чем не мечта
P.S. Я ему реферальную ссылку не по правилам отправил, а так бы и мне перепало.
У меня друг туда на удаленку устроился. Ни про какие такие ужасы не рассказывал.Мне про эту компанию рассказывал одноклассник, который уже лет 15 в .il и работал там относительно недолго. Вы думаете в .il мало спецов, которые могут справится с этой задачей? Их валом, но, видать, там уже никто не хочет работать, поэтому кинулись сюда, у меня другого объяснения нет.
Да, там если посмотреть на график получения призов, интересные выводы напрашиваются.
Впрочем, я желаю удачи всем участникам.
Этот?
3-Oct-2013 Alexey F. Norway
3 октября — это прошлый четверг. Может, вернёмся к вопросу его работы месяца через 3?
Условия задачи сформулированы неявно, а значит — неоднозначно, поэтому при обсуждении подобной задачи не так важно, что человек напишет, как что спросит и скажет. Выставление же приза за правильное решение предполагает однозначный acceptance criterion, что в связке с расплывчатыми условиями выглядит странно.
3-Oct-2013 Alexey F. NorwayТам есть ещё один чуть раньше месяцев на
Ну так цель же конкурса не дать 500 у.е. всем желающим :)) А найти сотрудника. Отсюда и условия.
Ну с этим и не поспоришь :)
так этому челенджу уже с пол-года — год. Там ещё в оригинальном тексте что-то про Jungo guys говорилось. Я правда не заметил что это ХР ихний. Думал кто-то в очередной раз набрёл на него
Кеды хорошо настроены, коньки использовала?
А почему именно C? Я думал на сях сейчас только низкоуровневые вещи пишутся.
Отдельный вопрос по hola — зачем выставлять продукт, если он ещё не работает??
Сегодня второй человек из русскоговорящих стран получит приз:))) (Первый был из Украины):)))
А Вам не кажется подозрительной сверхвысокая плотность призеров из Израиля и что большая часть из 25К может осесть у одного предводителя :)
Шо, ви таки завидуете умным людЯм?
Евреи не только умные, но и предприимчивые.
Как в анекдоте:
Судили еврея и армянина, прокурор получил 8 лет.
Кому ліньки клікати на картинку, — бюджет проекту 25К баксів, в Ізраїлі вже «біля» 60 людей отримали винагороду, ітого, 25000/60=~416 багсів. Євреї тут антисемітизму не побачать?)))
Если задача решена со второй попытки, они говорят, что платят 250 долларов, может дело в этом.
Абсолютное большинство получают половину — решают с подсказкой:))) habrahabr.ru/post/193308
Oleh Korotkov
Galip Oslon
Ruslan Shevchenko
Igor Petruk
Ruslan Shevchenko
Леголас Трандуилович
Леголас Трандуилович
Ivan Chuba
Олексій Пєніє
Апполинарий Эмануилович
Volodymyr Rudyi
325 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів