Как сделать перебор комбинаций?

Question

[Евгений]

Нужен алгоритм перебора(а в идеале скрипт). Есть фильтр товаров на сайте. Для каждой комбинации атрибутов формируется свой url. Нужно сформировать эти url.
Имеем: список атрибутов для каждого товара, у некоторых атрибутов есть множественные значения(например светодиодный, led, диодный), максимальное количество атрибутов, которые можно выбрать, атрибуты должны иметь четкую последовательность в соответствии с порядком сортировки( то есть из вариантов ЛПО 36Вт и 36Вт ЛПО будет только 1 вариант)
На текущий момент у товара в среднем 15-20 атрибутов, максимум можно выбрать 5, итоговое количество значений атрибутом(с учетом множественности 20-40.
Пробовал парсить сайт, все программы выдают out of memory через пару недель.
Была мысль брать каждый товар, для него формировать комбинации, записывать в БД исключая дубли, но 90% комбинаций от товара к товару будут повторяться и это просто бесполезная трата времени.
Может просто взять все атрибуты уникальные, перебрать все комбинации( к примеру 100 атрибутов, максимум 5 может быть выбрано одновременно, на знаю как посчитать кол-во комбинаций) потом проверить есть ли товар с такой комбинацией(как это сделать не через БД не знаю, а через БД запросы будут по 0,5сек отрабатываться).
Помогите, чтобы не попасть на out of memory и по возможности экономить время.

Answer 1

[Денис Артамонов]

Зачем заранее формировать url для каждой комбинации?
Насколько я понял, нужно делать выборку товаров в зависимости от выбранных атрибутов, т.е. фильтровать

Фильтр = форма
Каждый атрибут = чекбокс/инпут/селект
Отметили атрибуты
Отправили сабмит формы-фильтра
PHP ловит GET/POST-массив и смотрит какие были отмечены атрибуты, в зависимости от этого формирует ссылку и/или выдать результат из бд

как это сделать не через БД не знаю, а через БД запросы будут по 0,5сек отрабатываться

В любом случае нужно где-то хранить информацию и обрабатывать ее в зависимости от фильтра

Если товаров не много, тогда можно при запуске страницы с товарами создать js-объект и уже работать с ним

Либо работать с БД и настроить кеширование, тогда однинаковые запросы не будут отнимать по 0,5 сек

Comments

[Евгений]

нет. нужно сделать карту сайта. список всех возможных url, а соотв. комбинаций атрибутов. Выборки уже делаются на сайте.

[Денис Артамонов]

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

таким образом у нас будет таблица бд со всеми ссылками
ну а дальше запускаем скрипт, который уже сформирует xml-файлы карты

[Евгений]

создать карту со всеми url - в гугле имеется множество скриптов

И все это дохнет при кол-ве страниц более 1млн. Все уперлось именно в это.

По вашему алгоритму и думал делать, но есть тут проблема в том, что у части товаров 80% комбинаций будут совпадать(много товаров у которых из 18 характеристик отличается одна, например стекло прозрачное или матовое, остальное идентично). Очень много времени на перебор лишнего уходит. Как можно не перебирать то что уже перебрали при этом не исчерпав память ?

[Евгений]

Наверное можно решить задачу с помощью теории графов, но уже нефига не помню с институтских лет.

[Денис Артамонов]

И все это дохнет при кол-ве страниц более 1млн. Все уперлось именно в это.

В любом случае, в один xml файл карты Вы не сможете записать 1 млн ссылок
Я это к тому, что нужно обрабатывать ссылки порциями
Даже если Вы увеличите время выполнения скрипта и снимите ограничение на использование памяти этим скриптом, то он ведь все-равно может израсходовать все ресурсы

у части товаров 80% комбинаций будут совпадать(много товаров у которых из 18 характеристик отличается одна, например стекло прозрачное или матовое, остальное идентично).

Тогда, нужно сначала выделить товары у которых атрибуты совпадают
- Товар 1 : ат1, ат2, ат3
- Товар 2: ат1, ат2, ат3
- Товар 3: ат1, ат2, ат3

Далее, берем один товар из списка, прорабатываем для него все варианты, и пишем в базу ссылку для всех у кого имеется набор ат1, ат2, ат3. Тем самым, вместо одного товара обрабатываем сразу несколько.

Следующим шагом, берем товары, атрибуты которых отличаются
- Товар 1 : ат4, ат5, ат6
- Товар 3: ат9, ат8, ат7
Так же прорабатываем и их.

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