Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Astrologer от Ноябрь 02, 2010, 21:51

Название: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 02, 2010, 21:51

Собственно сабж. Есть какие нибудь мысли?

http://www.careercup.com/question?id=4794712
Оригинал.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Igors от Ноябрь 02, 2010, 22:14

Давеча обсуждали http://www.prog.org.ru/topic_14850_0.html (http://www.prog.org.ru/topic_14850_0.html)
Вообще, вопрос удивляет :)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 02, 2010, 22:29

Опять STL) Но топик просто удаление элемента с заданным условием. И честно говоря хотелось бы "пощупать" алгоритм, а не пользоваться STL. 8)

Я например не могу понять как это сделать не сортируя массив? Сортировка за O(n) не бывает?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Sancho_s_rancho от Ноябрь 02, 2010, 22:31

Цитата: Astrologer от Ноябрь 02, 2010, 22:29

Опять STL) Но топик просто удаление элемента с заданным условием. И честно говоря хотелось бы "пощупать" алгоритм, а не пользоваться STL. 8)

Вам запретили смотреть код реализации STL?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 02, 2010, 22:37

А вы напишите код без STL, я вам буду благодарен. :)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Igors от Ноябрь 02, 2010, 22:51

Цитата: Astrologer от Ноябрь 02, 2010, 22:37

А вы напишите код без STL, я вам буду благодарен. :)

Та я ж и написал в той же теме (пост #8) :)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 03, 2010, 08:48

Извиняюсь, уточню задачу. Мы знаем что элементы в массиве варьируются от 1 до N.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 03, 2010, 09:08

Алгоритм с той же страницы вопроса.

Код

C++ (Qt)
vector<int> a;
  a.push_back(1);
  a.push_back(5);
  a.push_back(3);
  a.push_back(8);
  a.push_back(4);
  a.push_back(3);
  a.push_back(8);
  a.push_back(5);
  a.push_back(2);
  int n = a.size();
  for (int i=0;i<n;++i){
                  if(a[i]==i+1 || a[i]>n)
                          continue; 			//i.e. either inplace or duplicate
                  else{
                          while(true){
                                  if(a[i]>n) 		//i.e. a duplicate that is already detected
                                          break;
                                  if (a[a[i]-1]==a[i])
                                  {
                                          a[i]+=n;	//i.e. a duplicate is detected
                                          break;
                                  }
                                  swap(&a[i],&a[a[i]-1]);
                          }
                  }
          }
  vector<int> out;
  for (int i=0;i<n;++i){
                  if(a[i]<n)
                          out.push_back(a[i]);
          }

Время О(3n)
Память О(1)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Astrologer от Ноябрь 03, 2010, 09:16

Вот мне интересно зачем такие вопросы задавать. Чтобы 90% кандидатов не прошли изначально? Или может быть кто то за 5 минут может прийти к подобному решению?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 11:59

Вот простой алгоритм:
сложность O(N);
доп память O(1);

Код

C
int removeDuplicateAndSort_ON_O1 (int* arr, int count) {
  int n, i;
 
  for(i=0; i<count; ++i) {                // check error values
    if(arr[i] < 1)     {return -1;}
    if(arr[i] > count) {return -1;}
  }  
 
  for(i=0; i<count;) {
    n = arr[i]-1;
    if(n == -1)         {++i; continue;}  // "Removed Value"
    if(n ==  i)         {++i; continue;}  // true place
    if(n ==  arr[n]-1)  {
      arr[i] = 0;                         // mark as "Removed Value"
      ++i; 
    } else {
      arr[i] = arr[n];                    // swap
      arr[n] = n+1;
    }
  }
 
  n = 0;           
  for(i=0; i<count; ++i) {                // remove "Removed Value"
    if(!arr[i]) {continue;}
    arr[n] = arr[i];
    ++n;
  }   
  return n;
}

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Igors от Ноябрь 03, 2010, 13:09

Ага, оказывается надо удалять повторяющиеся элементы. А еще не указано можно ли менять порядок следованию (если можно то получается намного проще). Ладно, полагаем нельзя. Тогда я бы делал так

Код

C++ (Qt)
void MarkDupAsNeg( int * arr, int n )
{
 for (int i = 0; i < n - 1; ++i) {
  int match = arr[i];
 
  if (match < 0)    
   continue;
 
  for (int j = i + 1; j < n; ++j) 
   if (arr[j] == match) 
    arr[i] = arr[j] = -1;
 } 
}
 
int RemoveNeg( int * arr, int n )
{
 int i, place = 0;
 for (i = 0; i < n; ++i) {
  if (arr[i] < 0) continue;
  if (i != place)
   arr[place] = arr[i];
  ++place;
 }
 return place;
}

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

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 13:54

Цитата: Igors от Ноябрь 03, 2010, 13:09

Код

C++ (Qt)
 ...

Мой алгоритм не оптимальный(вернее не оптимизированный), я специально писал так, чтоб каждый шаг был понятен.

Задача ставилась сложность/время O(N) и память O(1) и запрет на изменение порядка элементов ограничения не накладывалось.
А в приведенном вами алгоритме сложность O(N^2) - всегда, и это оценка для лучшего случая.
Если у вас N == 100 или 1000, то возможно приемлимо использовать алгоритм O(N^2). Но если N == 1000000 (что не так много), то вы не дождетесь пока O(N^2) досчитает :)

- Если бы запрещалось менять порядок элементов, то задача решается сложность O(N) и память O(N)
- Если значение элемента любое, но ограничено типом (например int), то задача тоже решается сложность O(N) и память O(N), но для массивов малого размера оптимально применять сложность O(N^2) и память O(1) - например ваш.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Igors от Ноябрь 03, 2010, 14:41

Давайте прильнем к первоисточнику

Цитировать

Write a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.

Подходит ли массив [5, 1, 5, 10] (4 элемента, диапазон 1..10) под условие задачи? Да, подходит. Sprectre, у Вас все прекрасно (линейная скорость) но только если "число элементов не меньше максимального значения" - не вижу такого условия.

Понятно что квадратичный перебор (строго говоря N ^ 2 / 2) никогда не хорош, но что делать практически? Ходов 2 - выделить память под указатели или прикинуть размер и смириться с тупым перебором (который имеет громадное достоинство что писать его несколько минут). А умирать в сложной/запутанной логике непрактично и ненужно.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 15:55

Цитата: Igors от Ноябрь 03, 2010, 14:41

Давайте прильнем к первоисточнику

Цитировать

Write a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.

Я вообще-то думал что размер массива N. Иначе условие задачи не корректно.
- если Size > N, то алгоритм имеет сложность O(Size)! Никогда O(N)!
- если Size <= N , то алгоритм имеет сложность O(Size)! Можно сказать в условии O(N)!

Поскольку про Size ничего в условии не сказано, а при Size > N алгоритм со сложеностью O(N) невозможно построить, и считая условие задачи корректным выводим что Size == N

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 16:25

А вот, новое условие.

Создать программу для удаления повторяющихся элементов из массива, изменение порядка элементов допускается.
Размер массива N. Элементы массива - целые числа типа int.
Алгоритм должен быть:
- сложностью O(N)
- доп. память O(1)!

P.S. Для тех кто не в курсе: доп. память O(1) не означает 1 ячейка памяти, O(1) - означает, что кол-во доп. памяти не зависит от N - т.е является константой. Но константа не INT_MAX :)

Это возможно!

Если никто не справится, то опишу алгоритм :)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: m_ax от Ноябрь 03, 2010, 17:16

Цитировать

P.S. Для тех кто не в курсе: доп. память O(1) не означает 1 ячейка памяти, O(1) - означает, что кол-во доп. памяти не зависит от N - т.е является константой. Но константа не INT_MAX

А как оценивается сложность O(N) - по числу обращений к элементам массива или по числу сравнений?
Или как?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 17:45

Цитата: m_ax от Ноябрь 03, 2010, 17:16

Цитировать

А как оценивается сложность O(N) - по числу обращений к элементам массива или по числу сравнений?
Или как?

O(N) можно определить как:
кол-во выполняемых элементарных операций(например процессорных инструкций) алгоритмом линейно зависит от N.

A линейно зависит от N значит:
Пусть F(X(N)) - точное кол-во элементарных операций выполняемое алгоритмом на конкретных данных X(N).
Тогда для любого допустимого X и N выполняется : Cmin * N <= F(X(N)) <= Cmax * N, где Cmin и Cmax константы.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 03, 2010, 20:31

Вот, скучно було решил написать алгоритм :)
сложность O(N) доп. память O(1);

Код

C++ (Qt)
extern void numsort   (int* arr, unsigned int size);
extern int  numunique (int* arr, unsigned int size);
extern void numsort   (unsigned int* arr, unsigned int size);
extern int  numunique (unsigned int* arr, unsigned int size);

Код

C++ (Qt)
unsigned char getbyte(int val, unsigned int digitpos) {
  if(digitpos == sizeof(int)) {
    return val>=0?1:0;
  }
 
  if(digitpos > 0) {
    val = val >> 8*digitpos; 
  }
  val = val & 0xFF;
  return val;
}
 
void swap(unsigned int* val1, unsigned int* val2) {
  unsigned int val = *val1;
  *val1 = *val2;
  *val2 = val;
}
 
void digitsort(unsigned int* arr, unsigned int size, unsigned int digitpos) {
   unsigned int spos[256+1];
   unsigned int npos[256];
 
   memset(&spos, 0, (256+1)*sizeof(int));
   for(int i=0; i<size; ++i) {
     spos[getbyte(arr[i], digitpos)+1]++;
   }
   for(int i=0; i<256; ++i) {
     spos[i+1] += spos[i];
   }
   memcpy(&npos, &spos, 256*sizeof(int));
 
   unsigned int val1;
   unsigned int val2;
   for(i=0; i<size;) {
     val1 = getbyte(arr[i], digitpos);
     if(i >= spos[val1] && i < npos[val1]) {
       i = npos[val1]; 
       continue;
     }
     if(i == npos[val1]) {
       npos[val1]++;
       ++i; 
       continue;
     }
     val2 = getbyte(arr[npos[val1]], digitpos);
     while(val2 == val1) {
       npos[val1]++;
       val2 = getbyte(arr[npos[val1]], digitpos);
     }
     swap(&arr[i], &arr[npos[val1]]);
   }
 
   if(!digitpos) {return;} 
   digitpos--;
   for(int i=0; i<256; ++i) {
     size = spos[i+1]-spos[i];
     if(!size) {continue;}
     digitsort(arr+spos[i], size, digitpos);
   }
}
 
void numsort(unsigned int* arr, unsigned int size) {
  if(!size) {return;}
  digitsort(arr, size, sizeof(int)-1);
}
 
void numsort(int* arr, unsigned int size) {
  if(!size) {return;}
  digitsort((unsigned int*)arr, size, sizeof(int));
}
 
int  numunique (unsigned int* arr, unsigned int size) {
  if(!size) {return 0;}
  digitsort(arr, size, sizeof(int)-1);
 
  int n = 1;
  unsigned int val = arr[0];
  for(int i=1; i<size; ++i) {
    if(val == arr[i]) {continue;}
    val = arr[i];
    if(i != n) {arr[n] = val;}
    ++n;
  }
 
  return n;
}
 
int  numunique (int* arr, unsigned int size) {
  if(!size) {return 0;}
  digitsort((unsigned int*)arr, size, sizeof(int));
 
  int n = 1;
  int val = arr[0];
  for(int i=1; i<size; ++i) {
    if(val == arr[i]) {continue;}
    val = arr[i];
    if(i != n) {arr[n] = val;}
    ++n;
  }
 
  return n;
}

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: m_ax от Ноябрь 04, 2010, 15:15

Вы, перед тем как выкладывать, проверяли корректно ли работает этот алгоритм?

numsort - судя по всему сортирует массив, но увы не всегда верно :(
например если взять вот такой массив: int arr[] = { 1, 2, 6, -4, 0, -9 };

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 05, 2010, 12:31

Цитата: m_ax от Ноябрь 04, 2010, 15:15

Проверял, корректно.
Ну, ошибся я с "0" при знаковой сортировке, с кем не бывает :).
Писал на коленке, просто чтоб показать сам алгоритм. Минимум тестирования. :(

вместо:

Код:

  if(digitpos == sizeof(int)) {
    return val>0?1:0;
  }

нужно:

Код:

  if(digitpos == sizeof(int)) {
    return val>=0?1:0;
  }

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: m_ax от Ноябрь 05, 2010, 13:09

Это понятно)

Почему тогда по времени почти на порядок выигрывает библиотечная std::sort? На сколько мне известно сложность там оценивается как O(N lnN). А время на сортировку в разы меньше?
Оценивалось это так:

Код

C++ (Qt)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <limits>
 
using namespace std;
 
extern void numsort   (int* arr, unsigned int size);
extern int  numunique (int* arr, unsigned int size);
extern void numsort   (unsigned int* arr, unsigned int size);
extern int  numunique (unsigned int* arr, unsigned int size);
 
unsigned char getbyte(int val, unsigned int digitpos) {
  if(digitpos == sizeof(int)) {
    return val>=0?1:0;
  }
 
  if(digitpos > 0) {
    val = val >> 8*digitpos;
  }
  val = val & 0xFF;
  return val;
}
 
void swap(unsigned int* val1, unsigned int* val2) {
  unsigned int val = *val1;
  *val1 = *val2;
  *val2 = val;
}
 
void digitsort(unsigned int* arr, unsigned int size, unsigned int digitpos) {
   unsigned int spos[256+1];
   unsigned int npos[256];
 
   memset(&spos, 0, (256+1)*sizeof(int));
   for(int i=0; i<size; ++i) {
     spos[getbyte(arr[i], digitpos)+1]++;
   }
   for(int i=0; i<256; ++i) {
     spos[i+1] += spos[i];
   }
   memcpy(&npos, &spos, 256*sizeof(int));
 
   unsigned int val1;
   unsigned int val2;
   for(int i=0; i<size;) {
     val1 = getbyte(arr[i], digitpos);
     if(i >= spos[val1] && i < npos[val1]) {
       i = npos[val1];
       continue;
     }
     if(i == npos[val1]) {
       npos[val1]++;
       ++i;
       continue;
     }
     val2 = getbyte(arr[npos[val1]], digitpos);
     while(val2 == val1) {
       npos[val1]++;
       val2 = getbyte(arr[npos[val1]], digitpos);
     }
     swap(&arr[i], &arr[npos[val1]]);
   }
 
   if(!digitpos) {return;}
   digitpos--;
   for(int i=0; i<256; ++i) {
     size = spos[i+1]-spos[i];
     if(!size) {continue;}
     digitsort(arr+spos[i], size, digitpos);
   }
}
 
void numsort(unsigned int* arr, unsigned int size) {
  if(!size) {return;}
  digitsort(arr, size, sizeof(int)-1);
}
 
void numsort(int* arr, unsigned int size) {
  if(!size) {return;}
  digitsort((unsigned int*)arr, size, sizeof(int));
}
 
int  numunique (unsigned int* arr, unsigned int size) {
  if(!size) {return 0;}
  digitsort(arr, size, sizeof(int)-1);
 
  int n = 1;
  unsigned int val = arr[0];
  for(int i=1; i<size; ++i) {
    if(val == arr[i]) {continue;}
    val = arr[i];
    if(i != n) {arr[n] = val;}
    ++n;
  }
 
  return n;
}
 
int  numunique (int* arr, unsigned int size) {
  if(!size) {return 0;}
  digitsort((unsigned int*)arr, size, sizeof(int));
 
  int n = 1;
  int val = arr[0];
  for(int i=1; i<size; ++i) {
    if(val == arr[i]) {continue;}
    val = arr[i];
    if(i != n) {arr[n] = val;}
    ++n;
  }
 
  return n;
}
 
int main()
{
    srand(time(0));
    const unsigned int size = 2000000;
    int arr[size];
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
 
    clock_t tStart = clock();
    //numsort(arr, size);
    sort(arr, arr+size);
    cout << (float)(clock() - tStart) / CLOCKS_PER_SEC << endl;
 
    return 0;
}

???

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 05, 2010, 16:30

Цитата: m_ax от Ноябрь 05, 2010, 13:09

1) std::sort - шаблонная функция
Кто сказал что std::sort для чисел имееет сложность O(N lnN) !
делаем простой тест:
1'000'000 - время T
10'000'000 - время ~ 10*T как для O(N), а для O(N lnN) время должно было быть ~30*T
100'000'000 - время ~ 100*T как для O(N), а для O(N lnN) время должно было быть ~600*T

2) Мой вариант был не оптимизирован. Большие накладные расходы на вызов getbyte. Я его писал так, чтоб был понятнее алгоритм.
Выкладываю более-менее оптимизированный.
На моей машине, в release скомпилированном под студией этот вариант ~ в 1.5 раза быстрее чем std::sort.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: m_ax от Ноябрь 06, 2010, 13:09

Цитировать

1) std::sort - шаблонная функция
Кто сказал что std::sort для чисел имееет сложность O(N lnN) !
делаем простой тест:
1'000'000 - время T
10'000'000 - время ~ 10*T как для O(N), а для O(N lnN) время должно было быть ~30*T
100'000'000 - время ~ 100*T как для O(N), а для O(N lnN) время должно было быть ~600*T

Вот почитайте: http://www.cplusplus.com/reference/algorithm/sort/
А вообще, всё зависит от конкретной её реализации.
У меня:

Код

C++ (Qt)
max@T1000:~$ g++ --version
g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3

Цитировать

2) Мой вариант был не оптимизирован. Большие накладные расходы на вызов getbyte. Я его писал так, чтоб был понятнее алгоритм.
Выкладываю более-менее оптимизированный.
На моей машине, в release скомпилированном под студией этот вариант ~ в 1.5 раза быстрее чем std::sort.

Не спешите. Ваша оптимизация не даёт заметного выигрыша: результат примерно тот же (попробуйте запустить на вашей машине этот код):

Код

C++ (Qt)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include "gm_num_sort.h"
 
using namespace std;
 
 
 
int main()
{
    srand(time(0));
    const unsigned int size = 2000000;
    int arr[size];
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
 
    clock_t tStart = clock();
    gm_NumSort(arr, size);
    cout << "gm_NumSort : " << (float)(clock() - tStart) / CLOCKS_PER_SEC << " sec" << endl;
 
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
 
    tStart = clock();
    sort(arr, arr+size);
    cout << "std::sort : " << (float)(clock() - tStart) / CLOCKS_PER_SEC << " sec" << endl;
 
    return 0;
}

У меня получается следующее (release -O2):

Код

C++ (Qt)
gm_NumSort : 2.44 sec
std::sort : 0.27 sec

Однако, Ваш алгоритм действительно примерно в 1.5 раза быстрее в том случае, если числа относительно малы. Но если диапазон [0, RAND_MAX) то выигрывает std::sort

Вопрос: Так какова истинная сложность вашего алгоритма в действительности?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 06, 2010, 13:56

Цитата: m_ax от Ноябрь 06, 2010, 13:09

Сложность O(N).

Код

C++ (Qt)
    srand(time(0));
    const unsigned int size = 2000000; //2'000'000, 20'000'000, 200'000'000
    int* arr = (int*) malloc(size*sizeof(int));
 
 
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
 
    clock_t tStart = clock();
    gm_NumSort(arr, size);
    cout << "gm_NumSort : " << (float)(clock() - tStart) / CLOCKS_PER_SEC << " sec" << endl;
 
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
 
    tStart = clock();
    sort(arr, arr+size);
    cout << "std::sort : " << (float)(clock() - tStart) / CLOCKS_PER_SEC << " sec" << endl;
 
    return 0;

Цитата: m_ax от Ноябрь 06, 2010, 13:09

У меня получается следующее (release -O2):

Код

C++ (Qt)
gm_NumSort : 2.44 sec
std::sort : 0.27 sec

Сборка release под VS2005 и mingw(gcc)

На size = 2'000'000; Ваш тест, сравните с моим
VS2005
gm_NumSort : 0.14 sec
std::sort : 0.265 sec
mingw
gm_NumSort : 0.187 sec
std::sort : 0.235 sec

На size = 20'000'000:
VS2005
gm_NumSort : 1.563 sec
std::sort : 2.562 sec
mingw
gm_NumSort : 1.906 sec
std::sort : 2.39 sec

На size = 200'000'000:
VS2005
gm_NumSort : 16.203 sec
std::sort : 25.969 sec
mingw
gm_NumSort : 20.329 sec
std::sort : 25.5 sec

Все очень наглядно, видимо у вас компилятор не очень. :)

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 06, 2010, 14:09

А вот еще результаты теста с массивом выделенным на стеке как у вас:

Код

C++ (Qt)
    const unsigned int size = 2000000;
    int arr[size];

VS2005
gm_NumSort : 0.156 sec
std::sort : 0.25 sec

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: m_ax от Ноябрь 06, 2010, 14:12

Вот что у меня:
CFLAGS = -pipe -O2 -Wall -W -D_REENTRANT $(DEFINES)
CXXFLAGS = -pipe -O2 -Wall -W -D_REENTRANT $(DEFINES)

Код

C++ (Qt)
size = 2000000
gm_NumSort : 2.45 sec
std::sort : 0.27 sec

Код

C++ (Qt)
size = 20000000
gm_NumSort : 11.16 sec
std::sort : 3.3 sec

Код

C++ (Qt)
size = 200000000
gm_NumSort : 31.8 sec
std::sort : 38.51 sec

CFLAGS = -pipe -O3 -Wall -W -D_REENTRANT $(DEFINES)
CXXFLAGS = -pipe -O3 -Wall -W -D_REENTRANT $(DEFINES)

Код

C++ (Qt)
size = 2000000
gm_NumSort : 0.99 sec
std::sort : 0.27 sec

Код

C++ (Qt)
size = 20000000
gm_NumSort : 5.6 sec
std::sort : 3.31 sec

Код

C++ (Qt)
size = 200000000
gm_NumSort : 25.21 sec
std::sort : 38.76 sec

У меня AMD64 1.8 Гц а у вас?

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: spectre71 от Ноябрь 06, 2010, 14:40

У меня ноутбук с Intel 1.83 GHz.

Но проблема у вас явно в компиляторе - плохой оптимизатор.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: BRE от Ноябрь 06, 2010, 21:45

Цитата: Spectre от Ноябрь 06, 2010, 14:40

Но проблема у вас явно в компиляторе - плохой оптимизатор.

Скорее всего дело в архитектуре целевого процессора.

Название: Re: Удаление элементов из массива величиной N за время O(n) и памятью O(1)
Отправлено: Igors от Ноябрь 06, 2010, 22:32

Тема/обсуждение хорошее, но поймите меня правильно - если б ее развернуть в более "практическую плоскость", было бы еще круче. У меня в работе сортировки и удаление повторов встречаются часто и в самых разных вариациях, но:

- мне неинтересно/неактуально рассматривать частный случай "целые числа", сортировать надо структуры (часто простые)

- сортировать "без выделения доп. памяти" безусловно хорошая "зарядка для ума" но .. далековато от жизни :) Даже для структур в стиле С время сортировки сжирается на обмене (больше структура - больше время). А если элементы не POD и имеют контструктор и/или оператор присваивания - ну тогда ОЙ!

Поэтому если мы говорим практически - сортировать надо указатели. А как? И что потом делать с отсортированным? Как напр. удалить те же повторы не меняя порядка элементов? А может даже есть такой паттерн? :) Все это было бы интересно обсудить, хотя конечно, я свое мнение не навязываю