Open ad1510875353 opened 6 months ago
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。
void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } }
另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
当插入第一个元素(i为0)的时候,不应该考虑上滤
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。
void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } }
另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
我怎么感觉他做的这个是最大堆呢,父节点比子节点大
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。
void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } }
另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
确实,这里需要修改一下
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。 void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } } 另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
我怎么感觉他做的这个是最大堆呢,父节点比子节点大
父节点比子节点大是最小堆的意思,堆顶是最小的,老哥复习一下数据结构
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。 void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } } 另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
我怎么感觉他做的这个是最大堆呢,父节点比子节点大
父节点比子节点大是最小堆的意思,堆顶是最小的,老哥复习一下数据结构
要不你再查查?最大堆是父节点比子节点大
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。 void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } } 另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
我怎么感觉他做的这个是最大堆呢,父节点比子节点大
父节点比子节点大是最小堆的意思,堆顶是最小的,老哥复习一下数据结构
要不你再查查?最大堆是父节点比子节点大
不好意思打错字了...,原作者实现的是小顶堆:
size_t j = (i - 1) / 2;
if (heap_[j] < heap_[i]) {
break;
}
j是父节点的索引,只要父节点的值大于子节点就进行交换,否则跳出循环,也就是用vector模拟小顶堆。
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。
void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } }
另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。
另外在GetNextTick中也有一个同样的小问题,作者直接令size_t res = -1,size_t 是无符号类型,如果尝试将 -1 赋值给它,会得到一个非常大的数
在原先的堆上滤的函数中,由于i是无符号数,因此会将与其进行运算的数全部转为无符号数,包括结果,因此当i==0时,i-1的结果是一个很大的整数,从而导致j超过了vector的size,从而导致了溢出。因此可以改成以下形式。
void HeapTimer::siftup_(sizet i) { assert(i >= 0 && i < heap.size()); sizet j = (i - 1) / 2; while (j >= 0 && i > 0 && heap[j] < heap[i]) { SwapNode(i, j); i = j; j = (i - 1) / 2; } }
另外,作者代码里使用了大量assert来方便调试,但是实际使用时这些判断会影响服务器性能,因此性能测试时构建release版本,可以提高服务器性能。