Бързо откриване, ако има 2 или повече равни числа - масиви, алгоритъм, език-агностик, hashmap, двоично-търсене-дърво

Имам масив от N различни числачесто се променят. След всяка промяна има шанс, че две или повече числа са станали равни и аз не искам това.Броят N може да бъде толкова голям, колкото максималното възможно число.Знам, че промените се случват често, не искам да сравнявам всяко число с всеки от останалите след всяка промяна.

Как мога бързо да намеря, ако в масива има поне 2 равни числа?

Отговори:

Това наистина зависи от това какви други ограничения имате, например:

1. Трябва ли да запазите реда, в който се появи номерът?
2. Дали числата се добавят само или са изтрити?
3. Какво представлява по-често срещаната операция: добавяне / изтриване или проверка за дублиране?
4. Какво трябва да запазите - наборът (т.е. уникалните номера) или множеството (номерата с техните множества)?

Има две основни опции: a Двойно търсене дърво и a Hash Таблица.

Първият ще ви даде O(log(n)) операции средно, последните - O(1); действителните резултати ще зависят от какъв поток имате (номерата са случайни? увеличавате? следвайте странен невидим модел?)

Ако решите да отидете за BST, не забравяйте, че ще трябва да го направите поддържайте го балансирано.

Пример (непроведен)

(defparameter *my-data-array* (make-array 100000))
;; fill *my-data-array*
(defparameter *my-data-table*
(let ((ht (make-hash-table)))
(loop for v across *my-data-array*
do (incf (gethash v *my-data-table* 0)))
ht))
(defun modify-data-array (pos new-value)
(let* ((old-value (aref *my-data-array* pos))
(old-count (decf (gethash old-value *my-data-table*)))
(new-count (incf (gethash new-value *my-data-table* 0))))
(setf (aref *my-data-array* pos) new-value)
(case old-count
(0 ; old-value is now not in the array
...)
(1 ; old-value is now unique
...)
(t ; old-value is still not unique
...))
(case new-count
(1 ; new-value was not in the array before
...)
(2 ; new-value was unique before, but not anymore
...)
(t ; new-value was not unique
...))))

Като вариант, който може да използвате Блум филтър, Тя позволява да се тества дали даден номер евече добавени или не. Но може да има фалшиви положителни грешки. В другата ръка филтрите за цъфтеж са ефективни и бързи, и ви позволяват да запазите масива си. Алгоритъмът за филтриране на цвят ще ви бъде полезен, ако вземете редки числа, в противен случай трябва да препробвате числата в линейно време твърде често.