Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: 6458
Последний выпуск: 19.06.2015

[C++]Удаление повторяющихся элементов массива

24K
22 января 2007 года
Funny15
1 / / 22.01.2007
Пожалуйста, умоляю, помогите!!! Нужно решить несколько задач по С++:

1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:
20K
22 января 2007 года
lnkgyv3
17 / / 12.01.2007
Цитата: Funny15
Пожалуйста, умоляю, помогите!!! Нужно решить несколько задач по С++:

1. Удалить все повторяющиеся элементы массива, т.е. получить массив, состоящий из различных элементов. (Массив одномерный)
:confused:



Если хочеш написать программу - с алгоритмом помогу, а саму программу увы. Меня уже тошнит от программ этого типа. Так ты хочеш написать программу, или тебе нада готовую?

232
22 января 2007 года
Оlga
2.2K / / 04.02.2006
Funny15, читай пожалуйста правила форума Студентам и не нарушай. [COLOR=red]Одна тема - один вопрос, темам даем смысловое название+указываем язык программирования в названии темы.[/COLOR]
260
22 января 2007 года
MrXaK
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;
}


использование например такое:
Код:
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;
}
351
22 января 2007 года
Odissey_
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<<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, символ проходил проверку и значит выводился, если нет то выводим его.
309
22 января 2007 года
m_Valery
1.0K / / 08.01.2007
Массив - это вектор . Забыли про 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;
}
3
22 января 2007 года
Green
4.8K / / 20.01.2000
Всем двойки! :)
Квадратичный алгоритм для такой простой задачки. Кто же так делает?!
Подсказка: можно за N*log(N)
53
23 января 2007 года
Zorkus
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)
351
23 января 2007 года
Odissey_
661 / / 19.09.2006
to Green
Где ты здесь усмотрел квадратичный алгоритм ? =)
for (int i = 0 ; i < strlen(str_temp_in);i++)
Практически линейная сложность.
309
23 января 2007 года
m_Valery
1.0K / / 08.01.2007
2Zorkus : Конечно set ! Отличное решение !
Как я забыл ? :)
9.5K
23 января 2007 года
ROLpogo
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;
53
23 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: ROLpogo
Задача, очевидно, для студентов начальных курсов, так что stl здесь не уместна


Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.

ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.

9.5K
23 января 2007 года
ROLpogo
80 / / 22.08.2006
Цитата: Zorkus
Гм. А я кто по-твоему?:)
Почему неуместна? При правильном использовании она очень улучшает код. Я не вижу в том примере кода, что привел, абсолютно ничего сложного, но могу, если нужно, написать комменты.

ROLpogo, без всяких обид, но в твоем коде я вижу подход большинства преподов ВУЗов. Дают примеры реализаций образца какого-то бородатого года, вместо того, чтоб пропагандировать современные решения. И как следствие - многие студенты, изучающие программирование, понятия не имеют, какой он - настоящий современный С++.



Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.

53
23 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: ROLpogo
Неуместна, потому что на начальных курсах в ВУЗе студентам не преподают STL. И делают правильно, т.к. STL скрывает реализацию простейших алгоритмов.


Хорошо, оставим пока в покое начальные курсы. Но на многих специальностях, связанных с программированием, предмет "программирование", как таковое, идет два года. И когда тогда узнавать язык? В идеале должно быть четкое разделение - "языки программирования" и "теория алгортмов".
Насчет того, что STL скрывает реализацию простейших алгоритмов - так эти простейшие алгоритмы являются некими кирпичиками, из которых могут строиться более сложные алгоритмы. Возьмем пример - алгоритм Прима использует в стандартной реализации 2 множества. Но, думаю, человеку проще понять суть алгоритма, когда он оперирует готовым множеством (естественно, понимая принцип его внутренней организации), чем когда он пишет реализацию множества самостоятельно. Не говоря уже об экономии времени сил и размера кода, так как не надо распылятся на реализацию мелких подзадач.
И потом - всегда можно посмотреть, как реализован тот или иной алгоритм в исходниках STL, точно зная, что эта реализация безошибочна и быстра.

309
23 января 2007 года
m_Valery
1.0K / / 08.01.2007
А в некоторых ( не хочу бросать тень на Alma Mater ) вообще выкинули
STL за ненадобностью ! Круто правда ! :( И даже не упоминать стараются , обьясняя это как раз тем что ... скрывает простейшие алгоритмы . И когда тебе кажется , что ты уже неплохо знаешь
язык , открываешь какую-нибудь современную книгу по С++...:)
Я например,открыл Саттера "Решение сложных задач на С++" ... Так вот после нескольких страниц у меня и возник вопрос - какой же язык я учил в институте ?:) Учили одно , а тут ... красота !
53
23 января 2007 года
Zorkus
2.6K / / 04.11.2006
Код:
#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;
}

~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;
}

116.4 cек. засеченное время.

Буду дальше экспериментировать:)
9.5K
23 января 2007 года
ROLpogo
80 / / 22.08.2006
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.

Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.
53
23 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: ROLpogo
Если Вузовский курс программирования не может охватить все аспекты, то приходится делать выбор из наиболее важных. А наиболее важными являются базовые основы языка и алгоритмизация. Все остальное либо преподаётся на спецкурсах, либо изучачется самостоятельно.


Да, конечно, согласен 100%.

Цитата: ROLpogo

Спорить о том, пользоваться ли STL для реализации данной задачи, бесполезно, т.к. препод юмора не оценит.


Причем тут юмор, и почему не оценит? у меня была на экзамене такая задача, где нужно было парсить строку в поисках чего-то, не вспомню щас условие. И я за каких-то 10 минут:) доказал преподу, что мое решение заслуживает 5, так как в том виде, в каком я его представил, оно скомпилится и будет работать, и выдаст правильный ответ.
Так что, автор, не бойся спорить с преподом, если он не принимает решение только потому, что он сам решал иначе!:)

9.5K
23 января 2007 года
ROLpogo
80 / / 22.08.2006
Цитата:

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();
}


кол-во элементов исходного массива: 10000000
При разбросе значений элементов от 0 до 10:
ROLpogo: ~3360 ms
Zorkus1: ~5906 ms
Zorkus2: ~4719 ms

При разбросе значений элементов от 0 до 10000000 (при меньшем кол-ве одинаковых элементов):
ROLpogo: ~4375 ms
Zorkus1: ~28125 ms
Zorkus2: ~5031 ms
53
24 января 2007 года
Zorkus
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 он проигрывает по быстродействию очень немного.
351
24 января 2007 года
Odissey_
661 / / 19.09.2006
ребята, где вы такие цифры достали?
на моей рабочей лошадке 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;
}


Вообщем то согласен что изучение STL, один из важных этапов в обучении современного программиста. Только без знания самых азов программирования ему этот STL как собаке пятая нога =).
ИМХО. мое скромное мнение...
3
24 января 2007 года
Green
4.8K / / 20.01.2000
Приведенный тобой алгоритм рационален лишь для численных значений, причем небольшого размера. Например для dword размер словаря (алфавита) составит 512Мб, при таких больших размерах время выборки становится логарифмическим, т.е. расширение набора дает снижение скорости.
Т.о. для массива int array[2] алгоритм становится нерациональным.

Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.
Т.о. метод применим лишь в очень узком кругу задач, но имеет право на жизнь.

Алгоритм же с сортировкой получается более универсальным, при этом не сильно проигрывает по скорости на специфичных данных (для которых твой алгоритм предпочтительнее) и сильно выигрывает в общем случае по скорости, объему под данные и применимости (универсальности).

Подмывает немного поругать твой код, но не буду... :)
Скажи только, для чего функция finish_him (это тоже придирка к коду, т.к. он не очевиден, не самодокументирован).

И ещё вопрос, что ты подразумеваешь под "азами программирования" ?
351
24 января 2007 года
Odissey_
661 / / 19.09.2006
Ну да, так и есть, для большего набора символов алгоритм не рационален и даже вреден =).
Если строка введенных пользователем сиволов представляется как массив char`ов, то вполне ничего. Вообщем то про это было оговорено.
Хотя конечно фраза
Цитата:
Да, и расширение набора символов не дает значительного увелечения времени работы.


здесь неуместна.
Функция finish_him? Да, задумывалась как проверка того, что все символы из набора уже перенесены в выходной массив.
Можно и код поругать, я не обидчивый... даже, наверное, и полезно будет =)
Азы программирования? Алгоритм+данные=программа. Базовые курсы по специальности программирование.

53
24 января 2007 года
Zorkus
2.6K / / 04.11.2006
Я не ставил задачу написать код, который будет работать максимально быстро на данной конкретной задаче. Я старался показать, что шаблонная реализация (в строго техническом смысле) может быть ненамного уступающей по скорости эксклюзивной, но неимоверно проще в реализации.
Для тех, кто хочет привязать решение к типу и добиться максимальной производительности - думаю, реализацию ROLpogo можно ускорить, в частности, написав код обмена переменных асмовой вставкой (так как асм не знаю, проверить не могу:))

2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?

Потом, алгоритм передачи в множество. Он зависит сильно от разброса, как видно из примеров, в отличие от сортировки, менее универсален.

P.S. И еще - большая просьба к авторам кодов указывать ось и IDE/компилер. А то у меня проги ROLpogo и Одиссея не собираются без некоторых поправок:)
3
24 января 2007 года
Green
4.8K / / 20.01.2000
Цитата: Zorkus

2 Green - ты говорил, что задача решается в общем случае (без привязки к типам и вообще какой-бы то ни было) алгоритмом O(N*Log(N)). Алгоритм sort имеет такую сложность (не берем предельный случай квадратичности), алгоритм unique - линейную. Значит, алгоритм в целом имеет указанную тобой сложность. Ты этот имел в виду, или что-то другое (если другое - не говори, что именно:))?


Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). :D

53
24 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: Green
Я имел в виду именно сортировку (в общем случае любую, кроме пузырька). :D


+1 :D

1.8K
24 января 2007 года
k3Eahn
365 / / 19.12.2005
Кстати использование hash_set вместо set должно дать (в общем то оно и даёт) вполне ощутимый выигрыш. Ещё немного можно отыграть у handmade кода, если использовать STLPort.
P.S.: Тесты проводились с отключённой оптимизацией?
309
24 января 2007 года
m_Valery
1.0K / / 08.01.2007
Ага , а еще +5% cкорости если без цикла
hash_set.insert(Vec.begin(),Vec.end());:)
Проверял.
53
24 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: k3Eahn
Кстати использование 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 в полтора раза.

1.8K
24 января 2007 года
k3Eahn
365 / / 19.12.2005
Цитата: Zorkus

Примечание: для разброса 10 работает медленней простого set в полтора раза.


А ты попробуй вариант m_Valery. Для разброса от 1 до 10 у меня время сократилось в 1.7 раза по сравнению с hash_set::insert.

53
24 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: 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, получается. Из них и выбирать, если больше мы тут ничего не придумаем, как улучшить:)

3
25 января 2007 года
Green
4.8K / / 20.01.2000
Цитата: 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;
}

Ну и маленькое предложение по оптимизации по памяти.
Т.к. массив str_temp_out заполняется не быстрее, чем производится выборка из массива str_temp_in, то это может быть одним массивом.
53
25 января 2007 года
Zorkus
2.6K / / 04.11.2006
Ну тогда тоже сделаю пару замечаний:)
1)
Цитата: Green

Если же мы попытаемся обработать массив каких-либо объектов (а в условии не говорится о каком массиве идет речь, т.е. ставится обобщенная задача), то задача вообще становится титанической, т.к. нам придется формировать некий ключ, размер которого будет зависеть от разряженности массива.


Если мы будет обрабатывать массив объектов, то надо будет уже юзать stable_sort. А вот она выполняется процентов на 70 медленней sort() на разбросе 10 000 000 для данных тестов.

2) Скорей вопрос. Если использовать ассемблерную вставку для обмена переменных в сортировке, написанной лапами, то можно ли код существенно ускорить (насколько)?

3
25 января 2007 года
Green
4.8K / / 20.01.2000
Цитата: Zorkus

2) Скорей вопрос. Если использовать ассемблерную вставку для обмена переменных в сортировке, написанной лапами, то можно ли код существенно ускорить (насколько)?


Я думаю, что существенно от этого ничего не измениться.
Есть другое (очевидное) замечание, что в случае объектов, рациональным будет не перемещать объекты в памяти, а перемещать ссылки (указатели, индексы и т.п.) на них.

53
25 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: Green

Есть другое (очевидное) замечание, что в случае объектов, рациональным будет не перемещать объекты в памяти, а перемещать ссылки (указатели, индексы и т.п.) на них.


Конечно, будет лучше с точки зрения оптимальности использовать list<>,
там и sort(), и unique() определены. И с точки зрения транзакционной безопасности намного надежнее вектора будет. Но просто тема началась с термина массив:)

3
25 января 2007 года
Green
4.8K / / 20.01.2000
Да можно и массив, массив указателей или массив индексов.
351
25 января 2007 года
Odissey_
661 / / 19.09.2006
toGreen
Отдельное спасибо за
Цитата:

if (j == BUKVA_BiTE_LEN)
break;


Почему-то такой вариант в голову не пришел =(.
Насчет массива тоже верно, просто не было задачи минимизации памяти.

Остальное, помоему, дело вкуса. Хорошего вкуса программировать у меня пока нет, команда разработчиков у нас небольшая, да и таких задач как стандарт кода перед нами не ставилось. Поэтому всё так как есть.
Все замечания дельные, спасибо.

3
25 января 2007 года
Green
4.8K / / 20.01.2000
Цитата: Odissey_
toGreen
Отдельное спасибо за


Там только ещё на 8 надо умножить: BUKVA_BiTE_LEN*8

Да, кстати, я бы отказался от применения битового массива.
Увеличение расхода памяти в 8 раз приведет к увеличению производительности на порядки, а как мы уже обсудили, вариант применим лишь к массивам значений небольшого диапазона, поэтому нет смысла экономить на таком небольшом объеме памяти (например для char это будет 256 байт против 32 байт).

99K
13 июня
dcc0
1 / / 13.06.2018
А если сделать еще одну копию массива и написать так:
Код:
/******************************************************************************

                            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]);;

}

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог