Алгоритм: выбор общих элементов коллекции - PullRequest
Новая
       27

Алгоритм: выбор общих элементов коллекции

1 голос
/ 02 декабря 2010

Мне недавно пришлось написать следующий алгоритм:

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

Это сравнение выполняется в памяти - доступ к любой коллекции не вызывает отключение по сети (т. е. к базе данных и т. д.).

Кроме того, коллекция Tags не имеет ссылки на BlogPosts, в которой она содержится.У BlogPosts есть коллекция Tags, которую они содержат.

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

Моя реализация в Actionscript, но мне любопытно больше с точки зрения алгоритма, поэтому примеры на любом языке хороши,(Но если я не знаю язык, я могу попросить вас уточнить некоторые аспекты)

Любые примеры улучшений будут очень приветствоваться. 

    private function getCommonTags(blogPosts:Vector.<BlogPost>):Vector.<Tag>
    {
        var commonTags:Vector.<Tag> = new Vector.<Tag>();
        if (!blogPosts || blogPosts.length == 0)
            return commonTags;

        var blogPost:BlogPost = blogPosts[0];
        if (!blogPost.tags || blogPost.tags.length == 0)
            return commonTags;

        commonTags = Vector.<Tag>(blogPosts[0].tags);

        for each (var blogPost:BlogPost in blogPosts)
        {
            if (!blogPost.tags || blogPost.tags.length == 0 || commonTags.length == 0)
                // Updated to fix bug mentioned below
                // Optomized exit - there are no common tags
                return new Vector.<Tag>();

            for each (var tag:Tag in commonTags)
            {
                if (!blogPost.containsTagId(tag.id))
                {
                    commonTags.splice(commonTags.indexOf(tag),1);
                }
            }
        }
        return commonTags;
    }

Ответы [ 2 ]

1 голос
/ 02 декабря 2010

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

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

0 голосов
/ 03 декабря 2010

Я могу сформулировать эту программу в английском предложении: «Вернуть все теги, которые встречаются равномерно среди сообщений.»

Давая имя all_tags списку тегов и post_tags списку тегов, связанных с сообщениями, я могу сказать то же самое с этим предложением на языке программирования J 

   all_tags #~ (#=+/) all_tags e.&>"_ 0 post_tags

Рассмотрим это подробнее:

  • #~ означает «копия где»

  • (# = +/) означает «сумма равна сумме»

  • e. означает «существует в»

  • &>"_ 0 изменяет e., поэтому все значения all_tags сравниваются с каждым из наборов тегов в post_tags

Если мы хотим сделать это программой, которая принимает два аргумента, а не программой, специфичной для этих именованных списков, соответствующая программа может быть: 

   common_to=:  [ #~ [:(#=+/) [ e.&>"_ 0 ]

Запуск этой программы с теми же именами данных будет выглядеть так: 

   all_tags common_to post_tags

Кажется, стоит отметить, что нам на самом деле не нужен полный список тегов, так как его можно получить. (Расчет ~. ; post_tags.) Это означает, что мы могли бы написать программу, которая бы принимала только один аргумент. Но так как проблема предполагает, что у нас уже есть список all_tags, нет необходимости вычислять его снова.

...