История изменений

// This is a personal academic project. Dear PVS-Studio, please check it.
// PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <assert.h>

typedef char* owned_string;

typedef char const* unowned_string;

typedef unowned_string* unowned_string_ptr;

typedef void* not_null_void_ptr;

typedef owned_string* owned_array_owned_string;

typedef char const*const* unowned_array_unowned_string;


not_null_void_ptr my_malloc(size_t size)
{
	void* result = malloc(size);
	if (result == NULL) {
		fprintf(stderr, "malloc\n");
		abort();
	}
	return result;
}

owned_string random_str(size_t len)
{
	static const char chars[] = 
		"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
	static const size_t chars_len = sizeof(chars)-1; // не учитываем последний '\0'

	owned_string random_chars = (owned_string)my_malloc(len+1); // +1 для '\0'
	for (size_t i = 0; i < len; ++i) {
		random_chars[i] = chars[rand() % chars_len];
	}
	random_chars[len] = '\0';
	return random_chars;
}

owned_string random_string_100()
{
	return random_str(100);
}

owned_string random_string_20()
{
	return random_str(20);
}

owned_array_owned_string array_init(size_t len, owned_string(*initializer) ())
{
	owned_array_owned_string array = 
		(owned_array_owned_string)my_malloc(len*sizeof(owned_string));

	for (size_t i = 0; i < len; ++i) {
		array[i] = initializer();
	}
	return array;
}

void array_free(size_t len, owned_array_owned_string array)
{
	for (size_t i = 0; i < len; ++i) {
		free(array[i]);
	}
	free(array);
}

static unowned_string_ptr test_string = NULL;

bool has_substring_of_test_string_in_str(unowned_string str)
{
	assert(test_string != NULL);
	return strstr(str, *test_string) != NULL;
}

bool array_exists(size_t len, 
	unowned_array_unowned_string arr, bool (*pred)(unowned_string))
{
	for (size_t i = 0; i < len; ++i) {
		if (pred(arr[i])) {
			return true;
		}
	}
	return false;
}


int main(void)
{
	srand((unsigned)time(NULL));

	for (int i = 0; i < 10; ++i) 
	{
		clock_t start = clock();
		size_t array_size = 100000;
		owned_array_owned_string array = array_init(array_size, random_string_100);
		size_t matches = 0;
		for (int j = 0; j < 1000; ++j)
		{
			owned_string s20 = random_string_20();
			unowned_string temp = s20;
			test_string = &temp;
			bool found = array_exists(array_size, (unowned_array_unowned_string)array,
				has_substring_of_test_string_in_str);
			if (found) {
				++matches;
			}
			free(s20);
			test_string = NULL; // просто убираем висячий указатель на 
			// всякий случай, компилятор выкинет это, но так спокойней
		}
		array_free(array_size, array);
		clock_t end = clock();
		double time_elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;
		printf("%zu strings matches, time=%f\n", matches, time_elapsed);
	}
}

0 strings matches, time=6.982000
0 strings matches, time=6.681000
0 strings matches, time=6.776000
0 strings matches, time=6.803000
0 strings matches, time=6.741000
0 strings matches, time=6.665000
0 strings matches, time=6.646000
0 strings matches, time=6.686000
0 strings matches, time=6.854000
0 strings matches, time=7.093000

// This is a personal academic project. Dear PVS-Studio, please check it.
// PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <assert.h>

typedef char* owned_string;

typedef char const* unowned_string;

typedef unowned_string* unowned_string_ptr;

typedef void* not_null_void_ptr;

typedef owned_string* owned_array_owned_string;

typedef char const*const* unowned_array_unowned_string;


not_null_void_ptr my_malloc(size_t size)
{
	void* result = malloc(size);
	if (result == NULL) {
		fprintf(stderr, "malloc\n");
		abort();
	}
	return result;
}

owned_string random_str(size_t len)
{
	static const char chars[] = 
		"abcdefghijklmnopqrtuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
	static const size_t chars_len = sizeof(chars)-1; // не учитываем последний '\0'

	owned_string random_chars = (owned_string)my_malloc(len+1); // +1 для '\0'
	for (size_t i = 0; i < len; ++i) {
		random_chars[i] = chars[rand() % chars_len];
	}
	random_chars[len] = '\0';
	return random_chars;
}

owned_string random_string_100()
{
	return random_str(100);
}

owned_string random_string_20()
{
	return random_str(20);
}

owned_array_owned_string array_init(size_t len, owned_string(*initializer) ())
{
	owned_array_owned_string array = 
		(owned_array_owned_string)my_malloc(len*sizeof(owned_string));

	for (size_t i = 0; i < len; ++i) {
		array[i] = initializer();
	}
	return array;
}

void array_free(size_t len, owned_array_owned_string array)
{
	for (size_t i = 0; i < len; ++i) {
		free(array[i]);
	}
	free(array);
}

static unowned_string_ptr test_string = NULL;

bool has_substring_of_test_string_in_str(unowned_string str)
{
	assert(test_string != NULL);
	return strstr(str, *test_string) != NULL;
}

bool array_exists(size_t len, 
	unowned_array_unowned_string arr, bool (*pred)(unowned_string))
{
	for (size_t i = 0; i < len; ++i) {
		if (pred(arr[i])) {
			return true;
		}
	}
	return false;
}


int main(void)
{
	srand((unsigned)time(NULL));

	for (int i = 0; i < 10; ++i) 
	{
		clock_t start = clock();
		size_t array_size = 100000;
		owned_array_owned_string array = array_init(array_size, random_string_100);
		size_t matches = 0;
		for (int j = 0; j < 1000; ++j)
		{
			owned_string s20 = random_string_20();
			unowned_string temp = s20;
			test_string = &temp;
			bool found = array_exists(array_size, (unowned_array_unowned_string)array,
				has_substring_of_test_string_in_str);
			if (found) {
				++matches;
			}
			free(s20);
			test_string = NULL; // просто убираем висячий указатель на 
			// всякий случай, компилятор выкинет это, но так спокойней
		}
		array_free(array_size, array);
		clock_t end = clock();
		double time_elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;
		printf("%zu strings matches, time=%f\n", matches, time_elapsed);
	}
}

0 strings matches, time=6.982000
0 strings matches, time=6.681000
0 strings matches, time=6.776000
0 strings matches, time=6.803000
0 strings matches, time=6.741000
0 strings matches, time=6.665000
0 strings matches, time=6.646000
0 strings matches, time=6.686000
0 strings matches, time=6.854000
0 strings matches, time=7.093000