Удаление дубликатов из массива

[xolod]

Вот столкнулся с проблемой. Нужен более оптимальный, чем мой алгоритм удаление элементов из массива.
На данный момент удаляю самым "дубовым" способом:
1) Создаю цикл в цикле, в первом прохожусь по всем элементам, во втором, прохожусь по всем элементам начиная с элемента больше на 1, чем в первом цикле и сравниваю. Если одинаковые - помечаю их к удалению.
2) Удаляю все помеченные элементы в цикле

Алгоритм тупой, но на ум приходят только еще более глупые реализации.
Что посоветуете?

[uhm]

А что у тебя в массиве? Если элементы можно сравнивать (в смысле, "больше - меньше"), проще отсортировать и дальше проверять только соседние элементы.

[xolod]

Элементы строковые, переменной длины.

[alibek]

Ничего более оптимального, чем обработка сортированного массива, я не знаю. Лучше всего изначально сортировать массив, тогда накладные расходы на сортировку будут очень маленькими.

[uhm]

Ну, по идее, в некоторых задачках еще более эффективно хранение массивов в виде дерева... Но я что-то не уверен, что здесь это в тему...

[xolod]

Дело в том, что отсортированный массив теряет актуальность. Мне важно сохранять порядок данных.
Забил бы на это дело, сославшись на специфичность задачи и невозможность реализации. Но в foobar2k из массива в 5000 элементов удаляются дубликаты за 2-3 секунды.

[ZlydenGL]

А если создать еще один массив, отсортировать его и уже в отсортированном искать совпадения - так поможет? Или создать допустим двумерный массив, первое поле - оригинальный номер, второе - строка из оригинального массива. Сортируешь, затем по номеру находишь задвоенные записи и...

[alibek]

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

[ZlydenGL]

alibek, я так понял что человек имеет дело с массивом, а не с БД? Разве у массивов есть индекс?

[xolod]

2 ZlydenGL
Ты не понял задачи. Создам отсортиртированный массив (допустим, QuickSort'ом, уже даже это долго), удалю дубликаты. Как я потом узнаю, в каком порядке они были до сортировки/удаления?
Второй вариант вообще не из той области. Многомерные массивы VB - тормоз страшнейший.

[uhm]

Все же еще зависит от размерности массива. "Тупой" алгоритм требует время порядка N*N, быстрые сортировки - N*ln(N) (Quicksort, кстати, если я правильно помню, требует в худшем случае как раз N*N ), но есть еще фиксированные временные издержки на создание доп. массива. При не очень больших размерностях "тупой" алгоритм может оказаться самым быстрым...

[ZlydenGL]

xolod, то есть как? Допустим ты обнаружил что строковая переменная "Здесь был Вася" в твоем массиве повторяется. Скользишь по своему ОРИГИНАЛЬНОМУ массиву и после первого нахождения этой фразы остальные совпадения удаляешь - не вариант?

Многомерные массивы... Могу только сказать (на своем опыте) что двумерный массив (10000х2) обрабатывается (по части сортировки) секунд за пять максимум - у меня 1.6 Гц и 1 Гб могзов. Массив как раз строковый.

Но если уж жаться на двумерный массив... Используй одномерный, а оригинальный номер сохрани где-нить допустим в конце переменной. Допустим в переменной хранится та же фраза "Здесь был Вася", оригинальный номер ее 256... Ну и запихни ее в массив как "Здесь был Вася {256}" и сравнивай только то, что идет ДО фигурных скобок.

[alibek]

А зачем вообще многомерный массив?
Создаешь массив idx(), в котором хранятся ссылки на номер элемента в основном массиве.

[ZlydenGL]

alibek, что я и предлагал выше

[alibek]

Не совсем. Операции со строками отнимут любые преимущества сортированного массива, надо использовать именно отдельный индексный массив. Вдобавок, ты предлагаешь физически переупорядочить элементы (хотя изначальный порядок и можно восстановить). Чтобы отобразить список в первоначальном порядке, потребуется много машинного времени.

[kif]

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

[xolod]

(c) "Всем спасибо, все свободны"
Задача решена.
Написал библиотеку на MSVC, в STL::Algorithm есть возможность удаления дубликатов из массивов. Не знаю, как он там что делает, но скорость на высшем уровне

[xolod]

2 kif
Представь себе добавление элемента 6740. Будешь бегать по всему массиву с вопросом, есть элемент или нет?

[alibek]

Опять таки, при сортированном массиве проверить наличие элемента в массиве из 6000 записей займет максимум 8 (9) итераций.

[Sebas]

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