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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
#1

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

07.01.2014, 12:22. Просмотров 496. Ответов 13
Метки нет (Все метки)

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;   
}
код работает правильно, но превышает лимит по времени..как можно ускорить программу?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2014, 12:22     Ускорение програмки
Посмотрите здесь:

програмки C++ - C++
1. Даны сведения об авто: фамилия владельца, марка, цвет, год выпуска: 1) Найти фамилии владельцев, у которых белые «Жигули». 2) Найти...

решите програмки на C++ - C++
1. Описать процедуру Swap(x,y), меняющую содержимо переменных x и y(x и y - вещественные параметры, являющиеся одновремнно входными и...

Две простенькие програмки - C++
При защите лабораторных спросили следующие задания : F(x)=N! Cin &gt; N Найти N! Дан масив из 10 символов нужно вывести на экран...

Програмки на cpp для вещественных массивов - C++
Пожалуйста помогите написать пару программ на языке cpp: 1. Даны вещественные массивы D, A. Для каждого массива определить среднее...

LPSTR не совместим ребят давно не писал програмки подскажите) - C++
вот раньше работало в 2006, а щас нет) Зарание спасибо

Можно примерчик простенькой програмки, которая читает строку с клавы и записывает ее в переменную. - C++
Собственно простенький примерчик. Надо, что бы человек вводил с клавиатуры строку, потом нажимал &lt;Enter&gt; и, то что он ввел попадало в...

Ускорение алгоритмов - C++
Имеется код, нужно его ускорить. (Помогите тупому!!!!!!!) #include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;string&gt; #include...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,184
Завершенные тесты: 1
07.01.2014, 12:27     Ускорение програмки #2
Надо все рекурсивные функции переделать на обычные.
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
07.01.2014, 12:35  [ТС]     Ускорение програмки #3
Цитата Сообщение от zss Посмотреть сообщение
Надо все рекурсивные функции переделать на обычные.
я не думаю что это сделает её намного быстрее, у меня другая идея, при добавлении строки в дерево, кажый раз ищется вершина самого дерева, на это идут большие затраты времени, идея состоит в том чтобы хранить указатель на вершину, но как я не знаю
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.01.2014, 13:32     Ускорение програмки #4
Doksim, вы бы хоть условие задачи написали. что программа должна делать то?

но судя по тому, что есть могу сказать следующее:
1. struct Tree - какой смысл вы вкладываете в название Tree, просто я вижу односвязный список
2. что должна делать функция Prefix, мне кажется цикл в строках 54-62 не верно работает, т.к. значение prefix в нем может только обнулиться
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
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.01.2014, 14:15     Ускорение програмки #6
1.
Цитата Сообщение от Doksim Посмотреть сообщение
Название можно и поменять.
...
все работает правильно
...
при добавлении строки в дерево...
да как же всё может работать правильно если вы не понимаете разницы между деревом и списком?
2. я так понимаю, что условие задачи великая тайна, раз вы не хотите им поделиться. ну что же, удачи, ждите экстрасенса, который поймет, что же делает / должна делать функция Prefix
Algiz
160 / 160 / 13
Регистрация: 23.02.2011
Сообщений: 347
07.01.2014, 14:25     Ускорение програмки #7
Цитата Сообщение от Doksim Посмотреть сообщение
struct Tree
{
* * * *char s[ 54925 ];
* * * *struct Tree *d;
};
зачем тебе так много чаров. уменьш длину массива и память под struct Tree будет выделятся намного быстрее(у тебя же они все в куче).
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,184
Завершенные тесты: 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
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
160 / 160 / 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
_
201 / 145 / 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++
#include &lt;bits/stdc++.h&gt; #define ll long long using namespace std; bool ar; int main() { int n,cnt=0; scanf(&quot;%d&quot;,...

Ускорение програмы на с++ - C++
Здраствуйте!Нужно ускорить программу по возможности. #include &lt;iostream&gt; #include &lt;vector&gt; #include...

Ускорение проги потоками - C++
Здорова господа! Только что у меня прога глючила и вылетала я от не заметил она именно в дебаг режиме вылетала и медленно работала, а...

Ускорение алгоритма перебора - C++
Здравствуйте! В общем есть такая задачка: Имеются N(1 ≤ N ≤ 18) камней с массами W1, W2 , … WN. И, короче, нужно разложить камни на...


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

Или воспользуйтесь поиском по форуму:
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     Ускорение програмки
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru