Могу ли я проверить, содержит ли ограниченный список дубликаты за линейное время? - PullRequest
Новая
       32

Могу ли я проверить, содержит ли ограниченный список дубликаты за линейное время?

3 голосов
/ 11 июля 2019

Предположим, у меня есть список Int, в котором элементы, как известно, ограничены, и список, как известно, не длиннее своего диапазона, так что вполне возможно, что он не будет содержать дубликаты. Как я могу наиболее быстро проверить, так ли это?

Я знаю о nubOrd. Это довольно быстро . Мы можем пройти наш список и посмотреть, станет ли он короче. Но эффективность nubOrd все еще не линейна.

Моя идея заключается в том, что мы можем обменять пространство на эффективность времени. Обязательно, мы должны выделить битовое поле, столь же широкое как наш диапазон, и затем пройтись по списку, отмечая записи, соответствующие значениям элементов списка. Как только мы пытаемся перевернуть бит, который уже равен 1, мы возвращаем False. Требуется только (чтение + сравнение + запись) * длина списка. Нет бинарных деревьев поиска, нет ничего.

Разумно ли попробовать подобную конструкцию в Хаскеле?

Ответы [ 3 ]

3 голосов
/ 12 июля 2019

Пакет дискриминация имеет линейное время nub , которое вы можете использовать. Или линейное время group , для которого не требуется, чтобы эквивалентные элементы были смежными, чтобы сгруппировать их, чтобы вы могли видеть, не является ли какая-либо из групп размером 1.

Весь пакет основан на обходе общеизвестных границ для сортировок на основе сравнения (и объединений и т. Д.) С использованием алгоритмов, основанных на «различении», а не на основе сравнений. Насколько я понимаю, этот метод похож на радикальная сортировка , но обобщен на ADT.

2 голосов
/ 12 июля 2019

Для целых чисел (и других Ix -подобных типов ) можно использовать изменяемый массив, например, с array пакет .

Здесь мы можем использовать STUArray здесь, например: 

import Control.Monad.ST
import Data.Array.ST

updateDups_ :: [Int] -> STArray s Int Bool -> ST s Bool
updateDups_ [] _ = return False
updateDups_ (x:xs) arr = do
    contains <- readArray arr x
    if contains then return True
    else writeArray arr x True >> updateDups_ xs arr

withDups_ :: Int -> [Int] -> ST s Bool
withDups_ mx l = newArray (0, mx) False >>= updateDups_ l

withDups :: Int -> [Int] -> Bool
withDups mx ls = runST (withDups_ mx ls)

Например: 

Prelude Control.Monad.ST Data.Array.ST> withDups 17 [1,4,2,5]
False
Prelude Control.Monad.ST Data.Array.ST> withDups 17 [1,4,2,1]
True
Prelude Control.Monad.ST Data.Array.ST> withDups 17 [1,4,2,16,2]
True

Итак, здесь первый параметр - это максимальное значение, которое можно добавить в список, а второй параметр - список значений, которые мы хотим проверить.

2 голосов
/ 12 июля 2019

Итак, у вас есть список размера N, и вы знаете, что элементы в списке находятся в диапазоне min .. min+N-1.

Существует простой линейный алгоритм времени, который требует O (1) пробела.

Сначала отсканируйте список, чтобы найти минимальные и максимальные элементы.

Если (max - min + 1) < N, то вы знаете, что есть дубликат. В противном случае ...

Поскольку диапазон равен N, минимальный элемент может быть равен a[0], а максимальный элемент - a[n-1]. Вы можете сопоставить любой элемент с его положением в массиве, просто вычтя min. Вы можете выполнить сортировку на месте в O (n), потому что вы точно знаете, куда должен идти каждый элемент.

Начиная с начала списка, возьмите первый элемент и вычтите min, чтобы определить, куда он должен идти. Перейдите в эту позицию и замените предмет, который там есть. С новым элементом вычислите, куда он должен идти, и замените элемент в этой позиции и т. Д.

Если вы когда-нибудь дойдете до точки, где вы пытаетесь разместить элемент на a[x], и уже существует значение, то есть предполагается , которое должно быть там (то есть a[x] == x+min), то вы нашли дубликат.

Код для всего этого довольно прост:

Исправленный код. 

min, max = findMinMax()
currentIndex = 0
while currentIndex < N
    temp = a[currentIndex]
    targetIndex = temp - min;
    // Do this until we wrap around to the current index
    // If the item is already in place, then targetIndex == currentIndex,
    // and we won't enter the loop.
    while targetIndex != currentIndex
        if (a[targetIndex] == temp)
            // the item at a[targetIndex] is the item that's supposed to be there.
            // The only way that can happen is if the item we have in temp is a duplicate.
            found a duplicate
        end if
        save = a[targetIndex]
        a[targetIndex] = temp
        temp = save
        targetIndex = temp - min
    end while
    // At this point, targetIndex == currentIndex.
    // We've wrapped around and need to place the last item.
    // There's no need to check here if a[targetIndex] == temp, because if it did,
    // we would not have entered the loop.
    a[targetIndex] = temp
    ++currentIndex
end while

Это основная идея.

...