求解 算法 及 程序优化 面试题

Question

for(int i =0;i<1000;i++){
   for(int j =0;j<100;j++){
        for(int z=0;z<10;z++){
             function(i,j,z);
         }
   }
}
以上代码片段如何优化，并解释理由。
another：给你一个单项链表，要你用方法判断此链表是否为单向闭环链表（即链表的最后一个结点的next指针指向前面的某个结点），给出算法，要求性能最优，内存消耗最低。

Answer 1

貌似以前见过了
for z{
    for j{
        for i...
    }
}

Answer 2

for(int i =0;i<1000;i++){
  for(int j =0;j<100;j++){
  for(int z=0;z<10;z++){
  function(i,j,z);
  }
  }
}
你这里边的 function(i,j,z);
是什么

Answer 3

留个记号，学习下~~
题意应该是要尽量减少for循环...等待高手来解决

Answer 4

for(int z=0;z<10;z++){
  for(int j =0;j<100;j++){
  for(int i =0;i<1000;i++){
  function(i,j,z);
  }
  }
}
为什么这样做
有可能这一小段程序加载在内存里是属于不同的页,如果执行次数多的放在外循环 那么就会造成页的频繁调度
反过来把执行次数多的放在内部 程序就会比较长时间里在一个页内执行 调度的次数就减少了.
所以答案是
这样可以减少"可能存在的"虚拟内存在硬盘和物理内存之间的调度次数 another：给你一个单项链表，要你用方法判断此链表是否为单向闭环链表（即链表的最后一个结点的next指针指向前面的某个结点），给出算法，要求性能最优，内存消耗最低。
===============
自己想吧 我是在网吧的.

Answer 5

1，对于第一题 倘若不存在数据依赖关系的话，是可以直接交换以提高执行效率。貌似不是缺页的问题吧，现在内存这么大。因为执行时，从外循环到内循环的跳转时很耗费周期的，所以当不存在数据依赖的时候把外层循环尽量放置的少一些，以减少跳转
2，对于第二题
总得有个优化过程吧
首先，我觉得这一题该分两种情况来讨论的。
case1:
倘若给出的链表的data是不重复的，
那么可以开辟足够大的数组空间（估计值）,然后遍历，一一插入排序存入数组（按某种顺序规则），
有相同的数组索引，返回true
case2:
倘若链表是data域重复的
有些复杂的，因为我们只能根据指针来判定
（事实上，我觉得，这种data重复的链表是不该存在的）继续想。

Answer 6

for(int z=10;z>0;z--){
for(int j =100;j>0;j--){
for(int i =1000;i>0;i--){
function(i,j,z);
}
}
}不是与0比较最快吗，呵呵

Answer 7

最后结点的next指针不一定指向第一个结点，可能是前面单链中除他之外的任一结点

Answer 8

遍历链表 如果各节点的next指针有重复的情况 表明闭环

Answer 9

第二个问题要看你使用什么语言了
这是在Java版 就用Java语言
class Mynode<T>{ //设节点数据结构是这样的。
 T data;
 Mynode;
 Mynode(T data){
  this.data=data;
 }
 public void dataopration(){
  ...//当然是要对这数据操作操作了
 }
}
class Mylink<T>{ //代表这堆数据
 T h;
 public boolean bianli(){
  T temp=h;
  if(temp.next!=null)  { temp.dataopration();temp=temp.next; }
  if(temp==h) return true;
  return false;
 }
}唉~乱写的 泛型我还不会用，所以关于泛型的不要作参考。

Answer 10

class Mynode<T>{ //设节点数据结构是这样的。
 T data;
 Mynode;
 Mynode(T data){
  this.data=data;
 }
 public void dataopration(){
  ...//当然是要对这数据操作操作了
 }
}
class Mylink<T>{ //代表这堆数据
 T h;
 public boolean bianli(){
  T temp=h;
  while(temp.next!=null)  { temp.dataopration();temp=temp.next; }
  if(temp==h) return true;
  return false;
 }
}
地方错了 改改。

Answer 11

没有优化用时 18719 ms  优化后 16703 mspublic class OptimizeFor {
static void function(int i, int j, int z){
System.out.println(i + " "+j+" "+z);
}
public static void main(String[] args) {
long begin = System.currentTimeMillis();
// for (int i = 0; i < 1000; i++) {
// for (int j = 0; j < 100; j++) {
// for (int z = 0; z < 10; z++) {
// function(i, j, z);
// }
// }
// }
//优化上面的for循环

for(int i= 0,j=0,z=0; i<1000; z++){
function(i, j, z);
if(z==9){
z = 0;
j ++;
if(j == 100){
j =0;
i++;
}
}
}
long end = System.currentTimeMillis();
System.out.println(" total time : " + (end-begin) +" millis");
}
}

Answer 12

没有优化用时 18719 ms 优化后 16703 mspublic class OptimizeFor {
static void function(int i, int j, int z){
System.out.println(i + " "+j+" "+z);
}
public static void main(String[] args) {
long begin = System.currentTimeMillis();
// for (int i = 0; i < 1000; i++) {
// for (int j = 0; j < 100; j++) {
// for (int z = 0; z < 10; z++) {
// function(i, j, z);
// }
// }
// }
//优化上面的for循环

for(int i= 0,j=0,z=0; i<1000; z++){
function(i, j, z);
if(z==9){
z = 0;
j ++;
if(j == 100){
j =0;
i++;
}
}
}
long end = System.currentTimeMillis();
System.out.println(" total time : " + (end-begin) +" millis");
}
}

Answer 13

for (int i=0;i<1000;i++) {
if (i<10) {
test(i,i,i);
} else if (i<100) {
for (int z=0;z<10;z++) {
test(i,i,z);
}
} else {
for (int j=0;j<100;j++) {
if (j<10) {
test(i,j,j);
} else {
for(int z=0;z<10;z++) {
test(i,j,z);
}
}
}
}
}