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

maxim1000

Дата 4.2.2008, 11:26 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(archimed7592 @ 4.2.2008, 00:01

)

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

про какую сортировку речь?
если я не ошибаюсь, сортировка нужна на всех этапах для быстрого поиска - ведь перед добавлением очередного элемента на любой уровень нужно найти его, если он вдруг уже есть

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

qqq

MAKCim

Дата 4.2.2008, 14:17 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

archimed7592,

Цитата(archimed7592 @ 4.2.2008, 00:01

)

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

ты это затеял
так что уж изволь smile

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

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

archimed7592

Дата 5.2.2008, 01:42 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 26.1.2008, 22:23

)

{
    FILE * fs = fopen(argv[1], "r");
    fseek(fs, 0, SEEK_END);
    long position = ftell(fs) + 1;

Эмм, Макс, это не совсем Си smile

.

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

Цитата(MAKCim @ 4.2.2008, 14:17

)

ты это затеял
так что уж изволь

Каюсь, каюсь, время было, но было жутко лень smile

.

Вот мой вариант:

Код


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

Сча попытаюсь отрефакторить Максовский код, чтобы он компилился как Сишный и, соответственно, затестить.

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

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

archimed7592

Дата 5.2.2008, 02:04 (ссылка)

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

Загрузка ...

Архимед

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

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

Вот подправленный вариант Макса из этого поста:

Код


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

На входных данных, сгенерённых скриптом из этого поста - AV на 121 строке...

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

archimed7592

Дата 5.2.2008, 02:34 (ссылка)

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

Загрузка ...

Архимед

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

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

Моё vs решение maxim1000. Замечу, что у maxim1000 нет разницы между необходимостью сортировки и её отсутствием, потому у него результаты одинаковые.

          archimed7592/nosort | archimed7592/sort | maxim1000/nosort | maxim1000/sort
data #1          1890         |       1703        |       2031       |      2031
data #2          2390         |       2203        |       2531       |      2531

Как можно заметить, толку от моей попытки соптимизировать ненадобность сортировки не вышло, точнее получился антитолк smile

.
Хотя, если тэстить на том файлике в котором будет много категорий/подкатегорий/элементов, у которых начало будет одинаковым(отличие только в конце строки - к примеру, порядковый номер), то, думаю, толк от хэширования выйдет.

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

maxim1000

Дата 5.2.2008, 09:41 (ссылка)

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

Загрузка ...

Эксперт

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

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

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

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

qqq

MAKCim

Дата 5.2.2008, 10:12 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(archimed7592 @ 5.2.2008, 01:42

)

Эмм, Макс, это не совсем Си

что здесь не С?

Добавлено через 1 минуту и 37 секунд
а boost-ом разве можно пользоваться?
по-моему, только стандартная библиотека
а то я тоже могу какую-нибудь библиотеку скачать smile

Добавлено через 6 минут и 15 секунд

Цитата(archimed7592 @ 5.2.2008, 02:04

)

На входных данных, сгенерённых скриптом из этого поста - AV на 121 строке...

я в курсе
у меня на 927
грешу на реализацию fgets
потому как на соответствующей итерации она возвращает хз какую строку
smile

Добавлено через 7 минут и 45 секунд
archimed7592,
ты файлик мой сишным компилятором компилил?
test2.cpp меня смущает smile

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

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

archimed7592

Дата 5.2.2008, 10:23 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 5.2.2008, 10:12

)

что здесь не С?

В Си можно объявлять/определять сущности только после открывающейся фигурной скобки. Вроде как...

Цитата(MAKCim @ 5.2.2008, 10:12

)

а boost-ом разве можно пользоваться?

Макс, я тебя умоляю. foreach и call_traits я могу убрать, а hash и mpl::if реализовать "на месте" smile

. Просто лень взяла своё smile

Цитата(MAKCim @ 5.2.2008, 10:12

)

по-моему, только стандартная библиотека

Ну это там была только стандартная, ибо у Дельфистов один аргумент: "вы без буста - ничто". У нас же задача не доказать друг другу, что один язык круче другого(и так очевидно, что Си - подмножество С++), а сравнить скорость, потому я предположил, что бустом воспользоваться можно smile

.
С другой стороны, если следовать букве задания, то нельзя использовать NTBS smile

Цитата(MAKCim @ 5.2.2008, 10:12

)

а то я тоже могу какую-нибудь библиотеку скачать smile

Я не против, только, чтобы простота установки была сравнима с бустом: скачал, поместил в include-paths и радуешься smile

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

MAKCim

Дата 5.2.2008, 10:34 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(archimed7592 @ 5.2.2008, 10:23

)

В Си можно объявлять/определять сущности только после открывающейся фигурной скобки. Вроде как...

я такого правила не знаю
хотя может я не прав
тыкните носом в стандарт smile

Цитата(archimed7592 @ 5.2.2008, 10:23

)

С другой стороны, если следовать букве задания, то нельзя использовать NTBS

C и NTBS понятия неразделимые smile

Добавлено через 2 минуты и 52 секунды
ты какой компиялтор для моего кода использовал?
судя по всему VS, и к тому же не С, да? smile

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

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

archimed7592

Дата 5.2.2008, 10:47 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 5.2.2008, 10:12

)

ты файлик мой сишным компилятором компилил?

Угу. Это коммент автосгенерённый. Потом я его переименовал. Откуда думаешь я тебе на "не совсем Си" выдумал? Компилятор ругался smile

Цитата(MAKCim @ 5.2.2008, 10:12

)

я в курсе
у меня на 927
грешу на реализацию fgets

Ты чего? Ладно, если бы это была одна реализация(glibc) - дык это уже MSVC и, скорее, нужно грешить не на библиотеку ;).

Цитата(MAKCim @ 5.2.2008, 10:34

)

тыкните носом в стандарт smile

Минуточку... smile

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

archimed7592

Дата 5.2.2008, 11:20 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 5.2.2008, 10:34

)

я такого правила не знаю
хотя может я не прав

В общем, в С99 уже можно(насколько я понял), но MSVC-2005 об этом не в курсе smile

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

MAKCim

Дата 5.2.2008, 11:41 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(archimed7592 @ 5.2.2008, 10:47

)

да, 5 баллов тому, кто найдет ошибку
я уже нашел smile

Добавлено через 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 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 5.2.2008, 11:41

)

чего-то я непонял

Ты Сишник - тебе виднее smile

Цитата(MAKCim @ 5.2.2008, 11:41

)

я уже нашел smile

Ага, нам не забудь показать smile

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

Void

Дата 5.2.2008, 16:20 (ссылка)

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

Загрузка ...

λcat.lolcat

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

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

archimed7592, мне лень (и почти нет места на диске smile

) ставить Boost, поэтому, будь добр, прогони на тех же тестовых данных питоновый скрипт.

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

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

Mayk

Дата 5.2.2008, 17:09 (ссылка)

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

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

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

Цитата(MAKCim @ 5.2.2008, 15:41

)

замечательно компилируется без скобок
ANSI это никак не C99

-pedantic добавь. получишь что-то типа a.c:7: warning: ISO C90 forbids mixed declarations and code

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

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

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

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