- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
typedef struct {
char * begin;
uint64_t size, data_size;
} str_t;
inline uint64_t max(uint64_t a, uint64_t b) {
return (a > b) ? a : b;
}
inline str_t correct_data_size(str_t str, uint64_t new_size) {
if(str.data_size < new_size) {
str.data_size = (max(str.data_size, new_size) << 1);
str.begin = realloc(str.begin, str.data_size);
}
return str;
}
inline str_t concat(str_t dest, str_t src) {
uint64_t new_size = (dest.size + src.size - 1);
dest = correct_data_size(dest, new_size);
memcpy((dest.begin + dest.size - 1), src.begin, src.size);
dest.size = new_size;
return dest;
}
inline str_t create_str(char * str, uint64_t size) {
return (str_t){.begin = strcat(malloc(size), str), .size = size, .data_size = size};
}
inline void print_str_t(str_t str) {
fprintf(stderr, "str = %ssize = %lu, data_size = %lu\n", str.begin, str.size, str.data_size);
}
uint64_t test(uint64_t star_n, uint64_t n, str_t str, str_t * gstr) {
uint64_t end = (star_n + n);
do {
*gstr = concat(*gstr, str);
char * pos = gstr->begin;
while((pos = strstr(pos, "efgh")))
memcpy(pos,"____",4);
} while((++star_n) != end);
return star_n;
}
int main(void) {
char data[] = "abcdefghefghefgh";
str_t str = create_str(data, sizeof(data));
str_t gstr = create_str("", 1);
time_t starttime = time(NULL);
uint64_t block_c = 0;
while((block_c = test(block_c, ((256/16) * 1024), str, &gstr)) != (((256/16) * 1024) * 20))
printf("%ldsec\t\t%lukb\n",time(NULL)-starttime,gstr.size/1024);
}
Минимально оптимизированный вариант в царь-стиле теста из предыдущего ГК. Никто не увидел и начали на меня кукарекать. То ещё ГК, давайте объясняйте что здесь говно.
Follow us!
Он выдает у меня результаты процентов на 25 быстрее твоего, при этом вдвое короче. Хотя возможно он просто что-то не то делает, я не проверял.
Вывод теста superhackkiller1997:
Вывод вражеского теста:
Система: intel i3 M370, Win7.
gcc 4.5.2
Тестить под линуксом и под новым gcc лень.
Вывод вражеского теста:
Система: 3.8.6-gentoo #2 SMP PREEMPT Sun Apr 21 15:21:31 UTC 2013 x86_64 Intel(R) Core(TM)2 CPU 6320 @ 1.86GHz GenuineIntel GNU/Linux
gcc версия 4.9.0-pre9999 20130708 (experimental) commit fda9f85fe1d91f9b64ebf10816e3365aa01c5a74 (Gentoo 4.9.0_pre9999)
И чем дальше - тем больше он сливать будет, а так сливает он просто в хлам, но ты увидишь это лишь на тысячах секунд, ибо 99.93% делается тот вайл.
Берём, выкидываем реплейс и смотрим за сколько оно делает вставки:
Мой пацанский вариант:
Это говно:
Иное:
И да, это не оригинальный код - я этого кода даже не видел, оригинал в ГК ниже.
Далее, это не даст перфоманса, ибо strstr() так работает.
Разница уже в пределах погрешности - поэтому профита нет.
Покажи -S - я погляжу.
Выхлоп gcc:http://pastebin.com/LBcp9x7F
Их код: http://pastebin.com/Ki0Kc5y3
Выхлоп gcc: http://pastebin.com/CxKKrT0S
Значит это что-то у вас там нитого.
Да, согласен Но там есть и баг - этот алгоритм никогда не заменяет первые 4 символа строки. На этой задаче канает, на более общей - хуй. Если хочется сделать +4, то это надо делать после memcpy, а не в аргументе strstr's.
Мой:
Его:
Значит я в прошлый раз чего-то нитого намерил. Пропитушился.
Код superhackkiller1997, в котором uint64_t заменены на uint32_t:
3sec 256kb
10sec 512kb
22sec 768kb
39sec 1024kb
61sec 1280kb
88sec 1536kb
120sec 1792kb
Код с ideone:
2sec 256kb
10sec 512kb
26sec 768kb
50sec 1024kb
81sec 1280kb
116sec 1536kb
157sec 1792kb
И чем дальше - тем больше разница. По идее из-за realloc'а на каждую строку.
Тормазит тут strcat(), ибо стоит n в лучшем случае, n^3 в худшем. два strlen() + один мемкопи. У меня же только мемкопи, без стрлена. У меня конкатенация стоит O(1) в данном случае. В твоей портянке оно стоит в районе n.
Он медленнее моего кода по определению, даже если выпилить тот вайл, о котором я сказал выше - у меня идеальная реализация, а то говно.
Поэтому у тебя там что-то врёт.
Деаллокация для анскиллед питухов?
http://raid6.com.au/~onlyjob/posts/arena/
Задача звучит примерно так - до посинения приклеивать в конец строки "ghjk", а затем пробегая по всей строке(!) заменять "ghjk" на "____".
str.replace
Python 2.7.2 @ Core i7-860
Никого не запутал?
Ибо O(n) обозначает, что время выполнения равно C * n, где C та самая константа. В нашем случае - где-то O(e^n), что соответствует C1 * e ^ (C2 * n), и речь идет о C1
П.С. Ты не мяут с сырцов?
Получается, С2 будет гораздо важнее С1. Разница между n^x и n^(x/2) будет гораздо больше, чем между k*(n^x) и n^x.
Блядь они ебанаты, ну ясен хуй ява будет сливать, там нет никаких оптимизаций и будет O(n^2). Там совсем макаки сидят, которые про StringBuilder не слышали?
Кстати, а почему в яве нет оптимизаций? В цпитоне это давно оптимизировано, хотя лучше список / bytearray.
> а затем пробегая по всей строке(!)
А, так O(n^2) там запрограммировано.
Даже ущербная реализация ан сишке, которая O(n^3) - мои стрки стоят меньше, чем O(n) - во всех языках тоже. Реплейс в сишке сделан по-ущербснки - во всех других ЯП это реализованно лучше.
Но даже несмотря на тотальный слив по O() у сишки - она в хламину рвёт всё живое.
gstr=realloc(gstr,lngth+str_len); - стоит n, но тут не стоит.
strcat(gstr,str); - стоит n^2.
while(pos=strstr(pos,"efgh")) memcpy(pos,"____",4); - стоит в районе n, ералеьно чуть больше.
Не, strcat тупо O(n), где n суммарная длина строк. Тут же сначала пробегают по одной строке, замеряя ее длину, а потом пробегают по другой, копируя символы. O(n^2) было бы если бы там был бы двойной цикл.
Твой код в целом все-таки O(n^2).
Да, некоторые вариации strcat() работают почти за O(n). Но они по вашему не безопасны, ибо они могут залезть в память за концом вашей строки. Хотя почему могут - они залезают.
Безопасный strcat() стоит дорого.
А так да, ты даже в чём-то прав. И да, копирование стоит O(n*2), а не n.
O(n+m) если быть точным, где n и m длины исходных строк.
> Мой код O(n).
У тебя внешний цикл, растущий пропорционально n. И внутри него цикл поиска\замены, который тоже растет пропорционально n. Отсюда O(n^2). Если построишь график по числам, которые выводит код - должно получиться что-то типа параболы.
O(min(n, m)*2). Это понимают все, поэтому n*2.
Внешний цикл мы не учитываем - мы учитываем общую сложность конката и реплейса.
Так тут задача специально хитровыебанная, чтобы яву слить (и любой другой язык с иммутабельными строками)... Заметь как построены итерации - добавляем чуть-чуть хуйни, прогоняем реплейс по всей строке. В итоге на каждом шаге клеятся всего 2 строки, стрингбилдер здесь не поможет.
Вместо
pos=gstr;
сделал
pos=gstr+(i-1)*16;
а в тесте c++ сделал
end = (i-1)*16
И все вышло как я и полагал C:
0sec 256kb
1sec 512kb
2sec 768kb
4sec 1024kb
7sec 1280kb
12sec 1536kb
16sec 1792kb
21sec 2048kb
29sec 2304kb
39sec 2560kb
52sec 2816kb
68sec 3072kb
85sec 3328kb
105sec 3584kb
127sec 3840kb
150sec 4096kb
cpp:
0sec 256kb
0sec 512kb
0sec 768kb
1sec 1024kb
1sec 1280kb
1sec 1536kb
1sec 1792kb
1sec 2048kb
1sec 2304kb
1sec 2560kb
1sec 2816kb
1sec 3072kb
1sec 3328kb
1sec 3584kb
1sec 3840kb
1sec 4096kb
без потери качества обработки строки, лол
В том то и дело, что ничего не потерялось. Мой код просто не перебирает лишние мегабайты, чтобы заменить 12 байт.
>ты идиот
будь проще затупок
Ты упоролся? Животное. Ты вообще понимаешь, что такое бенчмарк? Животное, ты понимаешь, что такое реплейс, животное? Реплейс обязан пройти ВСЮ строку, животное.
http://pastebin.com/XxY3urQx - на тебе, питушок:
>будь проще затупок
Питушок должен знать своё место.
Вот дай ссылку на код, где он выводит полностью строки до и после изменения. Выведи мне хотя бы 4 строки так. М.б. если тупо скопировать из libc и сделать как инлайн, хотя не надо нихрена так делать, т.к. они нормально скомпонуются как функции, тогда может будет нормально работать.
В течении часа не дашь ссылку на адекватный вывод засчитываю слив.
Ты несёшь какую-то херню, животинушка. Ты уже тотально слился и можешь не кукарекать.
http://ideone.com/6YNxIo
Тем самым ты нарушил условие задачи, читер хренов. Прочти уже оригинальную статью, чтобы понять почему все пишут такую херню, вместо того чтобы 1 раз прогнать реплейс после всех конкатенаций.
P.S. У царя, кстати, память выделяется примерно как в с++. Не на каждую конкатенацию.
кому не лень - сличите указатели после каждого роста
Cause c++ superior in everything
]Делаю минеты
Что-то мне аж прям как-то не по себе... как-то очень по-читерски это :)
И код с сайта:
Компилировал с -O3 gcc 4.6.3 Линукс 64 бит.
Так действуют 99% питушков, пытаясь доказать, что мой код не работает.
Поэтому Си - это ЯП, а остальные ЯП - это говно. Исключения с вариациями - это плюсы и асм.
Да в сишной либе на строки вообще хуй положен ;) Строки с ноликом на конце, это, пожалуй, самый эпичный фейл. Набор функций в той же либц - коллекция разношерстного говна, часть из которого "забывает" приклеить тот самый нолик... Если не писать свои функции, и не использовать сторонние либы, работать со строками очень неудобно. С этим можно поспорить, но это факт.
С другой стороны - сишка и проектировалась как минималистичный язык, не навязывающий своих законов. И для тех мест, где сишка действительно нужна - от этого только профит.
Вот тот ответ, которого я ждал :)
А вот с точки зрения удобства нультерминейтед строки говно. Постоянная возня с ручным хранением длин, strlen'ом, дописыванием ноликов к strncpy и т.п.
Сейчас это не сильно актуально, но в некоторых случаях си-строки реально удобней.
Даже длинну строки мы знаем и т.п. strlen() не нужен, копирование не нужно - всё быстро, круто - в кеше.
Почти!
exec.tm.sec str.length
1 sec 256 kb
6 sec 512 kb
14 sec 768 kb
25 sec 1024 kb
40 sec 1280 kb
58 sec 1536 kb
80 sec 1792 kb
105 sec 2048 kb
133 sec 2304 kb
166 sec 2560 kb
201 sec 2816 kb
240 sec 3072 kb
282 sec 3328 kb
327 sec 3584 kb
376 sec 3840 kb
428 sec 4096 kb
На той же машине немодифицированный cpp_test.cpp выдал:
exec.tm.sec str.length
4sec 256kb
15sec 512kb
34sec 768kb
60sec 1024kb
95sec 1280kb
138sec 1536kb
^C
Царский код выдал:
3sec 256kb
11sec 512kb
25sec 768kb
44sec 1024kb
70sec 1280kb
101sec 1536kb
138sec 1792kb
^C
3.8.6-gentoo #2 SMP PREEMPT Sun Apr 21 15:21:31 UTC 2013 x86_64 Intel(R) Core(TM)2 CPU 6320 @ 1.86GHz GenuineIntel GNU/Linux
Твоё говно в 10раз медленнее, чем на моём коре2 за 500рублей. Меня твои говнобенчи не интересуют - вбрасывай и дальше, сравнивая на говноОСи, говно х86 и говноконпеляторе.
Цифры того, что показал борманд:
http://govnokod.ru/13408#comment187596
http://govnokod.ru/13408#comment187601
http://govnokod.ru/13408#comment187603
http://govnokod.ru/13408#comment187608
http://govnokod.ru/13408#comment187839
Я хочу уточнить, в каком состоянии сейчас код.
Этот код?
На моей маздайке и недопроцессоре:
exec.tm.sec str.length
3sec 256kb
12sec 512kb
29sec 768kb
Ещё раз для сравнения царский:
3sec 256kb
11sec 512kb
25sec 768kb
И ещё раз для сравнения Delphi с prefixed-length strings:
exec.tm.sec str.length
1 sec 256 kb
6 sec 512 kb
14 sec 768 kb
Это производительность памяти в районе второго пня. На чём ты собирал мой код, какая у тебя либц, где исходники strstr().
И да, менять 64битные инты на 32битные тебя не учили?
http://pastebin.com/XxY3urQx - собери это - это просто конкатенация без реплайса - выпили из своего кода реплейс, оставь просто добавление в конец строки.
0sec 256kb
0sec 512kb
0sec 768kb
0sec 1024kb
...
4sec 239616kb
...
После замены интов:
0sec 256kb
1sec 512kb
...
3sec 239616kb
...
Delphi без реплейса:
0 sec 256 kb
...
1 sec 239616 kb
...
2 sec 277248 kb
Итого: мне нужно оптимизировать поиск и замену.
Кстати, вариант с zero-ended strings + ReallocMem в Delphi тормозил страшно:
9 sec 256 kb
Короче, дальше можно не смотреть.
Вывод такой: строки с завершающим нулём не нужны, потому что конкатенация строк с префиксом длины работает быстрее.
http://pastebin.com/5N7XBD45 - вот тебе вариант на 64/32 битных интах в зависимости от типа х86.