相关疑难解决方法(0)

可能重复:
Python"is"运算符使用整数意外运行

我偶然发现了以下Python的怪异性:

>>> two = 2
>>> ii = 2

>>> id(two) == id(ii)
True
>>> [id(i) for i in [42,42,42,42]]
[10084276, 10084276, 10084276, 10084276]

>>> help(id)
Help on built-in function id in module __builtin__:

id(...)
    id(object) -> integer

    Return the identity of an object.  This is guaranteed to be unique among
    simultaneously existing objects.  (Hint: it's the object's memory address.)

1. 每个数字都是唯一的对象吗？
2. 不同的变量是否保持相同的元素值(例如,2,ii)是同一个对象？
3. Python生成的数字的id是多少？
4. 在上面的例子中,是指向保持值为2的存储单元的两个和二个指针吗？那将是非常奇怪的.

帮助我解决这种身份危机.

更奇怪的是:

>>> a,b=id(0),id(1)
>>> for i in range(2,1000):
   a,b=b,id(i)
   if abs(a-b) …

假设您在内存中有大量连续的整数,每个整数属于一个类别.两个操作必须是O(log n):将范围从一个类别移动到另一个类别,并查找给定范围的类别计数.

我很确定第二次操作是在第一次操作的正确实现的情况下解决的.

每个整数都从一个类别开始,所以我从一组平衡的BST开始.将子树从一个BST移动到另一个BST(例如,将范围移动到另一个类别)具有相当于合并两个BST的运行时间,即O(n1*n2)[ 1 ].

这太慢了(在python中,C不是一个选项),我无法找到一种方法来利用我的数据的固有结构来创建一个有效的BST合并操作.

我现在正在研究AVL,红黑和间隔树,二进制堆和treaps.比较他们的属性是压倒性的.我应该使用哪种结构？

编辑(问题澄清):我对如何存储这些值并创建数据结构很灵活.关于我如何接收来自其他应用程序的输入,我不灵活,如下所示:CATEGORY(cat3, I, J).我当前的解决方案创建了一个树,其中包含该范围中每个整数的节点.这对于我的数据集的大小来说太慢了,所以如果给出更好的方法,我很乐意重新设计.

任何给定的请求都可以将任何可能的整数范围移动到任何类别中.换句话说,范围在CATEGORY(cat1, 1, 10)后面的意义上是重叠的CATEGORY(cat3, 5, 15),但是在任何给定时间每个整数将恰好属于一个类别的意义上是非重叠的.