парсер множеств #151439

Привет! Я пишу небольшую програмульку для работы со множествами. У меня вот какой вопрос - каким способом моно запрограммировать операцию объединения? Я помню тока как это выразить через пересечение и дополнение... Потом, вот если у меня целая куча множеств - то как мне оптимизировать операцию объединения(ну чтоб считалось это дело как моно быстрее)?

на каком языке ты пишешь программу?

Какое внутреннее представление у множеств?

Если множество через ТЗ с значениями - тогда обыкновенная операция слития ТЗ, Затем свернуть. Или у тебя Битовое представление? Тогда объединение OR, пересечение AND.

Чую, что здесь 1С и не пахнет, а сплошные объекты.

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

К 1С это тоже кстати применимо... веть структура информационных сущностей - это то же множество.

Гусары, внимание! "документированые функции использовать нельзя"!!!

Ну насколько я понимаю, проблема в поиске дублей. Можно сперва все объединить в одно множество, потом его отсортировать (например сортировкой Хоара) и дубли будут найдены автоматически (соседние равные элементы).

Или можно отсортировать только одно из множеств, а потом юзать продвинутый поиск в нем каждого элемента из другого множества. Хотя, по-моему, получится то же самое.

Дык проблема то как раз в объединении множеств. Ну то есть я определяю пересечение, а потом добавляю в массив дополнения каждого из множеств - это есть объединение. А вот как мне ускорить то (затачить) алгоритм под очень большие массивы?

Что-то я ни хрена не понимаю. В чем проблема? Ты массивы слить не можешь?

Ты множества сделал на массивах? Для больших множеств - быстрее будет работать на ТЗ. Из-за наличия методов заполнить и свернуть. Под массивы - сымый быстрый способ - тупо объединить, отсортировать, и слить исключая одинаковые (в отсортированном они идут подряд) значения.

РЖУНЕМАГУ, PASCAL!!!

Блин да так и сделал... Как ускорить то процесс? Блин с фундаментальной точки зрения...

(+12) Колбасит меня - каждый из массивов отсортировать по отдельности, а потом слить. Set поддерживает до 256 значений. Но есно нормально множество делается битовым, Если целые числа  - тем более. Делаем массив целых чисел, и для Объединения в Цикле OR, для пересечения в цикле AND.

Функции слияния и прочии - это уже готовые шаблоны.. надо свой способ оптимизации парсерных структур...Потом еще и доказывать почему так а не иначе работает быстрее.

Что значит готовые шаблоны? Ты ж их сам реализуешь, разумеется по готовому алгоритму. Ты по-своему лучше не сделаешь. В сортировке уже очень давно все велосипеды изобретены.

Ну незнаю... У меня и задача собственно придумать парсинг-алгоритм. Показать его эффективность в сравнении с другими. Спасибо.

Еще раз - быстрее, чем битовое представление множеств - еще ничего не придумано, но хависит от того, что являектся элементами множеств. Если число от 1 до 1000000, а мощность множеств порядка 1000, то конечно сортировка и слияние. Либо хранение в индексированной (отсортированной) структуре.

А если игрушку рискнуть запустить какую-нить или там тест какой-нить. Емулю выруби конечно.

+ не в ту ветку, виноват, удалите.

(+19) Еще и Хешированной.