Удаление элементов из массива величиной N за время O(n) и памятью O(1)

[m_ax]

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

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

[spectre71]

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

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

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

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

[spectre71]

Вот, скучно було решил написать алгоритм
сложность 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;
}
 

[m_ax]

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

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

[spectre71]

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

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

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

вместо:

Код:

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

нужно:

Код:

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

[m_ax]

Это понятно)

Почему тогда по времени почти на порядок выигрывает библиотечная 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;
}
 

   
 

[spectre71]

Это понятно)

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

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.

[m_ax]

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  

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

[spectre71]

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

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

Сложность 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;
 

         

У меня получается следующее (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       

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

[spectre71]

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

Код

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

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

[m_ax]

Вот что у меня:
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 Гц а у вас?

[spectre71]

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

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

[BRE]

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

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

[Igors]

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

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

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

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