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

(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()

То, что после слова, после символа "|" — что это?

В моем понимании ты не умеешь читать. Вот тебе был ответ.




Так доступно? Или разжевать, как школьнику?

Я тебя спрашиваю ещё раз: как ты будешь отсортировывать?

Я могу дать код, который у меня. Пока что не оч. понял, как предлагается сделать. Ну допустим, что мы взяли первую строку исходного файла - там основное слово перед чертой, которое мы должны искать - "a". И нужно определить, есть ли оно во всех строках других, если есть, то объединить их по тому принципу сверху. Куда мы денемся от этого перебора всех строк в двойном цикле?

  Отсортируй данные до обработки!!! или убейся.

Некоторый набор слов, разделенный запятыми. В них и нужно искать вхождение слова перед |, но после скобки ")". Если оно есть, объединяем этот набор слов с искомым словом.

Добавлено через 3 минуты и 9 секунд

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

Что именно? Уже три варианта предложено.

Надцатью различными способами.

Захочу - еще до записи всех слов в файл буду сортировать.

Захочу - в процессе подготовки файла буду сортировать.
Алгоритмы Шелла, Квик, Вставкой, Блочный, а может предпочту встроенные функции PHP sort, usort, array_multisort
Тебе это сильно помогло?

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

Бгг...

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

ищем букву а. Она есть во всех 4х строках мы ее ищем везде? Или все же как в первом сообщении, только при условии word1?


Кода не будет.

только если word1. Но далее мы берем вторую строку, там уже будет b - и опять начинаем искать среди всех строк.

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

Парень, если ты бегаешь по всему миллиону слов, то у тебя алгоритм сложности O(n^2) и сортировка до одного места.

Если все же алгоритм зависит от слова word1/word2 etc.
То чем больше у тебя разных слов вида word1/word2,
тем ближе алгоритм к С*O(n)

Где C  у тебя отношение числа слов к числу уникальных слов.

Ну вот я и говорю, куда же денется эта самая сложность? На самом деле, слов в скобках типа word1, word2 мало очень по сравнению с другими словами a,b,c,d.
Может, даже меньше 10. А этих - тысячи, мильоны.

Не надо нам искать среди всех. А только среди тех кто имеет word1 и находится ниже.

(word1)a|b,c,d
(word1)b|e,f,g,a

Или ты хочешь получить такой результат?
(word1)a|b,c,d,e,f,g
(word1)b|e,f,g,a,с,d

Т.е. слова word1,word2... в скобках (в начале строки) у многих слов одинаковы

Добавлено @ 22:31
Ну да, но чтобы узнать, имеется ли там word1, нужно все равно проверить каждую строку , пусть и ниже

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

ты врешь :(
а логика задачи тупая.

Что конкретно ты хочешь получить?

Как по-твоему должны быть обработаны такие данные? Какой результат?
(word1)a|b,c,d
(word1)b|e,f,g,a
(word1)r|t,q,w,y

Добавлено через 1 минуту и 54 секунды

          
Да ты гонишь. Нам не нужно проверять каждую строку ниже для того чтобы узнать если там там оно.
Если его не будет в следующей строке - его дальше уже нет!!!

Я знаю, что тупая, т.к. пишу этот скрипт по просьбе чужой. По его словам, там база около миллиона слов или больше.
Здесь будет вроде

(word1)a|b,c,d,e,f,g
(word1)r|t,q,w,y

Короче. Что за задача.
Какая конкретная конечная цель.

Добавлено через 59 секунд

Вроде? Или точно будет такой результат?
Если ты не знаешь что ты хочешь получить в итоге - то никто этого не знает.

Почему? Оно же не уникальное, может быть несколько раз. Или имелось в виду действие сортировки?

Задача только такая:

из исходной базы вида

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

получить строки такого вида:

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

Добавлено через 4 минуты и 3 секунды
Короче, мне нужно понять, можно ли здесь просто убрать квадратичность или это свойство алгоритма такого. Ну и почему может виснуть комп при такой обработке, как убрать это.

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

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

вобщем приводи все к виду


(word1)a|b
(word1)a|c
(word1)a|d
(word1)c|a
(word1)c|f
(word1)c|h

сортируй и обрабатывай. В такой форме данных можно будет совместить обработку с сортировкой.

При постановке задачи пойди туда не знаю куда, принеси то, не знаю что...
Я получается только зря наехал на Pitlord.

Я понимаю, что задача корявая, но такую мне дали. Словами это формулируется так: для каждой строки исх. базы найти строки, в которых после знака | между запятыми содержится в точности подстрока исходной строки до знака | (т.е. слово после скобки и перед |, напр. "a") и в результирующую строку записать все эл-ты этих строк без повторов. При этом строки с найденными вхождениями можно удалять.
В принципе, ничего потустороннего нет. Я бы сам такое не стал делать, просто тут заказали такой скрипт сделать

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

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