标签: sortedset

该场景是事件的时间线，我希望能够查询特定日期范围内的所有项目。

我正在寻找 .NET（最高 v4.0）中的数据结构，该结构将项目存储为排序且唯一的（例如，通过使用比较器或唯一键）。它应该支持不超过对数复杂度的添加/删除，并以该复杂度执行二分搜索。

System.Collections.Generic.SortedSet看起来像我想要的，但它的GetViewBetween()方法返回一个包含项目的列表，作为 SortedSet。

我遗漏了两件事：

1. 调用ToList()或枚举 SortedSet 的成本太高，因为列表很长。我需要方法返回 a List<T>，而不是 a SortedSet<T>。
2. 根据我的选择，使用包含/排除日期范围来调用它 - 不可能，我也需要它。

如果您知道一个包含这样的数据结构的好库，并且经过测试并且熟悉，我肯定会尝试一下。

谢谢。

考虑具有以下成员的Redis排序集:

ZADD mySortedSet 11 "A"
ZADD mySortedSet 21 "B"
ZADD mySortedSet 32 "C"
ZADD mySortedSet 46 "D"
ZADD mySortedSet 53 "E"
ZADD mySortedSet 68 "F"
ZADD mySortedSet 72 "G"
ZADD mySortedSet 82 "H" 
ZADD mySortedSet 94 "I"
ZADD mySortedSet 104 "J"
ZADD mySortedSet 113 "K"

如果我想以相反的顺序进行分页,从任意切片开始,我可以从这开始:

// Returns G, F, E, as expected.
ZREVRANGEBYSCORE mySortedSet 72 (46

现在,只知道我的上限是46,我可以得到集合中的前3个项目,D,C和B,而不知道下限:

ZREVRANGEBYSCORE mySortedSet 46 -inf LIMIT 0, 3

我的问题是,我怎么能按顺序得到集合中的下3个项目,J,I和H,只知道上限为72？

// Good start, returns K, J, I, H
ZREVRANGEBYSCORE mySortedSet +inf (72

// Returns …

我正在使用 Redis 排序集来存储我正在处理的项目的排名。我们没有预料到（！）我们想要如何处理关系。Redis 按字典顺序对具有相同分数的条目进行排序，但我们想要做的是对具有相同分数的所有条目给予相同的排名，例如在以下情况

redis 127.0.0.1:6379> ZREVRANGE foo 0 -1 WITHSCORES
1) "first"
2) "3"
3) "second3"
4) "2"
5) "second2"
6) "2"
7) "second1"
8) "2"
9) "fifth"
10) "1"

我们要考虑second1、second2和，second3因为它们都具有位置 2，并且fifth具有位置 5。因此，第三或第四位置没有条目。 ZREVRANK在这里没有用，那么获得我正在寻找的号码的最佳方法是什么？

我在内存中已经有一个已经排序的大小(N)并想要将其转储到redis中,如果首先插入头部或尾部,是否可以在O(N)中完成？或者没关系,插入将是O(log(N!))〜O(N log(N))

有关更多详细信息,redis排序集使用散列映射和跳转列表(用于排序)实现.

编辑:这个问题仍然没有答案,因为相当多,或者至少答案对我来说有点模棱两可:Redis:当插入的元素在开头或结尾时,ZADD是否优于O(logN)？

sorted-setClojure 有一个创建对象的函数PersistentTreeSet。顾名思义，sorted-set创建唯一对象的排序集合。

排序集什么时候有用？什么时候使用sorted-setandsort更好distinct？

=> (apply sorted-set [2 2 1 1 3 3])
#{1 2 3}
=> (sort (distinct [2 2 1 1 3 3]))
(1 2 3)

我有一个 SortedSet，我要向其中添加项目（以不受控制的顺序，显然利用了它的排序能力）。

集合中的物品总是按顺序使用和移除，一次一个。

set.Min.Process();
set.Remove(set.Min);

然而，我面临的问题是由于 Remove 方法的 O(log n) 方面以及 SortedSet 的二分搜索性质，这导致每次删除时进行最大可能的比较次数（~log n ）。

对我来说，基于访问最小和最大项目的集合没有有效的方法来删除它们，这似乎很奇怪。

实际上，我所追求的是 set.RemoveMin() 方法，利用更优化的方法（无比较）来获取第一个元素。

有什么办法可以做到这一点吗？是否有我可以利用的现有替代 SortedSet 实现？

我们正在运行 Redis，每秒对排序集中的键进行数百次增量，同时每秒对排序集进行数千次读取。

这似乎运行良好，但在峰值负载期间，CPU 使用率变得相当高，为单核的 80%。排序集本身占用的内存很小，只有几千个键。

CPU 使用率的增加是否可能是由于每秒数百次增量或数千次读取造成的？了解两者对性能的影响，但哪个影响更大？

鉴于此，在我的生产实例上监控以检查这些瓶颈的最佳指标是什么？

谷歌番石榴有一个SortedSetMultimap.精彩.现在哪里是不可变版本？有一个ImmutableSetMultimap.但那怎么样ImmutableSortedSetMultimap？(请不要回答"你为什么想要一个？")

有没有一种简单的方法可以在 Redis 中创建一个空的排序集？该文件指出

如果键不存在，则会创建一个新的排序集，将指定成员作为唯一成员，就像排序集为空一样。如果键存在但不包含排序集，则返回错误。

但是，它并没有说您可以创建一个空的排序集。以下不会创建空的排序集：

127.0.0.1:6379> zadd likes:0 1 one
(integer) 1
127.0.0.1:6379> exists likes:0
(integer) 1
127.0.0.1:6379> zcard likes:0
(integer) 1
127.0.0.1:6379> dbsize
(integer) 1
127.0.0.1:6379> zrem likes:0 one
(integer) 1
127.0.0.1:6379> exists likes:0
(integer) 0

用例是可靠地将数据从另一个数据库迁移到 Redis，即 Postgres：

1. 创建帖子时，创建一个空的排序集 likes:<postId>
2. 创建喜欢时，执行zadd likes:<postId> <createdAt> <userId>if exists likes:<postId。否则，查询 Postgres 以获得喜欢，并将它们存储在likes:<postId>.

创建一个空的排序集可以启用断言，当第一个喜欢该帖子时删除对 Postgres 的过多查询，但仍然支持尚未迁移到 Redis 的帖子。此优化将每天为我们的数据库节省 10 万次以上的读取次数。

SortedSet迭代该集合时,将元素添加到可修改是否安全？特别是,将元素添加到集合中的元素比迭代器指示的元素更安全吗？

例如,以下代码是否会破坏SortedSet s或抛出异常(可能是a ConcurrentModificationException):

 /**
  * s not null, is modifiable.
  */
 private final addSelectedFollowers(final SortedSet<Integer> s)
 {
    for (Integer i: s) {
       if (shouldAddNext(i)) {
          s.add(i + 1);
       }
    }
 }

 protected abstract boolean shouldAddNext(int i);

我的猜测是它是安全的,但我在JRE API文档中找不到明确的声明.我知道如果没有指定行为,实现可以自由决定行为.文件中缺乏明确的陈述SortedSet 不足以以某种方式回答这个问题; 可以在不同类或接口的文档中间接指定所需行为.遗憾的是,JRE记录员并不总是明确说明允许的内容.因此,我正在寻找引用JRE API的答案,而不是赞成或否定的秃头断言.我也知道a SortedSet可以不可修改,这会导致SortedSet.add()失败; 我对可修改的情况感兴趣SortedSet.

请注意,我要求向集合中添加元素,而不是修改集合中的元素.