Four is the number of letters in the ...: Difference between revisions

Content added Content deleted
(Performance improvement)
(C - reduce memory usage)
Line 136: Line 136:
}
}


⚫
typedef struct string_buffer_tag {
#define SHORT_STRING_MAX 16

⚫
typedef struct string_tag {
size_t size;
size_t size;
size_t capacity;
size_t capacity;
union {
char* string;
} string_buffer;
char buffer[SHORT_STRING_MAX];
char* ptr;
⚫
} str;
} string_t;


void string_create(string_t* s, const char* str) {
void string_buffer_create(string_buffer* buffer, size_t capacity) {
size_t len = strlen(str);
buffer->size = 0;
size_t capacity = len + 1;
buffer->capacity = capacity;
if (SHORT_STRING_MAX < capacity) {
buffer->string = xmalloc(capacity);
s->str.ptr = xmalloc(capacity);
⚫
s->capacity = capacity;
memcpy(s->str.ptr, str, len + 1);
} else {
s->capacity = SHORT_STRING_MAX;
⚫
memcpy(s->str.buffer, str, len + 1);
}
⚫
s->size = len;
}
}


void string_destroy(string_t* s) {
void string_buffer_destroy(string_buffer* buffer) {
⚫
free(buffer->string);
if (s->capacity > SHORT_STRING_MAX)
buffer->string = NULL;
⚫
free(s->str.ptr);
s->size = 0;
buffer->size = 0;
s->capacity = 0;
buffer->capacity = 0;
}
}


void string_buffer_clear(string_buffer* buffer) {
⚫
void string_append(string_t* s, const char* str) {
size_t len = strlen(str);
buffer->size = 0;
⚫
}
⚫
size_t min_capacity = len + s->size + 1;

if (s->capacity < min_capacity) {
void string_buffer_append(string_buffer* buffer, const char* str, size_t len) {
⚫
size_t new_capacity = 2 * s->capacity;
⚫
size_t min_capacity = buffer->size + len + 1;
⚫
if (buffer->capacity < min_capacity) {
⚫
size_t new_capacity = 5*buffer->capacity/4;
if (new_capacity < min_capacity)
if (new_capacity < min_capacity)
new_capacity = min_capacity;
new_capacity = min_capacity;
if (s->capacity == SHORT_STRING_MAX) {
buffer->string = xrealloc(buffer->string, new_capacity);
char* ptr = xmalloc(new_capacity);
buffer->capacity = new_capacity;
memcpy(ptr, s->str.buffer, s->size);
s->str.ptr = ptr;
}
else
s->str.ptr = xrealloc(s->str.ptr, new_capacity);
s->capacity = new_capacity;
}
}
⚫
memcpy(buffer->string + buffer->size, str, len + 1);
char* dst = s->capacity > SHORT_STRING_MAX ? s->str.ptr : s->str.buffer;
memcpy(dst + s->size, str, len + 1);
buffer->size += len;
⚫
s->size += len;
}
}


typedef struct word_tag {
const char* string_cstr(const string_t* s) {
size_t offset;
return s->capacity > SHORT_STRING_MAX ? s->str.ptr : s->str.buffer;
⚫
size_t length;
⚫
}
} word;

size_t string_length(const string_t* s) {
return s->size;
⚫
}


typedef struct word_list_tag {
typedef struct word_list_tag {
size_t size;
size_t size;
size_t capacity;
size_t capacity;
string_t* words;
word* words;
⚫
string_buffer str;
} word_list;
} word_list;


Line 206: Line 187:
words->size = 0;
words->size = 0;
words->capacity = capacity;
words->capacity = capacity;
words->words = xmalloc(capacity * sizeof(string_t));
words->words = xmalloc(capacity * sizeof(word));
string_buffer_create(&words->str, capacity*8);
}
}


void word_list_destroy(word_list* words) {
void word_list_destroy(word_list* words) {
for (size_t i = 0; i < words->size; ++i)
string_buffer_destroy(&words->str);
⚫
string_destroy(&words->words[i]);
free(words->words);
free(words->words);
words->words = NULL;
words->words = NULL;
Line 219: Line 200:


void word_list_clear(word_list* words) {
void word_list_clear(word_list* words) {
for (size_t i = 0; i < words->size; ++i)
string_buffer_clear(&words->str);
string_destroy(&words->words[i]);
words->size = 0;
words->size = 0;
}
}


string_t* word_list_append(word_list* words, const char* str) {
void word_list_append(word_list* words, const char* str) {
size_t offset = words->str.size;
size_t len = strlen(str);
string_buffer_append(&words->str, str, len);
size_t min_capacity = words->size + 1;
size_t min_capacity = words->size + 1;
if (words->capacity < min_capacity) {
if (words->capacity < min_capacity) {
size_t new_capacity = (words->capacity * 3)/2;
size_t new_capacity = (words->capacity * 5)/4;
if (new_capacity < min_capacity)
if (new_capacity < min_capacity)
new_capacity = min_capacity;
new_capacity = min_capacity;
words->words = xrealloc(words->words, new_capacity * sizeof(string_t));
words->words = xrealloc(words->words, new_capacity * sizeof(word));
words->capacity = new_capacity;
words->capacity = new_capacity;
}
}
string_t* s = &words->words[words->size++];
word* w = &words->words[words->size++];
⚫
w->offset = offset;
string_create(s, str);
return s;
w->length = len;
⚫
}

⚫
void word_list_extend(word_list* words, const char* str) {
word* w = &words->words[words->size - 1];
size_t len = strlen(str);
⚫
w->length += len;
string_buffer_append(&words->str, str, len);
}
}


Line 247: Line 237:
word_list_append(words, get_small_name(&tens[n/10 - 2], ordinal));
word_list_append(words, get_small_name(&tens[n/10 - 2], ordinal));
} else {
} else {
string_t* str = word_list_append(words, get_small_name(&tens[n/10 - 2], false));
word_list_append(words, get_small_name(&tens[n/10 - 2], false));
string_append(str, "-");
word_list_extend(words, "-");
string_append(str, get_small_name(&small[n % 10], ordinal));
word_list_extend(words, get_small_name(&small[n % 10], ordinal));
}
}
count = 1;
count = 1;
Line 268: Line 258:
}
}


size_t count_letters(const string_t* str) {
size_t count_letters(const word_list* words, size_t index) {
⚫
const word* w = &words->words[index];
size_t letters = 0;
size_t letters = 0;
const char* s = string_cstr(str);
const char* s = words->str.string + w->offset;
for (size_t i = 0, n = string_length(str); i < n; ++i) {
for (size_t i = 0, n = w->length; i < n; ++i) {
if (isalpha((unsigned char)s[i]))
if (isalpha((unsigned char)s[i]))
++letters;
++letters;
Line 288: Line 279:
word_list_append(result, words[i]);
word_list_append(result, words[i]);
for (size_t i = 1; count > n; ++i) {
for (size_t i = 1; count > n; ++i) {
n += append_number_name(result, count_letters(&result->words[i]), false);
n += append_number_name(result, count_letters(result, i), false);
word_list_append(result, "in");
word_list_append(result, "in");
word_list_append(result, "the");
word_list_append(result, "the");
Line 294: Line 285:
n += append_number_name(result, i + 1, true);
n += append_number_name(result, i + 1, true);
// Append a comma to the final word
// Append a comma to the final word
string_append(&result->words[result->size - 1], ",");
word_list_extend(result, ",");
}
}
}
}
Line 302: Line 293:
if (n == 0)
if (n == 0)
return 0;
return 0;
size_t length = n - 1;
return words->str.size + n - 1;
for (size_t i = 0; i < n; ++i)
length += string_length(&words->words[i]);
⚫
return length;
}
}


Line 318: Line 306:
if (i != 0)
if (i != 0)
printf("%c", i % 25 == 0 ? '\n' : ' ');
printf("%c", i % 25 == 0 ? '\n' : ' ');
printf("%'2lu", count_letters(&result.words[i]));
printf("%'2lu", count_letters(&result, i));
}
}
printf("\nSentence length: %'lu\n", sentence_length(&result));
printf("\nSentence length: %'lu\n", sentence_length(&result));
for (n = 1000; n <= 10000000; n *= 10) {
for (n = 1000; n <= 10000000; n *= 10) {
sentence(&result, n);
sentence(&result, n);
const string_t* word = &result.words[n - 1];
const word* w = &result.words[n - 1];
const char* s = result.str.string + w->offset;
printf("The %'luth word is '%s' and has %lu letters. ", n, string_cstr(word),
printf("The %'luth word is '%.*s' and has %lu letters. ", n, (int)w->length, s,
count_letters(word));
count_letters(&result, n - 1));
printf("Sentence length: %'lu\n" , sentence_length(&result));
printf("Sentence length: %'lu\n" , sentence_length(&result));
}
}
Retrieved from "https://rosettacode.org/wiki/Four_is_the_number_of_letters_in_the_..."