Есть большой текстовый файл со строками вида:

(word1)a|b,c,d
(word1)b|e,f,g,a
(word2)c|h,a
(word2)f|w,a,c
...

Нужно на выходе получить строки такие:

(word1)a|b,c,d,e,f,g
(word2)c|h,a,f,w
и т.п.

То есть берем первую строку и ищем в остальных, есть ли в них вхождение "a" (слова перед | ) и при этом слово в скобках должно быть в начале таким же, как и у исходного слова проверяемого (word1).
После этого объединяем все это в одну строку, там где такое вхождение есть, и эти строки можно дальше не рассматривать.

Проблема в том, что если исходных строк около 150к, а алгоритм у меня получается с двойным циклом (для каждой строки проверяются все остальные), то это все приводит к 150к^2, и все виснет.
Можно ли обойтись одним циклом? Желательно после каждого прохода добавлять полученную строку в результирующий файл.

Это сообщение отредактировал(а) motorway - 6.12.2009, 18:36

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

Можно ещё запихнуть всё в таблицу СУБД через INSERT ... ON DUPLICATE KEY UPDATE.

Добавлено через 8 минут и 11 секунд

Набор возможных значений (a, b, c, ...), вообще говоря, заранее известен? Тогда для второго варианта будет достаточно битового поля.

Это сообщение отредактировал(а) Pitlord - 6.12.2009, 19:39

Т.е. цикл по любому будет вложенным?

Нет

А как сделать указанную обработку "в один присест"? То есть, чтобы число прогонов цикла было не больше числа всех строк в файле?

Для начала отсортировать

Я уже написал как это сделать. Причём два варианта привёл.

Это сообщение отредактировал(а) Pitlord - 6.12.2009, 21:42

Не гоните, зачем тут БД?

прочитать в массив.

посортировать по первым надцати символам, которые являются словом.

Обработка:
1. Берем первый элемент, берем из него слово, остальное explode() и записываем в массив результатов
2. Берем следующий элемент,
2.а. если слово совпадает, то выкусываем, explode() и добавляем к массиву результататов
2. б. если не совпадает, то для набора делаем array_unique, implode() и добавляем слово и сохраняем где-нибудь.
3. Обнуляем массив результатов
4. С несовпавшим элементом и словом идем на обработку в начало.

Что это за алгоритм сортировки со сложностью O(n)?

Набор слов неизвестен заранее. Честно говоря, не очень понимаю, что даст сортировка (имеется в виду сортировка по началу строки (по алфавиту)?). Вроде надо же будет все равно для каждой строки проверять, есть ли в остальных строках слово это (нужно искать вхождение между запятыми после символа "|" ).
Пока что в моем коде было 2 for each.

Это сообщение отредактировал(а) motorway - 6.12.2009, 21:59

А значений "a, b, c, ..."?

Добавлено через 37 секунд
Имеется ввиду множество всех этих значений — известно?

парень, если ты полагаешь что БД не занимается сортировкой - то застрелись.

И не надо выдумывать то, о чем не говорилось.

Обработка будет именно со сложностью O(n), но данные должны прийти на обработку отсортированными.

В общем, есть исходный файл на входе со всеми этими словами. Если он уже есть, значит, вроде что-то известно. Но так как он весьма большой, это дает разве что-нибудь? Этих слов там может быть миллион или больше.
Основное, что нужно - чтобы комп не зависал при обработке, и она была не квадратичной зависимости от объема данных. После получения каждой строки результирующей ее сохранять в файл, чтобы в памяти не держать ее.

Это сообщение отредактировал(а) motorway - 6.12.2009, 22:06

Причём тут БД? Я задал вопрос — где ответ? Или в твоём понимании время сортировки будет зависить от количества элементов линейно? Приведи реальный код.

не надо. Слова будут идти подряд. Если в следующей записи слово изменилось, значит его больше не будет.
искать | необязательно. Можно на этапе чтения использовать explode("|", $line);
сортировать ты будешь по первым элементам подмассивов, делается это при помощи array_multisort()