ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Получить количество пересечений набора шаблонов с набором наборов значений
7 сообщений из 7, страница 1 из 1
Получить количество пересечений набора шаблонов с набором наборов значений
    #37191781
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
an0nym
Участник
Уже день голову ломаю, не могу придумать достаточно хороший алгоритм.

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

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

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

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

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

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

AlexandrPlusтак шаблоны и значения - списки?
так Пролог так и работает - в основе сопоставления с образцами
А у Erlang насколько интересовался в выражениям языка можно писать как на Прологе.
Хотя вот не уверен - работает всё по-прологовски.
P.S. Известно, что реализация не как во всех Прологах (хотя в каждом Прологе есть свои отличия в реализациях, но не в фундаментальных надалгоритмах).
...
Рейтинг: 0 / 0
31.03.2011, 14:04
| Ответить | Цитировать | Написать  
Получить количество пересечений набора шаблонов с набором наборов значений
    #37192426
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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, 14:15
| Ответить | Цитировать | Написать  
Получить количество пересечений набора шаблонов с набором наборов значений
    #37193003
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
31.03.2011, 17:53
| Ответить | Цитировать | Написать  
7 сообщений из 7, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Получить количество пересечений набора шаблонов с набором наборов значений
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&gotonew=1&tid=1343038]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 28ms
get topic data:
 11ms
get first new msg:
 7ms
get forum data:
 3ms
get page messages:
 48ms
get tp. blocked users:
 2ms
others: 245ms
total:  373ms
созд. / загр.: 373ms
x
x
Закрыть


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