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

MAKCim

Дата 26.1.2008, 19:00 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(Void @ 26.1.2008, 18:55

)

погоди, кто сказал, что имена категорий фиксированы? Из

где написано обратное? smile

цифры тоже могут отсутствовать?
если надо, могу исправить

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

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

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

Void

Дата 26.1.2008, 19:11 (ссылка)

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

Загрузка ...

λcat.lolcat

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

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

Цитата(MAKCim @ 26.1.2008, 21:00

)

где написано?

ТЗ чертовски неформальное.
Теперь понял логику, но, признаться, мне бы в жизни не пришло в голову так его интерпретировать smile

Потому что задачка из более менее осмысленной превращается в весьма искусственную.

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

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

MAKCim

Дата 26.1.2008, 19:12 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(Void @ 26.1.2008, 19:11

)

Теперь понял логику, но, признаться, мне бы в жизни не пришло в голову так его интерпретировать

а что, я как-то по-особенному проитерпретировал?

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

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

Void

Дата 26.1.2008, 19:21 (ссылка)

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

Загрузка ...

λcat.lolcat

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

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

Цитата(MAKCim @ 26.1.2008, 21:12

)

а что, я как-то по-особенному проитерпретировал?

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

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

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

MAKCim

Дата 26.1.2008, 19:45 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Void,
вообщем надо уточнить, что имелось в виду
сейчас у меня программа работает очень быстро
вот тестовый пример

Код


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

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

Загрузка ...

Архимед

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

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

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

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

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

Void

Дата 26.1.2008, 19:54 (ссылка)

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

Загрузка ...

λcat.lolcat

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

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

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

С произвольными строками по любому интереснее.

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

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

MAKCim

Дата 26.1.2008, 19:55 (ссылка)

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

Загрузка ...

Воін дZэна

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

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

Цитата(archimed7592 @ 26.1.2008, 19:50

)

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

сгенерируй правильный входной файл и выходной
так будет проще писАть

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

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

chipset

Дата 26.1.2008, 21:10 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4071
Регистрация: 11.1.2003
Где: Seattle, US

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

Цитата(archimed7592 @ 26.1.2008, 02:26

)

Ты как считаешь, в Google достаточно серьёзные вычисления бегают? smile
Там про С++ не слышали... Ну, точнее, слышали, но для обработки своих задач его не используют.

Ты неправ. Гугл ето ВСЕ С++. Кроме ГУИ.

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

Цитата(Jimi Hendrix)

Well, I stand up next to a mountain
And I chop it down with the edge of my hand

archimed7592

Дата 26.1.2008, 21:13 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(chipset @ 26.1.2008, 21:10

)

Гугл ето ВСЕ С++.

Чипс, откуда дровишки? smile

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

archimed7592

Дата 26.1.2008, 21:34 (ссылка)

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

Загрузка ...

Архимед

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

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

Цитата(MAKCim @ 26.1.2008, 19:55

)

сгенерируй правильный входной файл и выходной

Ишь ты хитрый какой smile

. Я могу сгенерировать, но сойдёт и тот, что в условии, ибо всё равно тестировать будем на другом файле smile

. Точнее говоря, никаких предположений о формате строк делать нельзя. Это просто произвольные строки. Нужно разбить на категории, на подкатегории и вывести результат smile

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

MAKCim

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

(голосов:1)

Загрузка ...

Воін дZэна

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

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

блин, за...лся писать smile

вот

Код


#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,
тест давай
smile

Добавлено @ 22:32
сортировка пузырьковая
было влом QuickSort писать, а стандартный qsort() со списками не работает

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

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

chipset

Дата 26.1.2008, 22:42 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4071
Регистрация: 11.1.2003
Где: Seattle, US

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

Цитата(archimed7592 @ 26.1.2008, 11:13

)

Чипс, откуда дровишки? smile

Ну а что там по твоему? Си шарп? ЫЫЫ, может Java? ))))

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

Цитата(Jimi Hendrix)

Well, I stand up next to a mountain
And I chop it down with the edge of my hand

MAKCim

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

(голосов:1)

Загрузка ...

Воін дZэна

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

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

блин, пока вас дождешься
вот генератор

Код


#!/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()

вот тестовый пример
вот результаты на моей системе

Цитата

# time ./main data out sort
real    0m0.012s
user    0m0.008s
sys     0m0.004s

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

archimed7592

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

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

Загрузка ...

Архимед

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

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

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

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

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

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