VPF::C++ - производительность - Форум программистов

MAKCim

Дата 26.1.2008, 23:29 (ссылка)

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

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

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

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

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

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

archimed7592

Дата 26.1.2008, 23:38 (ссылка)

(голосов:1)

Загрузка ...

Архимед

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

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

chipset, вот, можешь почитать Алёнкин конспект: http://alenacpp.blogspot.com/2007/02/blog-post_20.html .

Макс, ой, не сегодня... Не до этого, к сожалению. Может быть завтра руки дойдут.

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

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

maxim1000

Дата 27.1.2008, 01:14 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

вот небольшой набросок со стороны С++:

Код


#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-шный вариант

Это сообщение отредактировал(а) maxim1000 - 27.1.2008, 01:16

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

qqq

Любитель

Дата 27.1.2008, 01:53 (ссылка)

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

Загрузка ...

Программист-романтик

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

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

Цитата(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++" smile

В чём тогда мораль?

Добавлено через 5 минут и 32 секунды

Цитата(maxim1000 @ 27.1.2008, 01:14

)

с сортировкой некрасиво получилось (копирование вектора)

Банально - сет или мультисет (в зависимости от условий задачи - лень особо читать :/ ) вместо вектора.

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

http://oryolalex.mybrute.com

maxim1000

Дата 27.1.2008, 10:42 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

Цитата(Любитель @ 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;
}

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

qqq

Void

Дата 27.1.2008, 11:44 (ссылка)

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

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

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

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()

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

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

MAKCim

Дата 27.1.2008, 11:44 (ссылка)

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

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

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

господа
либо баг у меня, либо в 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

Это сообщение отредактировал(а) MAKCim - 27.1.2008, 11:45

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

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Void

Дата 27.1.2008, 11:58 (ссылка)

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

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

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

Цитата(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 в исходном коде

Я это и делал.

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

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

MAKCim

Дата 27.1.2008, 12:34 (ссылка)

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

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

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

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 (ссылка)

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

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

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

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)

Мда.

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

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

MAKCim

Дата 27.1.2008, 12:51 (ссылка)

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

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

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

Цитата(Void @ 27.1.2008, 12:43

)

Проблема в gcc. С -O2 у меня результат неверный, с -O0 всё нормально.

O_O
что за х....

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

archimed7592

Дата 27.1.2008, 14:28 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(maxim1000 @ 27.1.2008, 10:42

)

про set думал, но не хотелось объединять одинаковые значения

Оу, ребят, можете считать, что тройка cat;subcat;entry уникальна и, если она встречается дважды(или большее кол-во раз), то выводить её нужно единожды.

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

maxim1000

Дата 27.1.2008, 22:36 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

Цитата(archimed7592 @ 27.1.2008, 14:28

)

ну тогда так smile

Код


#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;
}

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

qqq

mr.DUDA

Дата 29.1.2008, 10:42 (ссылка)

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

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

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

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

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

archimed7592

Дата 4.2.2008, 00:01 (ссылка)

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

Загрузка ...

Архимед

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

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

maxim1000, в таком случае у тебя сортировка при любом раскладе отрабатывает... Т.е. в тестах без сортировки твой вариант теоретически "сольёт"...

Цитата(mr.DUDA @ 29.1.2008, 10:42

)

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

Когда появится время, чтобы затестить решения(ещё бы найти время, чтобы своё решение навоять)... smile

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

Правила ведения Религиозных войн
	1. Уважайте собеседника 2. Собеседник != враг 3. Старайтесь воздерживаться от тем вида "Windows Rulez" или "Linux Rulez" С уважением, Smartov.

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