Re: нужен алгоритм

Да, списки как видно связного хранения но это не имеет значения можно использовать последовательное или двухсвязное, если это повлияет на эффективность.

Re: нужен алгоритм

В данной постановке, очевидно, что O(n^2), эффективнее никак.

А вообще можно завести хеш-таблицу с ключом param и значением value, сначала проставить туда значения по умолчанию, потом проставить туда пользовательские значения. Результирующая таблица будет содержать требуемые данные.

Re: нужен алгоритм

http://en.wikipedia.org/wiki/Associative_array

один проход по A

один проход по B

каждая операция ln(n)

всего O(n*ln(n))

Re: нужен алгоритм

Упорядочить оба списка по param. При этом сгенерить их упорядоченными (сложность O(n)). Алгоритм формирования пересечения списков такой: Берем первый элемент из a и из b (param(1)). Если a.param(1) > b.param(1), сравниваем a.param(1) и второй элемент списка b - b.param(2), если a.param(1) < b.param(1) то сравниваем a.param(2) с b.param(1) и т.д. Если равны то присваиваем. В результате максимальное число операций не превышает суммы размеров списков, соотв. сложность O(n). Задача очень просто решается рекурсивной процедурой.

PS. Хеш-таблица кстати не даст выигрыша. Несмотря на то, что время поиска по ней константно, надо совершить n поисков, где n - размер одного из списков. В результате сложность та же - O(n). Гемора при реализации (если не брать готовую) на порядок больше.

PPS. Пример реализации (на scheme) есть в SICP в параграфе 2.3.3 - рекоммендую.

Re: нужен алгоритм

> Задача очень просто решается рекурсивной процедурой.

не стоит забывать, что C != scheme, и в хвостовую рекурсию ничего разворачивать не будет, посему при очень большом LENGTH(LIST) может тупо и цинично порвать стэк.

; asgard

Re: нужен алгоритм

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

наиболее приемлемое решение - хэш таблица.

; asgard

Re: нужен алгоритм

>> не стоит забывать, что C != scheme, и в хвостовую рекурсию ничего разворачивать не будет

Да один хрен на самом деле :)) Заменить рекурсию на цикл труда в этом случае не составит, просто не так красиво :)))

А насчет создания списков уже упорядоченными - согласен.

Хеш-таблица - если помимо пересечений будут вставки и поиски, то таки да, можно попробовать. Если ничего этого не планируется, то нах хэш-таблицу.

Re: нужен алгоритм

> не стоит забывать, что C != scheme, и в хвостовую рекурсию ничего разворачивать не будет

gcc может развернуть, хотя конечно полагаться на это нельзя.

Re: нужен алгоритм

> хотя конечно полагаться на это нельзя.

именно.

; asgard

Re: нужен алгоритм

> Как максимально эффективно найти нужные пары?

Если задачу ставить так строго, то её нужно и точно определить. Что значит за наименьшее время? Наименьшее в худшем случае или наименьшее матожидание? Какой язык программирования? Именно Си? А что значит время? Порядок асимптотической сложности? Ещё нужно знать ожидаемый размер A и B (почему-то все сразу предположили предел sizeA ~ sizeB ~ N -> +inf) и есть ли априорная упорядоченность элементов.

Второй вопрос - готовы ли принять сложное решение? :)

Как уже было сказано, теоретически тут, конечно, сложность O(N ln N) (хотя, если говорить теоретически и ещё точнее, то всё же O(N), но на практике это малоинтересно). И решений масса, с разными деталями в описанных выше вопросах :) Но, может, этого всего не нужно? ;-) Unix way - используйте простые алгоритмы и не бойтесь пузырьковой сортировки :-)

Re: нужен алгоритм

Если список А отсортирован, то >Берем первый элемент из a и из b (param(1)). Если a.param(1) > b.param(1), сравниваем a.param(1) и второй элемент списка b - b.param(2), если a.param(1) < b.param(1) то сравниваем a.param(2) с b.param(1) и т.д. Если равны то присваиваем. В результате максимальное число операций не превышает суммы размеров списков, соотв. сложность O(n). Задача очень просто решается рекурсивной процедурой.

Если список А не отсортирован, строим из него бинарное дерево и проверяем в нём каждый параметр Б. сложность O(n*log(n)). Получится быстрее, чем сортировать списки.

Re: нужен алгоритм

> Если список А отсортирован И список Б, разумеется, тоже %)

Re: нужен алгоритм

>PS. Хеш-таблица кстати не даст выигрыша. Несмотря на то, что время поиска по ней константно, надо совершить n поисков, где n - размер одного из списков. В результате сложность та же - O(n)

Э.. Откуда n поисков? Когда настройки из списка B грузятся, n=размер списка B?

Ну правда хеш считать надо, тоже время.. а с сортировкой получается минимально различимый хеш надо считать. Можно придумать что-то вроде пути в бинарном дереве, 1 влево, 0 - вправо, 00 или 11 -конец. Получается если список default опций меняться не будет, хеш или путь в дереве не будет меняться.

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

Re: нужен алгоритм

> PS. Хеш-таблица кстати не даст выигрыша. Несмотря на то, что время поиска по ней константно, надо совершить n поисков,

время поиска в хэше константно (в среднем) если его размер хотя бы O(n*ln(n)) Хэш нужно инициализировать. Конечно, вполне вероятно что волшебная связка хардваре+ОС сможет его инициализировать быстрее чем его размер, но все равно, с теоретической точки зрения это некий самообман..

Re: нужен алгоритм

>> Если список А не отсортирован, строим из него бинарное дерево и проверяем в нём каждый параметр Б. сложность O(n*log(n)). Получится быстрее, чем сортировать списки.

Не просто бинарное, а сбалансированное. Список достаточно один раз отсортировать если он еще не отсортирован, зато потом сложность линейная :)))

Re: нужен алгоритм

В догонку...

..а сбалансированное дерево можно построить только из упорядоченного списка :)))

Re: нужен алгоритм

> ..а сбалансированное дерево можно построить только из упорядоченного списка :)))

если они отсортированы, то никаких деревьев строить не нужно. Просто слить их одновременно проходя оба списка: http://en.wikipedia.org/wiki/Merge_algorithm

Re: нужен алгоритм

Ну дык а я о чем и говорю...

Re: нужен алгоритм

ясно, не понял стеба:)