// присутствует ли число a в массиве m размерности N
bool in_array( double a, double *m, int N )
{
int i;
for ( i = 0; i < N; i++ )
if( m == a )
return true;
return false;
}
// сдвиг влево на 1 начиная с a массива m размерностью N
void sdv( int a, double *m, int N )
{
int i;
for( i = a; i < N-1; i++ )
m = m[i+1];
}
// очистить массив m размерности N, возвращает размерность нового массива
int clean_array( double *m, int N )
{
double *m2;
int i, j = 0;
m2 = new double[N];
for( i = 0; i < N; i++ )
{
if( in_array(m, m2, j) == true )
{
sdv(i, m, N);
N--;
i--;
}
else
m2[j++] = m;
}
delete m2;
return N;
}
[C++]Удаление повторяющихся элементов массива
Пожалуйста, умоляю, помогите!!! Нужно решить несколько задач по С++:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
Цитата: Funny15
Пожалуйста, умоляю, помогите!!! Нужно решить несколько задач по С++:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
Если хочеш написать программу - с алгоритмом помогу, а саму программу увы. Меня уже тошнит от программ этого типа. Так ты хочеш написать программу, или тебе нада готовую?
Funny15, читай пожалуйста правила форума Студентам и не нарушай. [COLOR=red]Одна тема - один вопрос, темам даем смысловое название+указываем язык программирования в названии темы.[/COLOR]
вот такая реализация) не самая быстрая, но зато наглядная и работающая)))
алгоритм: создаётся дополнительный массив, потом проверяется исходный массив, если текущее число присутствует в дополнительном массиве, то оно удаляется (сдвигом на 1 начиная с текущей позиции) и размерность уменьшается на 1, если не найдено, то в дополнительный массив добавляется текущее значение...
использование например такое:
алгоритм: создаётся дополнительный массив, потом проверяется исходный массив, если текущее число присутствует в дополнительном массиве, то оно удаляется (сдвигом на 1 начиная с текущей позиции) и размерность уменьшается на 1, если не найдено, то в дополнительный массив добавляется текущее значение...
Код:
использование например такое:
Код:
int main( void )
{
double *m;
int N = 4;
m = new double[N];
m[0] = 1.0;
m[1] = 2.0;
m[2] = 1.0;
m[3] = 5.0;
for( int i = 0; i < N; i++ )
cout<<m<<" "; // возвращает 1 2 1 5
cout<<endl<<endl;
N = clean_array(m, N);
for( int i = 0; i < N; i++ )
cout<<m<<" "; // возвращает 1 2 5
return 0;
}
{
double *m;
int N = 4;
m = new double[N];
m[0] = 1.0;
m[1] = 2.0;
m[2] = 1.0;
m[3] = 5.0;
for( int i = 0; i < N; i++ )
cout<<m<<" "; // возвращает 1 2 1 5
cout<<endl<<endl;
N = clean_array(m, N);
for( int i = 0; i < N; i++ )
cout<<m<<" "; // возвращает 1 2 5
return 0;
}
=)
Реализация через битовую маску. ИМХО искать по массиву очень долго...
inp - битовая маска по кодам символов.
каждый симол имеет сой код, запоминаем его (отмечаем еденицей) в номере бита в битовой маске.
если в битовой маске бит равен 1, символ проходил проверку и значит выводился, если нет то выводим его.
Реализация через битовую маску. ИМХО искать по массиву очень долго...
Код:
#include "string.h"
#include "stdio.h"
void set_bit(unsigned char * in, char n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
in[byte_] =in[byte_] | (unsigned char )(1<<bit_);
}
unsigned char get_bit(unsigned char * in, char n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
if ( (in[byte_] & ((unsigned char )(1<<bit_))) != 0)
return 1;
else
return 0;
}
int main()
{
unsigned char inp[32];
memset(inp,0,sizeof(unsigned char)*32);
char * str_temp_in = new char [256];
strcpy(str_temp_in,"hwrthq2rthrltknpogh4o2\0");
for (int i = 0 ; i < strlen(str_temp_in);i++)
{
if(get_bit(inp,str_temp_in) == 0)
printf("%c",str_temp_in);
set_bit(inp,str_temp_in);
};
delete [] str_temp_in;
return 0;
}
#include "stdio.h"
void set_bit(unsigned char * in, char n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
in[byte_] =in[byte_] | (unsigned char )(1<<bit_);
}
unsigned char get_bit(unsigned char * in, char n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
if ( (in[byte_] & ((unsigned char )(1<<bit_))) != 0)
return 1;
else
return 0;
}
int main()
{
unsigned char inp[32];
memset(inp,0,sizeof(unsigned char)*32);
char * str_temp_in = new char [256];
strcpy(str_temp_in,"hwrthq2rthrltknpogh4o2\0");
for (int i = 0 ; i < strlen(str_temp_in);i++)
{
if(get_bit(inp,str_temp_in) == 0)
printf("%c",str_temp_in);
set_bit(inp,str_temp_in);
};
delete [] str_temp_in;
return 0;
}
inp - битовая маска по кодам символов.
каждый симол имеет сой код, запоминаем его (отмечаем еденицей) в номере бита в битовой маске.
если в битовой маске бит равен 1, символ проходил проверку и значит выводился, если нет то выводим его.
Массив - это вектор . Забыли про STL ? :)
Код:
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(0));
cout<<"input size of array"<<endl;
int size;
cin>>size;
vector<int> vec1;
for(int i = 0;i<size;++i)
vec1.push_back(rand()%9+1);// заполняем
// вектор заполнен случ. числами
for(vector<int>::iterator it = vec1.begin();
it != vec1.end();++it)
cout<<*it<<' ';
for(int j = 0;j<vec1.size();++j)
{
for(int i = 0;i<vec1.size();++i){
if(vec1 == vec1[j] && i != j)
vec1.erase(vec1.begin() + i);// удаляем
}
}
cout<<endl;
for(vector<int>::iterator it = vec1.begin();
it != vec1.end();++it)// выводим на экран
cout<<*it<<' ';
cout<<endl;
return 0;
}
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(0));
cout<<"input size of array"<<endl;
int size;
cin>>size;
vector<int> vec1;
for(int i = 0;i<size;++i)
vec1.push_back(rand()%9+1);// заполняем
// вектор заполнен случ. числами
for(vector<int>::iterator it = vec1.begin();
it != vec1.end();++it)
cout<<*it<<' ';
for(int j = 0;j<vec1.size();++j)
{
for(int i = 0;i<vec1.size();++i){
if(vec1 == vec1[j] && i != j)
vec1.erase(vec1.begin() + i);// удаляем
}
}
cout<<endl;
for(vector<int>::iterator it = vec1.begin();
it != vec1.end();++it)// выводим на экран
cout<<*it<<' ';
cout<<endl;
return 0;
}
Всем двойки! :)
Квадратичный алгоритм для такой простой задачки. Кто же так делает?!
Подсказка: можно за N*log(N)
Квадратичный алгоритм для такой простой задачки. Кто же так делает?!
Подсказка: можно за N*log(N)
Можно так:):
или так:
Код:
for(int i =0; i < Vector.size(); ++i)
{
Set.insert(Vector); //попытка скопировать элементы вектора в
//множество. Еслт такой элемент уже там есть -
//то, так как элементы множества уникальны,
//элемент не будет скопирован.
}
{
Set.insert(Vector); //попытка скопировать элементы вектора в
//множество. Еслт такой элемент уже там есть -
//то, так как элементы множества уникальны,
//элемент не будет скопирован.
}
или так:
Код:
sort(Vector.begin() , Vector.end()); //сорт. со сложностью O(N*Log(N))
unique(Vector.begin() , Vector.end());//удаляются элементы, равные
предыдущему. O(N)
unique(Vector.begin() , Vector.end());//удаляются элементы, равные
предыдущему. O(N)
to Green
Где ты здесь усмотрел квадратичный алгоритм ? =)
for (int i = 0 ; i < strlen(str_temp_in);i++)
Практически линейная сложность.
Где ты здесь усмотрел квадратичный алгоритм ? =)
for (int i = 0 ; i < strlen(str_temp_in);i++)
Практически линейная сложность.
2Zorkus : Конечно set ! Отличное решение !
Как я забыл ? :)
Как я забыл ? :)
Задача, очевидно, для студентов начальных курсов, так что stl здесь не уместна
Код:
int DimOld[20],
DimNew[20]; // Временный массив для хранения уникальных элементов исходного
for (int i = 0; i < 20; i++)
DimOld = (int)(((double) rand() / (double) RAND_MAX) * 20); // Забиваем массив случайными числами от 0 до 20
int CurIndex = 0;
bool Found;
for (int i = 0; i < 20; i++)
{
Found = false;
for (int j = 0; j < CurIndex; j++)
if ( DimNew[j] == DimOld )
{
Found = true;
break;
}
if ( !Found )
DimNew[CurIndex++] = DimOld;
}
// Создаём динамический массив с размерностью равной кол-ву уникальных элементов исходного и переписываем в него элементы из временного массива
int *DimFinal = new int[CurIndex];
for (int i = 0; i < CurIndex; i++)
DimFinal = DimNew;
DimNew[20]; // Временный массив для хранения уникальных элементов исходного
for (int i = 0; i < 20; i++)
DimOld = (int)(((double) rand() / (double) RAND_MAX) * 20); // Забиваем массив случайными числами от 0 до 20
int CurIndex = 0;
bool Found;
for (int i = 0; i < 20; i++)
{
Found = false;
for (int j = 0; j < CurIndex; j++)
if ( DimNew[j] == DimOld )
{
Found = true;
break;
}
if ( !Found )
DimNew[CurIndex++] = DimOld;
}
// Создаём динамический массив с размерностью равной кол-ву уникальных элементов исходного и переписываем в него элементы из временного массива
int *DimFinal = new int[CurIndex];
for (int i = 0; i < CurIndex; i++)
DimFinal = DimNew;
Цитата: ROLpogo
Задача, очевидно, для студентов начальных курсов, так что stl здесь не уместна
Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.
ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.
Цитата: Zorkus
Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.
ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.
ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.
Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.
Цитата: ROLpogo
Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.
Хорошо, оставим пока в покое начальные курсы. Но на многих специальностях, связанных с программированием, предмет "программирование", как таковое, идет два года. И когда тогда узнавать язык? В идеале должно быть четкое разделение - "языки программирования" и "теория алгортмов".
Насчет того, что STL скрывает реализацию простейших алгоритмов - так эти простейшие алгоритмы являются некими кирпичиками, из которых могут строиться более сложные алгоритмы. Возьмем пример - алгоритм Прима использует в стандартной реализации 2 множества. Но, думаю, человеку проще понять суть алгоритма, когда он оперирует готовым множеством (естественно, понимая принцип его внутренней организации), чем когда он пишет реализацию множества самостоятельно. Не говоря уже об экономии времени сил и размера кода, так как не надо распылятся на реализацию мелких подзадач.
И потом - всегда можно посмотреть, как реализован тот или иной алгоритм в исходниках STL, точно зная, что эта реализация безошибочна и быстра.
А в некоторых ( не хочу бросать тень на Alma Mater ) вообще выкинули
STL за ненадобностью ! Круто правда ! :( И даже не упоминать стараются , обьясняя это как раз тем что ... скрывает простейшие алгоритмы . И когда тебе кажется , что ты уже неплохо знаешь
язык , открываешь какую-нибудь современную книгу по С++...:)
Я например,открыл Саттера "Решение сложных задач на С++" ... Так вот после нескольких страниц у меня и возник вопрос - какой же язык я учил в институте ?:) Учили одно , а тут ... красота !
STL за ненадобностью ! Круто правда ! :( И даже не упоминать стараются , обьясняя это как раз тем что ... скрывает простейшие алгоритмы . И когда тебе кажется , что ты уже неплохо знаешь
язык , открываешь какую-нибудь современную книгу по С++...:)
Я например,открыл Саттера "Решение сложных задач на С++" ... Так вот после нескольких страниц у меня и возник вопрос - какой же язык я учил в институте ?:) Учили одно , а тут ... красота !
Код:
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
int main()
{
vector<int> Vec;
for(int i = 0; i < 100000000; i++)
{
Vec.push_back(i % 1000000);
}
int BegTime = clock();
sort(Vec.begin() , Vec.end());
Vec.resize(unique(Vec.begin() , Vec.end()) - Vec.begin());
/*for(int i = 0; i < Vec.size(); i++)
{
cout << Vec << endl;
}*/
cout << "Obshee vremja preobrazovanija vectora\n" << clock() - BegTime;
return EXIT_SUCCESS;
}
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
int main()
{
vector<int> Vec;
for(int i = 0; i < 100000000; i++)
{
Vec.push_back(i % 1000000);
}
int BegTime = clock();
sort(Vec.begin() , Vec.end());
Vec.resize(unique(Vec.begin() , Vec.end()) - Vec.begin());
/*for(int i = 0; i < Vec.size(); i++)
{
cout << Vec << endl;
}*/
cout << "Obshee vremja preobrazovanija vectora\n" << clock() - BegTime;
return EXIT_SUCCESS;
}
~108.5 сек. засеченное время.
Код:
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
int main()
{
vector<int> Vec;
for(int i = 0; i < 100000000; i++)
{
Vec.push_back(i % 1000000);
}
int BegTime = clock();
set<int> Set;
for(int i = 0; i < Vec.size(); i++)
{
Set.insert(Vec);
}
/*for(int i = 0; i < Vec.size(); i++)
{
cout << Vec << endl;
}*/
cout << "Obshee vremja preobrazovanija vectora\n" << clock() - BegTime;
return EXIT_SUCCESS;
}
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
int main()
{
vector<int> Vec;
for(int i = 0; i < 100000000; i++)
{
Vec.push_back(i % 1000000);
}
int BegTime = clock();
set<int> Set;
for(int i = 0; i < Vec.size(); i++)
{
Set.insert(Vec);
}
/*for(int i = 0; i < Vec.size(); i++)
{
cout << Vec << endl;
}*/
cout << "Obshee vremja preobrazovanija vectora\n" << clock() - BegTime;
return EXIT_SUCCESS;
}
116.4 cек. засеченное время.
Буду дальше экспериментировать:)
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.
Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
Цитата: ROLpogo
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.
Да, конечно, согласен 100%.
Цитата: ROLpogo
Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
Причем тут юмор, и почему не оценит? у меня была на экзамене такая задача, где нужно было парсить строку в поисках чего-то, не вспомню щас условие. И я за каких-то 10 минут:) доказал преподу, что мое решение заслуживает 5, так как в том виде, в каком я его представил, оно скомпилится и будет работать, и выдаст правильный ответ.
Так что, автор, не бойся спорить с преподом, если он не принимает решение только потому, что он сам решал иначе!:)
Цитата:
Zorkus:
~108.5 сек. засеченное время.
116.4 cек. засеченное время.
Буду дальше экспериментировать:)
Код:
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
#include <conio.h>
void qsort(int* Mas, int L, int R)
{
int Lo, Hi, Mid, T;
Lo = L;
Hi = R;
Mid = Mas[(Lo + Hi) / 2];
do
{
while ( Mas[Lo] < Mid )
Lo++;
while ( Mas[Hi] > Mid )
Hi--;
if ( Lo <= Hi )
{
T = Mas[Lo];
Mas[Lo] = Mas[Hi];
Mas[Hi] = T;
Lo++;
Hi--;
}
}
while ( Lo <= Hi );
if ( Hi > L )
qsort(Mas, L, Hi);
if ( Lo < R )
qsort(Mas, Lo, R);
}
using namespace std;
void main(void)
{
int *DimOld = new int[10000000];
randomize();
for (int i = 0; i < 10000000; i++)
DimOld = (int)(((double) rand() / (double) RAND_MAX) * 10000000);
int CurIndex = 0;
bool Found;
vector<int> Vec;
for(int i = 0; i < 10000000; i++)
Vec.push_back(DimOld);
int BegTime = clock();
int *DimBuf = new int[10000000];
for (int i = 1; i < 10000000; i++)
DimBuf = DimOld;
qsort(DimBuf, 0 , 9999999);
int CurElem = DimBuf[0];
int *DimNew = new int[10000000];
DimNew[CurIndex++] = CurElem;
for (int i = 1; i < 10000000; i++)
if ( DimBuf != CurElem )
{
CurElem = DimBuf;
DimNew[CurIndex++] = CurElem;
}
delete []DimBuf;
int *DimFinal = new int[CurIndex];
for (int i = 0; i < CurIndex; i++)
DimFinal = DimNew;
delete []DimNew;
cout << "ROLpogo: obshee vremja preobrazovanija: " << clock() - BegTime<<" ms\n\n";
set<int> Set;
BegTime = clock();
for(int i = 0; i < Vec.size(); i++)
Set.insert(Vec);
cout << "Obshee vremja preobrazovanija vectora1: " << clock() - BegTime<<" ms\n";
BegTime = clock();
sort(Vec.begin() , Vec.end());
Vec.resize(unique(Vec.begin() , Vec.end()) - Vec.begin());
cout << "Obshee vremja preobrazovanija vectora2: " << clock() - BegTime<<" ms";
getch();
}
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <ctime>
#include <conio.h>
void qsort(int* Mas, int L, int R)
{
int Lo, Hi, Mid, T;
Lo = L;
Hi = R;
Mid = Mas[(Lo + Hi) / 2];
do
{
while ( Mas[Lo] < Mid )
Lo++;
while ( Mas[Hi] > Mid )
Hi--;
if ( Lo <= Hi )
{
T = Mas[Lo];
Mas[Lo] = Mas[Hi];
Mas[Hi] = T;
Lo++;
Hi--;
}
}
while ( Lo <= Hi );
if ( Hi > L )
qsort(Mas, L, Hi);
if ( Lo < R )
qsort(Mas, Lo, R);
}
using namespace std;
void main(void)
{
int *DimOld = new int[10000000];
randomize();
for (int i = 0; i < 10000000; i++)
DimOld = (int)(((double) rand() / (double) RAND_MAX) * 10000000);
int CurIndex = 0;
bool Found;
vector<int> Vec;
for(int i = 0; i < 10000000; i++)
Vec.push_back(DimOld);
int BegTime = clock();
int *DimBuf = new int[10000000];
for (int i = 1; i < 10000000; i++)
DimBuf = DimOld;
qsort(DimBuf, 0 , 9999999);
int CurElem = DimBuf[0];
int *DimNew = new int[10000000];
DimNew[CurIndex++] = CurElem;
for (int i = 1; i < 10000000; i++)
if ( DimBuf != CurElem )
{
CurElem = DimBuf;
DimNew[CurIndex++] = CurElem;
}
delete []DimBuf;
int *DimFinal = new int[CurIndex];
for (int i = 0; i < CurIndex; i++)
DimFinal = DimNew;
delete []DimNew;
cout << "ROLpogo: obshee vremja preobrazovanija: " << clock() - BegTime<<" ms\n\n";
set<int> Set;
BegTime = clock();
for(int i = 0; i < Vec.size(); i++)
Set.insert(Vec);
cout << "Obshee vremja preobrazovanija vectora1: " << clock() - BegTime<<" ms\n";
BegTime = clock();
sort(Vec.begin() , Vec.end());
Vec.resize(unique(Vec.begin() , Vec.end()) - Vec.begin());
cout << "Obshee vremja preobrazovanija vectora2: " << clock() - BegTime<<" ms";
getch();
}
кол-во элементов исходного массива: 10000000
При разбросе значений элементов от 0 до 10:
ROLpogo: ~3360 ms
Zorkus1: ~5906 ms
Zorkus2: ~4719 ms
При разбросе значений элементов от 0 до 10000000 (при меньшем кол-ве одинаковых элементов):
ROLpogo: ~4375 ms
Zorkus1: ~28125 ms
Zorkus2: ~5031 ms
Для определенности: использовал MinGW Developer Studio 2.05
build 04-01-2005.
Все тесты при условии, что на машине работала только эта программа.
При разбросе значений от 0 до 10:
ROLpogo: : 3078 ms
Zorkus-1: 3016 ms
Zorkus-2: 7188 ms0
ROLpogo: : 2891 ms
Zorkus-1: 2969 ms
Zorkus-2: 7187 ms
ROLpogo: 2969 ms
Zorkus-1: 2969 ms
Zorkus-2: 7156 ms0
ROLpogo: 3406 ms
Zorkus-1: 2969 ms
Zorkus-2: 7125 ms
Учитывая точность засекания системного времени, ты, думаю, согласишься, что первое мое решение (хотя это не решение, конечно, это эффективность стандартных реализаций, скажем так:)) либо приблизительно такое же по времени как и твое, , либо (судя по твоим тестам) уступает ему порядка нескольких десятков процентов.
При разбросе элементов 1000 получаются значения такого типа:
ROLpogo: порядка 3,5 - 3,7
Zorkus-1: порядка 4,9-5,2
Zorkus-2: порядка 6,7-7,0
и при полном разбросе (10 000 000):
ROLpogo: порядка 4,3 - 4,6
Zorkus-1: порядка 8,9-9,0
Zorkus-2: порядка 6,7-7,0
Тут мое решение проигрывает, конечно по скорости, но несравнимо проще в кодинге, отладке и читабельности. После сессии попробую код на других компиляторах/реализациях STL, и скажу результаты.
P.S. Я не утверждаю, что код STL может быть быстрее грамотно написанного вручную кода, но считаю, и собираюсь проверить, что в новых реализациях STL он проигрывает по быстродействию очень немного.
build 04-01-2005.
Все тесты при условии, что на машине работала только эта программа.
При разбросе значений от 0 до 10:
ROLpogo: : 3078 ms
Zorkus-1: 3016 ms
Zorkus-2: 7188 ms0
ROLpogo: : 2891 ms
Zorkus-1: 2969 ms
Zorkus-2: 7187 ms
ROLpogo: 2969 ms
Zorkus-1: 2969 ms
Zorkus-2: 7156 ms0
ROLpogo: 3406 ms
Zorkus-1: 2969 ms
Zorkus-2: 7125 ms
Учитывая точность засекания системного времени, ты, думаю, согласишься, что первое мое решение (хотя это не решение, конечно, это эффективность стандартных реализаций, скажем так:)) либо приблизительно такое же по времени как и твое, , либо (судя по твоим тестам) уступает ему порядка нескольких десятков процентов.
При разбросе элементов 1000 получаются значения такого типа:
ROLpogo: порядка 3,5 - 3,7
Zorkus-1: порядка 4,9-5,2
Zorkus-2: порядка 6,7-7,0
и при полном разбросе (10 000 000):
ROLpogo: порядка 4,3 - 4,6
Zorkus-1: порядка 8,9-9,0
Zorkus-2: порядка 6,7-7,0
Тут мое решение проигрывает, конечно по скорости, но несравнимо проще в кодинге, отладке и читабельности. После сессии попробую код на других компиляторах/реализациях STL, и скажу результаты.
P.S. Я не утверждаю, что код STL может быть быстрее грамотно написанного вручную кода, но считаю, и собираюсь проверить, что в новых реализациях STL он проигрывает по быстродействию очень немного.
ребята, где вы такие цифры достали?
на моей рабочей лошадке 1.7 Ghz, 256 RAM на ASPLinux 9, KDE 2.1
программка, вообщем то делающая тоже самое, ну с разумными ограничениями - набором символов в 1024 символа, делает это за 0,1125 сек.
Да, и расширение набора символов не дает значительного увелечения времени работы.
Вообщем то согласен что изучение STL, один из важных этапов в обучении современного программиста. Только без знания самых азов программирования ему этот STL как собаке пятая нога =).
ИМХО. мое скромное мнение...
на моей рабочей лошадке 1.7 Ghz, 256 RAM на ASPLinux 9, KDE 2.1
программка, вообщем то делающая тоже самое, ну с разумными ограничениями - набором символов в 1024 символа, делает это за 0,1125 сек.
Да, и расширение набора символов не дает значительного увелечения времени работы.
Код:
#include <iostream.h>
#include <stdlib.h>
#include "sys/time.h"
// итого можно закодировать 128*8 число букв
#define BUKVA_BiTE_LEN 128
void set_bit(unsigned char * in, unsigned int n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
in[byte_] =in[byte_] | (unsigned char )(1<<bit_);
}
unsigned char get_bit(unsigned char * in,unsigned int n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
if ( (in[byte_] & ((unsigned char )(1<<bit_))) != 0)
return 1;
else
return 0;
}
bool finish_him (unsigned char * in)
{
bool ret = false;
unsigned char finish_byte = 0xFF;
for (unsigned char l = 0; l <BUKVA_BiTE_LEN; l++)
finish_byte = finish_byte & in[l];
if (finish_byte == 0xFF)
return true;
return ret;
}
int main(int argc, char *argv[])
{
unsigned char inp[BUKVA_BiTE_LEN];
long i=0;
long j=0;
timeval t1,t2;
memset(inp,0,sizeof(unsigned char)*BUKVA_BiTE_LEN);
int * str_temp_in = new int [10000000];
int * str_temp_out = new int [10000000];
for ( i = 0 ; i < 10000000;i++)
str_temp_in = ((unsigned int)(rand()%(BUKVA_BiTE_LEN*8)));
j=0;
gettimeofday(&t1,0);
for ( i = 0 ; i < 10000000;i++)
{
if(get_bit(inp,str_temp_in) == 0)
{
str_temp_out[j++] = str_temp_in;
set_bit(inp,str_temp_in);
if (finish_him(inp))
break;
};
};
gettimeofday(&t2,0);
printf(" rez = %ld, %ld\n",t2.tv_sec-t1.tv_sec,t2.tv_usec-t1.tv_usec);
delete [] str_temp_in;
delete [] str_temp_out;
return 0;
}
#include <stdlib.h>
#include "sys/time.h"
// итого можно закодировать 128*8 число букв
#define BUKVA_BiTE_LEN 128
void set_bit(unsigned char * in, unsigned int n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
in[byte_] =in[byte_] | (unsigned char )(1<<bit_);
}
unsigned char get_bit(unsigned char * in,unsigned int n)
{
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
if ( (in[byte_] & ((unsigned char )(1<<bit_))) != 0)
return 1;
else
return 0;
}
bool finish_him (unsigned char * in)
{
bool ret = false;
unsigned char finish_byte = 0xFF;
for (unsigned char l = 0; l <BUKVA_BiTE_LEN; l++)
finish_byte = finish_byte & in[l];
if (finish_byte == 0xFF)
return true;
return ret;
}
int main(int argc, char *argv[])
{
unsigned char inp[BUKVA_BiTE_LEN];
long i=0;
long j=0;
timeval t1,t2;
memset(inp,0,sizeof(unsigned char)*BUKVA_BiTE_LEN);
int * str_temp_in = new int [10000000];
int * str_temp_out = new int [10000000];
for ( i = 0 ; i < 10000000;i++)
str_temp_in = ((unsigned int)(rand()%(BUKVA_BiTE_LEN*8)));
j=0;
gettimeofday(&t1,0);
for ( i = 0 ; i < 10000000;i++)
{
if(get_bit(inp,str_temp_in) == 0)
{
str_temp_out[j++] = str_temp_in;
set_bit(inp,str_temp_in);
if (finish_him(inp))
break;
};
};
gettimeofday(&t2,0);
printf(" rez = %ld, %ld\n",t2.tv_sec-t1.tv_sec,t2.tv_usec-t1.tv_usec);
delete [] str_temp_in;
delete [] str_temp_out;
return 0;
}
Вообщем то согласен что изучение STL, один из важных этапов в обучении современного программиста. Только без знания самых азов программирования ему этот STL как собаке пятая нога =).
ИМХО. мое скромное мнение...
Приведенный тобой алгоритм рационален лишь для численных значений, причем небольшого размера. Например для dword размер словаря (алфавита) составит 512Мб, при таких больших размерах время выборки становится логарифмическим, т.е. расширение набора дает снижение скорости.
Т.о. для массива int array[2] алгоритм становится нерациональным.
Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
Т.о. метод применим лишь в очень узком кругу задач, но имеет право на жизнь.
Алгоритм же с сортировкой получается более универсальным, при этом не сильно проигрывает по скорости на специфичных данных (для которых твой алгоритм предпочтительнее) и сильно выигрывает в общем случае по скорости, объему под данные и применимости (универсальности).
Подмывает немного поругать твой код, но не буду... :)
Скажи только, для чего функция finish_him (это тоже придирка к коду, т.к. он не очевиден, не самодокументирован).
И ещё вопрос, что ты подразумеваешь под "азами программирования" ?
Т.о. для массива int array[2] алгоритм становится нерациональным.
Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
Т.о. метод применим лишь в очень узком кругу задач, но имеет право на жизнь.
Алгоритм же с сортировкой получается более универсальным, при этом не сильно проигрывает по скорости на специфичных данных (для которых твой алгоритм предпочтительнее) и сильно выигрывает в общем случае по скорости, объему под данные и применимости (универсальности).
Подмывает немного поругать твой код, но не буду... :)
Скажи только, для чего функция finish_him (это тоже придирка к коду, т.к. он не очевиден, не самодокументирован).
И ещё вопрос, что ты подразумеваешь под "азами программирования" ?
Ну да, так и есть, для большего набора символов алгоритм не рационален и даже вреден =).
Если строка введенных пользователем сиволов представляется как массив char`ов, то вполне ничего. Вообщем то про это было оговорено.
Хотя конечно фраза
Если строка введенных пользователем сиволов представляется как массив char`ов, то вполне ничего. Вообщем то про это было оговорено.
Хотя конечно фраза
Цитата:
Да, и расширение набора символов не дает значительного увелечения времени работы.
здесь неуместна.
Функция finish_him? Да, задумывалась как проверка того, что все символы из набора уже перенесены в выходной массив.
Можно и код поругать, я не обидчивый... даже, наверное, и полезно будет =)
Азы программирования? Алгоритм+данные=программа. Базовые курсы по специальности программирование.
Я не ставил задачу написать код, который будет работать максимально быстро на данной конкретной задаче. Я старался показать, что шаблонная реализация (в строго техническом смысле) может быть ненамного уступающей по скорости эксклюзивной, но неимоверно проще в реализации.
Для тех, кто хочет привязать решение к типу и добиться максимальной производительности - думаю, реализацию ROLpogo можно ускорить, в частности, написав код обмена переменных асмовой вставкой (так как асм не знаю, проверить не могу:))
2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?
Потом, алгоритм передачи в множество. Он зависит сильно от разброса, как видно из примеров, в отличие от сортировки, менее универсален.
P.S. И еще - большая просьба к авторам кодов указывать ось и IDE/компилер. А то у меня проги ROLpogo и Одиссея не собираются без некоторых поправок:)
Для тех, кто хочет привязать решение к типу и добиться максимальной производительности - думаю, реализацию ROLpogo можно ускорить, в частности, написав код обмена переменных асмовой вставкой (так как асм не знаю, проверить не могу:))
2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?
Потом, алгоритм передачи в множество. Он зависит сильно от разброса, как видно из примеров, в отличие от сортировки, менее универсален.
P.S. И еще - большая просьба к авторам кодов указывать ось и IDE/компилер. А то у меня проги ROLpogo и Одиссея не собираются без некоторых поправок:)
Цитата: Zorkus
2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?
Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). :D
Цитата: Green
Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). :D
+1 :D
Кстати использование hash_set вместо set должно дать (в общем то оно и даёт) вполне ощутимый выигрыш. Ещё немного можно отыграть у handmade кода, если использовать STLPort.
P.S.: Тесты проводились с отключённой оптимизацией?
P.S.: Тесты проводились с отключённой оптимизацией?
Ага , а еще +5% cкорости если без цикла
hash_set.insert(Vec.begin(),Vec.end());:)
Проверял.
hash_set.insert(Vec.begin(),Vec.end());:)
Проверял.
Цитата: k3Eahn
Кстати использование hash_set вместо set должно дать (в общем то оно и даёт) вполне ощутимый выигрыш. Ещё немного можно отыграть у handmade кода, если использовать STLPort.
P.S.: Тесты проводились с отключённой оптимизацией?
P.S.: Тесты проводились с отключённой оптимизацией?
Я ее вообще не смотрел, и собирал в debug.
А вот я включил (верней, он у меня и стоял)средний уровень оптимизацию и собрал релиз, результаты поменялись...;)
на 10 - разбросе:
ROLpogo: : 921 ms
Zorkus-1: 531 ms
Zorkus-2: 891 ms
на 1000 разбросе:
ROLpogo: : 1156 ms
Zorkus-1: 1093 ms
Zorkus-2: 1079 ms
и наконец, на 10 000 000
ROLpogo: : 1391 ms
Zorkus-1: 3672 ms
Zorkus-2: 1297 ms
Как видим, результаты поменялись. Теперь связка sort-unique работает быстрей вручную написанного кода. Насчет того, что на больших разбросах множество отстает - но я перепишу на hash, должен быть сущ. прирост, как ты и сказал.
Про хэш-таблицу я как-то не подумал, т.к. въелось, что в стандартной STL ее нету:).
Для hash_set, тест для разброса 10 000 000:
ROLpogo: : 1328 ms
Zorkus-1: 1453 ms
Zorkus-2: 1281 ms
Примечание: для разброса 10 работает медленней простого set в полтора раза.
Цитата: Zorkus
Примечание: для разброса 10 работает медленней простого set в полтора раза.
А ты попробуй вариант m_Valery. Для разброса от 1 до 10 у меня время сократилось в 1.7 раза по сравнению с hash_set::insert.
Цитата: k3Eahn
А ты попробуй вариант m_Valery. Для разброса от 1 до 10 у меня время сократилось в 1.7 раза по сравнению с hash_set::insert.
Я пробовал сразу вставлять
insert(Vec.begin() , Vec.end())
Для разброса 10 точно, такой как ты говоришь, выигрыш, около 1,5 - 1,7, т.е. работает по времени примерно как обычный set.insert(Elem).
Зато на тесте 10 000 000 такой вариант проигрывает последовательному добавлению, 1431 ms VS 1689. И в любом случае, для большого разброса, вариант с сортировой предпочтительнее выходит. Ну а для маленьких разбросов - hash_set, получается. Из них и выбирать, если больше мы тут ничего не придумаем, как улучшить:)
Цитата: Odissey_
Можно и код поругать, я не обидчивый... даже, наверное, и полезно будет =)
Ну сам напросился... :)
Начнем.
1. Для начала маленькое замечание: переменные лучше определять перед их непосредственным использованием. Я отношу это и к счетчикам циклов.
2. Если при определении массива его ещё можно и инициализировать нулями, не надо будет вызывать memset.
3. Есть более простой способ определять, что все символы из набора уже перенесены в выходной массив, - просто подсчитывать сколько символов уже перенесено. У тебя для этого уже и счетчик заведен j.
4. Вместо возвращения значения бита в твоем коде более уместна проверка "установлен ли бит?".
5. Точка с запятой после программных скобок не нужна.
Т.о. твой код превращается в такой:
Код:
// итого можно закодировать 128*8 число букв
#define BUKVA_BiTE_LEN 128
void set_bit(unsigned char* in, unsigned int n)
{
int bit_ = n%8;
int byte_ = n/8;
in[byte_] = in[byte_] | (unsigned char)(1<<bit_);
}
bool is_bit(unsigned char* in, unsigned int n)
{
int bit_ = n%8;
int byte_ = n/8;
return in[byte_] & (unsigned char )(1<<bit_);
}
int main(int argc, char *argv[])
{
unsigned char inp[BUKVA_BiTE_LEN] = {0};
int* str_temp_in = new int [10000000];
int* str_temp_out = new int [10000000];
for (long i = 0 ; i < 10000000;i++)
str_temp_in = (unsigned int)(rand()%(BUKVA_BiTE_LEN*8));
for (long i=0, j=0; i < 10000000; i++)
{
if ( is_bit(inp,str_temp_in) )
{
str_temp_out[j++] = str_temp_in;
set_bit(inp, str_temp_in);
if (j == BUKVA_BiTE_LEN)
break;
}
}
delete[] str_temp_in;
delete[] str_temp_out;
return 0;
}
#define BUKVA_BiTE_LEN 128
void set_bit(unsigned char* in, unsigned int n)
{
int bit_ = n%8;
int byte_ = n/8;
in[byte_] = in[byte_] | (unsigned char)(1<<bit_);
}
bool is_bit(unsigned char* in, unsigned int n)
{
int bit_ = n%8;
int byte_ = n/8;
return in[byte_] & (unsigned char )(1<<bit_);
}
int main(int argc, char *argv[])
{
unsigned char inp[BUKVA_BiTE_LEN] = {0};
int* str_temp_in = new int [10000000];
int* str_temp_out = new int [10000000];
for (long i = 0 ; i < 10000000;i++)
str_temp_in = (unsigned int)(rand()%(BUKVA_BiTE_LEN*8));
for (long i=0, j=0; i < 10000000; i++)
{
if ( is_bit(inp,str_temp_in) )
{
str_temp_out[j++] = str_temp_in;
set_bit(inp, str_temp_in);
if (j == BUKVA_BiTE_LEN)
break;
}
}
delete[] str_temp_in;
delete[] str_temp_out;
return 0;
}
Ну и маленькое предложение по оптимизации по памяти.
Т.к. массив str_temp_out заполняется не быстрее, чем производится выборка из массива str_temp_in, то это может быть одним массивом.
Ну тогда тоже сделаю пару замечаний:)
1)
Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
1)
Цитата: Green
Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
Если мы будет обрабатывать массив объектов, то надо будет уже юзать stable_sort. А вот она выполняется процентов на 70 медленней sort() на разбросе 10 000 000 для данных тестов.
2) Скорей вопрос. Если использовать ассемблерную вставку для обмена переменных в сортировке, написанной лапами, то можно ли код существенно ускорить (насколько)?
Цитата: Zorkus
2) Скорей вопрос. Если использовать ассемблерную вставку для обмена переменных в сортировке, написанной лапами, то можно ли код существенно ускорить (насколько)?
Я думаю, что существенно от этого ничего не измениться.
Есть другое (очевидное) замечание, что в случае объектов, рациональным будет не перемещать объекты в памяти, а перемещать ссылки (указатели, индексы и т.п.) на них.
Цитата: Green
Есть другое (очевидное) замечание, что в случае объектов, рациональным будет не перемещать объекты в памяти, а перемещать ссылки (указатели, индексы и т.п.) на них.
Конечно, будет лучше с точки зрения оптимальности использовать list<>,
там и sort(), и unique() определены. И с точки зрения транзакционной безопасности намного надежнее вектора будет. Но просто тема началась с термина массив:)
Да можно и массив, массив указателей или массив индексов.
toGreen
Отдельное спасибо за
if (j == BUKVA_BiTE_LEN)
break;
Отдельное спасибо за
Цитата:
if (j == BUKVA_BiTE_LEN)
break;
Почему-то такой вариант в голову не пришел =(.
Насчет массива тоже верно, просто не было задачи минимизации памяти.
Остальное, помоему, дело вкуса. Хорошего вкуса программировать у меня пока нет, команда разработчиков у нас небольшая, да и таких задач как стандарт кода перед нами не ставилось. Поэтому всё так как есть.
Все замечания дельные, спасибо.
Цитата: Odissey_
toGreen
Отдельное спасибо за
Отдельное спасибо за
Там только ещё на 8 надо умножить: BUKVA_BiTE_LEN*8
Да, кстати, я бы отказался от применения битового массива.
Увеличение расхода памяти в 8 раз приведет к увеличению производительности на порядки, а как мы уже обсудили, вариант применим лишь к массивам значений небольшого диапазона, поэтому нет смысла экономить на таком небольшом объеме памяти (например для char это будет 256 байт против 32 байт).
А если сделать еще одну копию массива и написать так:
Код:
/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
int main()
{
int a[100] = {}; /*Here will be a result. Тут будет результат*/
int b[12] = {1,2,3,4,5,5,6,6,7,0};
int c[12] = {1,2,3,4,5,5,6,6,7,0};
int i = 0;
int j = 0;
int z = 0;
int p = 0;
/*Here we remove twins. Удаляем дубликаты*/
z = 0;
for (i = 0; c[i] != 0; i++) {
j = 0;
p = 0;
while (b[j] != 0) {
if (c[i] == b[j]) p++;
j++;
}
if (p == 1) a[z++] = c[i];
}
for (i = 0; a[i] != 0; i++) printf("%d", a[i]);;
}
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
int main()
{
int a[100] = {}; /*Here will be a result. Тут будет результат*/
int b[12] = {1,2,3,4,5,5,6,6,7,0};
int c[12] = {1,2,3,4,5,5,6,6,7,0};
int i = 0;
int j = 0;
int z = 0;
int p = 0;
/*Here we remove twins. Удаляем дубликаты*/
z = 0;
for (i = 0; c[i] != 0; i++) {
j = 0;
p = 0;
while (b[j] != 0) {
if (c[i] == b[j]) p++;
j++;
}
if (p == 1) a[z++] = c[i];
}
for (i = 0; a[i] != 0; i++) printf("%d", a[i]);;
}