c++ Удаление повторяющихся элементов массива
В денном решении все одинаковые сдвигаются в хвост массива с уменьшением длины.
Хвост можно обрезать, а можно не учитывать.
for (m = 0; m < size; m++) < // cout size--; > > > Отслеживать
ответ дан 7 дек 2019 в 12:16
5,898 2 2 золотых знака 8 8 серебряных знаков 17 17 бронзовых знаков
Возможен вариант решения через запись уникальных значений в новый массив. Приведен код, когда ВСЕ повторяющиеся значения удаляются. При необходимости можно переработать код для удаления всех повторяющихся кроме первого (проверять все значения изначального массива с финальным массивом, а не с первичным).
void main() < int k = 0; int i = 0; int firstSize = 0; int outSize = 0; int controlNumb = 0; setlocale(LC_ALL, "Russian"); std::cin >> firstSize; int* arrayFirst = new int[firstSize]; int* arrayOut = new int[firstSize]; for (int count = 0; count < firstSize; count++) std::cin >> arrayFirst[count]; for (int count = 0; count < firstSize; count++) arrayOut[count]=0; for (i = 0; i < firstSize; i++) //Для каждого числа в массиве < controlNumb = 1;//Обновляем контрольное значение for (k = 0; k < firstSize; k++) //проверяем каждое значение массива if ((k!=i) & (arrayFirst[i] == arrayFirst[k])) controlNumb = 0; //кроме него самого, и если какое то из них совпало, присваиваем контрольному значению 0 if (controlNumb) //если контрольное значение осталось 1, то прибавляем 1 к условному размеру Конечного массива и записываем в конец уникальное число < outSize++; arrayOut[outSize - 1] = arrayFirst[i]; >> if (!outSize) //если условный размер финального массива остался равен нулю std::cout Отслеживать ответ дан 9 окт 2020 в 20:46 11 2 2 бронзовых знакаДля решения Вашей задачи есть много вариантов.
ИМХО работайте с вектором. Скопируйте Ваши данные в вектор
int *arr = new int[10]; std::vector v; . if (arr)Для Вас я привел 2 варианта решения задачи :
1) С предварительной сортировкой и использование std::unique
2) С сохранением последовательности
#include #include #include #include int main() < // Вариант для последовательности с предворительной сортировкой std::vectorv; std::copy(std::begin(v), std::end(v), std::ostream_iterator); std::cout << std::endl; std::sort(v.begin(), v.end()); auto last = std::unique(v.begin(), v.end()); v.erase(last, v.end()); std::copy(std::begin(v), std::end(v), std::ostream_iterator); std::cout << std::endl; std::cout << std::endl; // Вариант для несоритрованной последовательности std::vectorv2; std::copy(std::begin(v2), std::end(v2), std::ostream_iterator); std::cout ; it != std::end(v2); it = std::next(it)) < for (auto sub_it; sub_it != std::end(v2); sub_it = std::next(sub_it)) < if (*sub_it == *it) < v2.erase(sub_it); --sub_it; >> > std::copy(std::begin(v2), std::end(v2), std::ostream_iterator); std::coutУдалить из массива дубликаты элементов
Написать функцию: int arrayUnique(int array[], int size) , которая будет удалять из массива дубликаты элементов, и в конце работы вернёт новую длину массива.
Предлагаю для решения этой задачи организовать заполнение массива случайными числами. Это сократит время на ввод элементов двумерного массива. Результат работы программы показан ниже:
// new_line_array.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include #include using namespace std; int arrayUnique(int *ar, int); int main(int argc, char* argv[]) < srand(time(NULL)); const int array_size = 20; // размер массива const int interval = 10; // масштаб генерируемых случайных чисел int ar[array_size]; for (int counter1 = 0; counter1 < array_size; counter1++) < ar[counter1] = rand() % interval; // заполняем массив случайными числами cout cout << "\n"; for (int counter1 = 0; counter1 < arrayUnique(ar, array_size)/*вызов функции отбора значений*/; counter1++) < cout cout int arrayUnique(int *ar, int size) // функция, определяющая элементы массива в единственном экземпляре < for (int counter1 = 0; counter1 < size; counter1++) < for (int counter2 = counter1 + 1; counter2 < size ; counter2++) < if ( ar[counter1] == ar[counter2] ) // если найден одинаковый элемент < for (int counter_shift = counter2; counter_shift < size -1; counter_shift++) < // выполнить сдвиг всех остальных элементов массива на -1, начиная со следующего элемента, после найденного дубля ar[counter_shift] = ar[counter_shift + 1]; >size -= 1; // уменьшить размер массива на 1 if (ar[counter1] == ar[counter2]) // если следующий элемент - дубль < counter2--; // выполнить переход на предыдущий элемент >> > > return size; >CppStudio.com
8 2 4 0 6 8 9 3 7 9 7 4 9 9 3 5 1 2 2 9 8 2 4 0 6 9 3 7 5 1Следующие статьи помогут вам в решении данной задачи:
Дата: 11.09.2012
Поделиться:Комментарии
art_h4rd
void arr_uniq(int * mas, int & size) < for (auto i = 0; i < size; i++) < for (auto j = 0; j < size; j++) < if(i != j) < if (mas[i] == mas[j]) < swap(mas[size - 1], mas[j]); size--; >> > > >iYasha
#include #include #include #include using namespace std; void printVector(const vector& a) < cout cout int main() < vectornums; vector end_nums; bool nums_0 = true, nums_1 = true, nums_2 = true, nums_3 = true, nums_4 = true, nums_5 = true; bool nums_6 = true, nums_7 = true, nums_8 = true, nums_9 = true; for (int i = 0; i < 10; i++) < nums.push_back((rand() % 9)/2); >printVector(nums); for (int i = 0; i < nums.size(); i++)< if (nums[i] == 0 && nums_0 == true) < end_nums.push_back(0); nums_0 = false; >if (nums[i] == 1 && nums_1 == true) < end_nums.push_back(1); nums_1 = false; >if (nums[i] == 2 && nums_2 == true) < end_nums.push_back(2); nums_2 = false; >if (nums[i] == 3 && nums_3 == true) < end_nums.push_back(3); nums_3 = false; >if (nums[i] == 4 && nums_4 == true) < end_nums.push_back(4); nums_4 = false; >if (nums[i] == 5 && nums_5 == true) < end_nums.push_back(5); nums_5 = false; >if (nums[i] == 6 && nums_6 == true) < end_nums.push_back(6); nums_6 = false; >if (nums[i] == 7 && nums_7 == true) < end_nums.push_back(7); nums_7 = false; >if (nums[i] == 8 && nums_8 == true) < end_nums.push_back(4); nums_8 = false; >if (nums[i] == 9 && nums_9 == true) < end_nums.push_back(9); nums_9 = false; >> printVector(end_nums); return 0; >Максим Квачёв
/* * Created by IrishSilvan at 06.08.2016 * This program delete repeating elements from random matrix */ #include #include #include using namespace std; //Прототипы функций void random_massive(int, int, int); int random_number(int, int); void print_massive(int); int find_repeat(int*, int); int massive[20]; //Матрица 10x1 int main() < SetConsoleCP(1251); SetConsoleOutputCP(1251); cout > size0; if(size0 cout > n0; cout > n1; if(n0 == n1) < cout random_massive(n0,n1, size0); //Вызов функции генерации массива по заданным параметрам cout > n0; return 0; > //Функция - Генератор массива со случайными числами void random_massive(int a, int b, int size) < for(int i = 0; i < size; i++) < //Перебираем элементы в строке по индексам до 10го massive[i] = random_number(a, b); //Запись в массив случайного числа >> //Функция - Генератор случайных чисел int random_number(int N0, int N1) < int spray = N1 - N0; //Вычисление диапазона допустимых чисел int number = (N0 + (rand() % spray)); //Складываем все вместе и получаем случайное число в заданном диапазоне return number; //Возвращаем случайное число с дробной частью >//Функция - Вывод массива на экран в удобной для чтения форме void print_massive(int size) < for(int i = 0; i < size; i++) < //Перебираем элементы в строке по индексам до 10го cout > //Функция - Отсеивание повторяющихся элементов массива int find_repeat(int *matrix, int size) < bool var; int temp_massive[size]; int index = 0; for(int i = 0; i < size; i++) < int temp_el = matrix[i]; var = true; for(int s = 0; (s < size) && var; s++) < if(temp_el == temp_massive[s]) var = false; else if(s == size-1) < temp_massive[index] = matrix[i]; index++; >> > for(int i = 0; i < index; i++) < massive[i] = temp_massive[i]; >return index; >Arthur
#include #include #include #include using namespace std; const int SZ = 20; int main() < int mas[SZ]; int i = 0; srand(time(0)); for(int x = 0; x(cout," ")); cout(cout," ")); return 0; >Arthur
#include #include #include #include using namespace std; const int SZ = 20; int main() < int mas[SZ]; srand(time(0)); for(int x = 0; xcout
Arthur
15.12.2015 Функция удаляет все повторяющиеся элементы
#include #include #include using namespace std; const int SZ = 20; int arrayUnique(int* , const int ); int main() < int mass[SZ]; srand(time(0)); for(int x = 0; xcout int arrayUnique(int* mass, const int SZ) < int x = 0; int newmass[SZ]; int n = 0; for(x = 0; xfor(int i = 0; iОставить комментарий
Вы должны войти, чтобы оставить комментарий.
�� Rust Journey: Хотите освоить язык программирования, который завоевывает мир?
�� Илон Маск, один из ведущих инноваторов нашего времени, утверждает, что за Rust будущее. А когда последний раз он ошибался в своих прогнозах? ��
✨ Не упустите свой шанс быть в авангарде IT-революции. Подписывайтесь на канал Rust Journey и начните свой путь в захватывающий мир Rust сегодня!
Удалить все повторяющиеся элементы из массива?
Всем привет. Мне 16, 4 месяца изучаю С++ и наткнулся на такую казалось бы тривиальную задачку. Решил я ее за сутки, кое-как) Задача: Дан целочисленный массив. Необходимо просто удалить все повторяющиеся элементы. НО С УСЛОВИЕМ! НЕЛЬЗЯ использовать решения из коробки языка! Все это время я занимался процедурным программированием ну и 2 недельки ООП изучаю. В общем прошу оценить и сказать на сколько все плохо) Если не трудно, предложите свои варианты решений.
Заранее всем спасибо и добра вам!Вот рез. работы:
- Вопрос задан более трёх лет назад
- 4205 просмотров
3 комментария
Средний 3 комментария
[C++]Удаление повторяющихся элементов массива
Пожалуйста, умоляю, помогите. Нужно решить несколько задач по С++:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
38 ответов
22 января 2007 года
17 / / 12.01.2007
Пожалуйста, умоляю, помогите. Нужно решить несколько задач по С++:
1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
Если хочеш написать программу - с алгоритмом помогу, а саму программу увы. Меня уже тошнит от программ этого типа. Так ты хочеш написать программу, или тебе нада готовую?
22 января 2007 года
2.2K / / 04.02.2006
Funny15, читай пожалуйста правила форума Студентам и не нарушай. [COLOR=red]Одна тема - один вопрос, темам даем смысловое название+указываем язык программирования в названии темы.[/COLOR]
22 января 2007 года
721 / / 31.12.2002
вот такая реализация) не самая быстрая, но зато наглядная и работающая)))
алгоритм: создаётся дополнительный массив, потом проверяется исходный массив, если текущее число присутствует в дополнительном массиве, то оно удаляется (сдвигом на 1 начиная с текущей позиции) и размерность уменьшается на 1, если не найдено, то в дополнительный массив добавляется текущее значение.
// присутствует ли число 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;
>
использование например такое:
22 января 2007 года
661 / / 19.09.2006
=)
Реализация через битовую маску. ИМХО искать по массиву очень долго.
#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 <
unsigned char get_bit(unsigned char * in, char n)
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
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, символ проходил проверку и значит выводился, если нет то выводим его.
22 января 2007 года
1.0K / / 08.01.2007
Массив - это вектор . Забыли про STL ? 🙂
#include "stdafx.h"
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
srand(time(0));
cout int size;
cin>>size;
vector vec1;
for(int i = 0;i
// вектор заполнен случ. числами
for(vector::iterator it = vec1.begin();
it != vec1.end();++it)
cout for(int j = 0;j
>
>
cout for(vector::iterator it = vec1.begin();
it != vec1.end();++it)// выводим на экран
cout cout return 0;
>
22 января 2007 года
4.8K / / 20.01.2000
Всем двойки! 🙂
Квадратичный алгоритм для такой простой задачки. Кто же так делает?!
Подсказка: можно за N*log(N)
23 января 2007 года
2.6K / / 04.11.2006
for(int i =0; i < Vector.size(); ++i)
Set.insert(Vector); //попытка скопировать элементы вектора в
//множество. Еслт такой элемент уже там есть -
//то, так как элементы множества уникальны,
//элемент не будет скопирован.
>
sort(Vector.begin() , Vector.end()); //сорт. со сложностью O(N*Log(N))
unique(Vector.begin() , Vector.end());//удаляются элементы, равные
предыдущему. O(N)
23 января 2007 года
661 / / 19.09.2006
to Green
Где ты здесь усмотрел квадратичный алгоритм ? =)
for (int i = 0 ; i < strlen(str_temp_in);i++)
Практически линейная сложность.
23 января 2007 года
1.0K / / 08.01.2007
2Zorkus : Конечно set ! Отличное решение !
Как я забыл ? 🙂
23 января 2007 года
80 / / 22.08.2006
Задача, очевидно, для студентов начальных курсов, так что 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;
23 января 2007 года
2.6K / / 04.11.2006
Задача, очевидно, для студентов начальных курсов, так что stl здесь не уместна
Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.
ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.
23 января 2007 года
80 / / 22.08.2006
Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.
ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.
Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.
23 января 2007 года
2.6K / / 04.11.2006
Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.
Хорошо, оставим пока в покое начальные курсы. Но на многих специальностях, связанных с программированием, предмет "программирование", как таковое, идет два года. И когда тогда узнавать язык? В идеале должно быть четкое разделение - "языки программирования" и "теория алгортмов".
Насчет того, что STL скрывает реализацию простейших алгоритмов - так эти простейшие алгоритмы являются некими кирпичиками, из которых могут строиться более сложные алгоритмы. Возьмем пример - алгоритм Прима использует в стандартной реализации 2 множества. Но, думаю, человеку проще понять суть алгоритма, когда он оперирует готовым множеством (естественно, понимая принцип его внутренней организации), чем когда он пишет реализацию множества самостоятельно. Не говоря уже об экономии времени сил и размера кода, так как не надо распылятся на реализацию мелких подзадач.
И потом - всегда можно посмотреть, как реализован тот или иной алгоритм в исходниках STL, точно зная, что эта реализация безошибочна и быстра.
23 января 2007 года
1.0K / / 08.01.2007
А в некоторых ( не хочу бросать тень на Alma Mater ) вообще выкинули
STL за ненадобностью ! Круто правда ! 🙁 И даже не упоминать стараются , обьясняя это как раз тем что . скрывает простейшие алгоритмы . И когда тебе кажется , что ты уже неплохо знаешь
язык , открываешь какую-нибудь современную книгу по С++. )
Я например,открыл Саттера "Решение сложных задач на С++" . Так вот после нескольких страниц у меня и возник вопрос - какой же язык я учил в институте ?:) Учили одно , а тут . красота !
23 января 2007 года
2.6K / / 04.11.2006
#include
#include
#include
#include
#include
#include
using namespace std;
~108.5 сек. засеченное время.
#include
#include
#include
#include
#include
#include
using namespace std;
116.4 cек. засеченное время.
Буду дальше экспериментировать:)
23 января 2007 года
80 / / 22.08.2006
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.
Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
23 января 2007 года
2.6K / / 04.11.2006
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.
Да, конечно, согласен 100%.
Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
Причем тут юмор, и почему не оценит? у меня была на экзамене такая задача, где нужно было парсить строку в поисках чего-то, не вспомню щас условие. И я за каких-то 10 минут:) доказал преподу, что мое решение заслуживает 5, так как в том виде, в каком я его представил, оно скомпилится и будет работать, и выдаст правильный ответ.
Так что, автор, не бойся спорить с преподом, если он не принимает решение только потому, что он сам решал иначе!:)
23 января 2007 года
80 / / 22.08.2006
Zorkus:
~108.5 сек. засеченное время.
116.4 cек. засеченное время.
Буду дальше экспериментировать:)
#include
#include
#include
#include
#include
#include
#include
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 T = Mas[Lo];
Mas[Lo] = Mas[Hi];
Mas[Hi] = T;
Lo++;
Hi--;
>
>
while ( Lo 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 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
кол-во элементов исходного массива: 10000000
При разбросе значений элементов от 0 до 10:
ROLpogo: ~3360 ms
Zorkus1: ~5906 ms
Zorkus2: ~4719 ms
При разбросе значений элементов от 0 до 10000000 (при меньшем кол-ве одинаковых элементов):
ROLpogo: ~4375 ms
Zorkus1: ~28125 ms
Zorkus2: ~5031 ms
24 января 2007 года
2.6K / / 04.11.2006
Для определенности: использовал 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 он проигрывает по быстродействию очень немного.
24 января 2007 года
661 / / 19.09.2006
ребята, где вы такие цифры достали?
на моей рабочей лошадке 1.7 Ghz, 256 RAM на ASPLinux 9, KDE 2.1
программка, вообщем то делающая тоже самое, ну с разумными ограничениями - набором символов в 1024 символа, делает это за 0,1125 сек.
Да, и расширение набора символов не дает значительного увелечения времени работы.
// итого можно закодировать 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 <
unsigned char get_bit(unsigned char * in,unsigned int n)
int bit_ = 0;
int byte_ = 0;
byte_ = n/8;
bit_ = n%8;
bool finish_him (unsigned char * in)
bool ret = false;
unsigned char finish_byte = 0xFF;
for (unsigned char l = 0; 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 как собаке пятая нога =).
ИМХО. мое скромное мнение.
24 января 2007 года
4.8K / / 20.01.2000
Приведенный тобой алгоритм рационален лишь для численных значений, причем небольшого размера. Например для dword размер словаря (алфавита) составит 512Мб, при таких больших размерах время выборки становится логарифмическим, т.е. расширение набора дает снижение скорости.
Т.о. для массива int array[2] алгоритм становится нерациональным.
Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
Т.о. метод применим лишь в очень узком кругу задач, но имеет право на жизнь.
Алгоритм же с сортировкой получается более универсальным, при этом не сильно проигрывает по скорости на специфичных данных (для которых твой алгоритм предпочтительнее) и сильно выигрывает в общем случае по скорости, объему под данные и применимости (универсальности).
Подмывает немного поругать твой код, но не буду. 🙂
Скажи только, для чего функция finish_him (это тоже придирка к коду, т.к. он не очевиден, не самодокументирован).
И ещё вопрос, что ты подразумеваешь под "азами программирования" ?
24 января 2007 года
661 / / 19.09.2006
Ну да, так и есть, для большего набора символов алгоритм не рационален и даже вреден =).
Если строка введенных пользователем сиволов представляется как массив char`ов, то вполне ничего. Вообщем то про это было оговорено.
Хотя конечно фраза
Да, и расширение набора символов не дает значительного увелечения времени работы.
здесь неуместна.
Функция finish_him? Да, задумывалась как проверка того, что все символы из набора уже перенесены в выходной массив.
Можно и код поругать, я не обидчивый. даже, наверное, и полезно будет =)
Азы программирования? Алгоритм+данные=программа. Базовые курсы по специальности программирование.
24 января 2007 года
2.6K / / 04.11.2006
Я не ставил задачу написать код, который будет работать максимально быстро на данной конкретной задаче. Я старался показать, что шаблонная реализация (в строго техническом смысле) может быть ненамного уступающей по скорости эксклюзивной, но неимоверно проще в реализации.
Для тех, кто хочет привязать решение к типу и добиться максимальной производительности - думаю, реализацию ROLpogo можно ускорить, в частности, написав код обмена переменных асмовой вставкой (так как асм не знаю, проверить не могу:))
2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?
Потом, алгоритм передачи в множество. Он зависит сильно от разброса, как видно из примеров, в отличие от сортировки, менее универсален.
P.S. И еще - большая просьба к авторам кодов указывать ось и IDE/компилер. А то у меня проги ROLpogo и Одиссея не собираются без некоторых поправок:)
24 января 2007 года
4.8K / / 20.01.2000
2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?
Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). 😀
24 января 2007 года
2.6K / / 04.11.2006
Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). 😀
24 января 2007 года
365 / / 19.12.2005
Кстати использование hash_set вместо set должно дать (в общем то оно и даёт) вполне ощутимый выигрыш. Ещё немного можно отыграть у handmade кода, если использовать STLPort.
P.S.: Тесты проводились с отключённой оптимизацией?
24 января 2007 года
1.0K / / 08.01.2007
Ага , а еще +5% cкорости если без цикла
hash_set.insert(Vec.begin(),Vec.end());:)
Проверял.
24 января 2007 года
2.6K / / 04.11.2006
Кстати использование hash_set вместо set должно дать (в общем то оно и даёт) вполне ощутимый выигрыш. Ещё немного можно отыграть у handmade кода, если использовать STLPort.
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 в полтора раза.