Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Получить количество пересечений набора шаблонов с набором наборов значений / 7 сообщений из 7, страница 1 из 1
31.03.2011, 10:31
    #37191781
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
Уже день голову ломаю, не могу придумать достаточно хороший алгоритм.

Есть набор шаблонов [p1, p2, ..., pN], где N - количество шаблонов.
Есть набор наборов значений [{i1, [v11, ...]}, {i2, [v21, ...]}, ..., {iI, [vI1, ...]}],
где i* - уникальный идентификатор набора значений, v** - сами значения соответственно, причем количество значений в каждом наборе значений произвольно, но в 99.99% случаев достаточно мало (меньше 5).

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

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

Язык реализации - Erlang, но даже если вы с ним незнакомы, но есть мысли насчет алгоритма - предлагайте, попробую сам адаптировать.
...
Рейтинг: 0 / 0
31.03.2011, 10:32
    #37191788
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
an0nymНужно получить количество уникальных идентификаторов, в любое из набора значений которого входит любой из шаблонов.

Или иначе (если это сильно поменяет алгоритм): нужно проверить, превышает ли количество уникальных идентификаторов, в любое из набора значений которого входит любой из шаблонов некоторый порог.
Входит слева, т. е. любое из значений в наборе начинается с любого из шаблонов.
...
Рейтинг: 0 / 0
31.03.2011, 10:34
    #37191793
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
Количество шаблонов достаточно мало (пусть будет до 10), количество уникальных идентификаторов (и наборов значений) весомо (от сотен до тысяч).
...
Рейтинг: 0 / 0
31.03.2011, 14:01
    #37192379
AlexandrPlus
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
так шаблоны и значения - списки?
так Пролог так и работает - в основе сопоставления с образцами
А у Erlang насколько интересовался в выражениям языка можно писать как на Прологе.
Хотя вот не уверен - работает всё по-прологовски.
P.S. Известно, что реализация не как во всех Прологах (хотя в каждом Прологе есть свои отличия в реализациях, но не в фундаментальных надалгоритмах).
...
Рейтинг: 0 / 0
31.03.2011, 14:04
    #37192389
AlexandrPlus
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
AlexandrPlusтак шаблоны и значения - списки?
так Пролог так и работает - в основе сопоставления с образцами
А у Erlang насколько интересовался в выражениям языка можно писать как на Прологе.
Хотя вот не уверен - работает всё по-прологовски.
P.S. Известно, что реализация не как во всех Прологах (хотя в каждом Прологе есть свои отличия в реализациях, но не в фундаментальных надалгоритмах).

тьфу, хотел подчеркнуть - вот жеж админы форума редактирование запретели (хотя бы первые 10 минут)

AlexandrPlusтак шаблоны и значения - списки?
так Пролог так и работает - в основе сопоставления с образцами
А у Erlang насколько интересовался в выражениям языка можно писать как на Прологе.
Хотя вот не уверен - работает всё по-прологовски.
P.S. Известно, что реализация не как во всех Прологах (хотя в каждом Прологе есть свои отличия в реализациях, но не в фундаментальных надалгоритмах).
...
Рейтинг: 0 / 0
31.03.2011, 14:15
    #37192426
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
AlexandrPlus,

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

Код: plaintext
1.
2.
3.
4.
 168 > [Pattern | _] = ["abc"], [{Id, [Value | _]} | _] = [{ 1 , ["abcd", "abce"]}, { 2 , ["a", "b"]}], {Pattern, Value}.
{"abc","abcd"}
 169 > Pattern ++ _ = Value.
*  1 : illegal pattern
...
Рейтинг: 0 / 0
31.03.2011, 17:53
    #37193003
AlexandrPlus
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить количество пересечений набора шаблонов с набором наборов значений
an0nym,
То есть - список является началом другого

А Erlang-то - как Пролог работает-то или иначе? Выражения вроде аналогичны и
заявлено, что и как Пролог может, но - реально?

На Прологе (SWI и Amzi под рукой есть) - так например
Код: plaintext
1.
podspisleft([X|T1],[X|T2]):-podspisleft(T1,T2).
podspisleft([],T2).
-> в Erlang отобразить

подсписок в любом месте списке
podspis(X,Y):-append(_,L,Y),append(X,_,L).
append - встроеный, но можно расписать - конкатенация то есть это
konkat([],T,T).
konkat([X|T1],T2,[X|T3]):-konkat(T1,T2,T3).
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Получить количество пересечений набора шаблонов с набором наборов значений / 7 сообщений из 7, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]