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

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

11.12.2008 00:45:46
Хм ... Кто-нибудь просто получает -1 при публикации пьесы без комментариев в этой теме?
eaanon01 12.12.2008 06:13:35
5 ОТВЕТОВ

Если вы сортируете массив, вам все равно потребуется еще один проход для удаления дубликатов, поэтому сложность составляет O (N N) в худшем случае (при условии быстрой сортировки) или 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
0
11.12.2008 01:28:39

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

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

При быстрой сортировке это будет среднее значение O (n-log-n) и O (n) для последнего прохода.

1
11.12.2008 01:15:56

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

Этот алгоритм всегда 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;
}
0
11.12.2008 03:19:16

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

Очевидно, что этот пример на 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, как вы можете видеть выше. Сделайте комментарий, если я должен уточнить, или вы видите какие-либо недостатки.

0
11.12.2008 09:16:28

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

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

Это может быть показано как O (N), если патологический сценарий в хешировании отсутствует: даже если нет дубликатов, примерно 2/3 элементов будут удаляться при каждой рекурсии. Каждый уровень рекурсии равен O (n), где small 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);
}
2
12.12.2008 04:43:40
Как все эти хеш-таблицы не выделяют место в куче?
jmucchiello 11.12.2008 23:38:29
Вы не создаете хеш-таблицу. Вы просто переупорядочиваете текущий массив на месте так, чтобы как можно больше элементов находилось в позициях, соответствующих их хешу.
dsimcha 12.12.2008 03:42:09