Всем привет.
Есть такая задача:

большой массив:
fname id
[file_1.txt] [10]
[file_2.txt] [11]
[file_3.txt] [12]
.................
[FilE_1.txt] [115000]
(результат из базы)

Необходимо найти дубликаты в поле fname, поиск должен быть регистронезависим ([FilE_1.txt] == [file_1.txt]).

Вариант с перебором и проверкой каждого элемента наверное не пойдет, массив насчитывает более 200 000 элементов, а при переборе мне прийдется перебрать
40 000 000 000 элементов.

язык — php, но за алгоритм буду тоже очень благодарен.

Здравствуйте, vnevsky2006, Вы писали:

V>большой массив:
V> fname id
V>[file_1.txt] [10]
V>[file_2.txt] [11]
V>[file_3.txt] [12]
V>.................
V>[FilE_1.txt] [115000]
V>(результат из базы)

V>Необходимо найти дубликаты в поле fname, поиск должен быть регистронезависим ([FilE_1.txt] == [file_1.txt]).

Массив можно отсортировать (N*log(N)) по полю fname.
В отсортированном массиве дубликаты будут идти друг за другом.

Здравствуйте, vnevsky2006, Вы писали:

V>Всем привет.
V>Есть такая задача:

V>большой массив:
V> fname id
V>[file_1.txt] [10]
V>[file_2.txt] [11]
V>[file_3.txt] [12]
V>.................
V>[FilE_1.txt] [115000]
V>(результат из базы)

А может SQL сразу запросом? Чего гонять за зря 200000 записей?

select * from t where upper(fname) in (select upper(fname) from t having count(*) > 1 group by 1)

Запрос не проверял — чисто как отправная точка. При наличии индекса upper(fname) должно летать.

V>Необходимо найти дубликаты в поле fname, поиск должен быть регистронезависим ([FilE_1.txt] == [file_1.txt]).

Функция upper есть во всех языках

V>Вариант с перебором и проверкой каждого элемента наверное не пойдет, массив насчитывает более 200 000 элементов, а при переборе мне прийдется перебрать
V>40 000 000 000 элементов. :wow

ну так точно делать не надо

V>язык — php, но за алгоритм буду тоже очень благодарен.

Ну если очень хочешь алгоритм...

1 сорируешь массив (без учета регистра)
2 проходишь по отсортированному массиву и отбираешь дубликаты.

Но проще сраз в SQL отобрать.

Если я правильно понял, то длина File_name у тебя не очень большая.
При таком условии легко проверить все записи со сложностью O(n*m*X), где m-максимальная длина "имени файла",
что дает более быстрое решение, нежели сортировка, X — может сильно варьироваться — зависит от конкретной реализации. Подробнее после.
Решается — легко. Походу работы строится дерево, где путь от вершины до листа — имя файла, а значение в листе — количество встреченных имен. Время добавления/прибавления в дерево нового слова — m*X.
Понятно, что для того, что бы спуститься до нужной вершины нам придется в каждой вершине дерева находить ребенка с подходящим ребром к отцу — вот тут-то и появляется этот самый Х. В случае, если памяти не сильно жалко, то можно просто создать массив длиной размера алфавита символов названия файла, если жалко памяти, то стоит воспользоваться красно-черными деревьями (или любыми другими самобалансирующимися), для нахождения конкретного ребенка — хотя тут так же придется поработать над оптимизацией выделения ресурсов. (Во втором случае поиск ребенка — так же спуск по дереву[в этот раз бинарному].). Вроде ответил.

Здравствуйте, vnevsky2006, Вы писали:

Не спасёт ли тебя хеш-таблица?
Пусть даже поиск повторений в списках коллизий будет последовательным (за квадратичное время, то есть) — всяко это не 250000 записей в одном списке.

При условии, что нет возможности решить задачу прямо в базе.