Какой алгоритм наиболее хорошо подходит для удаления дубликатов строк из массива?

Question

[12rbah]

Знаю два способа для удаления дубликатов (либо через map, либо вложенным циклом где все будет перебираться), есть ли еще какие нибудь способы для этого?

Comments

[Армянское Радио]

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

[12rbah]

Армянское Радио, а подсказать алгоритмы без этих данных не получится?

[Армянское Радио]

12rbah, Универсального алгоритма на все случаи жизни нет.
Задача в вашей постановке оторвана от реальности. Вполне возможно, что это удаление дубликатов по итогу занимает 1% от времени работы программы, и лучший выигрыш можно получить, оптимизировав хранение этих данных.

[granty]

На PGP есть функция array_flip, она меняет местами ключи с их значениями в массиве. Если применить её 2 раза, массив автоматически уникализуется.
Возможно, в GO есть что-либо подобное.

[Максим Федоров]

granty,

На PGP есть функция array_flip, она

в PHP массив является структурой хэш-мап (просто из коробки такой комбайн создатели замутили), это довольно замудренная структура, хотя на Go есть реализации... в любом случае над ней еще нужно навернуть flip

А если суммарно, то для данной задачи подойдет любая реализация по циклу (reduce/map как пример)
и не колдовать с хэш-мапой и колдовством над ней, чтобы не явно получить нужно поведение

[Максим Федоров]

в любом случае итерация по всем элементам, но одна
делайте в лоб, не ошибетесь, если размеры не катастрофические

[Михаил Кростелев]

Один из вариантов:
Выполнить сортировку массива, а затем обойти все до предпоследней. Если текущая строка равна следующей - удалить ее.

Answer 1

[uvelichitel]

Фильтр Блума быстрее и легче чем hash-map. Готовый пакет - https://github.com/willf/bloom Вручную можно сделать примерно так - https://medium.com/@meeusdylan/creating-a-bloom-fi...

Comments

[WinPooh32]

Еще есть вот такой пакет с фильтром, реализованным на битовых полях, что очень хорошо экономит память при больших множествах:
https://github.com/ipfs/bbloom

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

Answer 2

[Папа Стифлера]

Есть. Сортировка исходного массива строк и цикл в один проход.
https://play.golang.org/p/Sx0sHeixC-s