Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Религиозные войны > C++ - производительность

Автор: archimed7592 25.1.2008, 19:40

Сишники, кто хочет бенчмарк?  Давайте поставим задачу и сравним реализации на С и С++ по скорости.

Автор: MAKCim 25.1.2008, 19:49

archimed7592,  давай в качестве компиляторов предлагаю G++ и GCC осталось только задачу придумать

Автор: JackYF 25.1.2008, 20:07

Цитата(MAKCim @  25.1.2008,  18:49 ) в качестве компиляторов предлагаю G++ и GCC полностью поддерживаю Цитата(MAKCim @  25.1.2008,  18:49 ) осталось только задачу придумать это самое сложное  проблема в том, что в С++-ом коде можно написать почти все те же конструкции, что и в С-шном. Тогда будет сравнение компиляторов

Автор: archimed7592 25.1.2008, 20:25

Цитата(MAKCim @  25.1.2008,  19:49 ) в качестве компиляторов предлагаю G++ и GCC Не думаю, что это критично. Давай проверим на разных компиляторах, заодно узнаем разницу между компиляторами . Цитата(MAKCim @  25.1.2008,  19:49 ) осталось только задачу придумать Можно взять http://forum.sources.ru/index.php?showtopic=181364. Добавлено через 2 минуты и 17 секунд Цитата(JackYF @  25.1.2008,  20:07 ) проблема в том, что в С++-ом коде можно написать почти все те же конструкции, что и в С-шном Обещаю не списывать . Добавлено через 2 минуты и 51 секунду

Автор: Void 25.1.2008, 21:47

Цитата(archimed7592 @  25.1.2008,  22:25 ) Можно взять эту. А чего не http://forum.sources.ru/index.php?showtopic=207483?  По поводу задачи с сортировкой по категориям: как будут версии на Си и C++, сравним с этим, у меня есть подозрение, что как минимум не сортирующий вариант будет не медленнее  Код #!/usr/bin/python from __future__ import with_statement import sys def main():     need_sort = len(sys.argv) > 3 and sys.argv[3] == 'sort'     tree = {}     with open(sys.argv[1]) as in_file:         for line in in_file.xreadlines():             cat, subcat, elem = line.rstrip().split(';')             tree.setdefault(cat, {}).setdefault(subcat, []).append(elem)     sort = lambda s: sorted(s) if need_sort else s     with open(sys.argv[2], "w") as out_file:         for cat, subcats in sort(tree.items()):             out_file.write('%s\n' % cat)             for subcat, elems in sort(subcats.items()):                 out_file.write('  %s\n' % subcat)                 for elem in sort(elems):                     out_file.write('    %s\n' % elem) if __name__ == '__main__':     main()

Автор: archimed7592 25.1.2008, 22:16

Цитата(Void @  25.1.2008,  21:47 ) А чего не эту? Это будет несправедливо по отношению к Сишникам, но я не против . Цитата(Void @  25.1.2008,  21:47 ) как будут версии на Си и C++ Дык возьми оттуда любую плюсовую версию и проверь .

Автор: Void 25.1.2008, 22:20

Цитата(archimed7592 @  26.1.2008,  00:16 ) Дык возьми оттуда любую плюсовую версию и проверь Мне лень регистрироваться на форуме только ради того, чтобы скачать пару аттачей (никогда, кстати, не понимал этой политики не показывать аттачи гостям). Я лучше подожду родных винградовских решений

Автор: MAKCim 25.1.2008, 22:38

Цитата(archimed7592 @  25.1.2008,  22:16 ) Это будет несправедливо по отношению к Сишникам, но я не против с чего это? настоящие сишники трудностей не боятся

Автор: archimed7592 26.1.2008, 10:20

Цитата(MAKCim @  25.1.2008,  22:38 ) с чего это? настоящие сишники трудностей не боятся  smile  А ты настоящий?

Автор: MAKCim 26.1.2008, 11:19

Цитата(archimed7592 @  26.1.2008,  10:20 ) А ты настоящий? настоящие недолюливают С++ так что я наполовину настоящий

Автор: archimed7592 26.1.2008, 11:33

Ну так чё? Fight? Или не fight? Т.к. тестировать собираемся скорость, лучше, на мой взгляд, первая задача... угу?  Добавлено через 21 секунду Или своё чё-нибудь предложишь?

Автор: Alexeis 26.1.2008, 12:16

Цитата(archimed7592 @  26.1.2008,  10:33 ) Или своё чё-нибудь предложишь?   Давайте возьмем текстовый текстовый файл на 1Мб и удалим из него все слова длинее длинее 6 символов.

Автор: chipset 26.1.2008, 12:21

Востребован в: - Настольных прилагах для широкого круга пользователей: важна скорость и отточеность, также поддержка старых ОС (95-98). - Серьёзных вычисляниях (кластеры солярис к примеру). - Кросс-платформенные прилаги (не надо гнать про Моно, пожалуйста). - Движках: БД, ОС, игры, всякого рода ЕРП (не прикладуха), итд.

Автор: archimed7592 26.1.2008, 12:26

Цитата(Alexeis @  26.1.2008,  12:16 ) Давайте возьмем текстовый текстовый файл на 1Мб и удалим из него все слова длинее длинее 6 символов. Не вижу изюминки, но, если возьмёшься чётко поставить задачу - можно. Цитата(chipset @  26.1.2008,  12:21 ) Движках Вот, с чем не поспоришь - с тем не поспоришь . Любой донет-ява-питон имеет RTL, написанную на С/C++ и, если бы не эта RTL, ни о какой скорости в этих языках не было бы речи. Цитата(chipset @  26.1.2008,  12:21 ) Серьёзных вычисляниях Ты как считаешь, в Google достаточно серьёзные вычисления бегают?  Там про С++ не слышали... Ну, точнее, слышали, но для обработки своих задач его не используют.

Автор: JackYF 26.1.2008, 13:19

Цитата(archimed7592 @  26.1.2008,  11:26 ) Там про С++ не слышали...  *поперхнулся* ... это вообще как? кто сказал?

Автор: archimed7592 26.1.2008, 13:31

Цитата(JackYF @  26.1.2008,  13:19 ) *поперхнулся* ... это вообще как? Очень просто . Они очень амбициозны: на рынке нет устраивающего их ЯП - создадим свой! Аналогично у них своя ФС, своя СУБД(не реляционная, к слову ). Цитата(JackYF @  26.1.2008,  13:19 ) кто сказал?  Сами ходят по ВУЗам и рассказывают . На YouTube можно посмотреть записи их лекций... Искать по кл. словам "Google tech talks".

Автор: Alexeis 26.1.2008, 13:43

Цитата(archimed7592 @  26.1.2008,  11:26 ) Не вижу изюминки, но, если возьмёшься чётко поставить задачу - можно.   Ну хорошо, можно тогда еще добавить дублирование слов. Не хочеться особо сложной задачи, чтобы не лень было реализовывать  . Значит формулировка такая. --------------------------------------------------------------------------------------------- Из предложенного текста удалить все слова длинее 6 символов (только слова пробелы не трогать), все слова длиной в 3 символа продублировать 7 раз.  --------------------------------------------------------------------------------------------- пример : "Гостиная Анны Павловны  начала  понемногу  наполняться." -> " Анны   начала    "  "война и мир" -> "война и мирмирмирмирмирмирмир" --------------------------------------------------------------------------------------------- текстовый файлик http://alexei-s1.narod.ru/books/tolstoi_l_n__voina_i_mir2.7z

Автор: archimed7592 26.1.2008, 13:47

Добавлю к этому, что нужно считывать не из файла, а из потока стандартного ввода, а результат выводить в поток стандартного вывода, причём без каких-либо приблуд(помимо результата).

Автор: JackYF 26.1.2008, 13:54

Цитата(archimed7592 @  26.1.2008,  12:31 ) Они очень амбициозны: на рынке нет устраивающего их ЯП - создадим свой! и что у них вместо С/С++? Python не катит.

Автор: archimed7592 26.1.2008, 14:04

Цитата(JackYF @  26.1.2008,  13:54 ) и что у них вместо С/С++? Если я поднатужусь и вспомню название, боюсь, что тебе оно ни о чём не скажет, ибо это их внутрений язык. Лучше потрать полчаса на то чтобы скачать лекции и ещё немного, чтобы прослушать их - много интересного узнаешь ;). Начни отсюда: http://youtube.com/watch?v=uwa7tRAUlPQ

Автор: Alexeis 26.1.2008, 14:11

Цитата(archimed7592 @  26.1.2008,  12:47 ) Добавлю к этому, что нужно считывать не из файла, а из потока стандартного ввода, а результат выводить в поток стандартного вывода, причём без каких-либо приблуд(помимо результата).   А я и не говорил, что читать нужно из файла, не важно каков первоначальный источник, хоть ресурс, хоть сегмент данных. Время засекаем после того как получили готовый буфер в ОЗУ.

Автор: MAKCim 26.1.2008, 15:44

archimed7592,  давай лучше задачу про категории

Автор: archimed7592 26.1.2008, 15:51

Цитата(Alexeis @  26.1.2008,  14:11 )  А я и не говорил, что читать нужно из файла, не важно каков первоначальный источник, хоть ресурс, хоть сегмент данных. Вот не надо этих "хоть" . Я чётко определил откуда будет читаться, куда будет писаться. Ты можешь быть против стандартных потоков и сказать "хочу чтобы читалось из test.in, писалось в test.out" - ок, без проблем, но должна быть определённость без "хоть" ;). Т.о. можно будет написать тестер, который будет на автомате прогонять тысячу тестов для 3-5 решений. Цитата(Alexeis @  26.1.2008,  14:11 ) Время засекаем после того как получили готовый буфер в ОЗУ.   Нет, время засекается с момента старта приложения и до момента его завершения. Для того чтобы исключить разные издержки тест прогоняется 101 раз и берётся среднее от последних 100 запусков, причём делается это всё внешней утилитой. Цитата(MAKCim @  26.1.2008,  15:44 ) archimed7592,  давай лучше задачу про категории  Ну давай . Могу я поинтересоваться, чем тебя эта задача смутила?

Автор: Alexeis 26.1.2008, 16:01

Цитата(archimed7592 @  26.1.2008,  14:51 ) Нет, время засекается с момента старта приложения и до момента его завершения.   Давайте еще время отсчитывать от старта операционки   . Просто гениально! А ничего, что запуск программы зависит от ее размера и количества подгруженных модулей, времени инициализации программы и т.д.? Это что тоже определяет скорость работы алгоритма?

Автор: MAKCim 26.1.2008, 16:31

Цитата(archimed7592 @  26.1.2008,  15:51 ) Могу я поинтересоваться, чем тебя эта задача смутила? лень слишком много работы со строками

Автор: archimed7592 26.1.2008, 16:34

Хорошо, наполовину настоящий Сишник, давай. Задача там вроде чётко поставлена .

Автор: JackYF 26.1.2008, 16:51

Цитата(Alexeis @  26.1.2008,  15:01 ) Это что тоже определяет скорость работы алгоритма? а мы сравниваем программы, а не алгоритмы, не так ли?

Автор: Alexeis 26.1.2008, 17:03

Цитата(JackYF @  26.1.2008,  15:51 ) а мы сравниваем программы, а не алгоритмы, не так ли?    Ну это уж кто как хочет. Меня интересует в как быстро сработает алгоритм и вернет, результат, а не как быстро загрузиться и проинициализируется программа, перед выполнением нужных мне действий.   Хотя в задаче про строки время работы алгоритма будет исчисляется десятками секунд, потому погрешность будет невелика. Но вот если разница будет 2-5%, то достоверность таких опытов будет нулевая.

Автор: MAKCim 26.1.2008, 18:43

Код #include <stdlib.h> #include <stdio.h> static char buffer[4096]; static char * ptr = buffer; static void * (*search)(const void*, const void*, size_t,          size_t, int (*)(const void*, const void*)) = &bsearch; static int compare(const void * a, const void * b) {     const int * first = a;     const int * second = b;     if (first[2] < second[2])         return -1;     else if (first[2] > second[2])         return 1;     else if (first[1] < second[1])         return -1;     else if (first[1] > second[1])         return 1;     else if (first[0] < second[0])         return -1;     else if (first[0] > second[0])         return 1;     return 0; } static void * find(const void * key, const void * base, size_t nmemb,         size_t size, int (*compar)(const void*, const void*)) {     const int * element = base;     for (; nmemb--; ++element) {         if (!compare(key, element))             return (void*)1;     }     return NULL; } static void print(int level, int * numbers, FILE * fs) {     static char array[sizeof(int) * 2];     if (level == -1)         return;     unsigned int * ptr = (unsigned int*)array;     ptr[0] = ptr[1] = 0x20202020; #define HIGH    "high" #define MIDDLE    "middle" #define LOW    "low"     switch (level) {         case 0:             array[0] = '\0';             fprintf(fs, "%s%s%d\n", array, HIGH, numbers[2]);             array[0] = ' ';         case 1:             array[2] = '\0';             fprintf(fs, "%s%s%d\n", array, MIDDLE, numbers[1]);             array[2] = ' ';         case 2:             array[4] = '\0';             fprintf(fs, "%s%s%d\n", array, LOW, numbers[0]);     } } int main(int argc, char * argv[]) {     FILE * fs = fopen(argv[1], "r");     if (fs == NULL)         return 1;     if (fseek(fs, 0, SEEK_END) != 0)         return 2;     long position = ftell(fs) + 1;     if (position == 0)         return 3;     rewind(fs);     size_t elements;     size_t number;     size_t multiply;     size_t count = 0;     int * current = (int*)malloc(position), *start = current;     if (current == NULL)         return 4;     char symbol;     while (fgets(ptr, 4096, fs) != NULL) {         elements = 3;         for (; *ptr++;);         ptr -= 3;         do {             for (; *ptr < 0x30 || *ptr > 0x39; --ptr);             number = 0;             multiply = 1;             do {                 number += (*ptr - 0x30) * multiply;                 multiply *= 10;             } while (*--ptr > 0x2F && *ptr < 0x3A);             *current++ = number;         } while (--elements);         ++count;     }     if (argc == 4 && !strcmp(argv[3], "sort"))         qsort(start, count, 3 * sizeof(int), &compare);     else search = &find;     FILE * writer = fopen(argv[2], "w");     if (writer == NULL)         return 5;     int level;     void * base = start;     print(0, start, writer);     elements = count;     while (--count) {         current = start;         start += 3;         print(start[2] == current[2] ? (start[1] == current[1] ? (                 search(start, base, elements - count, 3 * sizeof(int), &compare) == NULL ? 2: -1): 1) : 0, start, writer);     }     return 0; } названия категорий high, middle и low хотя это только на вывод влияет

Автор: Void 26.1.2008, 18:55

MAKCim, погоди, кто сказал, что имена категорий фиксированы? Из Цитата Animals;Mammals;Cat Мы должны получить Цитата Animals   Mammals     Cat , но никак не Цитата high9   middle0     low0 Боюсь, низачот

Автор: MAKCim 26.1.2008, 19:00

Цитата(Void @  26.1.2008,  18:55 ) погоди, кто сказал, что имена категорий фиксированы? Из где написано обратное?    цифры тоже могут отсутствовать?  если надо, могу исправить

Автор: Void 26.1.2008, 19:11

Цитата(MAKCim @  26.1.2008,  21:00 ) где написано?  ТЗ чертовски неформальное. Теперь понял логику, но, признаться, мне бы в жизни не пришло в голову так его интерпретировать  Потому что задачка из более менее осмысленной превращается в весьма искусственную.

Автор: MAKCim 26.1.2008, 19:12

Цитата(Void @  26.1.2008,  19:11 ) Теперь понял логику, но, признаться, мне бы в жизни не пришло в голову так его интерпретировать а что, я как-то по-особенному проитерпретировал?

Автор: Void 26.1.2008, 19:21

Цитата(MAKCim @  26.1.2008,  21:12 ) а что, я как-то по-особенному проитерпретировал?  Ты принял, что названия категорий, подкатегорий и имена элементов — не произвольные строки, а имеют вид "%s%d", где первая часть фиксирована для всех элементов. Я лично для себя сразу решил, что названия вида «Категория1;Подкатегория1;Элемент1» использовались только как пример, чтобы не утруждать себя придумыванием разнообразных строк.

Автор: MAKCim 26.1.2008, 19:45

Void,  вообщем надо уточнить, что имелось в виду сейчас у меня программа работает очень быстро http://falaleev.at.tut.by/data.rar тестовый пример Код # time ./main in out sort real    0m0.005s user    0m0.004s sys     0m0.000s C2D, 1.86Ghz, Linux (2.6.18, x86-64)

Автор: archimed7592 26.1.2008, 19:50

MAKCim, естественно, что все строки во входе произвольные .

Автор: Void 26.1.2008, 19:54

Пусть archimed7592 прояснит ситуацию, он засветился в оригинальном топике  С произвольными строками по любому интереснее.

Автор: MAKCim 26.1.2008, 19:55

Цитата(archimed7592 @  26.1.2008,  19:50 ) MAKCim, естественно, что все строки во входе произвольные сгенерируй правильный входной файл и выходной так будет проще писАть

Автор: chipset 26.1.2008, 21:10

Цитата(archimed7592 @  26.1.2008,  02:26 ) Ты как считаешь, в Google достаточно серьёзные вычисления бегают? smile Там про С++ не слышали... Ну, точнее, слышали, но для обработки своих задач его не используют.  Ты неправ. Гугл ето ВСЕ С++. Кроме ГУИ.

Автор: archimed7592 26.1.2008, 21:13

Цитата(chipset @  26.1.2008,  21:10 ) Гугл ето ВСЕ С++. Чипс, откуда дровишки?

Автор: archimed7592 26.1.2008, 21:34

Цитата(MAKCim @  26.1.2008,  19:55 ) сгенерируй правильный входной файл и выходной Ишь ты хитрый какой . Я могу сгенерировать, но сойдёт и тот, что в условии, ибо всё равно тестировать будем на другом файле . Точнее говоря, никаких предположений о формате строк делать нельзя. Это просто произвольные строки. Нужно разбить на категории, на подкатегории и вывести результат .

Автор: MAKCim 26.1.2008, 22:23

блин, за...лся писать    вот Код #include <stdlib.h> #include <stdio.h> #include <stddef.h> #define AREA_SIZE    (4096 << 3) static char area[AREA_SIZE]; static char buffer[4096]; static char * pointer = buffer; struct list_head {     struct list_head * prev;     struct list_head * next; }; struct element {     char * string;     int offsets;     struct list_head list; }; struct list_head elements = {     &elements, &elements }; static int compare(struct element * a, struct element * b) {     int result = strcmp(a -> string, b -> string);     if (result > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + (a -> offsets & 0xFFFF), b -> string + (b -> offsets & 0xFFFF))) > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + ((a -> offsets) >> 16), b -> string + ((b -> offsets) >> 16))) > 0)         return 1;     else if (result < 0)         return -1;     return 0; } static void sort(void) {     struct list_head * entrya;     struct list_head * entryb;     struct element * elementa;     struct element * elementb;     char * sw_string;     int sw_offsets;     for (entrya = elements.next; entrya != &elements; entrya = entrya -> next) {         for (entryb = entrya -> next; entryb != &elements; entryb = entryb -> next) {             elementa = (struct element*)((char*)entrya - offsetof(struct element, list));             elementb = (struct element*)((char*)entryb - offsetof(struct element, list));             if (compare(elementa, elementb) <= 0)                 continue;             sw_string = elementa -> string;             elementa -> string = elementb -> string;             elementb -> string = sw_string;             sw_offsets = elementa -> offsets;             elementa -> offsets = elementb -> offsets;             elementb -> offsets = sw_offsets;         }     } } static int find(struct element * elem) {     struct list_head * entry = elem -> list.prev;     struct element * a;     for (; entry != &elements; entry = entry -> prev) {         a = (struct element*)((char*)entry - offsetof(struct element, list));         if (!compare(elem, a))             return 0;     } } static void print(int level, struct element * elem, FILE * fs) {     static char array[sizeof(int) * 2];     unsigned int * ptr = (unsigned int*)array;     ptr[0] = ptr[1] = 0x20202020;     switch (level) {         case 0:             array[0] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string);             array[0] = ' ';         case 1:             array[2] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) & 0xFFFF));             array[2] = ' ';         case 2:             array[4] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) >> 16));     } } #define DELIMITER    ':' int main(int argc, char * argv[]) {     FILE * fs = fopen(argv[1], "r");     fseek(fs, 0, SEEK_END);     long position = ftell(fs) + 1;     rewind(fs);     long start = 0, end;     unsigned long last = AREA_SIZE;     char * current = area;     struct element * element;     while (fgets(pointer, 4096, fs) != NULL) {         if ((end = ftell(fs)) - start > last) {             current = malloc(AREA_SIZE);             last = AREA_SIZE;         }         start = end;         element = (struct element*)current;         current = (char*)(element + 1);         element -> string = current;         element -> offsets = 0;         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= (current - element -> string);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= ((int)(current - element -> string) << 16);         for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);         *current++ = '\0';         last -= current - element -> string + 1;         elements.next -> prev = &element -> list;         element -> list.next = elements.next;         element -> list.prev = &elements;         elements.next = &element -> list;         pointer = buffer;     }     if (argc == 4 && !strcmp(argv[3], "sort"))         sort();     FILE * w = fopen(argv[2], "w");     struct list_head * entry = elements.next;     struct list_head * previos;     struct element * entrye;     struct element * previose;     print(0, (struct element*)((char*)entry - offsetof(struct element, list)), w);     for (previos = entry, entry = entry -> next; entry != &elements; previos = entry, entry = entry -> next) {             entrye = (struct element*)((char*)entry - offsetof(struct element, list));         previose = (struct element*)((char*)previos - offsetof(struct element, list));         if (!find(entrye))             continue;         if (!strcmp(entrye -> string, previose -> string)) {             if (!strcmp(entrye -> string + ((entrye -> offsets) & 0xFFFF),                          previose -> string + ((previose -> offsets) & 0xFFFF))) {                 print(2, entrye, w);             } else print(1, entrye, w);         } else print(0, entrye, w);     }     return 0; } разделитель определен через #define как DELIMITER Добавлено @ 22:28 archimed7592,  тест давай   Добавлено @ 22:32 сортировка пузырьковая было влом QuickSort писать, а стандартный qsort() со списками не работает

Автор: chipset 26.1.2008, 22:42

Цитата(archimed7592 @  26.1.2008,  11:13 ) Чипс, откуда дровишки? smile  Ну а что там по твоему? Си шарп? ЫЫЫ, может Java? ))))

Автор: MAKCim 26.1.2008, 23:10

блин, пока вас дождешься вот генератор Код #!/usr/bin/python from random import randint def get():     return "".join([chr(randint(ord("a"), ord("z"))) for i in xrange(0, 3)]) fs = open("data", "w") for i in xrange(0, 100000):     fs.write("%s %s %s\n" % (get(), get(), get())) fs.close() http://falaleev.at.tut.by/data.rar тестовый пример вот результаты на моей системе Цитата # time ./main data out sort real    0m0.012s user    0m0.008s sys     0m0.004s

Автор: archimed7592 26.1.2008, 23:11

Чипс, мой тебе совет: прослушай ту лекцию, на которую я давал ссылку, чтобы беседа получалась хоть немного конструктивной... Угу? Они используют некоторый ф-циональный язык, который они написали сами.

Автор: MAKCim 26.1.2008, 23:29

archimed7592,  где вариант на С++?

Автор: archimed7592 26.1.2008, 23:38

chipset, вот, можешь почитать Алёнкин конспект: http://alenacpp.blogspot.com/2007/02/blog-post_20.html . Макс, ой, не сегодня... Не до этого, к сожалению. Может быть завтра руки дойдут.

Автор: maxim1000 27.1.2008, 01:14

вот небольшой набросок со стороны С++: Код #include <fstream> #include <map> #include <vector> #include <string> #include <algorithm> typedef std::vector<std::string> TThirdCategories; typedef std::map<std::string,TThirdCategories> TSecondCategories; typedef std::map<std::string,TSecondCategories> TFirstCategories; int main(int argc,char *argv[]) {     const std::string delimiters=" ";     const std::string indent="  ";     TFirstCategories container;     {//read         std::ifstream file(argv[1]);         while(true)         {             std::string line;             std::getline(file,line);             if(file.eof())                 break;             const std::string::size_type firstDelimiter=line.find_first_of(delimiters);             const std::string::size_type secondDelimiter=line.find_first_of(delimiters,firstDelimiter+1);             const std::string firstCategory=line.substr(0,firstDelimiter);             const std::string secondCategory=line.substr(firstDelimiter+1,secondDelimiter-firstDelimiter-1);             const std::string thirdCategory=line.substr(secondDelimiter+1);             container[firstCategory][secondCategory].push_back(thirdCategory);         }     }     {//write         std::ofstream file(argv[2]);         for(TFirstCategories::iterator i1=container.begin();i1!=container.end();++i1)         {             file<<i1->first<<std::endl;             for(TSecondCategories::iterator i2=i1->second.begin();i2!=i1->second.end();++i2)             {                 file<<indent<<i2->first<<std::endl;                 {//output sorted vector                     TThirdCategories v=i2->second;                     std::sort(v.begin(),v.end());                     for(TThirdCategories::iterator i3=v.begin();i3!=v.end();++i3)                         file<<indent<<indent<<*i3<<std::endl;                 }             }         }     }     return 0; } с сортировкой некрасиво получилось (копирование вектора), но на скорую руку, наверное, и так пойдёт да и расширяемость не очень будет, если количество категорий будет другое или переменное сравнивать, наверное, лучше на той же машине и системе, что и представленный C-шный вариант

Автор: Любитель 27.1.2008, 01:53

Цитата(MAKCim @  25.1.2008,  19:22 ) если не использовать "фичи" С++, разница небольшая Цитата(archimed7592 @  25.1.2008,  19:23 ) В какую сторону разница?  Цитата(MAKCim @  25.1.2008,  19:29 ) С <= C++ по скорости (в смысле С-программы более быстры) это мое имхо тестов не видел Цитата(archimed7592 @  25.1.2008,  19:40 ) Сишники, кто хочет бенчмарк? Чего-то я в итоге не понял - вы решили тестить реализацию на си и реализацию на C++ "без использования фич C++"   В чём тогда мораль? Добавлено через 5 минут и 32 секунды Цитата(maxim1000 @  27.1.2008,  01:14 ) с сортировкой некрасиво получилось (копирование вектора) Банально - сет или мультисет (в зависимости от условий задачи - лень особо читать :/ ) вместо вектора.

Автор: maxim1000 27.1.2008, 10:42

Цитата(Любитель @  27.1.2008,  01:53 ) Банально - сет или мультисет (в зависимости от условий задачи - лень особо читать :/ ) вместо вектора. про set думал, но не хотелось объединять одинаковые значения в вот про multiset как-то не подумал... исправленный вариант: Код #include <fstream> #include <map> #include <set> #include <string> #include <algorithm> typedef std::multiset<std::string> TThirdCategories; typedef std::map<std::string,TThirdCategories> TSecondCategories; typedef std::map<std::string,TSecondCategories> TFirstCategories; int main(int argc,char *argv[]) {     const std::string delimiters=" ";     const std::string indent="  ";     TFirstCategories container;     {//read         std::ifstream file(argv[1]);         while(true)         {             std::string line;             std::getline(file,line);             if(file.eof())                 break;             const std::string::size_type firstDelimiter=line.find_first_of(delimiters);             const std::string::size_type secondDelimiter=line.find_first_of(delimiters,firstDelimiter+1);             const std::string firstCategory=line.substr(0,firstDelimiter);             const std::string secondCategory=line.substr(firstDelimiter+1,secondDelimiter-firstDelimiter-1);             const std::string thirdCategory=line.substr(secondDelimiter+1);             container[firstCategory][secondCategory].insert(thirdCategory);         }     }     {//write         std::ofstream file(argv[2]);         for(TFirstCategories::iterator i1=container.begin();i1!=container.end();++i1)         {             file<<i1->first<<std::endl;             for(TSecondCategories::iterator i2=i1->second.begin();i2!=i1->second.end();++i2)             {                 file<<indent<<i2->first<<std::endl;                 for(TThirdCategories::iterator i3=i2->second.begin();i3!=i2->second.end();++i3)                     file<<indent<<indent<<*i3<<std::endl;             }         }     }     return 0; }

Автор: Void 27.1.2008, 11:44

MAKCim, быть может я чего-то не понимаю, но твоя программа ТЗ не соответствует. Даю на вход: Цитата aaa:bbb:ccc aaa:bbb:ddd bbb:ccc:ddd aaa:ccc:eee Получаю на выходе: Цитата aaa   ccc     eee bbb   ccc     ddd aaa   bbb     ddd Во-первых, категории надо объединять, во-вторых, кто зохавал четвёртый элемент? Кроме того, если DELIMITER заменить на точку с запятой и соответственно изменить приведённые строки, то получится другой результат, но опять неправильный. Вот альтернативный скрипт генерации исходных данных, с немного более реальными характеристиками: Код #!/usr/bin/python import random def rand_string(minlen, maxlen):     length = random.randint(minlen, maxlen)     return ''.join(chr(random.randint(ord('a'), ord('z'))) for i in xrange(length)) categories = [rand_string(3, 12) for i in xrange(100)] subcategories = [rand_string(3, 12) for i in xrange(1000)] out = open('data', 'w') for i in xrange(100000):     cat = random.choice(categories)     subcat = random.choice(subcategories)     out.write('%s;%s;%s\n' % (cat, subcat, rand_string(3, 12))) out.close()

Автор: MAKCim 27.1.2008, 11:44

господа либо баг у меня, либо в libc -> fgets() вот часть кода рушится с SIGSEGV на 927 итерации факт в том, что на этой итерации fgets() не возвращает NULL (якобы строка прочитана) но при работе с pointer идет SIGSEGV я исхожу из того, что fgets() должна записать в выходной буфер в конце \n и \0 (во всяком случае так в мане написано) что не так? вполне возможно, что не прав я, но не пойму где Код while (fgets(pointer, 4096, fs) != NULL) {         if ((end = ftell(fs)) - start > last) {             current = malloc(AREA_SIZE);             last = AREA_SIZE;         }         start = end;         element = (struct element*)current;         current = (char*)(element + 1);         element -> string = current;         element -> offsets = 0;         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= (current - element -> string);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= ((int)(current - element -> string) << 16);         for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);          *current++ = '\0';         last -= current - element -> string + 1;         elements.next -> prev = &element -> list;         element -> list.next = elements.next;         element -> list.prev = &elements;         elements.next = &element -> list;         pointer = buffer;     } Добавлено через 4 минуты и 55 секунд Цитата(Void @  27.1.2008,  11:44 ) быть может я чего-то не понимаю, но твоя программа ТЗ не соответствует. еще раз исходник скомпилируй Цитата(Void @  27.1.2008,  11:44 ) Кроме того, если DELIMITER заменить на точку с запятой и соответственно изменить приведённые строки, то получится другой результат, но опять неправильный. измени DELIMITER в исходном коде Добавлено через 8 минут и 8 секунд Void,  у меня на выходе Цитата aaa   bbb     ccc     ddd   ccc     eee bbb   ccc     ddd

Автор: Void 27.1.2008, 11:58

Цитата(MAKCim @  27.1.2008,  13:44 ) еще раз исходник скомпилируй   Теперь и того хуже. Как-то очень неустойчиво оно у тебя работает. Цитата rooslan@home:~$ gcc -O2 makcim.c -o makcim rooslan@home:~$ cat test.txt aaa:bbb:ccc aaa:bbb:ddd bbb:ccc:ddd aaa:ccc:eee rooslan@home:~$ grep DELIMITER makcim.c #define DELIMITER    ':'         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current); rooslan@home:~$ ./makcim test.txt out.txt && cat out.txt aaa   ccc     eee Цитата(MAKCim @  27.1.2008,  13:44 ) измени DELIMITER в исходном коде Я это и делал.

Автор: MAKCim 27.1.2008, 12:34

Void,  вот код Код #include <stdlib.h> #include <stdio.h> #include <stddef.h> #include <string.h> #define AREA_SIZE    (4096 << 3) static char area[AREA_SIZE]; static char buffer[4096]; static char * pointer = buffer; struct list_head {     struct list_head * prev;     struct list_head * next; }; struct element {     char * string;     int offsets;     struct list_head list; }; struct list_head elements = {     &elements, &elements }; static int compare(struct element * a, struct element * b) {     int result = strcmp(a -> string, b -> string);     if (result > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + (a -> offsets & 0xFFFF), b -> string + (b -> offsets & 0xFFFF))) > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + ((a -> offsets) >> 16), b -> string + ((b -> offsets) >> 16))) > 0)         return 1;     else if (result < 0)         return -1;     return 0; } static void sort(void) {     struct list_head * entrya;     struct list_head * entryb;     struct element * elementa;     struct element * elementb;     char * sw_string;     int sw_offsets;     for (entrya = elements.next; entrya != &elements; entrya = entrya -> next) {         for (entryb = entrya -> next; entryb != &elements; entryb = entryb -> next) {             elementa = (struct element*)((char*)entrya - offsetof(struct element, list));             elementb = (struct element*)((char*)entryb - offsetof(struct element, list));             if (compare(elementa, elementb) <= 0)                 continue;             sw_string = elementa -> string;             elementa -> string = elementb -> string;             elementb -> string = sw_string;             sw_offsets = elementa -> offsets;             elementa -> offsets = elementb -> offsets;             elementb -> offsets = sw_offsets;         }     } } static int find(struct element * elem) {     struct list_head * entry = elem -> list.prev;     struct element * a;     for (; entry != &elements; entry = entry -> prev) {         a = (struct element*)((char*)entry - offsetof(struct element, list));         if (!compare(elem, a))             return 0;     } } static void print(int level, struct element * elem, FILE * fs) {     static char array[sizeof(int) * 2];     unsigned int * ptr = (unsigned int*)array;     ptr[0] = ptr[1] = 0x20202020;     switch (level) {         case 0:             array[0] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string);             array[0] = ' ';         case 1:             array[2] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) & 0xFFFF));             array[2] = ' ';         case 2:             array[4] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) >> 16));     } } #define DELIMITER    ';' int main(int argc, char * argv[]) {     FILE * fs = fopen(argv[1], "r");     fseek(fs, 0, SEEK_END);     long position = ftell(fs);     rewind(fs);     long start = 0, end;     unsigned long last = AREA_SIZE;     char * current = area;     struct element * element;     unsigned long count = 0;     while (fgets(pointer, 4096, fs) != NULL) {         if ((end = ftell(fs)) - start > last) {             current = malloc(AREA_SIZE);             last = AREA_SIZE;         }         start = end;         element = (struct element*)current;         current = (char*)(element + 1);         element -> string = current;         element -> offsets = 0;         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= (current - element -> string);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= ((int)(current - element -> string) << 16);         for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);         *current++ = '\0';         last -= current - element -> string;         elements.next -> prev = &element -> list;         element -> list.next = elements.next;         element -> list.prev = &elements;         elements.next = &element -> list;         pointer = buffer;     }     if (argc == 4 && !strcmp(argv[3], "sort"))         sort();     FILE * w = fopen(argv[2], "w");     struct list_head * entry = elements.next;     struct list_head * previos;     struct element * entrye;     struct element * previose;     print(0, (struct element*)((char*)entry - offsetof(struct element, list)), w);     for (previos = entry, entry = entry -> next; entry != &elements; previos = entry, entry = entry -> next) {             entrye = (struct element*)((char*)entry - offsetof(struct element, list));         previose = (struct element*)((char*)previos - offsetof(struct element, list));         if (!find(entrye))             continue;         if (!strcmp(entrye -> string, previose -> string)) {             if (!strcmp(entrye -> string + ((entrye -> offsets) & 0xFFFF),                          previose -> string + ((previose -> offsets) & 0xFFFF))) {                 print(2, entrye, w);             } else print(1, entrye, w);         } else print(0, entrye, w);     }     return 0; } на твой пример он выводит правильные результаты

Автор: Void 27.1.2008, 12:43

MAKCim, всё, понял. Проблема в gcc. С -O2 у меня результат неверный, с -O0 всё нормально. Цитата rooslan@home:~$ gcc -v Используются внутренние спецификации. Целевая архитектура: i486-linux-gnu Параметры конфигурации: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --enable-checking=release i486-linux-gnu Модель многопотоковости: posix gcc версия 4.1.2 (Ubuntu 4.1.2-0ubuntu4) Мда.

Автор: MAKCim 27.1.2008, 12:51

Цитата(Void @  27.1.2008,  12:43 ) Проблема в gcc. С -O2 у меня результат неверный, с -O0 всё нормально. O_O что за х....

Автор: archimed7592 27.1.2008, 14:28

Цитата(maxim1000 @  27.1.2008,  10:42 ) про set думал, но не хотелось объединять одинаковые значения Оу, ребят, можете считать, что тройка cat;subcat;entry уникальна и, если она встречается дважды(или большее кол-во раз), то выводить её нужно единожды.

Автор: maxim1000 27.1.2008, 22:36

Цитата(archimed7592 @  27.1.2008,  14:28 ) Оу, ребят, можете считать, что тройка cat;subcat;entry уникальна и, если она встречается дважды(или большее кол-во раз), то выводить её нужно единожды. ну тогда так  Код #include <fstream> #include <map> #include <set> #include <string> #include <algorithm> typedef std::set<std::string> TThirdCategories; typedef std::map<std::string,TThirdCategories> TSecondCategories; typedef std::map<std::string,TSecondCategories> TFirstCategories; int main(int argc,char *argv[]) {     const std::string delimiters=" ";     const std::string indent="  ";     TFirstCategories container;     {//read         std::ifstream file(argv[1]);         while(true)         {             std::string line;             std::getline(file,line);             if(file.eof())                 break;             const std::string::size_type firstDelimiter=line.find_first_of(delimiters);             const std::string::size_type secondDelimiter=line.find_first_of(delimiters,firstDelimiter+1);             const std::string firstCategory=line.substr(0,firstDelimiter);             const std::string secondCategory=line.substr(firstDelimiter+1,secondDelimiter-firstDelimiter-1);             const std::string thirdCategory=line.substr(secondDelimiter+1);             container[firstCategory][secondCategory].insert(thirdCategory);         }     }     {//write         std::ofstream file(argv[2]);         for(TFirstCategories::iterator i1=container.begin();i1!=container.end();++i1)         {             file<<i1->first<<std::endl;             for(TSecondCategories::iterator i2=i1->second.begin();i2!=i1->second.end();++i2)             {                 file<<indent<<i2->first<<std::endl;                 for(TThirdCategories::iterator i3=i2->second.begin();i3!=i2->second.end();++i3)                     file<<indent<<indent<<*i3<<std::endl;             }         }     }     return 0; }

Автор: mr.DUDA 29.1.2008, 10:42

Эммм.. а когда будут результаты бенчмарков ?

Автор: archimed7592 4.2.2008, 00:01

maxim1000, в таком случае у тебя сортировка при любом раскладе отрабатывает... Т.е. в тестах без сортировки твой вариант теоретически "сольёт"... Цитата(mr.DUDA @  29.1.2008,  10:42 ) Эммм.. а когда будут результаты бенчмарков ?  smile  Когда появится время, чтобы затестить решения(ещё бы найти время, чтобы своё решение навоять)...

Автор: maxim1000 4.2.2008, 11:26

Цитата(archimed7592 @  4.2.2008,  00:01 ) maxim1000, в таком случае у тебя сортировка при любом раскладе отрабатывает... Т.е. в тестах без сортировки твой вариант теоретически "сольёт"... про какую сортировку речь? если я не ошибаюсь, сортировка нужна на всех этапах для быстрого поиска - ведь перед добавлением очередного элемента на любой уровень нужно найти его, если он вдруг уже есть

Автор: MAKCim 4.2.2008, 14:17

archimed7592,  Цитата(archimed7592 @  4.2.2008,  00:01 ) Когда появится время, чтобы затестить решения(ещё бы найти время, чтобы своё решение навоять)... ты это затеял так что уж изволь

Автор: archimed7592 5.2.2008, 01:42

Цитата(MAKCim @  26.1.2008,  22:23 ) {     FILE * fs = fopen(argv[1], "r");     fseek(fs, 0, SEEK_END);     long position = ftell(fs) + 1; Эмм, Макс, это не совсем Си . Добавлено через 5 минут и 25 секунд Цитата(MAKCim @  4.2.2008,  14:17 ) ты это затеял так что уж изволь  Каюсь, каюсь, время было, но было жутко лень . Вот мой вариант: Код #include <fstream> #include <iostream> #include <istream> #include <map> #include <ostream> #include <set> #include <sstream> #include <string> #include <boost/functional/hash.hpp> #include <boost/call_traits.hpp> #include <boost/mpl/if.hpp> #include <boost/foreach.hpp> #define foreach BOOST_FOREACH template< typename T > struct HashedWrapper { private:     typedef typename boost::call_traits< T >::param_type ParamType;     typedef boost::hash< T > Hash;     T value_;     Hash hasher;     std::size_t hash_; public:     HashedWrapper(ParamType value = T())         :    value_(value), hash_(hasher(value))     { }     const T &value() const     { return value_; }     const std::size_t hash() const     { return hash_; } }; template< typename T > struct DummyWrapper { private:     typedef typename boost::call_traits< T >::param_type ParamType;     T value_; public:     DummyWrapper(ParamType value = T())         :    value_(value)     { }     const T &value() const     { return value_; } }; template< typename T > struct LessWrapper; template< typename T > struct LessWrapper< DummyWrapper< T > >     :    public std::binary_function< const DummyWrapper< T > &, const DummyWrapper< T > &, bool > {     bool operator()(const DummyWrapper< T > &lhs, const DummyWrapper< T > &rhs) const     { return less(lhs.value(), rhs.value()); } private:     std::less< T > less; }; template< typename T > struct LessWrapper< HashedWrapper< T > >     :    public std::binary_function< const HashedWrapper< T > &, const HashedWrapper< T > &, bool > {     bool operator()(const HashedWrapper< T > &lhs, const HashedWrapper< T > &rhs) const     {         return    lhs.hash() < rhs.hash()                     ?    true                     :    rhs.hash() < lhs.hash()                         ?    false                         :    less(lhs.value(), rhs.value());     } private:     std::less< T > less; }; template< bool sorted > class Solution {     typedef std::string String;     typedef typename boost::mpl::if_c< sorted, DummyWrapper< String >, HashedWrapper< String > >::type ValueWrapper;     typedef LessWrapper< ValueWrapper > Less;     typedef std::set< ValueWrapper, Less > L2Container;     typedef std::map< ValueWrapper, L2Container, Less > L1Container;     typedef std::map< ValueWrapper, L1Container, Less > L0Container;     static const char lineDelimeter = '\n';     static const char keyDelimeter = ';';     L0Container container; public:     void input(std::istream &is)     {         while (is)         {             String ln;             std::getline(is, ln, lineDelimeter);             if (is)             {                 std::istringstream iss(ln);                 String l0Key, l1Key, l2Key;                 std::getline(iss, l0Key, keyDelimeter);                 std::getline(iss, l1Key, keyDelimeter);                 std::getline(iss, l2Key, keyDelimeter);                 if (iss)                     container[l0Key][l1Key].insert(l2Key);             }         }     }     void output(std::ostream &os)     {         foreach(const typename L0Container::value_type &l0, container)         {             os << l0.first.value() << std::endl;             foreach(const typename L1Container::value_type &l1, l0.second)             {                 os << "  " << l1.first.value() << std::endl;                 foreach(const typename L2Container::value_type &l2, l1.second)                     os << "    " << l2.value() << std::endl;             }         }     } }; int usage(const char *appName) {     std::cerr << "Usage: " << appName << " {<input-file> | - } {<output-file> | - } [sort]" << std::endl;     std::cerr << "If `-' passed, standard input/output stream will be used." << std::endl;     return EXIT_FAILURE; } template< bool sorted > int solve(std::istream &is, std::ostream &os) {     std::clock_t startTime, endTime;     std::clog << (startTime = std::clock()) << std::endl;     Solution< sorted > solution;     solution.input(is);     solution.output(os);     std::clog << (endTime = std::clock()) << std::endl;     std::clog << (endTime - startTime) << std::endl;     return EXIT_SUCCESS; } int main( #ifdef NDEBUG         int argc, const char *argv[] #endif ) { #ifndef NDEBUG //    const char * const argv[] = { "app", "-", "-" };     const char * const argv[] = { "app", "-", "-", "sort" };     const int argc = sizeof(argv) / sizeof(*argv); #endif     if (argc < 3)         return usage(argv[0]);     std::ifstream ifs;     std::ofstream ofs;     const bool isUseStd = !std::strcmp(argv[1], "-");     const bool osUseStd = !std::strcmp(argv[2], "-");     if (!isUseStd)         ifs.open(argv[1]);     if (!osUseStd)         ofs.open(argv[2]);     std::istream &is = isUseStd ? std::cin : ifs;     std::ostream &os = osUseStd ? std::cout : ofs;     const bool sort = argc > 3 && !std::strcmp(argv[3], "sort");     if (!is || !os)         return usage(argv[0]);     return    sort                 ? solve< true >(is, os)                 : solve< false >(is, os); } Сча попытаюсь отрефакторить Максовский код, чтобы он компилился как Сишный и, соответственно, затестить.

Автор: archimed7592 5.2.2008, 02:04

Вот подправленный вариант Макса из http://forum.vingrad.ru/index.php?showtopic=193332&view=findpost&p=1393606 поста: Код // test2.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdlib.h> #include <stdio.h> #include <stddef.h> #include <string.h> #include <time.h> #define AREA_SIZE    (4096 << 3) static char area[AREA_SIZE]; static char buffer[4096]; static char * pointer = buffer; struct list_head {     struct list_head * prev;     struct list_head * next; }; struct element {     char * string;     int offsets;     struct list_head list; }; struct list_head elements = {     &elements, &elements }; static int compare(struct element * a, struct element * b) {     int result = strcmp(a -> string, b -> string);     if (result > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + (a -> offsets & 0xFFFF), b -> string + (b -> offsets & 0xFFFF))) > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + ((a -> offsets) >> 16), b -> string + ((b -> offsets) >> 16))) > 0)         return 1;     else if (result < 0)         return -1;     return 0; } static void sort(void) {     struct list_head * entrya;     struct list_head * entryb;     struct element * elementa;     struct element * elementb;     char * sw_string;     int sw_offsets;     for (entrya = elements.next; entrya != &elements; entrya = entrya -> next) {         for (entryb = entrya -> next; entryb != &elements; entryb = entryb -> next) {             elementa = (struct element*)((char*)entrya - offsetof(struct element, list));             elementb = (struct element*)((char*)entryb - offsetof(struct element, list));             if (compare(elementa, elementb) <= 0)                 continue;             sw_string = elementa -> string;             elementa -> string = elementb -> string;             elementb -> string = sw_string;             sw_offsets = elementa -> offsets;             elementa -> offsets = elementb -> offsets;             elementb -> offsets = sw_offsets;         }     } } static int find(struct element * elem) {     struct list_head * entry = elem -> list.prev;     struct element * a;     for (; entry != &elements; entry = entry -> prev) {         a = (struct element*)((char*)entry - offsetof(struct element, list));         if (!compare(elem, a))             return 0;     } } static void print(int level, struct element * elem, FILE * fs) {     static char array[sizeof(int) * 2];     unsigned int * ptr = (unsigned int*)array;     ptr[0] = ptr[1] = 0x20202020;     switch (level) {         case 0:             array[0] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string);             array[0] = ' ';         case 1:             array[2] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) & 0xFFFF));             array[2] = ' ';         case 2:             array[4] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) >> 16));     } } #define DELIMITER    ';' int main(int argc, char * argv[]) {     clock_t startTime = clock(), endTime;     FILE * fs;     long position, start, end;     unsigned long last;     char * current;     struct element * element;     unsigned long count;     printf("%d\n", startTime);     fs = fopen(argv[1], "r");     fseek(fs, 0, SEEK_END);     position = ftell(fs);     rewind(fs);     start = 0;     last = AREA_SIZE;     current = area;     count = 0;     while (fgets(pointer, 4096, fs) != NULL) {         if ((end = ftell(fs)) - start > last) {             current = malloc(AREA_SIZE);             last = AREA_SIZE;         }         start = end;         element = (struct element*)current;         current = (char*)(element + 1);         element -> string = current;         element -> offsets = 0;         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= (current - element -> string);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= ((int)(current - element -> string) << 16);         for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);         *current++ = '\0';         last -= current - element -> string;         elements.next -> prev = &element -> list;         element -> list.next = elements.next;         element -> list.prev = &elements;         elements.next = &element -> list;         pointer = buffer;     }     if (argc == 4 && !strcmp(argv[3], "sort"))         sort();     {         FILE * w = fopen(argv[2], "w");         struct list_head * entry = elements.next;         struct list_head * previos;         struct element * entrye;         struct element * previose;         print(0, (struct element*)((char*)entry - offsetof(struct element, list)), w);         for (previos = entry, entry = entry -> next; entry != &elements; previos = entry, entry = entry -> next) {                 entrye = (struct element*)((char*)entry - offsetof(struct element, list));             previose = (struct element*)((char*)previos - offsetof(struct element, list));             if (!find(entrye))                 continue;             if (!strcmp(entrye -> string, previose -> string)) {                 if (!strcmp(entrye -> string + ((entrye -> offsets) & 0xFFFF),                              previose -> string + ((previose -> offsets) & 0xFFFF))) {                     print(2, entrye, w);                 } else print(1, entrye, w);             } else print(0, entrye, w);         }     }     endTime = clock();     printf("%d\n", endTime);     printf("%d\n", endTime - startTime);     return 0; } На входных данных, сгенерённых скриптом из http://forum.vingrad.ru/index.php?showtopic=193332&view=findpost&p=1393575 поста - AV на 121 строке...

Автор: archimed7592 5.2.2008, 02:34

Моё vs http://forum.vingrad.ru/index.php?showtopic=193332&view=findpost&p=1394052 maxim1000. Замечу, что у maxim1000 нет разницы между необходимостью сортировки и её отсутствием, потому у него результаты одинаковые.           archimed7592/nosort | archimed7592/sort | maxim1000/nosort | maxim1000/sort data #1          1890         |       1703        |       2031       |      2031      data #2          2390         |       2203        |       2531       |      2531      Как можно заметить, толку от моей попытки соптимизировать ненадобность сортировки не вышло, точнее получился антитолк . Хотя, если тэстить на том файлике в котором будет много категорий/подкатегорий/элементов, у которых начало будет одинаковым(отличие только в конце строки - к примеру, порядковый номер), то, думаю, толк от хэширования выйдет.

Автор: maxim1000 5.2.2008, 09:41

да... про хеш надо было мне подумать

Автор: MAKCim 5.2.2008, 10:12

Цитата(archimed7592 @  5.2.2008,  01:42 ) Эмм, Макс, это не совсем Си что здесь не С? Добавлено через 1 минуту и 37 секунд а boost-ом разве можно пользоваться? по-моему, только стандартная библиотека а то я тоже могу какую-нибудь библиотеку скачать   Добавлено через 6 минут и 15 секунд Цитата(archimed7592 @  5.2.2008,  02:04 ) На входных данных, сгенерённых скриптом из этого поста - AV на 121 строке...  я в курсе у меня на 927 грешу на реализацию fgets потому как на соответствующей итерации она возвращает хз какую строку   Добавлено через 7 минут и 45 секунд archimed7592,  ты файлик мой сишным компилятором компилил? test2.cpp меня смущает

Автор: archimed7592 5.2.2008, 10:23

Цитата(MAKCim @  5.2.2008,  10:12 ) что здесь не С? В Си можно объявлять/определять сущности только после открывающейся фигурной скобки. Вроде как... Цитата(MAKCim @  5.2.2008,  10:12 ) а boost-ом разве можно пользоваться? Макс, я тебя умоляю. foreach и call_traits я могу убрать, а hash и mpl::if реализовать "на месте" . Просто лень взяла своё . Цитата(MAKCim @  5.2.2008,  10:12 ) по-моему, только стандартная библиотека Ну это там была только стандартная, ибо у Дельфистов один аргумент: "вы без буста - ничто". У нас же задача не доказать друг другу, что один язык круче другого(и так очевидно, что Си - подмножество С++), а сравнить скорость, потому я предположил, что бустом воспользоваться можно . С другой стороны, если следовать букве задания, то нельзя использовать NTBS . Цитата(MAKCim @  5.2.2008,  10:12 ) а то я тоже могу какую-нибудь библиотеку скачать  smile   Я не против, только, чтобы простота установки была сравнима с бустом: скачал, поместил в include-paths и радуешься .

Автор: MAKCim 5.2.2008, 10:34

Цитата(archimed7592 @  5.2.2008,  10:23 ) В Си можно объявлять/определять сущности только после открывающейся фигурной скобки. Вроде как... я такого правила не знаю хотя может я не прав тыкните носом в стандарт    Цитата(archimed7592 @  5.2.2008,  10:23 ) С другой стороны, если следовать букве задания, то нельзя использовать NTBS C и NTBS понятия неразделимые   Добавлено через 2 минуты и 52 секунды ты какой компиялтор для моего кода использовал? судя по всему VS, и к тому же не С, да?

Автор: archimed7592 5.2.2008, 10:47

Цитата(MAKCim @  5.2.2008,  10:12 ) ты файлик мой сишным компилятором компилил? Угу. Это коммент автосгенерённый. Потом я его переименовал. Откуда думаешь я тебе на "не совсем Си" выдумал? Компилятор ругался . Цитата(MAKCim @  5.2.2008,  10:12 ) я в курсе у меня на 927 грешу на реализацию fgets Ты чего? Ладно, если бы это была одна реализация(glibc) - дык это уже MSVC и, скорее, нужно грешить не на библиотеку ;). Цитата(MAKCim @  5.2.2008,  10:34 ) тыкните носом в стандарт  smile  Минуточку...

Автор: archimed7592 5.2.2008, 11:20

Цитата(MAKCim @  5.2.2008,  10:34 ) я такого правила не знаю хотя может я не прав В общем, в С99 уже можно(насколько я понял), но MSVC-2005 об этом не в курсе .

Автор: MAKCim 5.2.2008, 11:41

Цитата(archimed7592 @  5.2.2008,  10:47 ) Ты чего? Ладно, если бы это была одна реализация(glibc) - дык это уже MSVC и, скорее, нужно грешить не на библиотеку ;). да, 5 баллов тому, кто найдет ошибку я уже нашел   Добавлено через 2 минуты и 17 секунд Цитата(archimed7592 @  5.2.2008,  11:20 ) В общем, в С99 уже можно(насколько я понял), но MSVC-2005 об этом не в курсе чего-то я непонял но у меня Код # gcc -ansi test.c -o test замечательно компилируется без скобок ANSI это никак не C99

Автор: archimed7592 5.2.2008, 11:54

Цитата(MAKCim @  5.2.2008,  11:41 ) чего-то я непонял Ты Сишник - тебе виднее . Цитата(MAKCim @  5.2.2008,  11:41 ) я уже нашел  smile Ага, нам не забудь показать .

Автор: Void 5.2.2008, 16:20

archimed7592, мне лень (и почти нет места на диске  ) ставить Boost, поэтому, будь добр, прогони на тех же тестовых данных http://forum.vingrad.ru/index.php?showtopic=193332&view=findpost&p=1392598.

Автор: Mayk 5.2.2008, 17:09

Цитата(MAKCim @  5.2.2008,  15:41 ) замечательно компилируется без скобок ANSI это никак не C99 -pedantic добавь. получишь что-то типа a.c:7: warning: ISO C90 forbids mixed declarations and code

Автор: Mayk 5.2.2008, 18:54

Ещё одна си-шная реализация против реализации maxim1000 ( по сравнению с Архимедом в ней букв мало, в варианте MAKcimа sigsegv ). Код #include <stdlib.h> #include <string.h> #include <stdio.h> #include <assert.h> enum{ DEPTH = 3 }; static char* DELIMITERS = ";:"; typedef struct buffer_s {     void** data;     int count;     int capacity; }buffer_t; typedef struct entry_s {     int entries[DEPTH]; }entry_t; static buffer_t strings[DEPTH]; void** buffer_alloc( buffer_t* buffer ) {     ++buffer->count;     if( buffer->count >= buffer->capacity ){         if( buffer->capacity )             buffer->capacity *= 2;         else              buffer->capacity = 8;         buffer->data = realloc(buffer->data, sizeof(void*) * buffer->capacity );     }     return &buffer->data[buffer->count - 1]; } static char* hash_to_string( int hash, unsigned depth ) {     assert( depth < DEPTH );     return strings[depth].data[hash]; } static int string_to_hash( const char* ptr, unsigned depth ) {     assert( depth < DEPTH );     buffer_t* buf = &strings[depth];     for( int i = 0; i < buf->count; ++i ){         if( strcmp(buf->data[i], ptr) == 0 ){             return i;         }     }     char** new_string = (char**)buffer_alloc( buf );     *new_string = strdup( ptr );     return buf->count-1; } static int compar( entry_t* a, entry_t * b ) {     for( int i = 0; i < DEPTH; ++i ){         if( a->entries[i] < b->entries[i] ){             return -1;         }         if( a->entries[i] > b->entries[i] ){             return  1;         }     }     return 0; } static buffer_t entries; void sort_entries() {     for( int i = 0; i < entries.count; ++i ){         for( int j = i+1; j < entries.count; ++j ){             if( compar( entries.data[i], entries.data[j] ) < 0 ){                 entry_t* tmp = entries.data[j];                 entries.data[j] = entries.data[i];                 entries.data[i] = tmp;             }         }     } } void add_entry(entry_t* entry) {     entry_t* dup = malloc(sizeof(entry_t));     memcpy( dup, entry, sizeof(entry_t) );     *buffer_alloc(&entries) = dup; }; void parse_entry( char* ptr ) {     entry_t entry;     for( int i = 0; i < DEPTH-1; ++i ){         int len = strcspn(ptr, DELIMITERS );         assert( len > 0 );         ptr[len]=0;         entry.entries[i] = string_to_hash( ptr, i );         ptr += 1+len;     }     ptr[strlen(ptr)-1] = 0;     entry.entries[DEPTH - 1] = string_to_hash( ptr, DEPTH - 1 );     add_entry( &entry ); } int main( int argc, char** argv) {     int sort = argc==4;     char buffer[1024];     if( argc < 3 ){         fprintf( stderr, "usage: %s in out [sort]\n", argv[0] );         return 1;     }     FILE* f = fopen(argv[1],"r");     int c =0;     while( fgets(buffer, sizeof(buffer), f) ){         parse_entry( buffer );     }     fclose(f);     if( sort ){         sort_entries();     }     entry_t nonEntry;     entry_t lastEntry;     for( int i = 0; i < DEPTH; ++i ){         nonEntry.entries[i]=-1;     }     lastEntry = nonEntry;     char* indents[DEPTH]={"","  ","    "};     assert( indents[DEPTH-1] != NULL );     FILE* out = fopen( argv[2], "w" );     for( int i = 0; i < entries.count; ++i ){         int printTail = 0;         entry_t* entry = entries.data[i];         for( int j = 0; j < DEPTH; ++j ){             if( printTail || lastEntry.entries[j] != entry->entries[j] ){                 fprintf( out, "%s%s\n",indents[j], hash_to_string(entry->entries[j], j));                 printTail = 1;                 lastEntry.entries[j] = entry->entries[j];             }         }     }     fclose(out); } а теперь цифры(порежу всё что не real) Код 21:49:dvl:~/src/catsort$ time ./main data /dev/null real    0m0.021s 21:49:dvl:~/src/catsort$ time ./main data /dev/null real    0m0.024s 21:49:dvl:~/src/catsort$ time ./main data /dev/null real    0m0.022s 21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null real    0m0.009s 21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null real    0m0.011s 21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null real    0m0.009s Итого. Вариант maxim1000 рулит. Во всех остальных букв много. В топку.  с сортировкой сишный вариант ухудшается до 0.0056-0.0080[квотить не буду, лень] секунд.   PS. заменил в maxim1000'вском варианте map'ы на unordered_map'ы. результаты ухудшились до ~0.0014.

Автор: Void 5.2.2008, 19:12

Mayk, входных данных побольше бы надо, миллисекунды опасно приближаются к пределам статистической погрешности. По хорошему, всегда надо делать серию и давать не только среднее, но и стандартное отклонение. Zed Shaw по этому поводу http://www.zedshaw.com/rants/programmer_stats.html.

Автор: Mayk 5.2.2008, 19:18

Цитата(Void @  5.2.2008,  23:12 ) Mayk, входных данных побольше бы надо, миллисекунды опасно приближаются к пределам статистической погрешности. Когда речь идёт о 0.0021 против 0.0009 в течение нескольких запусков --- не думаю что погрешности здесь исказят лидера.  А ждать пока они отработают на миллион записей мне лень. 1000 записей весьма большая n.  К тому же при увеличении n мой сишный код начнёт ещё больше тормозить  из-за квардатичнго построение строк через string_to_hash'а (кстати, привет profiler).  Переписывать во что-то более быстрое не получится не раздувая код(раздувать код -- лень). Сишный по компактности с STL'ным точно не сравнится. вообщем моё имхо --- фффтопку Варианты с >100 строками.

Автор: Любитель 5.2.2008, 19:34

Цитата(Mayk @  5.2.2008,  19:18 ) фффтопку Варианты с >100 строками +1

Автор: Void 5.2.2008, 21:21

В Boost 1.33, который в пакетах, нет foreach, поэтому вариант с бустом по совету Mayk пошёл в топку. Поскольку решили, что выруливает вариант maxim1000, буду сравнивать с ним. GCC 4.1.2, Python 2.5.1, Athlon 64 3200+ Из флагов gcc только -O2. Входной файл на 100 тыс. элементов, ~2,5 Мб. Вывод в /dev/null. Серии по 12 запусков, первый не учитывается. C++ (STL): mean = 0.93, stddev = 0.04 Python: mean = 0.92, stddev = 0.09 Python (sort): mean = 1.11, stddev = 0.02 Итак, мой прогноз оправдался в точности: Цитата(Void @  25.1.2008,  23:47 ) у меня есть подозрение, что как минимум не сортирующий вариант будет не медленнее Если в варианте C++ использовать unordered_map/hash_map, вероятно, будет прибавка в скорости, но вряд ли более чем двукратная. Та-ак, на чём бы ещё написать этот тестик

Автор: MAKCim 5.2.2008, 22:39

Mayk,  сортировочку у тебя можно в qsort() запихнуть будет быстрее в add_entry() вызывать постоянно malloc()...не слишком быстро Добавлено через 12 минут и 38 секунд вот мой исправленный вариант Код #include <stdlib.h> #include <stdio.h> #include <stddef.h> #include <string.h> #include <time.h> #define AREA_SIZE    (4096 << 3) static char area[AREA_SIZE]; static char buffer[4096]; static char * pointer = buffer; struct list_head {     struct list_head * prev;     struct list_head * next; }; struct element {     char * string;     int offsets;     struct list_head list; }; struct list_head elements = {     &elements, &elements }; static int compare(struct element * a, struct element * b) {     int result = strcmp(a -> string, b -> string);     if (result > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + (a -> offsets & 0xFFFF), b -> string + (b -> offsets & 0xFFFF))) > 0)         return 1;     else if (result < 0)         return -1;     else if ((result = strcmp(a -> string + ((a -> offsets) >> 16), b -> string + ((b -> offsets) >> 16))) > 0)         return 1;     else if (result < 0)         return -1;     return 0; } static void sort(void) {     struct list_head * entrya;     struct list_head * entryb;     struct element * elementa;     struct element * elementb;     char * sw_string;     int sw_offsets;     for (entrya = elements.next; entrya != &elements; entrya = entrya -> next) {         for (entryb = entrya -> next; entryb != &elements; entryb = entryb -> next) {             elementa = (struct element*)((char*)entrya - offsetof(struct element, list));             elementb = (struct element*)((char*)entryb - offsetof(struct element, list));             if (compare(elementa, elementb) <= 0)                 continue;             sw_string = elementa -> string;             elementa -> string = elementb -> string;             elementb -> string = sw_string;             sw_offsets = elementa -> offsets;             elementa -> offsets = elementb -> offsets;             elementb -> offsets = sw_offsets;         }     } } static int find(struct element * elem) {     struct list_head * entry = elements.next;     struct element * a;     for (; entry != &elements; entry = entry -> next) {         a = (struct element*)((char*)entry - offsetof(struct element, list));         if (!compare(elem, a))             return 0;     } } static void print(int level, struct element * elem, FILE * fs) {     static char array[sizeof(int) * 2];     unsigned int * ptr = (unsigned int*)array;     ptr[0] = ptr[1] = 0x20202020;     switch (level) {         case 0:             array[0] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string);             array[0] = ' ';         case 1:             array[2] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) & 0xFFFF));             array[2] = ' ';         case 2:             array[4] = '\0';             fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) >> 16));     } } #define DELIMITER    ';' int main(int argc, char * argv[]) {     clock_t startTime = clock(), endTime;     FILE * fs;     long position, start, end;     unsigned long last;     char * current;     struct element * element;     unsigned long count;     unsigned long shift = 1;     printf("%d\n", startTime);     fs = fopen(argv[1], "r");     fseek(fs, 0, SEEK_END);     position = ftell(fs);     rewind(fs);     start = 0;     last = AREA_SIZE;     current = area;     count = 0;     while (fgets(pointer, 4096, fs) != NULL) {         if ((end = (ftell(fs) - start + sizeof(struct element))) > last) {             last = AREA_SIZE << shift;             current = malloc(last);            ++shift;         }         start = end + start - sizeof(struct element);         element = (struct element*)current;         current = (char*)(element + 1);         element -> string = current;         element -> offsets = 0;         for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= (current - element -> string);         for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);         *current++ = '\0';         element -> offsets |= ((int)(current - element -> string) << 16);         for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);         *current++ = '\0';         pointer = buffer;         if (!find(element)) {             current = (char*)element;             continue;         }         last -= (current - element -> string + sizeof(struct element));         elements.next -> prev = &element -> list;         element -> list.next = elements.next;         element -> list.prev = &elements;         elements.next = &element -> list;     }     if (argc == 4 && !strcmp(argv[3], "sort"))         sort();     FILE * w = fopen(argv[2], "w");     struct list_head * entry = elements.next;     struct list_head * previos;     struct element * entrye;     struct element * previose;     print(0, (struct element*)((char*)entry - offsetof(struct element, list)), w);     for (previos = entry, entry = entry -> next; entry != &elements; previos = entry, entry = entry -> next) {             entrye = (struct element*)((char*)entry - offsetof(struct element, list));         previose = (struct element*)((char*)previos - offsetof(struct element, list));         if (!strcmp(entrye -> string, previose -> string)) {             if (!strcmp(entrye -> string + ((entrye -> offsets) & 0xFFFF),                      previose -> string + ((previose -> offsets) & 0xFFFF))) {                 print(2, entrye, w);             } else print(1, entrye, w);         } else print(0, entrye, w);     }     endTime = clock();     printf("%d\n", endTime);     printf("%d\n", endTime - startTime);     return 0; }

Автор: Mayk 6.2.2008, 07:23

Цитата(MAKCim @  6.2.2008,  02:39 ) сортировочку у тебя можно в qsort() запихнуть будет быстрее в add_entry() вызывать постоянно malloc()...не слишком быстро Про сортировку соглашусь. Самое смешное что в начале так и было, но я зачем-то убрал    А на add_entry  профайлер не советует обращать вниманин. По идее нужно string_to_hash чем-то нормальным заменить.  Ибо n раз линейный поиск отстой ещё тот.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)