标签: bag

抱歉,我无法为以下算法提出算法或问题的名称.我将陈述问题,然后我尝试过,也许有人可以指出我正确的方向.

想象一下,你有一袋物品(无序,重复允许).在实践中,袋子可以包含2-20个物品,以防这种放松有帮助.

目标是找到最小长度链(如果我们有不同的链概念,有序链接列表),其中包含任何顺序的包中的所有项目.

链包含一个开始标记(不存在于包中),后跟任意数量的项目,后跟一个结束标记(也不在包中).

链是通过拼凑n元组形成的(顺序很重要),作为进一步的放松,让我们说n值对于所有元组是相同的.在实践中,我正在使用n = 3.链条可以"混合"而不是连接,如果它们具有重叠元素.例如,考虑(a,b,c)和(c,d,e).可以作为(a,b,c,d,e)连接.同样地,(a,b,c)和(b,c,d)可以连接为(a,b,c,d).一些元组可能在第一个位置具有开始标记,并且一些标记在最后位置具有结束标记,这当然允许存在解决问题的方法.

因此,在我看来,问题的确切解决方案通常是不易处理的.为了获得问题的"好"解决方案,需要某种优化算法.我可以忍受的"好"解决方案.

我开始的是一种贪婪的方法,在第一次通过时,你会发现包含袋中元素数量最多的元组,任意打破关系.创建一个数据结构,它保存我们迄今为止构建的链,并将选定的元组粘贴到此数据结构中.将问题拆分为2个子问题,即开始令牌侧和结束令牌侧.在子问题1的数据结构的第一个标记是起始标记并且子问题2的最后一个标记是结束标记之前,增长链以使我们尽快找到停止条件(开始或结束标记取决于在子问题上,同时也试图尽快排出袋子的内容.

有人在任何地方看到这个问 有关如何改进(或正常工作)此算法的任何想法？这是我正在解决的一个真正的问题,它是一个更大系统的智能部分,不是玩具问题或家庭作业问题.

编辑

对不起我今天一直远离电脑.我将尝试发布一个示例解决方案,该解决方案不是太微不足道,但也不会太复杂.

鉴于:

1. Bag = {A, B, C, D} (为了示例,我把它设为一组,但每个项目可以出现多次)
2. / = Start Token
3. \ = End Token

4. 3元组(三元组):为了简化命名,我将它们标记为ag.小写字母在问题中没有实际功能.

   (/,A, E) a
   (/,C, D) b
   (/,G, H) c
   (D,B, A) d
   (C,G, H) e
   (B,A, \) f
   (G,H, \) g
   

   Run Code Online (Sandbox Code Playgroud)

解决方案:如果我们将b,d和f链接在一起,我们就会得到(/,C,D,B,A,\).
这是包含包中所有元素的最短链,如果计算开始和结束标记,则该长度为6.通常,最短路径的长度为| BAG | + 2,如果它确实存在.我希望我的问题陈述现在更有意义.

我希望这个问题具体到足以被认为适合StackOverflow.我检查了常见问题解答,我认为这符合资格,因为它是特定的并且与编程有关.

我正在Java中实现复杂的数据挖掘算法(FP-growth).算法的一些初始阶段要求我扫描大型数据库并保持找到的每个项目类型的运行计数.这似乎非常适合Hashbag界面.我在Apache Commons中找到了一个似乎对我有用的东西.

所以现在,我的HashBag填充了[itemType,count]条目(对).稍后在算法中,我需要在这些对上做很多类似列表的操作.在某些情况下,我必须按itemType对集合进行排序.在其他人中,我必须按计数排序.这似乎非常适合List界面.

我得出的结论是,我必须将我的Hasbag转换为List.但它在某种程度上感觉很脏,就像浪费空间和时间.是否有一种更聪明的方法可以做到这一点,或者是一个常见的情况,如果你必须在不同的时间以不同的方式处理你的收藏,那么转换是必要的恶魔？

另一种方法是制作我自己的界面,这是一个真正的列表,但允许"袋式"添加.每次我想添加一些东西时,我必须保持列表排序并使用自定义比较器执行二进制搜索.构建该集合可能比构建Hashbag需要更长的时间,但我会在最后保存转换步骤.有什么想法更好吗？

谢谢!

是否有任何工具可以在C#中为字符串创建Bag of Words模型和计算特征向量？像pythons CountVectorizer之类的东西:

vectorizer = CountVectorizer(analyzer = "word",   
                         tokenizer = None,    
                         preprocessor = None, 
                         stop_words = None,   
                         max_features = 1000)

我目前正在研究算法和数据结构,当我阅读Book of Algorithms第4版时,我发现了Bag数据结构以及Stack和Queue.读它的解释后,仍然不清楚我,我会更喜欢使用什么Bag(它没有remove()比其他的数据结构,如法)Stack,Queue,LinkedList还是Set？据我所知,本书的实现与a Bag相同Stack,只是替换了push()to 的名称add()并删除了该pop()方法.

所以a的想法Bag基本上是能够收集物品然后遍历收集的物品,检查行李是否为空并找到其中的物品数量.但在哪种情况下我会更好地使用Bag上面提到的一个以上的集合？为什么一个基本上Bag没有remove()方法？它有特定的原因吗？

提前致谢.

而不是实现我自己,我想知道是否有人知道我可以使用Objective-C中的直方图或包数据结构实现.

本质上,直方图是列表的散列映射,其中列表包含与其散列条目相关的值.一个很好的例子是超市物品的直方图,您可以将每组物品放入奶瓶,肉类,罐头食品中.然后,您可以根据其类型轻松访问每组项目.

我有一对对象列表.对象可以按任意顺序出现在对中.什么是最有效的算法(和实现？)来找到相同对象之间的所有包(即允许重复的集合).为了我的目的,可以假定对象引用是指针,或名称或一些类似的方便,简短,有用的表示.单个对是可识别的.在该对的两个部分中没有对具有相同的对象.

所以给出一对对列表(Oid是一个对象引用; Pid一对引用)

O1-P1-O2
O3-P2-O4
O5-P3-O1
O1-P4-O2
O2-P5-O1
O1-P6-O5
O7-P7-O8

应该返回:

P1;P4;P5 and P3;P6

研究该主题,可以找到作者使用"Bag of Words"模型进行图像分类/检索的论文,而其他人使用"Bag of features"模型进行类似的任务.

即使我对所涉及的方法有基本的了解(检测和提取视觉词,构建视觉词典,使用机器学习来训练分类器),我仍然看不出两种模型之间的差异.他们是同义词吗？也许我错过了显示差异的具体示例/文档......

我有一个需要根据某些条件进行过滤的项目列表。我想知道 Dask 是否可以并行执行此过滤，因为列表很长（几十万条记录）。

基本上，我需要做的是：

items = [
    {'type': 'dog', 'weight': 10},
    {'type': 'dog', 'weight': 20},
    {'type': 'cat', 'weight': 15},
    {'type': 'dog', 'weight': 30},
]

def item_is_valid(item):
    item_is_valid = True

    if item['type']=='cat':
        item_is_valid = False
    elif item['weight']>20:
        item_is_valid = False
    # ...
    # elif for n conditions

    return item_is_valid

items_filtered = [item for item in items if item_is_valid(item)]

通过 Dask，我实现了以下目标：

def item_is_valid_v2(item):
    """Return the whole item if valid."""
    item_is_valid = True

    if item['type']=='cat':
        item_is_valid = False
    elif item['weight']>20:
        item_is_valid = False …

我刚刚看到一个关于System.Collections.ConcurrentBag<T>类的SO问题,我已经看到了ASP.NET MVC 的ViewBag属性Controller.根据我的经验,我已经了解到如果你理解他们在撰写文章时到底得到了什么,那么使用人们的代码会更容易.我认为它非常直观地表示a List<T>或a Dictionary<TKey,TValue>或a ReadOnlyCollection<T>表示什么.Bag另一方面,A 不是那么直观.

所以,我的问题是:这个比喻的意思是什么Bag,特别是关于.NET框架？

袋装成阵列。我知道我们可以根据需要更改袋子的大小等。但是，由于它存储在数组中，因此它基本上有一个索引号，对吗？在这种情况下，为什么我们仍然说它是无序的？