C# 中的事件和回调有什么区别？
我有几个加权间隔的列表 - 这些是元组(value, start, stop)：
# 0 1 2 3 4 5 6 7 8 9 10
# 1 [___]
# 2 [___________________________________]
# 3 [_______]
# 8 [_______________________]
# 7 [___________________]
# 6 [___]
# 4 [_______________________]
# input
# (value: float, start: float, stop: float)
list_in = [(2, 0, 9), (3, 0, 2), (8, 1, 7), (4, 1, 7), (1, 3, 4), (5, 5, 10), (6, 8, 9)]
我想找到所有部分重叠并选择“最佳”重叠，即 最大的重叠value。
对于我的示例，正确答案是：
# 0 1 2 3 4 5 6 7 8 9 10
# 1
# 2
# 3 [___]
# 8 [_______________________]
# 7 [___________]
# 6
# 4
# output
list_out = [(3, 0, 1), (8, 1, 7), (7, 7, 10)]
我会尽量保持简单，说明我所拥有的所有条件，但以下是您应该了解的最低限度：
- 输入的元组数组未以任何方式排序
- 我有一个区间树的实现，如果算法性能更高或更简单，请使用它
3）需要考虑-float('inf')区间的开始和float('inf')区间的结束。
- 如果两个间隔的值
value相同，则越短越好。如果它们的长度相同，则它是间隔的精确副本 - 忽略精确副本。 - 忽略具有的间隔
start == stop
如果这对您来说更容易，以下是相对间距的所有可能情况：
# Target interval:
# 0 1 2 3 4 5 6 7 8 9
# [___________]
# All cases for target:
# 0 1 2 3 4 5 6 7 8 9
# [_______]
# [_______]
# [_______]
# [_______]
# [___]
# [_______]
# [_______]
# [_______]
# [___________________]
# [___________]
区间和点的所有情况：
value, start, stop = interval
point = x
point < start
point == start
start < point and point < stop
point == stop
stop < point
我正面解决这个问题的任何尝试都会导致组合爆炸并将代码变成回调地狱
请帮忙。PS：我可以粘贴我的尝试，但它需要 200 行代码，并且开始如下：
def calc_factor(integral_value: float, depth_start: float, depth_stop: float):
return integral_value / (depth_stop - depth_start)
def split_by_intersections(interval_l: IntegralValueInterval, interval_r: IntegralValueInterval):
assert interval_l.depth_start < interval_l.depth_stop
assert interval_r.depth_start < interval_r.depth_stop
assert interval_l.depth_start > -float('inf')
assert interval_l.depth_stop < float('inf')
assert interval_r.depth_start > -float('inf')
assert interval_r.depth_stop < float('inf')
# if-hell I know this, but I don't know how to simplify it.
if interval_l.depth_start < interval_r.depth_start:
if interval_l.depth_stop < interval_r.depth_start:
# L.start L.stop R.start R.stop
return [interval_l, interval_r]
elif interval_l.depth_stop == interval_r.depth_start:
# L.start (L.stop R.start) R.stop
interval_l.depth_stop -= settings.gis_delta_depth
return [interval_l, interval_r]
elif interval_l.depth_stop > interval_r.depth_start and interval_l.depth_stop < interval_r.depth_stop:
# L.start R.start L.stop R.stop
a = interval_l.depth_start
b = interval_r.depth_start
c = interval_l.depth_stop
d = interval_r.depth_stop
interval_l.depth_start = a
interval_l.depth_stop = b - settings.gis_delta_depth
interval_c = IntegralValueInterval()
interval_c.depth_start = b
interval_c.depth_stop = c - settings.gis_delta_depth
left_factor = calc_factor(interval_l.integral_value, interval_c.depth_start, interval_c.depth_stop)
right_factor = calc_factor(interval_r.integral_value, interval_c.depth_start, interval_c.depth_stop)
if left_factor < right_factor:
interval_c.integral_value = interval_r.integral_value
else:
interval_c.integral_value = interval_l.integral_value
interval_r.depth_stop = d
interval_r.depth_start = c
return [interval_l, interval_c, interval_r]
elif interval_l.depth_stop == interval_r.depth_stop:
# L.start R.start (L.stop R.stop)
left_factor = calc_factor(interval_l.integral_value, interval_l.depth_start, interval_l.depth_stop)
right_factor = calc_factor(interval_r.integral_value, interval_r.depth_start, interval_r.depth_stop)
if left_factor < right_factor:
interval_l.depth_stop = interval_r.depth_start - settings.gis_delta_depth
else:
interval_r.depth_start = interval_l.depth_stop
interval_l.depth_stop -= settings.gis_delta_depth
return [interval_l, interval_r]
...
PS 2.0：我尝试为所有情况编写测试，发现不可能考虑到-float('inf')，float('inf')因为存在矛盾的例子，例如，[(2, -float('inf'), 6), (1, -float('inf'), 2)]不清楚哪个段更好。因此，我正在修改这个问题。
PS 3.0：我在代码中附上了“测试”，以便您可以检查您的解决方案。
def test():
for intervals, expected in (
# value left > value right
([(2, 3, 6), (1, 0, 2)], [(1, 0, 2), (2, 3, 6)]),
([(2, 3, 6), (1, 1, 3)], [(1, 1, 3), (2, 3, 6)]),
([(2, 3, 6), (1, 2, 4)], [(1, 2, 3), (2, 3, 6)]),
([(2, 3, 6), (1, 3, 5)], [(2, 3, 6)]),
([(2, 3, 6), (1, 4, 5)], [(2, 3, 6)]),
([(2, 3, 6), (1, 3, 6)], [(2, 3, 6)]),
([(2, 3, 6), (1, 2, 6)], [(1, 2, 3), (2, 3, 6)]),
([(2, 3, 6), (1, 2, 7)], [(1, 2, 3), (2, 3, 6), (1, 6, 7)]),
([(2, 3, 6), (1, 3, 7)], [(2, 3, 6), (1, 6, 7)]),
([(2, 3, 6), (1, 4, 6)], [(2, 3, 6)]),
([(2, 3, 6), (1, 5, 7)], [(2, 3, 6), (1, 6, 7)]),
([(2, 3, 6), (1, 6, 8)], [(2, 3, 6), (1, 6, 8)]),
([(2, 3, 6), (1, 7, 9)], [(2, 3, 6), (1, 7, 9)]),
# value left == value right
([(2, 3, 6), (2, 0, 2)], [(2, 0, 2), (2, 3, 6)]), # 2 / (6 - 3) < 2 / (2 - 0)
([(2, 3, 6), (2, 1, 3)], [(2, 1, 3), (2, 3, 6)]), # 2 / (6 - 3) < 2 / (3 - 1)
([(2, 3, 6), (2, 2, 4)], [(2, 2, 4), (2, 4, 6)]), # 2 / (6 - 3) < 2 / (4 - 2)
([(2, 3, 6), (2, 3, 5)], [(2, 3, 5), (2, 5, 6)]), # 2 / (6 - 3) < 2 / (5 - 3)
([(2, 3, 6), (2, 4, 5)], [(2, 3, 4), (2, 4, 5), (2, 5, 6)]), # 2 / (6 - 3) < 2 / (5 - 4)
([(2, 3, 6), (2, 3, 6)], [(2, 3, 6)]), # 2 / (6 - 3) == 2 / (6 - 3) (copy)
([(2, 3, 6), (2, 2, 6)], [(2, 2, 3), (2, 3, 6)]), # 2 / (6 - 3) > 2 / (6 - 2)
([(2, 3, 6), (2, 2, 7)], [(2, 2, 3), (2, 3, 6), (2, 6, 7)]), # 2 / (6 - 3) > 2 / (7 - 2)
([(2, 3, 6), (2, 3, 7)], [(2, 3, 6), (2, 6, 7)]), # 2 / (6 - 3) > 2 / (7 - 3)
([(2, 3, 6), (2, 4, 6)], [(2, 3, 4), (2, 4, 6)]), # 2 / (6 - 3) < 2 / (6 - 4)
([(2, 3, 6), (2, 5, 7)], [(2, 3, 5), (2, 5, 7)]), # 2 / (6 - 3) < 2 / (7 - 5)
([(2, 3, 6), (2, 6, 8)], [(2, 3, 6), (2, 6, 8)]), # 2 / (6 - 3) < 2 / (8 - 6)
([(2, 3, 6), (2, 7, 9)], [(2, 3, 6), (2, 7, 9)]), # 2 / (6 - 3) < 2 / (9 - 7)
# value left < value right
([(2, 3, 6), (3, 0, 2)], [(3, 0, 2), (2, 3, 6)]),
([(2, 3, 6), (3, 1, 3)], [(3, 1, 3), (2, 3, 6)]),
([(2, 3, 6), (3, 2, 4)], [(3, 2, 4), (2, 4, 6)]),
([(2, 3, 6), (3, 3, 5)], [(3, 3, 5), (2, 5, 6)]),
([(2, 3, 6), (3, 4, 5)], [(2, 3, 4), (3, 4, 5), (2, 5, 6)]),
([(2, 3, 6), (3, 3, 6)], [(3, 3, 6)]),
([(2, 3, 6), (3, 2, 6)], [(3, 2, 6)]),
([(2, 3, 6), (3, 2, 7)], [(3, 2, 7)]),
([(2, 3, 6), (3, 3, 7)], [(3, 3, 7)]),
([(2, 3, 6), (3, 4, 6)], [(2, 3, 4), (3, 4, 6)]),
([(2, 3, 6), (3, 5, 7)], [(2, 3, 5), (3, 5, 7)]),
([(2, 3, 6), (3, 6, 8)], [(2, 3, 6), (3, 6, 8)]),
([(2, 3, 6), (3, 7, 9)], [(2, 3, 6), (3, 7, 9)]),
):
actual = list(max_values(intervals))
if actual != expected:
print(intervals, expected, actual)
test()
有一架飞机，上面有许多不同的物体。如果这很重要，那就让有不同半径的圆或正方形——这并不重要。就说圆圈吧。
对于任意点的任务是快速确定哪个邻域未被占用。也就是说，对于圆，我们只需查看从中心到该点的距离减去圆的半径，然后寻找最小值。
但圈子多，时间少。解决这个问题最简单的方法是什么？我研究了四叉树、R 树。但要么我不太理解他们的想法，要么他们适合找点，但不适合找圆。对于点 - 如果四叉树中最近的点位于相邻象限 - 这对我们有什么帮助？不管怎样，事实证明几乎整棵树都需要重新考虑？
告诉我在这种情况下应该使用什么算法？检查尽可能少的不同圆圈？
首先，我们可以假设这些圆不相交（如果有帮助的话）。但一般来说，这不是事实。
有一个关于用线段覆盖点的经典问题 - 数轴上有 n 个整数点，该问题要求找到能够覆盖所有点的指定长度的线段的最小数量。如果一个点位于线段的边界上，则该点被视为被覆盖。例如，我们有五个坐标为 {1, 2, 3, 4, 5} 的点和单位长度的线段 - 对于这样一个集合，问题的答案将为 3，因为所有点都可以被 3 个线段覆盖 [ 1,2]、[3,4]、[4,5]，这在两个段中不起作用。这个问题可以通过贪心算法轻松解决。
int Cover(std::vector<int>& data, int l) {
//сортируем вектор координат точек
std::sort(data.begin(), data.end());
int interval_count = 1; // количество отрезков
int r_point = data[0] + l; //правая граница последнего установленного отрезка
for(int& elem : data){
if(elem > r_point){
interval_count += 1;
r_point = elem + l;
}
}
return interval_count;
}
所以我对逆问题感兴趣——根据条件，给定一组点和线段数量，找到线段的最小长度。事实上，我没有想出比尝试不同长度更好的方法:(我基于对 (0, data.back() - data.front()) 范围内的长度的二进制搜索构建了我的解决方案。检查搜索中的每个长度 - 它们将覆盖或 k 个长度为 l 的段（按条件），一组数据点（经典问题的修改解决方案）。
bool CanCover(const std::vector<int>& data, int l, int k){
--k;
int r_point = data[0] + l;
for(const int& elem : data){
if(elem > r_point){
--k;
r_point = elem + l;
if (k < 0) return false;
}
}
return true;
}
这是二分搜索本身
int Binary(std::vector<int>& data, int k){
if(k >= data.size()) return 0; //если отрезков больше чем точек, то отрезки могут быть длиной 0 и лежать на каждой из точек
std::sort(data.begin(), data.end());
//границы поиска
int left = 0;
int right = data.back() - data.front();
while(left < right){
int mid = (left + right) / 2;
if(CanCover(data, mid, k)) right = mid;
else left = mid + 1;
}
return left;
}
但测试结果表明，二分查找的解决方案速度不够快。有没有一种方法可以在不遍历所有长度的情况下找到线段的最小长度？像贪婪算法之类的东西，就像经典问题一样？
一个理解语言“内部运作方式”的问题。代码如下：
class NoIter():
def __init__(self):
self.some = [1, 2, 3, 4, 5]
def __getitem__(self, index):
return self.some[index]
t = NoIter()
for item in t:
print(item)
结论：
1
2
3
4
5
问题：
- 为什么一个对象可以被迭代，即使它不包含
__iter__and__next__？ - 为什么
__getitem__在迭代过程中隐式调用它？