p*****2
发帖数: 21240 | 1 public void Add(Task task)
{
int i=0;
for(;i
{
if(task.deadline
{
list.Insert(i,task);
break;
}
}
if(i==list.Count)
list.Add(task);
}
public void Add(Task task)
{
if (list.Count == 0)
{
list.Add(task);
return;
}
int start = 0;
int end = list.Count - 1;
while (start <= end)
{
if (start == end)
{
if (list[start].deadline > task.deadline)
list.Insert(start, task);
else
list.Insert(start + 1, task);
return;
}
int mid = (start + end) / 2;
if (list[mid].deadline == task.deadline)
{
list.Insert(mid, task);
return;
}
if (list[mid].deadline < task.deadline)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
}
} |
c**********e
发帖数: 2007 | 2 How do you know it is slower than linear? Is your n large enough? |
q****x
发帖数: 7404 | 3 你的二分法罗嗦。
【在 p*****2 的大作中提到】
: public void Add(Task task)
: {
: int i=0;
: for(;i: {
: if(task.deadline: {
: list.Insert(i,task);
: break;
: }
|
L*****R
发帖数: 56 | |
p*****2
发帖数: 21240 | 5 我做一道题，linear能pass 50%的test case， binary 只能过10%。虽然写的罗嗦，但
是还是很奇怪为什么这样子。
我后来从后往前linear search, 还是这个结果。 |
f*******t
发帖数: 7549 | 6 你这个是java的arraylist?
insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
。 |
q****x
发帖数: 7404 | 7 不是list吗？
【在 f*******t 的大作中提到】
: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。
|
r****t
发帖数: 10904 | 8 arraylist 有 random access 吗？insert 该没有关系，两个办法最后都是 insert 一次。
话说你这个 binary search 有私货，找到以后 return iterator 好了，为啥要 insert 呢？
【在 f*******t 的大作中提到】
: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。
|
f*******t
发帖数: 7549 | 9 list不能random access
【在 q****x 的大作中提到】
: 不是list吗？
|
q****x
发帖数: 7404 | 10 good catch, thx.
【在 f*******t 的大作中提到】
: list不能random access
|
|
|
p*****2
发帖数: 21240 | 11
一次。
insert 呢？
return iterator什么意思呀？我insert是因为下次还需要用。
【在 r****t 的大作中提到】
: arraylist 有 random access 吗？insert 该没有关系，两个办法最后都是 insert 一次。
: 话说你这个 binary search 有私货，找到以后 return iterator 好了，为啥要 insert 呢？
|
q****x
发帖数: 7404 | 12 你算法有问题。
如果是数组，插入是线性的。
如果是链表，二分查找不行。
【在 p*****2 的大作中提到】
:
: 一次。
: insert 呢？
: return iterator什么意思呀？我insert是因为下次还需要用。
|
r****t
发帖数: 10904 | 13 只 pass 部分估计是边界条件没搞对。自己能搞点 test case 么？
【在 p*****2 的大作中提到】
: 我做一道题，linear能pass 50%的test case， binary 只能过10%。虽然写的罗嗦，但
: 是还是很奇怪为什么这样子。
: 我后来从后往前linear search, 还是这个结果。
|
r****t
发帖数: 10904 | 14 c++ 里面 search 都返回 iterator/pointer, 以为 java 应该更自然点。。。
【在 p*****2 的大作中提到】
:
: 一次。
: insert 呢？
: return iterator什么意思呀？我insert是因为下次还需要用。
|
q****x
发帖数: 7404 | 15 bool std::binary_search()
【在 r****t 的大作中提到】
: c++ 里面 search 都返回 iterator/pointer, 以为 java 应该更自然点。。。
|
p*****2
发帖数: 21240 | 16
相当于java 的 arraylist, 关键是两种算法都有insert呀。
【在 q****x 的大作中提到】
: 你算法有问题。
: 如果是数组，插入是线性的。
: 如果是链表，二分查找不行。
|
q****x
发帖数: 7404 | 17 你怎么知道慢？
【在 p*****2 的大作中提到】
:
: 相当于java 的 arraylist, 关键是两种算法都有insert呀。
|
p*****2
发帖数: 21240 | 18
test case 运行到50%超时， binary运行到10%就超时了。很奇怪。
【在 q****x 的大作中提到】
: 你怎么知道慢？
|
r****t
发帖数: 10904 | 19 okay, 原来只要返回 true/false 就行了。
【在 q****x 的大作中提到】
: bool std::binary_search()
|
x***2
发帖数: 93 | 20 同意这个观点。
楼主不妨注释掉insert操作再跑一次
【在 f*******t 的大作中提到】
: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。
|
a**p
发帖数: 258 | 21 同意楼上说的。search是重点。写了点玩玩，看看对不对。
public class Test {
Task[] list;
int search(Task task) {
int i = 0;
do {
if (task.deadline <= list[i].deadline) {
return i;
}
} while (++i < list.length);
return list.length-1;
}
int binarySearch(Task task) {
int i = list.length;
int k = 0;
int j;
do {
if ((i+1 + k) % 2 != 0){
j = (i+k)/2;
} else{
j = (i+1 + k)/2;
}
if (j == i) {
if (task.deadline >= list[i-1].deadline) {
return i-1;
} else {
return i;
}
} else {
if (task.deadline >= list[j].deadline) {
k = j;
} else {
i = j;
j = 0;
}
}
} while (j < i);
return j;
}
public static void main(String[] args) {
int size = 5*1000*1000;
Test test = new Test();
test.list = new Task[size];
Task task;
for (int i = 0; i < size; i++) {
task = new Task(i);
test.list[i] = task;
}
Task t = new Task((int) (Math.random() * size));
System.out.println("list size:"+size+"; deadline:"+t.deadline);
long time = System.currentTimeMillis();
System.out.println("index: " + test.search(t));
System.out.println(System.currentTimeMillis() - time);
time = System.currentTimeMillis();
System.out.println("index: " + test.binarySearch(t));
System.out.println(System.currentTimeMillis() - time);
}
}
class Task {
int deadline;
Task(int i){
deadline = i;
}
} |
