VPF::Задачка на С не на 5 минут - Форум программистов

MGami

Дата 2.10.2013, 12:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 2.10.2013

Репутация: нет
Всего: нет

Добрый день! Друг прислал ссылку с задачей на языке С. Показалось - очень простая. На деле - совсем нет.
Условия тут: http://hola.org/jobs_ru.html
Дорешал до:

Код

int str_cpy(char **out_str, const char *arg)
{
        char *str = malloc(strlen(arg) + 1);

        if (str) {
                strcpy(str, arg);

                free(*out_str);

                /* update the result */
                *out_str = str;
        }
        else {
                /* error handling */
                return -1;
        }

        return 0;
}

int str_cat(char **out_str, const char *arg)
{
        size_t out_len = strlen(*out_str);
        char *str = realloc(*out_str, out_len + strlen(arg) + 1);

        if (str) {
                strcpy(str + out_len, arg);

                /* update the result */
                *out_str = str;
        }
        else {
                /* error handling */
                return -1;
        }

        return 0;
}

и застрял. Прошу помощи. Если решиам - приз отдам, не в призу уже дело:))) Или сами попробуйте...

Модератор: Не забываем пользоваться кнопочкой "код".

Это сообщение отредактировал(а) bsa - 2.10.2013, 22:04

feodorv

Дата 2.10.2013, 13:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Какой-то развод smile

Понятие об идеале у всех разное... Так пойдёт:

Код


char *str_cpy( char **pdst, const char *src)
{
  char *s = *pdst;
  *pdst = strdup( src );
  if( s != NULL ) str_free( &s );
  return *pdst;
}

или нужно "эффективнее":

Код


char *str_cpy( char **pdst, const char *src)
{
  if( *pdst != NULL && strlen(*pdst) >= strlen(src) )
    strcpy( *pdst, src);
  else 
  {
    if( *pdst != NULL ) str_free( pdst );
    *pdst = strdup( src );
  }
  return *pdst;
}

Это сообщение отредактировал(а) feodorv - 2.10.2013, 13:08

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

volatile

Дата 2.10.2013, 16:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата

На этот проект выделено 25 000 долларов. В Израиле около 60 человек уже получили вознаграждение

60 x $500 = $30,000

Походу, у них перерасход бюджета уже. smile

И кстати, почему только в израиле? Что, в других странах не нашлось программистов способных решить столь сложную задачу?

baldina

Дата 2.10.2013, 21:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

они пишут, что решившие не с первого раза по 250 получают, так что с арифметикой в порядке.
но денег осталось мало, спешите smile

bsa

Дата 2.10.2013, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

MGami, feodorv, у вас лишние ресурсы тратятся на измерение длины строки. strcpy работает медленней memcpy. А длина строки все равно вычисляется. Более того, можно использовать realloc для выделения памяти.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

volatile

Дата 2.10.2013, 23:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(bsa @ 2.10.2013, 22:01

)

memcpy

меммув лучше заюзать, там накладываются строки у них.

Добавлено через 3 минуты и 3 секунды
да и кто получит хоть 1$ с этой темы, отпишитесь, плиз smile

bsa

Дата 3.10.2013, 00:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

volatile, memmove лучше не использовать. Так как это уже неоптимально - лишняя буферизация.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

volatile

Дата 3.10.2013, 08:24 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(bsa @ 3.10.2013, 00:11

)

volatile, memmove лучше не использовать.

В варианте предложенным feodorv, нет разговора, лучше или хуже.
Мы там просто обязаны использовать memmove, потому-что у них в примере есть такой вызов:

Код

str_cpy(&s, s+5);

здесь memcpy (как впрочем и strcpy) поведет себя неопределенным образом.

Цитата(bsa @ 3.10.2013, 00:11

)

Так как это уже неоптимально - лишняя буферизация.

нет никокой лишней буферизации, мы уже это обсуждали с вами.

MGami

Дата 3.10.2013, 09:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 2.10.2013

Репутация: нет
Всего: нет

Вот тут прикольные размышления на эту тему и, кстати, о том, кто уже получил бабки:)))

http://habrahabr.ru/post/193308/

akizelokro

Дата 3.10.2013, 15:24 (ссылка)

(нет голосов)

Загрузка ...

Крокодил

Профиль
Группа: Участник
Сообщений: 761
Регистрация: 30.7.2007

Репутация: 1
Всего: 5

Я вообще не уверен в порядке вычисления в строках, инициализируемых в параметрах (но я не особо лихой программист, если по чесноку).
Я что-то всегда считал, что подобная конструкция

Код


func(char ** dest, "Hola Hola");

может в разных компиляторах исполняться либо как

Код


char * temp = "Hola Hola";
func(dest, temp);

либо как

Код


char * temp;
func(dest, temp);
temp = "Hola Hola";

Добавлено @ 15:26
Отсюда я бы начал с того, что сигнатура функций должна быть другой.
Но если меня подправят знающие люди, то я избавлюсь от одного заблуждения, что уже прогресс

Это сообщение отредактировал(а) akizelokro - 3.10.2013, 15:28

--------------------

a = a + b; b = a - b; a = a - b;

volatile

Дата 3.10.2013, 15:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(akizelokro @ 3.10.2013, 15:24

)

Я что-то всегда считал, что подобная конструкция
func(char ** dest, "Hola Hola");

К слову, подобная конструкция вообще не скомпилируеца, но не будем придирацца
вы видимо имели ввиду вызов функции:

Код


func(dest, "Hola Hola");

Здесь порядок будет именно таким:
const char * temp = "Hola Hola";
func(dest, temp);

А то что вы слышали звон про неопределенность порядка вычисления аргуметнов функций, то не от туда он.
Неопредееленность здесь в том что неизвестно, что вычислится первым
dest или temp

akizelokro

Дата 3.10.2013, 16:01 (ссылка)

(нет голосов)

Загрузка ...

Крокодил

Профиль
Группа: Участник
Сообщений: 761
Регистрация: 30.7.2007

Репутация: 1
Всего: 5

Цитата(volatile @ 3.10.2013, 15:55

)

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

Спасибо большое!

--------------------

a = a + b; b = a - b; a = a - b;

bsa

Дата 9.10.2013, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Я бы сделал как-то так:

Код

/* Copyright (C) Hola 2012, 2013
 *
 * Welcome to TheCodeIL.com Challenge!
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

void str_cpy(char **dst, const char *src)
{
    size_t size = strlen(src) + 1; //do not forget of '\0'
    char *ret = (char*)malloc(size);
    memcpy(ret, src, size);
    if (*dst)
       str_free(*dst);
    *dst = ret;
}

void str_cat(char **dst, const char *src)
{
   if (*dst) {
      size_t src_size = strlen(src) + 1;
      size_t dst_size = strlen(*dst);
      *dst = (char*)realloc(*dst, src_size + dst_size);
      memcpy(*dst + dst_size, src, src_size);
   } else
      str_cpy(dst, src);
}

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 нельзя использовать realloc, так как он сделает неверным указатель src.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

feodorv

Дата 12.10.2013, 11:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(volatile @ 3.10.2013, 09:24

)

Мы там просто обязаны использовать memmove

Ну да, однозначно memmove.
Я просто хотел понять, что "идеальнее" с точки зрения hola.org: использовать старую память, если в неё влезает строка (а единственный доступный способ - сравнить длины строк), или лучше каждый раз перезаказывать память smile

Есть некоторый намёк на то, что всё не просто:

Цитата

эффективная реализация функций str_cpy и str_cat умещается в 7 строк кода на функцию

Куда там 7 строк для str_cpy, если делаем банальный strdup.

Цитата(bsa @ 10.10.2013, 00:22

)

В str_cpy нельзя использовать realloc, так как он сделает неверным указатель src.

Можно проверять перекрытие строк smile

Но опять-таки, входит это в понятие "идеальности" или нет...

Цитата(bsa @ 10.10.2013, 00:22

)

if (*dst)
str_free(*dst);

Мне почему-то кажется, что str_free проверит аргумент на NULL. И таки str_free(dst)...

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

bsa

Дата 14.10.2013, 09:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »