|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-31
luke_kai 写道 import java.util.Random;
import java.util.Set; import java.util.TreeSet; public class TestSF { public static Set<Integer> getTop100(int[] inputArray) { TreeSet<Integer> top100 = new TreeSet(); for (int i = 0; i < inputArray.length; i++) { if (top100.size()<100){ top100.add(inputArray[i]); }else if ((Integer)top100.first()<inputArray[i]){ Object obj = top100.first(); top100.remove(obj); top100.add(inputArray[i]); } } return top100; } public static void main(String[] args) { int numberCount = 100000000; int maxNumber = numberCount; int inputArray[] = new int[numberCount]; Random random = new Random(); for (int i = 0; i < numberCount; ++i) { inputArray[i] = Math.abs(random.nextInt(maxNumber)); } System.out.println("Sort begin..."); long current = System.currentTimeMillis(); Set<Integer> result = TestSF.getTop100(inputArray); System.out.println("Spend time:"+(System.currentTimeMillis() - current)); } } 这个是比较快我的机器上一亿才用2.7秒 |
| 返回顶楼 | |
|
发表时间：2010-03-31
luke_kai 写道 zwhc 写道 luke_kai 写道 zwhc 写道 luke_kai 写道 不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375 要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。 算进去，大概是 10 秒左右。在我机子上。 初始化时间不能算啊，我们讨论的是算法的时间。楼主的也没算，这样才好对比嘛。 应该要算的。题目没有要求你初始化这么大的一个数组啊。别人不用初始化大数组的方式，怎么对比？ 你这种说法有点投机取巧啊。实际应用中，数据应该另有来源。 我改了一下，不初始化数组，也是6秒多。 import java.util.Random; import java.util.Set; import java.util.TreeSet; public class TestSF { public static Set<Integer> getTop100(int inputCount) { TreeSet<Integer> top100 = new TreeSet(); Random random = new Random(); for (int i = 0; i < inputCount; i++) { int numb = random.nextInt(inputCount); if (top100.size()<100){ top100.add(numb); }else if ((Integer)top100.first()<numb){ Object obj = top100.first(); top100.remove(obj); top100.add(numb); } } return top100; } public static void main(String[] args) { int numberCount = 100000000; int maxNumber = numberCount; // int inputArray[] = new int[numberCount]; // Random random = new Random(); // // for (int i = 0; i < numberCount; ++i) { // // inputArray[i] = Math.abs(random.nextInt(maxNumber)); // // } System.out.println("Sort begin..."); long current = System.currentTimeMillis(); Set<Integer> result = TestSF.getTop100(numberCount); System.out.println("Spend time:"+(System.currentTimeMillis() - current)); // for (Integer i :result) { // System.out.print(result+ ","); // } } } top100.first() 操作次数太多了。我刚才试了一下你这代码，9 秒多。加个中间变量就变成 6 秒左右了。 看来 top100.first() 很花时间。 另外，我测了一下，random.nextInt 一亿次，是 5 秒多，也就是说，实际的排序，只要半秒多。 |
| 返回顶楼 | |
|
发表时间：2010-03-31
最后修改：2010-03-31
public class AppMain {
private final static Random rnd = new Random();
public static int[] top(int[] data, int count) {
LinkedList<Integer> topNums = new LinkedList<Integer>();
topNums.add(Integer.MIN_VALUE);
for (int i : data) {
if (topNums.getLast() > i) {
if (topNums.size() < count) {
topNums.add(i);
}
continue;
}
for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
if (i > iter.next()) {
iter.previous();
iter.add(i);
if (topNums.size() > count) {
topNums.removeLast();
}
break;
}
}
}
int[] result = new int[count];
for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
result[iter.nextIndex()] = iter.next();
}
return result;
}
public static void main(String[] args) {
int n = 100000000;
int[] ia = new int[n];
for (int i = 0; i < n; i++) {
ia[i] = rnd.nextInt(n);
}
long start = System.currentTimeMillis();
int[] result = top(ia, 100);
System.out.println(System.currentTimeMillis() - start + "ms");
for (int i : result) {
System.out.println(i);
}
}
}
|
| 返回顶楼 | |
|
发表时间：2010-03-31
哈哈，拿MapReduce做啦
|
| 返回顶楼 | |
|
发表时间：2010-03-31
cat test.txt | sort -nr | head -n10
|
| 返回顶楼 | |
|
发表时间：2010-03-31
插入数据库，这么多数据不会有存在文件的业务使用环境的
然后嘛 sybase: select top 100 * from table oracle: select * from table where rownum<100 
|
| 返回顶楼 | |
|
发表时间：2010-03-31
用treeset实现 1亿条数据内存不够
1000W条 234ms |
| 返回顶楼 | |
|
发表时间：2010-03-31
ldinh 写道
public class AppMain {
private final static Random rnd = new Random();
public static int[] top(int[] data, int count) {
LinkedList<Integer> topNums = new LinkedList<Integer>();
topNums.add(Integer.MIN_VALUE);
for (int i : data) {
if (topNums.getLast() > i) {
if (topNums.size() < count) {
topNums.add(i);
}
continue;
}
for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
if (i > iter.next()) {
iter.previous();
iter.add(i);
if (topNums.size() > count) {
topNums.removeLast();
}
break;
}
}
}
int[] result = new int[count];
for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
result[iter.nextIndex()] = iter.next();
}
return result;
}
public static void main(String[] args) {
int n = 100000000;
int[] ia = new int[n];
for (int i = 0; i < n; i++) {
ia[i] = rnd.nextInt(n);
}
long start = System.currentTimeMillis();
int[] result = top(ia, 100);
System.out.println(System.currentTimeMillis() - start + "ms");
for (int i : result) {
System.out.println(i);
}
}
}
你。。。这是冒泡吧。。。 如果取 top 10000 的话，好象很慢啊。 |
| 返回顶楼 | |
|
发表时间：2010-03-31
你自己那个不就是自己构造了一个有序树,难道你自己都不知道的吗?
|
| 返回顶楼 | |
|
发表时间：2010-03-31
针对这道题优化下算法：
public static int[] findTop100(int[] numbers) {
int[] findNum = new int[100];
int temp = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] > findNum[99]) {
findNum[99] = numbers[i];
}
for (int j = 99; j > 0; j--) {
if (findNum[j] > findNum[j - 1]) {
temp = findNum[j - 1];
findNum[j - 1] = findNum[j];
findNum[j] = temp;
} else {
break;
}
}
}
return findNum;
}
本人机器上1.1秒左右( E2160 * 2G ) |
| 返回顶楼 | |
