Форум программистов, компьютерный форум CyberForum.ru

Ускорение програмки - C++

Восстановить пароль Регистрация
 
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 12:22     Ускорение програмки #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
struct Tree
{
       char s[ 54925 ];
       struct Tree *d;
};
 
 /*void show(struct Tree **tree) //Функция обхода
{
    if (*tree!=NULL) //Пока не встретится пустое звено
    {
       show(&((*tree)->d)); //Рекурсивная функция для вывода левого поддерева
       printf( "%s\n", (*tree)->s ); //Отображаем корень дерева
    }
}*/
void Insert( struct Tree **tree, char newstring[] )
{
     if( *tree == NULL )
     {
         *tree = (struct Tree *) malloc( sizeof( struct Tree ) );
         strcpy( (*tree)->s, newstring );
         (*tree)->d = NULL;
     }
     else
     {
         if ( (*tree)->d != NULL )Insert( &((*tree)->d), newstring );
         else 
         {
              (*tree)->d = (struct Tree *) malloc( sizeof( struct Tree ) );
              (*tree)->d->d = NULL; 
              strcpy( (*tree)->d->s, newstring );
         }
     }
}
 
void Delete( struct Tree **tree )
{
     if( (*tree)->d != NULL )
     {
         strcpy( (*tree)->s, (*tree)->d->s );
         Delete( &((*tree)->d) );
     }
}
 
int Prefix( struct Tree **tree, char prefstring[] )
{
    if( *tree != NULL )
    {
        int prefix = 1, len = strlen( prefstring );
        int i = 0;
        while( i < len )
        {
             if( (*tree)->s[ i ] != prefstring[ i ] )
             {
                 prefix = 0;
                 break;
             }
             i++;
        }
        return prefix + Prefix( &((*tree)->d), prefstring );
    }
    else return 0;
}
 
struct Tree *Prisystvie( struct Tree **tree, char string[] )
{
     if( *tree != NULL )
     {
         if( strcmp( (*tree)->s, string ) == 0 )
         return *tree;
         else return Prisystvie( &((*tree)->d), string );
     }
     else return NULL;
}
 
struct Tree *FindTop( struct Tree **tree )
{
       if( (*tree)->d == NULL )return *tree;
       else FindTop( &((*tree)->d) );
}
 
void FreeTree( struct Tree **tree )
{
     if( *tree != NULL )
     {
        FreeTree( &((*tree)->d) );
         
        free( *tree );
        *tree = NULL;
     }
}
void FreeTop( struct Tree **tree )
{
     if( (*tree)->d == NULL )
     {
        free( *tree );
        *tree = NULL;
     }
     else FreeTop( &((*tree)->d) );
}
 
int main()
{
    struct Tree *tree = NULL, *d = NULL;
    int n;
    scanf( "%d", &n );
    
    char cmd[ 6 ], string[ 1000000 ];
    
    int i = 0;
    while( i < n )
    {
         scanf( "%s %s", &cmd, &string);
         
         if( strcmp( cmd, "INSERT" ) == 0 )
         {
             if( !Prisystvie( &tree, string ) )
             Insert( &tree, string );
         }
         if( strcmp( cmd, "DELETE" ) == 0 )
         {
             if( d = Prisystvie( &tree, string ) )
             {
                 Delete( &d );
                 FreeTop( &tree );
             }
         }
         if( strcmp( cmd, "PREFIX" ) == 0 )
         {
             printf( "%d\n", Prefix( &tree, string ) );
         }
         i++;
    }
    
    return 0;   
}
код работает правильно, но превышает лимит по времени..как можно ускорить программу?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,154
Завершенные тесты: 1
07.01.2014, 12:27     Ускорение програмки #2
Надо все рекурсивные функции переделать на обычные.
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 12:35  [ТС]     Ускорение програмки #3
Цитата Сообщение от zss Посмотреть сообщение
Надо все рекурсивные функции переделать на обычные.
я не думаю что это сделает её намного быстрее, у меня другая идея, при добавлении строки в дерево, кажый раз ищется вершина самого дерева, на это идут большие затраты времени, идея состоит в том чтобы хранить указатель на вершину, но как я не знаю
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.01.2014, 13:32     Ускорение програмки #4
Doksim, вы бы хоть условие задачи написали. что программа должна делать то?

но судя по тому, что есть могу сказать следующее:
1. struct Tree - какой смысл вы вкладываете в название Tree, просто я вижу односвязный список
2. что должна делать функция Prefix, мне кажется цикл в строках 54-62 не верно работает, т.к. значение prefix в нем может только обнулиться
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 13:59  [ТС]     Ускорение програмки #5
Цитата Сообщение от ya_noob Посмотреть сообщение
Doksim, вы бы хоть условие задачи написали. что программа должна делать то?

но судя по тому, что есть могу сказать следующее:
1. struct Tree - какой смысл вы вкладываете в название Tree, просто я вижу односвязный список
2. что должна делать функция Prefix, мне кажется цикл в строках 54-62 не верно работает, т.к. значение prefix в нем может только обнулиться
Название можно и поменять., все работает правильно, но очень долго выше писал как можно ускорить но не пойму как это сделать
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.01.2014, 14:15     Ускорение програмки #6
1.
Цитата Сообщение от Doksim Посмотреть сообщение
Название можно и поменять.
...
все работает правильно
...
при добавлении строки в дерево...
да как же всё может работать правильно если вы не понимаете разницы между деревом и списком?
2. я так понимаю, что условие задачи великая тайна, раз вы не хотите им поделиться. ну что же, удачи, ждите экстрасенса, который поймет, что же делает / должна делать функция Prefix
Algiz
159 / 159 / 13
Регистрация: 23.02.2011
Сообщений: 347
07.01.2014, 14:25     Ускорение програмки #7
Цитата Сообщение от Doksim Посмотреть сообщение
struct Tree
{
* * * *char s[ 54925 ];
* * * *struct Tree *d;
};
зачем тебе так много чаров. уменьш длину массива и память под struct Tree будет выделятся намного быстрее(у тебя же они все в куче).
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,154
Завершенные тесты: 1
07.01.2014, 14:25     Ускорение програмки #8
Цитата Сообщение от Doksim Посмотреть сообщение
я не думаю что это сделает её намного быстрее
Рекурсивные функции очень много времени тратят на запись параметров и адресов возврата в стек,
поэтому сильно замедляют программу.
В целом, считаю рекурсивные функции баловством.
Timur_CF
39 / 39 / 3
Регистрация: 12.12.2013
Сообщений: 227
Записей в блоге: 1
07.01.2014, 14:47     Ускорение програмки #9
Перепиши на ассемблере (inline).
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 16:34  [ТС]     Ускорение програмки #10
Цитата Сообщение от ya_noob Посмотреть сообщение
да как же всё может работать правильно если вы не понимаете разницы между деревом и списком?
магия, но программа отвечает на тесты правильно.
Цитата Сообщение от ya_noob Посмотреть сообщение
я так понимаю, что условие задачи великая тайна
Реализуйте структуру данных, представляющую множество строк с операциями Insert (добавление строки в множество), Delete (удаление строки из множества) и Prefix (подсчёт количества строк множества, имеющих указанных префикс). Операции Insert и Delete должны работать за время O(len (k)), где k – добавляемая или удаляемая строка, а операция Prefix – за время O(len (p)) – где p – префикс.
Составьте программу ptrie.c, демонстрирующую работоспособность реализованных операций.

Формат входных данных

Первая строка, считываемая со стандартного потока ввода, содержит общее количество выполняемых операций n (0 < n ≤ 10000). Каждая из следующих n строк содержит описание операции.
Операция либо имеет форму INSERT k (добавить в множество строку k, 0 < len(k ) < 100000), либо форму DELETE k (удалить из множества имеющуюся в нём строку k), либо форму PREFIX p (вычислить количество строк в множестве, имеющих префикс p).
Отметим, что аргументы операций – это строки, составленные из маленьких латинских букв.
Кроме того, допустим вызов операции INSERT для строки, уже присутствующей в множестве.
Формат результата работы программы

Для каждой операции PREFIX вывести в стандартный поток вывода количество строк в множестве, имеющих указанный префикс.
Цитата Сообщение от Algiz Посмотреть сообщение
зачем тебе так много чаров.
http://195.19.53.94:3386/tasks/iu9/a...ptrie/tests/22 данные теста 22
Цитата Сообщение от zss Посмотреть сообщение
Рекурсивные функции очень много времени тратят на запись параметров и адресов возврата в стек,
Будет больше мороки переписывать из рекурсии в циклы чем я выжму из этого всего время.
Цитата Сообщение от Timur_CF Посмотреть сообщение
Перепиши на ассемблере (inline).
Не вариант Я не знаю ассемблер, к тому же надо на С
Timur_CF
39 / 39 / 3
Регистрация: 12.12.2013
Сообщений: 227
Записей в блоге: 1
07.01.2014, 19:50     Ускорение програмки #11
Цитата Сообщение от Doksim Посмотреть сообщение
магия, но программа отвечает на тесты правильно.

Реализуйте структуру данных, представляющую множество строк с операциями Insert (добавление строки в множество), Delete (удаление строки из множества) и Prefix (подсчёт количества строк множества, имеющих указанных префикс). Операции Insert и Delete должны работать за время O(len (k)), где k – добавляемая или удаляемая строка, а операция Prefix – за время O(len (p)) – где p – префикс.
Составьте программу ptrie.c, демонстрирующую работоспособность реализованных операций.

Формат входных данных

Первая строка, считываемая со стандартного потока ввода, содержит общее количество выполняемых операций n (0 < n ≤ 10000). Каждая из следующих n строк содержит описание операции.
Операция либо имеет форму INSERT k (добавить в множество строку k, 0 < len(k ) < 100000), либо форму DELETE k (удалить из множества имеющуюся в нём строку k), либо форму PREFIX p (вычислить количество строк в множестве, имеющих префикс p).
Отметим, что аргументы операций – это строки, составленные из маленьких латинских букв.
Кроме того, допустим вызов операции INSERT для строки, уже присутствующей в множестве.
Формат результата работы программы

Для каждой операции PREFIX вывести в стандартный поток вывода количество строк в множестве, имеющих указанный префикс.

http://195.19.53.94:3386/tasks/iu9/a...ptrie/tests/22 данные теста 22

Будет больше мороки переписывать из рекурсии в циклы чем я выжму из этого всего время.

Не вариант Я не знаю ассемблер, к тому же надо на С
Я имел в виду inline ассемблер.
Algiz
159 / 159 / 13
Регистрация: 23.02.2011
Сообщений: 347
07.01.2014, 20:22     Ускорение програмки #12
Цитата Сообщение от Doksim Посмотреть сообщение
http://195.19.53.94:3386/tasks/iu9/a...ptrie/tests/22 данные теста 22
У тебя плохой алгоритм. Должен быть более простой способ решения(завтра сам попробую, сейчас спать очень хочу). В любом случае строка длинной 54925 это костыль, из-за которого потребелние памяти огромное, и на скорость тоже влияет.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.01.2014, 21:32     Ускорение програмки #13
Doksim, в вашей ссылке на тест содержится решение задачи , а именно ptrie. если владеете английским, то вот описание этой структуры: http://ecommons.library.cornell.edu/handle/1813/5722 . интересная но сложная структура данных на Trie-деревьях. я бы посоветовал реализовать простое Trie-дерево. Хотя можно вообще без деревьев обойтись с помощью хэшей.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2014, 23:18     Ускорение програмки
Еще ссылки по теме:

C++ Ускорение алгоритмов
C++ Ускорение алгоритма
C++ Ускорение проги потоками

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 23:18  [ТС]     Ускорение програмки #14
Цитата Сообщение от Algiz Посмотреть сообщение
У тебя плохой алгоритм. Должен быть более простой способ решения(завтра сам попробую, сейчас спать очень хочу). В любом случае строка длинной 54925 это костыль, из-за которого потребелние памяти огромное, и на скорость тоже влияет.
http://195.19.53.94:3386/tasks/iu9/a...ptrie/tests/22 данные теста 22

Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
Doksim, в вашей ссылке на тест содержится решение задачи , а именно ptrie. если владеете английским, то вот описание этой структуры: http://ecommons.library.cornell.edu/handle/1813/5722 . интересная но сложная структура данных на Trie-деревьях. я бы посоветовал реализовать простое Trie-дерево. Хотя можно вообще без деревьев обойтись с помощью хэшей.
Я с этими легкими ели разобрался..и то не до конца..
Yandex
Объявления
07.01.2014, 23:18     Ускорение програмки
Ответ Создать тему
Опции темы

Текущее время: 04:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru