数据结构来有效地合并起来，以多集的n个元素 [英] Data structure to efficiently merge up to n elements of multiset

问题描述

我试图解决以下问题。让我们来定义2多集操作：

I am trying to solve the following problem. Let's define 2 multiset operations:

1. | M，E | 操作有序多集为获得最低电子的多重集的元素 M 。例如， | {1,1,2,3,3,4}，4 | = {1,1,2,3}
2. 会替代金额设置 [E，F，G，E] ：
   • [E，F，G，E] = | E + F，E | ，如果多集的E总和的所有元素是偶数，
   • [E，F，G，E] = | E + G，E | ，如果多集的E总和的所有元素为奇数

1. |M,e| operation for an ordered multiset as getting lowest e elements of the multiset M. For example, |{1,1,2,3,3,4},4|={1,1,2,3}.
2. Alternative sum set [E,F,G,e] as:
   • [E,F,G,e]=|E+F,e|, if sum all elements of multiset E is even,
   • [E,F,G,e]=|E+G,e|, if sum all elements of multiset E is odd

例如： [{0,2}，{1,2}，{0,3}，3] = | {0,2} + {1,2}，3 | = | {0,2,1,2}，3 | = | {0,1,2,2}，3 | = {0,1,2}

问题的说法是：给一个家庭的 N 非空自然数多集： X = {X（0），X（1 ），...，X（N-1）} 和数量 M 和 K ，发现多重集在下面的操作的结果的总和： [... [[{}中，x（I_0）中，x（j_0）中，m]中，x（I_1）中，x（j_1），米] ...，X（I_（K-1）），X（J_（K-1）），M] ，即适用 K 倍在启动组替代求和运算（ {} ），对于一些给＆LT; I，J＆GT; 对。

The problem statement is: give a family of n non-empty natural numbers multisets: X={x(0), x(1), …, x(n-1)} and number m and k, find the sum of multiset being the result of the following operation: […[[{},x(i_0),x(j_0),m],x(i_1),x(j_1),m]…,x(i_(k-1)),x(j_(k-1)),m], i.e. applying k times the alternative sum operation on the starting set ({}), for some give <i,j> pairs.

现在我有使用重多集的presentation数组和合并两个多集一样有效，我可以合并两个有序排列，裁剪其规模在同一时间（解决这个问题Ø （L） l为 MIN（）的数组为合并）和求和结果数组，同时大小的。

Right now I have solve this problem using an array representation of multisets and merging two multisets as efficient as I can merge two ordered arrays, cropping its size at the same time (in O(l) where l is min() of the sizes of both arrays being merged) and summing the result array at the same time.

不过，我觉得可能是一个更快的树/堆为基础的解决方案，让我来合并多集速度更快，并保持对多集的更灵活的方式求和信息。

But I think there might be a faster tree/heap-based solution that would allow me to merge the multisets faster and keep information about sum of the multiset in more flexible way.

什么数据结构将在这种情况下，最好的选择？

What data structure would be the best choice in this case?

推荐答案

当然有堆状的数据结构，可以做合并更快，例如的斐波那契堆或配对堆。但是，任何堆数据结构，将在找到M最小输入速度较慢;这几乎总是为O（M的log（n））。如果米的值一般较小，也可能是值得尝试的，但如果m通常没有太多小于N，我猜你现在的解决办法可能是更快的整体。

There certainly are heap-like data structures that can do the merge more quickly, for example the Fibonacci heap or pairing heap. However, any heap-like data structure will be slower at finding the m smallest entries; this will almost always be O(m log(n)). If the values for m are typically small, it could be worth trying, but if m is typically not too much smaller than n, I would guess your current solution is probably faster overall.

这篇关于数据结构来有效地合并起来，以多集的n个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！