Удалить дублирующиеся элементы с минимальной вспомогательной памятью?

Question

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

Answer 1

Если вы отсортируете массив, вам понадобится еще один проход для удаления дубликатов, поэтому сложность O (N N) в худшем случае (при условии Quicksort) или O (N sqrt (N)), используя ShellSort.

Вы можете достичь O (N * N) простым сканированием массива для каждого элемента, удаляющего дубликаты по мере продвижения.

Вот пример в Lua:

function removedups (t) 
    local result = {} 
    local count = 0 
    local found 
    for i,v in ipairs(t) do 
     found = false 
     if count > 0 then 
      for j = 1,count do 
       if v == result[j] then found = true; break end 
      end 
     end 
     if not found then 
      count = count + 1 
      result[count] = v 
     end 
    end 
    return result, count 
end 

Answer 2

Сохраняя добавочное использование памяти до минимума, лучше всего было бы сделать эффективный вид, чтобы получить их в порядке, а затем сделать один проход массива с индексом FROM и TO.

Вы каждый раз переходите к индексу FROM через цикл. Вы копируете только элемент из FROM в TO (и увеличиваете TO), когда ключ отличается от последнего.

С Quicksort, который будет равен O (n-log-n) и O (n) для окончательного прохода.

Answer 3

Я не вижу никакого способа сделать это без чего-то вроде пузыря. Когда вы находите обман, вам нужно уменьшить длину массива. Quicksort не предназначен для изменения размера массива.

Этот алгоритм всегда O (n^2), но он также не использует почти никакой дополнительной памяти - стек или кучу.

// returns the new size 
int bubblesqueeze(int* a, int size) { 
    for (int j = 0; j < size - 1; ++j) { 
     for (int i = j + 1; i < size; ++i) { 
      // when a dupe is found, move the end value to index j 
      // and shrink the size of the array 
      while (i < size && a[i] == a[j]) { 
      a[i] = a[--size]; 
      } 
      if (i < size && a[i] < a[j]) { 
      int tmp = a[j]; 
      a[j] = a[i]; 
      a[i] = tmp; 
      } 
     } 
    } 
    return size; 
} 

Answer 4

ли у вас есть два различных вар для обходе datadet InstEd только одного, то вы можете ограничить вывод, отвергая все diplicates, которые в настоящее время уже находятся в наборе данных.

Очевидно, что этот пример в C не является эффективным алгоритмом сортировки, а является лишь примером для одного из способов взглянуть на пробкем.

Вы также можете вслепую отсортировать данные сначала, а затем переместить данные для удаления дубликатов, но я не уверен, что это будет быстрее.

#define ARRAY_LENGTH 15 
int stop = 1; 
int scan_sort[ARRAY_LENGTH] = {5,2,3,5,1,2,5,4,3,5,4,8,6,4,1}; 

void step_relocate(char tmp,char s,int *dataset) 
{ 
    for(;tmp<s;s--) 
     dataset[s] = dataset[s-1]; 
} 
int exists(int var,int *dataset) 
{ 
    int tmp=0; 
    for(;tmp < stop; tmp++) 
    { 
     if(dataset[tmp] == var) 
      return 1;/* value exsist */ 
     if(dataset[tmp] > var) 
      tmp=stop;/* Value not in array*/ 
    } 
    return 0;/* Value not in array*/ 
} 
void main(void) 
{ 
    int tmp1=0; 
    int tmp2=0; 
    int index = 1; 
    while(index < ARRAY_LENGTH) 
    { 
     if(exists(scan_sort[index],scan_sort)) 
      ;/* Dismiss all values currently in the final dataset */ 
     else if(scan_sort[stop-1] < scan_sort[index]) 
     { 
      scan_sort[stop] = scan_sort[index];/* Insert the value as the highest one */ 
      stop++;/* One more value adde to the final dataset */ 
     } 
     else 
     { 
      for(tmp1=0;tmp1<stop;tmp1++)/* find where the data shall be inserted */ 
      { 
       if(scan_sort[index] < scan_sort[tmp1]) 
       { 
        index = index; 
        break; 
       } 
      } 
      tmp2 = scan_sort[index]; /* Store in case this value is the next after stop*/ 
      step_relocate(tmp1,stop,scan_sort);/* Relocated data already in the dataset*/ 
      scan_sort[tmp1] = tmp2;/* insert the new value */ 
      stop++;/* One more value adde to the final dataset */ 
     } 
     index++; 
    } 
    printf("Result: "); 
    for(tmp1 = 0; tmp1 < stop; tmp1++) 
     printf("%d ",scan_sort[tmp1]); 
    printf("\n"); 
    system("pause"); 
} 

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

Answer 5

Я отвечу на свой вопрос, так как после публикации я придумал действительно умный алгоритм для этого. Он использует хэширование, создавая что-то вроде хеш-набора на месте. Гарантируется, что O (1) в подмышечной области (рекурсия - это хвостовой вызов) и, как правило, O (N). Алгоритм выглядит следующим образом:

1. Возьмите первый элемент массива, это будет сторожевого.
2. Измените порядок остальной части массива, насколько это возможно, чтобы каждый элемент находился в положении, соответствующем его хешу. По завершении этого действия будут обнаружены дубликаты.Установите их равными дозорному.
3. Переместить все элементы, для которых индекс равен хешу в начале массива.
4. Переместить все элементы, которые равны дозорному, за исключением первого элемента массива, в конец массива.
5. То, что осталось между правильными хэшированными элементами и повторяющимися элементами, будет элементами, которые не могут быть помещены в индекс, соответствующий их хешу, из-за столкновения. Учтите, чтобы иметь дело с этими элементами.

Это может быть показано, что O (N) не предусмотрено никаких патологических сценария в хэширования: Даже если нет дубликатов, примерно 2/3 элементов будут устранены в каждой рекурсии. Каждый уровень рекурсии равен O (n), где малый n - количество оставшихся элементов. Единственная проблема заключается в том, что на практике он медленнее, чем быстрый, когда имеется несколько дубликатов, т. Е. Много столкновений. Однако, когда есть огромное количество дубликатов, это удивительно быстро.

Редактировать: В текущих реализациях D hash_t составляет 32 бита. Все об этом алгоритме предполагает, что будет очень мало, если таковые имеются, хеш-коллизий в полном 32-битном пространстве. Однако столкновения могут часто возникать в пространстве модулей. Однако это предположение, по всей вероятности, будет справедливым для любого набора данных с разумным размером. Если ключ меньше или равен 32 битам, это может быть его собственный хеш, что означает, что столкновение в полном 32-битном пространстве невозможно. Если он больше, вы просто не можете разместить их достаточно в 32-битном адресном пространстве памяти, чтобы это было проблемой. Я предполагаю, что hash_t будет увеличено до 64 бит в 64-битных реализациях D, где наборы данных могут быть больше. Более того, если это когда-либо окажется проблемой, можно изменить хеш-функцию на каждом уровне рекурсии.

Вот реализация на языке программирования D:

void uniqueInPlace(T)(ref T[] dataIn) { 
    uniqueInPlaceImpl(dataIn, 0); 
} 

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) { 
    if(dataIn.length - start < 2) 
     return; 

    invariant T sentinel = dataIn[start]; 
    T[] data = dataIn[start + 1..$]; 

    static hash_t getHash(T elem) { 
     static if(is(T == uint) || is(T == int)) { 
      return cast(hash_t) elem; 
     } else static if(__traits(compiles, elem.toHash)) { 
      return elem.toHash; 
     } else { 
      static auto ti = typeid(typeof(elem)); 
      return ti.getHash(&elem); 
     } 
    } 

    for(size_t index = 0; index < data.length;) { 
     if(data[index] == sentinel) { 
      index++; 
      continue; 
     } 

     auto hash = getHash(data[index]) % data.length; 
     if(index == hash) { 
      index++; 
      continue; 
     } 

     if(data[index] == data[hash]) { 
      data[index] = sentinel; 
      index++; 
      continue; 
     } 

     if(data[hash] == sentinel) { 
      swap(data[hash], data[index]); 
      index++; 
      continue; 
     } 

     auto hashHash = getHash(data[hash]) % data.length; 
     if(hashHash != hash) { 
      swap(data[index], data[hash]); 
      if(hash < index) 
       index++; 
     } else { 
      index++; 
     } 
    } 


    size_t swapPos = 0; 
    foreach(i; 0..data.length) { 
     if(data[i] != sentinel && i == getHash(data[i]) % data.length) { 
      swap(data[i], data[swapPos++]); 
     } 
    } 

    size_t sentinelPos = data.length; 
    for(size_t i = swapPos; i < sentinelPos;) { 
     if(data[i] == sentinel) { 
      swap(data[i], data[--sentinelPos]); 
     } else { 
      i++; 
     } 
    } 

    dataIn = dataIn[0..sentinelPos + start + 1]; 
    uniqueInPlaceImpl(dataIn, start + swapPos + 1); 
}