标签: sortedset

在微软文档中，复杂度表示为O(n)

但如果你看看实施情况

  foreach (T item in other)
            {
                if (Contains(item))
                {
                    return true;
                }
            }

，然后对每个元素调用搜索方法，其复杂度为 O(m*log(n))

谁是真正正确的？

在Redis排序集中获取SCORES总和的最佳方法是什么？

合并2组排序值的最快方法是什么？速度(大O)在这里很重要; 不清楚 - 假设这已经完成了数百万次.

假设你不知道值的类型或范围,但有一个高效IComparer<T>和/或IEqualityComparer<T>.

给出以下数字:

var la = new int[] { 1, 2, 4, 5, 9 };
var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

我期待1,2,3,4,5,6,7,8,9.以下存根可用于测试代码:

static void Main(string[] args)
{
    var la = new int[] { 1, 2, 4, 5, 9 };
    var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

    foreach (var item in UnionSorted(la, ra, Int32Comparer.Default))
    {
        Console.Write("{0}, ", item);
    } …

我正在寻找具有有限数量元素的SortedSet的实现.因此,如果添加了更多元素,则指定的最大值比较器决定是否添加项目并从集合中删除最后一个项目.

SortedSet<Integer> t1 = new LimitedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
// [1,3,5]
t1.add(2);
// [1,2,3]
t1.add(9);
// [1,2,3]
t1.add(0);
// [0,1,2]

标准API中是否有一种优雅的方法来实现这一目标？

我写了一个JUnit Test来检查实现:

@Test
public void testLimitedSortedSet() {
final LimitedSortedSet<Integer> t1 = new LimitedSortedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
System.out.println(t1);
// [1,3,5]
t1.add(2);
System.out.println(t1);
// [1,2,3]
t1.add(9);
System.out.println(t1);
// [1,2,3]
t1.add(0);
System.out.println(t1);
// [0,1,2]
Assert.assertTrue(3 == t1.size());
Assert.assertEquals(Integer.valueOf(0), t1.first());
}

假设我们有一个排序集合,例如SortedSet或SortedList,有很多(10M +)元素.大量的查询正在发生,因此性能很重要.从运行时比较,我的印象是,LINQ到对象不采取排序的优势,因此不能服用的潜在性能提升的优势下.

第一个例子 - 计算范围内的元素:

        var mySortedSet1 = new SortedSet<int>();
        // populate ...
        int rangeCount = (from n in mySortedSet1
                          where ((n >= 1000000000) && (n <= 2000000000))
                          select n).Count();

不完全确定LINQ to Objects在内部执行什么操作,最坏的情况是它检查每个元素是否为O(n).通过利用二进制搜索排序O(log n)的下限和上限,可以更快地完成.

第二个示例 - 在集合列表上选择多个:

        var myListOfSortedSets = new List<SortedSet<int>>();
        // populate...

        var q = myListOfSortedSets.SelectMany(s => s).OrderBy(s => s);
        foreach (var n in q)
        {
            Console.WriteLine(n);
        }

如果LINQ to SQL Objects要利用排序,它可以有效拉链 - 将所有已排序的集合合并到O(n)中的一个大型排序列表中.然后可以忽略结果上的.OrderBy,因为列表已经排序.

相反,SelectMany将所有已排序的集合连接成一个大的(现在未排序的)列表,这将需要另一个O(n log n)排序.这可以通过删除.OrderBy并观察元素写入控制台的顺序来轻松验证.

我的问题是:是否已经有一个替代的,更高效的LINQ to SortedSet/SortedList实现？

i4o看起来很有趣,但它似乎需要二级索引集合来提高原始集合的查询性能.我只是希望通过利用排序来对我的已排序集合进行查询以更快地运行.

我应该维护
1.)一个SortedDictionary(double,struct)
2.)或者只是一个普通的Dictionary(double,struct)加一个SortedSet(double)？

我只想要快速插入.我不关心检索,因为我不会做很多查找.我需要排序自然因为,我所做的唯一查找将是最大双倍或几个最大双倍.

我觉得时间表现明智 - 两者都是一样的,SortedSet<double>只做额外的工作.你们能证实吗？

我不知道的部分是维持排序,SortedDictionary仅仅是键(双打),还是键和值的移动.在后一种情况下2.)将胜过1.),不是吗？

此外,尚不清楚SortedDictionary内部如何实施.Sortedset是红黑树,是一个经过验证的表演者.

来自Java Collections Framework的Java教程的练习要求使用SortedSet来消除参数的重复,并指定Comparator,以便在排序和标识set元素时忽略大小写.

这是确切的要求:"获取FindDupsexample并修改它以使用SortedSet而不是Set.指定一个Comparator,以便在排序和识别set元素时忽略大小写."

这是FindDupsExample:

import java.util.*;
public class FindDups {
public static void main(String[] args) {
    Set<String> s = new HashSet<String>();
    for (String a : args)
           s.add(a);
           System.out.println(s.size() + " distinct words: " + s);
}
}

我能想出的最多可以达到预期的行为(通过考虑用小型大写字母写一次的单词来消除重复,而另一次用大大写字母作为副本来消除重复)是下面的代码,但我对如何使用比较器毫无头绪和SortedSet.我在我的例子中使用了SortedSet,但我可以很好地使用一个简单的Set:

public class FindDups {
public static void main(String[] args) {
    Set<String> s = new HashSet<String>();
    List<String> list = new ArrayList<String>();
    SortedSet<String> eliminatedDups = null;

    for (String a : args) {
           s.add(a);
           list.add(a.toLowerCase());
    }
    eliminatedDups = new TreeSet<String>(list);

    System.out.println(s.size() + " distinct …

Redis文档如下：

ZSET 是使用两个数据结构来保存相同元素的有序集合，以便在排序数据结构中进行 O(log(N)) INSERT 和 REMOVE 操作。

这些元素被添加到将 Redis 对象映射到分数的哈希表中。同时，元素被添加到将分数映射到 Redis 对象的跳跃列表中（因此对象在此“视图”中按分数排序）。

我不太明白。有人能给我详细的解释吗？

为什么我会在 aredis sorted set上使用按 unix 时间戳排序的a of 文章redis list并将元素推送到它上面。它们似乎提供了相同的最终结果。我注意到的一件事是，redis sorted set您可以与其他集合和 zset 进行交集

我正在尝试预测使用排序集时 Redis (v6.2.5) 集群上的内存使用情况。从我最初的研究中我可以看出，密钥的长度、每个单独元素的长度以及每个单独分数的长度都会对内存使用产生影响。

这是我到目前为止所拥有的：

• 使用 1 到 8 个字符之间的键、长度为 1 的元素和长度为 1 的分数，我发现使用了 63 字节的内存。
• 9 个字符的密钥会增加 8 个字节（71 个字节）的内存使用量
• 8 个字符密钥、8 个字符元素和 1 个字符分数将使用量增加 4 个字节（75 个字节）
• 8 个字符的键、元素和分数又增加了 4 个字节的使用量 (79)

我可以看到一种模式，但我希望 Redis 专家可以帮助我在源代码中或通过解释 Redis 中排序集的实现来理解这一点。

FWIW，我发现这表明分数存储为长度为128的字符数组。https://github.com/redis/redis/blob/c5e6a6204c4cf57f85e7c83a9b4e99f1a7204fd2/src/t_zset.c#L1029

任何帮助表示赞赏。