挑战:将数组中空值删去并改变数组长度的最快算法!

Question

如:
    string [] str = new string[12];
    str[0]="sdf";
    str[3]="hh";
    Delete_Array_Null(ref str);
    //现在str成为str[2],str[0]="sdf",str[1]="hh";    public static void Delete_Array_Null(ref string [] obj)
    {
      //这个中间我至少要两次遍历数组才能完成,不知道有没牛人有更快的速度?
    }    最终目标:支持常见类型的数组,及输入个数不限.如:params ref object [] obj,但我实现不了，因为还不懂泛型及不知道怎么控制多个数组的情况.

Answer 1

public static void Delete_Array_Null(ref string[] obj)
{
    int l = obj.Length;
    for (int i = 0; i < l; i++)
    {
        if (obj[i] == null || obj[i] == string.Empty)
        {
            Array.ConstrainedCopy(obj, i + 1, obj, i, l - i - 1);
            obj[l - 1] = null;
            l--;
            i--;
        }
    }
     
}

Answer 2

//如果要改变长度，参考：
public static void DeleteEmpty(ref string[] AArray)
{
    int l = AArray.Length;
    for (int i = 0; i < l; i++)
    {
        if (AArray[i] == null || AArray[i] == string.Empty)
        {
            Array.ConstrainedCopy(AArray, i + 1, AArray, i, l - i - 1);
            //AArray[l - 1] = null;
            l--;
            i--;
        }
    }
    string[] Result = new string[l];
    Array.ConstrainedCopy(AArray, 0, Result, 0, l);
    AArray = Result;
}private void button1_Click(object sender, EventArgs e)
{
    string[] str = new string[12];
    str[0] = "sdf";
    str[3] = "hh";
    str[11] = "Zswang 路过";
    DeleteEmpty(ref str);
    foreach (string s in str)
        textBox1.AppendText(s + "\r\n");
}

Answer 3

不过虽然只遍历了一次
但多次调用Array.ConstrainedCopy，这是个复杂操作另Array.ConstrainedCopy是.NET Framework 2.0中新增的方法，1.1中没有的

Answer 4

Array.ConstrainedCopy(AArray, 0, Result, 0, l);
这个操作不知道效率怎么样?是否在起内部也遍历了数组呢?

Answer 5

怎么会有那么麻烦的算法？
List方案：
public static void Delete_Array_Null(ref string [] array)
{
  List<string> list = new List<string)()
  foreach ( string s in array )
  {
    if ( s != null )
      list.Add( s );
  }  array = list.ToArray();
}
非List方案public static void Delete_Array_Null(ref string [] array)
{
  int i = 0;
  string[] array1 = new string[ array.Length ];
  foreach ( string s in array )
  {
    if ( s != null )
      array1[i++] = s;
  }
  array = new string[i];
  Array.Copy( array1, array, i );
}

Answer 6

//不知道楼主的代码怎么写的，贴出来看看，比较一下效率
//测试的方法如下，循环100000次，看看花多少时间int vTickCount = Environment.TickCount;
for (int i = 0; i < 100000; i++)
{
    string[] str = new string[12];
    str[0] = "sdf";
    str[3] = "hh";
    str[11] = "Zswang 路过";
    DeleteEmpty(ref str);
}
Text = (Environment.TickCount - vTickCount).ToString();//模拟输入的时候再多几种情况

Answer 7

如果追求极端效率，直接在数组内排序，然后利用反射把那个数组的Length给改了，就不知道会不会导致内存泄漏什么的。

Answer 8

public static void Delete_Array_Null(ref string [] obj)
        {
            int myC = 0;
            foreach (string o in obj)
            {
                if (o != null && o != "")
                    myC++;
            }
            string[] res = new string[myC];
            myC = 0;
            foreach (string o in obj)
            {
                if (o != null && o != "")
                    res[myC++] = o;
            }
            obj = res;
        }
我是最原始的方法,并且看时间并不是最准的，因为机器配置都不一样的,我测试时间为:
100000次,31毫秒.
机器配置:p4 2.8 超线程 + 512M内存
软件:xp sp2 + vs2005(ts)

Answer 9

Ivony的非list方法,我这边时间是:47毫秒.

Answer 10

Array.ConstrainedCopy(AArray, 0, Result, 0, l);
这个操作不知道效率怎么样?是否在起内部也遍历了数组呢?
是的

Answer 11

因为是字符串数组，所以麻烦
如果是基本类型数组，可以用unsafe代码
或者至少可以用Buffer.BlockCopy复制元素

Answer 12

leixueqiyi() ( ) 信誉：100    Blog  2007-03-28 15:39:55  得分: 0  
   Array.ConstrainedCopy(AArray, 0, Result, 0, l);
这个操作不知道效率怎么样?是否在起内部也遍历了数组呢?
是的
  
你怎么知道是这样的？难道你是微软内部员工？
有证据和资料证明吗？

Answer 13

呵呵。直接的Copy我觉得不太好,如:Array.ConstrainedCopy(AArray, 0, Result, 0, l);。
循环两次不代表效率差啊public static void Delete_Array_Null(ref string[] obj)
{
    int l = obj.Length;
    int j = 0;
    //用这个，循环两次效率一定差吗？总比string copy来copy去的好吧。
    UInt16[] list = new UInt16[l];    for (int i=0; i<l; i++)
    {
        if (obj[i] != null && obj[i] != string.Empty)
        {
            //非空的数组下标取下来。
            list[j++] = i;
        }
    }    string[] result = new string[j];    for(int i=0; i<j; i++)
    {
        //必要的东西传一下。
        result[i] = obj[list[i]];
    }    obj = result;
}

Answer 14

遍历一次得到非空元素的个数，建立新数组，copy

Answer 15

zswang(伴水清清)(专家门诊清洁工) ( ) 信誉：100    Blog  2007-03-28 14:21:53  得分: 0  
 
 
   public static void Delete_Array_Null(ref string[] obj)
{
    int l = obj.Length;
    for (int i = 0; i < l; i++)
    {
        if (obj[i] == null || obj[i] == string.Empty)
        {
            Array.ConstrainedCopy(obj, i + 1, obj, i, l - i - 1);
            obj[l - 1] = null;
            l--;
            i--;
        }
    }
     
}  
 
=================================================================
//如果为空。。
if (obj[i] == null || obj[i] == string.Empty)
{
   //要做这些。
   //......
}假如着个10000个数据中只有三个非空呢？ 那不是有9997次要copy了？
优化要针对 lz 的数据构成是怎么样的来说。
也就是说我们要归纳出这些的规律性。从规律中谈优化。
最适合的才是最优的。

Answer 16

测试及结果:
测试环境:p4 2.8 超线程 + 512M内存 + xp sp2 + vs2005(ts)
测试程序:
 int vTickCount = Environment.TickCount;
 for (int i = 0; i < 100000; i++)
 {
    string[] abc = new string[4];
    abc[0] = "2";
    abc[1] = "0";
    abc[3] = "0";
    Delete_Array_Null4(ref abc);
  }
  string Text = (Environment.TickCount - vTickCount).ToString();
  MessageBox.Show(Text);
偶自己的最原始方法:
1)
public static void Delete_Array_Null(ref string [] obj)
        {
            int myC = 0;
            foreach (string o in obj)
            {
                if (o != null && o != "")
                    myC++;
            }
            string[] res = new string[myC];
            myC = 0;
            foreach (string o in obj)
            {
                if (o != null && o != "")
                    res[myC++] = o;
            }
            obj = res;
        }
时间:恒定为31ms.
2)zswang(伴水清清)(专家门诊清洁工)
public static void DeleteEmpty(ref string[] AArray)
{
    int l = AArray.Length;
    for (int i = 0; i < l; i++)
    {
        if (AArray[i] == null || AArray[i] == string.Empty)
        {
            Array.ConstrainedCopy(AArray, i + 1, AArray, i, l - i - 1);
            //AArray[l - 1] = null;
            l--;
            i--;
        }
    }
    string[] Result = new string[l];
    Array.ConstrainedCopy(AArray, 0, Result, 0, l);
    AArray = Result;
}
时间:31-47(ms)即,在31到47之间的任意整数值
3)Ivony(授人以鱼不如授人以渔，上海谋生)
非List方案
public static void Delete_Array_Null(ref string [] array)
{
  int i = 0;
  string[] array1 = new string[ array.Length ];
  foreach ( string s in array )
  {
    if ( s != null )
      array1[i++] = s;
  }
  array = new string[i];
  Array.Copy( array1, array, i );
}
时间:31-47(ms)
4)FBug(花知)
public static void Delete_Array_Null(ref string[] obj)
{
    int l = obj.Length;
    int j = 0;
    //用这个，循环两次效率一定差吗？总比string copy来copy去的好吧。
    UInt16[] list = new UInt16[l];    for (int i=0; i<l; i++)
    {
        if (obj[i] != null && obj[i] != string.Empty)
        {
            //非空的数组下标取下来。
            list[j++] = i;    //这里有个bug,i需要显示转换,(ushort)i
        }
    }    string[] result = new string[j];    for(int i=0; i<j; i++)
    {
        //必要的东西传一下。
        result[i] = obj[list[i]];
    }    obj = result;
}
时间:31-47(ms)以上说明:第一种算法虽然简单,但不简陋,没有什么特殊的系统函数几调用,反而速度最快。
我没有任何夸耀自己算法的意思，其实这是每个人都会写的算法,我想说的是:
   在我们写程序久了之后，总是有中潜意思的想让自己与别人(特别是菜鸟)的程序不同，并爱用系统自带算法和函数,其实这些都是没有必要的。适合情况的算法才是最好的.即使是系统自带的也要看是否真的是最优的，因为系统函数总是有最大的兼容性.

Answer 17

从这个例子也可以看出，用C#来做有时间要求的算法是多么的ugly,如果用C++，速度会快的多得多。

Answer 18

我也发一个：
 public static void Delete_Array_Null(ref string[] obj)
{
    int Index1=0;
    int Index2=0;
    foreach(string s in obj)
    {
        if (s != null && s.Length>0)
        {
            if( Index1 < Index2)
             {
                obj[Index1++]=obj[Index2];
              }
        }
        Index2++;
    }
    string[] obj2 = new string[Index1];
    
    Array.ConstrainedCopy(obj,0, obj2, 0, Index1);    obj = obj2;
}

Answer 19

觉得可以用两个list搞定，一个是free list, 一个是used list

Answer 20

不好意思，好像发错了，改了下 
public static void Delete_Array_Null(ref string[] obj)
{
    int Index1=0;
    int Index2=0;
    foreach(string s in obj)
    {
        if (s != null && s.Length>0)
        {
            if( Index1 < Index2)
             {
                obj[Index1]=obj[Index2];
              }
           Index1++;
        }
        Index2++;
    }
    string[] obj2 = new string[Index1];
    
    Array.ConstrainedCopy(obj,0, obj2, 0, Index1);    obj = obj2;
}

Answer 21

为什么不用泛型呢？
List<string> myStrs = new List<string>();
然后你要增删改都很好用而且在 myStrs[x]得到的就是string类型，不用做转换。

Answer 22

public static void Delete_Array_Null(ref string [] obj)
        {
            int x = 0;
            string [] tmpStr=obj;
            for (int i = 0; i < tmpStr.Length; i++)
            {
                if (tmpStr[i] == "" || tmpStr[i] == null)
                {
                    if (i < tmpStr.Length - 1)
                    {
                        tmpStr[x] = Str[i + 1];
                        tmpStr[i + 1] = "";
                        if(tmpStr[x]!="" && tmpStr[x]!=null)
                              x++;
                    }
                }
                else
                    x++;
            }
            obj= new string[x];
            Array.Copy(tmpStr, obj, x);
        }

Answer 23

两个遍历指针i 和j；
i从前面开始遍历，j从后面开始遍历，以i为主。
如果array[i]为null，利用j获得从后往前的不为null的值array[j]
array[i] = array[j]; j --;
当i大于或者等于j时，表明两个指针相遇，遍历结束。
-----------------------------------------
int newLength = 0;
for (int i = 0, j = array.lenth - 1; i < j; i ++; )
{
    if(array[i] == null){
        while(array[j] == null){
            j--;
            if( i == j){
               newLength  = i;
               return;
            } 
        }
       array[i] = array[j];
       j --;
      }
}

Answer 24

我记得StringColletion就是list<string>， 难道generics类操作起来要比字串专用类快么？

Answer 25

楼上的测试是不合适的，因为您给出的例子是不好的。您应该创建一个长度是100以上的数组，按照不同的置空率试试， 再下结论不迟。
.........................................
按照你说，我将测试程序改为:
            int vTickCount = Environment.TickCount;
            for (int i = 0; i < 100000; i++)
            {                string[] abc = new string[400];
                abc[0] = "2";
                abc[1] = "0";
                abc[3] = "0";
                Delete_Array_Null(ref abc);
            }
           string Text = (Environment.TickCount - vTickCount).ToString();
            MessageBox.Show(Text);
则所有时间按循序依次为:[688,703],[782,829],(12031,11765),[594,625]
第三种不知道怎么回事,时间那么长,开始我还以为是机子死掉了!
结论:手工遍历快于系统的array copy.

Answer 26

都不知道是怎么测试的，我这边的测试结果是我的非List方案最快（也是在意料之中），而zswang的虽然平均速度最慢，但，如果数组中空元素比较少的情况下，会变成最快的算法。

Answer 27

还有一个问题，数组元素越少，则zswang的算法越快，数组越大，zswang的算法越慢，而且zswang的算法随机性很大，在测试中几次出现突然变快的情况，暂时没发现规律。

Answer 28

string[] abc = new string[100000];
Random vRandom = new Random();
for (int i = 0; i < abc.Length - 1; i++)
    if (vRandom.Next(3) != 0)
        abc[i] = i.ToString();用横向来测试的话，还是List<>的方法最快，空间换时间

Answer 29

楼主： 试试我下面的两个方法。都是循环一次的。
我想看看ConstrainedCopy和直接赋值哪个效率高。
和其他的又谁好。我的是1。1的。不能测试。
=================================================================
public static void DeleteEmpty(ref string[] AArray)
{
    int k = l = AArray.Length;
    bool f;
    for (int i=0; i<k; i++)
    {
        if (AArray[i] == null || AArray[i] == string.Empty)
        {
            f = false;
            for (int j=k-1; j>i; j--)
            {
                if (AArray[j] != null && AArray[j] != string.Empty)
                {
                //  最后一非空数据copy到第一空数据处。并把k向前提一位！
                    Array.ConstrainedCopy(AArray,j,AArray,i,1);
                    k = j;
                    f = true;
                    break;
                }
            }
            if (!f)
            {
            //  找不到了;这时候i没有+1,补它。;
                k = i + 1;
                break;
            }
        }
    }    string[] Result = new string[k];
    Array.ConstrainedCopy(AArray, 0, Result, 0, k);
    AArray = Result;
}
-------------------------------------------
public static void DeleteEmpty(ref string[] AArray)
{
    int k = l = AArray.Length;
    bool f;
    for (int i=0; i<k; i++)
    {
        if (AArray[i] == null || AArray[i] == string.Empty)
        {
            f = false;
            for (int j=k-1; j>i; j--)
            {
                if (AArray[j] != null && AArray[j] != string.Empty)
                {
                //  最后一非空数据copy到第一空数据处。并把k向前提一位！
                    AArray[i] = AArray[j];  //就这里变了。
                    k = j;
                    f = true;
                    break;
                }
            }
            if (!f)
            {
            //  找不到了;这时候i没有+1,补它。;
                k = i + 1;
                break;
            }
        }
    }    string[] Result = new string[k];
    Array.ConstrainedCopy(AArray, 0, Result, 0, k);
/*
    for (int i=0; i<k; i++)
    {
        Result[i] = AArray[i]; 
    //  感觉说不定。。
    //  因为这里都是string。赋值不会再创建新string。
    //  好比s1 = "aaa"; s2 = s1;原理一样。
    //  而ConstrainedCopy如果是一个copy操作的话，内存中就会有两个"aaa"。说不定这样写快
    }
*/
    AArray = Result;
}

Answer 30

第三种不知道怎么回事,时间那么长,开始我还以为是机子死掉了!
结论:手工遍历快于系统的array copy.
==========================================
呵呵和。 好象我最后的注释里说的更加有道理了哦。
说不顶ConstrainedCopy就是在内存中创建了副本。
导致你说的这情况发生。而直接值的赋予(s1=s2)却不会。

Answer 31

zswang:
    0/200,  0%  00:00:03.3374858
   10/200,  5%  00:00:04.2499335
   20/200, 10%  00:00:03.9444584
   30/200, 15%  00:00:03.4827985
   40/200, 20%  00:00:03.1244133
   50/200, 25%  00:00:02.8720739
   60/200, 30%  00:00:02.5469598
   70/200, 35%  00:00:02.2927643
   80/200, 40%  00:00:01.9629475
   90/200, 45%  00:00:01.7443237
  100/200, 50%  00:00:01.6542375
  110/200, 55%  00:00:00.0562920
  120/200, 60%  00:00:00.0603907
  130/200, 65%  00:00:00.0551617
  140/200, 70%  00:00:00.0487993
  150/200, 75%  00:00:00.0580027
  160/200, 80%  00:00:00.0592906
  170/200, 85%  00:00:00.0573284
  180/200, 90%  00:00:00.0592880
  190/200, 95%  00:00:00.0579463
  200/200,100%  00:00:00.0541857
Total: 00:00:31.7790816Ivony1:
    0/200,  0%  00:00:00.0305635
   10/200,  5%  00:00:00.0742891
   20/200, 10%  00:00:00.1069343
   30/200, 15%  00:00:00.1425275
   40/200, 20%  00:00:00.1571788
   50/200, 25%  00:00:00.1876528
   60/200, 30%  00:00:00.2188552
   70/200, 35%  00:00:00.2483576
   80/200, 40%  00:00:00.2900804
   90/200, 45%  00:00:00.2799028
  100/200, 50%  00:00:00.3062270
  110/200, 55%  00:00:00.3300896
  120/200, 60%  00:00:00.3251081
  130/200, 65%  00:00:00.3836652
  140/200, 70%  00:00:00.3894911
  150/200, 75%  00:00:00.3877972
  160/200, 80%  00:00:00.3886056
  170/200, 85%  00:00:00.3975170
  180/200, 90%  00:00:00.3774876
  190/200, 95%  00:00:00.4301607
  200/200,100%  00:00:00.3914382
Total: 00:00:05.8439293Ivony2:
    0/200,  0%  00:00:00.0383079
   10/200,  5%  00:00:00.0549465
   20/200, 10%  00:00:00.0735612
   30/200, 15%  00:00:00.0884823
   40/200, 20%  00:00:00.1051316
   50/200, 25%  00:00:00.1286132
   60/200, 30%  00:00:00.1478973
   70/200, 35%  00:00:00.1485038
   80/200, 40%  00:00:00.1730459
   90/200, 45%  00:00:00.1803099
  100/200, 50%  00:00:00.1861967
  110/200, 55%  00:00:00.2079977
  120/200, 60%  00:00:00.2070702
  130/200, 65%  00:00:00.2141607
  140/200, 70%  00:00:00.2110620
  150/200, 75%  00:00:00.2083418
  160/200, 80%  00:00:00.2312071
  170/200, 85%  00:00:00.1913051
  180/200, 90%  00:00:00.2016836
  190/200, 95%  00:00:00.1868633
  200/200,100%  00:00:00.1895091
Total: 00:00:03.3741969icefeiji:
    0/200,  0%  00:00:00.0314196
   10/200,  5%  00:00:00.0770329
   20/200, 10%  00:00:00.1040775
   30/200, 15%  00:00:00.1142357
   40/200, 20%  00:00:00.1389016
   50/200, 25%  00:00:00.1760726
   60/200, 30%  00:00:00.1909166
   70/200, 35%  00:00:00.2031099
   80/200, 40%  00:00:00.2531155
   90/200, 45%  00:00:00.2407475
  100/200, 50%  00:00:00.2621631
  110/200, 55%  00:00:00.2888987
  120/200, 60%  00:00:00.2919084
  130/200, 65%  00:00:00.3277153
  140/200, 70%  00:00:00.2795539
  150/200, 75%  00:00:00.3019341
  160/200, 80%  00:00:00.3054480
  170/200, 85%  00:00:00.2943048
  180/200, 90%  00:00:00.3004451
  190/200, 95%  00:00:00.2887959
  200/200,100%  00:00:00.2747108
Total: 00:00:04.7455075
在数组大小为200时候的情况。分别按不同的比率随机填充随机元素的运行结果。

Answer 32

zswang:
    0/100,  0%  00:00:01.2010151
    5/100,  5%  00:00:01.3157035
   10/100, 10%  00:00:01.3123459
   15/100, 15%  00:00:01.2248389
   20/100, 20%  00:00:01.0503588
   25/100, 25%  00:00:00.9720770
   30/100, 30%  00:00:00.0351993
   35/100, 35%  00:00:00.7813923
   40/100, 40%  00:00:00.7005207
   45/100, 45%  00:00:00.6212647
   50/100, 50%  00:00:00.0324698
   55/100, 55%  00:00:00.0321271
   60/100, 60%  00:00:00.4258206
   65/100, 65%  00:00:00.0320850
   70/100, 70%  00:00:00.0317756
   75/100, 75%  00:00:00.2516262
   80/100, 80%  00:00:00.0355813
   85/100, 85%  00:00:00.0310512
   90/100, 90%  00:00:00.0363335
   95/100, 95%  00:00:00.0288014
  100/100,100%  00:00:00.0343590
Total: 00:00:10.1867469Ivony1:
    0/100,  0%  00:00:00.0208153
    5/100,  5%  00:00:00.0399120
   10/100, 10%  00:00:00.0667497
   15/100, 15%  00:00:00.0713376
   20/100, 20%  00:00:00.0969221
   25/100, 25%  00:00:00.1171185
   30/100, 30%  00:00:00.1162749
   35/100, 35%  00:00:00.1378043
   40/100, 40%  00:00:00.1492179
   45/100, 45%  00:00:00.1529493
   50/100, 50%  00:00:00.1532346
   55/100, 55%  00:00:00.1684902
   60/100, 60%  00:00:00.1803097
   65/100, 65%  00:00:00.1983868
   70/100, 70%  00:00:00.2019192
   75/100, 75%  00:00:00.2010122
   80/100, 80%  00:00:00.2088179
   85/100, 85%  00:00:00.2157345
   90/100, 90%  00:00:00.1981376
   95/100, 95%  00:00:00.2102113
  100/100,100%  00:00:00.2109847
Total: 00:00:03.1163403Ivony2:
    0/100,  0%  00:00:00.0263621
    5/100,  5%  00:00:00.0313105
   10/100, 10%  00:00:00.0414868
   15/100, 15%  00:00:00.0412877
   20/100, 20%  00:00:00.0503510
   25/100, 25%  00:00:00.0537006
   30/100, 30%  00:00:00.0740474
   35/100, 35%  00:00:00.0768665
   40/100, 40%  00:00:00.0854224
   45/100, 45%  00:00:00.0891073
   50/100, 50%  00:00:00.0916744
   55/100, 55%  00:00:00.0986288
   60/100, 60%  00:00:00.0967142
   65/100, 65%  00:00:00.0991700
   70/100, 70%  00:00:00.0972425
   75/100, 75%  00:00:00.1024890
   80/100, 80%  00:00:00.1108950
   85/100, 85%  00:00:00.0964153
   90/100, 90%  00:00:00.1030257
   95/100, 95%  00:00:00.0918199
  100/100,100%  00:00:00.0952207
Total: 00:00:01.6532378icefeiji:
    0/100,  0%  00:00:00.0208002
    5/100,  5%  00:00:00.0291888
   10/100, 10%  00:00:00.0511330
   15/100, 15%  00:00:00.0529531
   20/100, 20%  00:00:00.0683731
   25/100, 25%  00:00:00.0804929
   30/100, 30%  00:00:00.0901896
   35/100, 35%  00:00:00.1041446
   40/100, 40%  00:00:00.1218968
   45/100, 45%  00:00:00.1126917
   50/100, 50%  00:00:00.1231031
   55/100, 55%  00:00:00.1249687
   60/100, 60%  00:00:00.1201740
   65/100, 65%  00:00:00.1361177
   70/100, 70%  00:00:00.1448803
   75/100, 75%  00:00:00.1444292
   80/100, 80%  00:00:00.1524351
   85/100, 85%  00:00:00.1405920
   90/100, 90%  00:00:00.1319680
   95/100, 95%  00:00:00.1447135
  100/100,100%  00:00:00.1311737
Total: 00:00:02.2264191数组大小为100的情况。

Answer 33

zswang:
    0/40,  0%   00:00:06.5144309
    2/40,  5%   00:00:03.8523881
    4/40, 10%   00:00:03.6672482
    6/40, 15%   00:00:03.4037422
    8/40, 20%   00:00:00.1896942
   10/40, 25%   00:00:02.9098545
   12/40, 30%   00:00:02.6941304
   14/40, 35%   00:00:02.4005082
   16/40, 40%   00:00:02.1792670
   18/40, 45%   00:00:01.9904412
   20/40, 50%   00:00:01.8087644
   22/40, 55%   00:00:01.6009897
   24/40, 60%   00:00:00.1906975
   26/40, 65%   00:00:00.1820306
   28/40, 70%   00:00:00.1743247
   30/40, 75%   00:00:00.1758454
   32/40, 80%   00:00:00.1884245
   34/40, 85%   00:00:00.5746920
   36/40, 90%   00:00:00.1808177
   38/40, 95%   00:00:00.1890304
   40/40,100%   00:00:00.1777972
Total: 00:00:35.2451190Ivony1:
    0/40,  0%   00:00:00.1359181
    2/40,  5%   00:00:00.1739858
    4/40, 10%   00:00:00.2471797
    6/40, 15%   00:00:00.3975315
    8/40, 20%   00:00:00.3907984
   10/40, 25%   00:00:00.5619033
   12/40, 30%   00:00:00.5328553
   14/40, 35%   00:00:00.6159554
   16/40, 40%   00:00:00.6273309
   18/40, 45%   00:00:00.8048867
   20/40, 50%   00:00:00.8927519
   22/40, 55%   00:00:00.9095944
   24/40, 60%   00:00:00.9315730
   26/40, 65%   00:00:00.9724017
   28/40, 70%   00:00:00.9525183
   30/40, 75%   00:00:00.9296622
   32/40, 80%   00:00:00.9787078
   34/40, 85%   00:00:01.1779396
   36/40, 90%   00:00:01.1647568
   38/40, 95%   00:00:01.1899834
   40/40,100%   00:00:01.1766952
Total: 00:00:15.7649294Ivony2:
    0/40,  0%   00:00:00.1750757
    2/40,  5%   00:00:00.1921765
    4/40, 10%   00:00:00.2142540
    6/40, 15%   00:00:00.2258601
    8/40, 20%   00:00:00.3110889
   10/40, 25%   00:00:00.2780812
   12/40, 30%   00:00:00.3460928
   14/40, 35%   00:00:00.3663562
   16/40, 40%   00:00:00.3615521
   18/40, 45%   00:00:00.3873942
   20/40, 50%   00:00:00.4008893
   22/40, 55%   00:00:00.4297437
   24/40, 60%   00:00:00.4420117
   26/40, 65%   00:00:00.4307388
   28/40, 70%   00:00:00.4795671
   30/40, 75%   00:00:00.4595048
   32/40, 80%   00:00:00.4765597
   34/40, 85%   00:00:00.4793754
   36/40, 90%   00:00:00.4550752
   38/40, 95%   00:00:00.4735997
   40/40,100%   00:00:00.4448198
Total: 00:00:07.8298169icefeiji:
    0/40,  0%   00:00:00.0901699
    2/40,  5%   00:00:00.1548510
    4/40, 10%   00:00:00.1856310
    6/40, 15%   00:00:00.2296042
    8/40, 20%   00:00:00.2696443
   10/40, 25%   00:00:00.3135997
   12/40, 30%   00:00:00.3469013
   14/40, 35%   00:00:00.4100468
   16/40, 40%   00:00:00.4504087
   18/40, 45%   00:00:00.4477736
   20/40, 50%   00:00:00.5165984
   22/40, 55%   00:00:00.4829030
   24/40, 60%   00:00:00.5690284
   26/40, 65%   00:00:00.5599353
   28/40, 70%   00:00:00.6285056
   30/40, 75%   00:00:00.5650096
   32/40, 80%   00:00:00.6169563
   34/40, 85%   00:00:00.5622627
   36/40, 90%   00:00:00.5905200
   38/40, 95%   00:00:00.6111481
   40/40,100%   00:00:00.5857243
Total: 00:00:09.1872222数组大小为40的情况，增加了十倍运行次数。

Answer 34

zswang:
    0/10,  0%   00:00:00.8687796
    0/10,  5%   00:00:00.8119383
    1/10, 10%   00:00:00.7069950
    1/10, 15%   00:00:00.7111814
    2/10, 20%   00:00:00.6284365
    2/10, 25%   00:00:00.6199212
    3/10, 30%   00:00:00.6266275
    3/10, 35%   00:00:00.5902703
    4/10, 40%   00:00:00.1108878
    4/10, 45%   00:00:00.4844417
    5/10, 50%   00:00:00.4078793
    5/10, 55%   00:00:00.4127844
    6/10, 60%   00:00:00.0991123
    6/10, 65%   00:00:00.1089260
    7/10, 70%   00:00:00.2835577
    7/10, 75%   00:00:00.3045647
    8/10, 80%   00:00:00.1008665
    8/10, 85%   00:00:00.2355975
    9/10, 90%   00:00:00.0995357
    9/10, 95%   00:00:00.1203638
   10/10,100%   00:00:00.1104349
Total: 00:00:08.4431021Ivony1:
    0/10,  0%   00:00:00.1058195
    0/10,  5%   00:00:00.1124359
    1/10, 10%   00:00:00.1317232
    1/10, 15%   00:00:00.1575010
    2/10, 20%   00:00:00.2588695
    2/10, 25%   00:00:00.1842657
    3/10, 30%   00:00:00.1549544
    3/10, 35%   00:00:00.1680239
    4/10, 40%   00:00:00.1817818
    4/10, 45%   00:00:00.1657671
    5/10, 50%   00:00:00.3140874
    5/10, 55%   00:00:00.3061426
    6/10, 60%   00:00:00.3083780
    6/10, 65%   00:00:00.2936825
    7/10, 70%   00:00:00.3387912
    7/10, 75%   00:00:00.3152609
    8/10, 80%   00:00:00.3275762
    8/10, 85%   00:00:00.3571157
    9/10, 90%   00:00:00.4628898
    9/10, 95%   00:00:00.4556721
   10/10,100%   00:00:00.4959866
Total: 00:00:05.5967250Ivony2:
    0/10,  0%   00:00:00.1140274
    0/10,  5%   00:00:00.1107956
    1/10, 10%   00:00:00.1191372
    1/10, 15%   00:00:00.1163662
    2/10, 20%   00:00:00.1398531
    2/10, 25%   00:00:00.1305536
    3/10, 30%   00:00:00.1347055
    3/10, 35%   00:00:00.1374646
    4/10, 40%   00:00:00.1372124
    4/10, 45%   00:00:00.1557651
    5/10, 50%   00:00:00.1424890
    5/10, 55%   00:00:00.1619205
    6/10, 60%   00:00:00.1859276
    6/10, 65%   00:00:00.1762510
    7/10, 70%   00:00:00.1709375
    7/10, 75%   00:00:00.1724705
    8/10, 80%   00:00:00.1747326
    8/10, 85%   00:00:00.2185491
    9/10, 90%   00:00:00.1924585
    9/10, 95%   00:00:00.1877860
   10/10,100%   00:00:00.1883639
Total: 00:00:03.2677669icefeiji:
    0/10,  0%   00:00:00.0302786
    0/10,  5%   00:00:00.0288424
    1/10, 10%   00:00:00.0368590
    1/10, 15%   00:00:00.0440233
    2/10, 20%   00:00:00.0751572
    2/10, 25%   00:00:00.0647466
    3/10, 30%   00:00:00.0778086
    3/10, 35%   00:00:00.0966253
    4/10, 40%   00:00:00.1143141
    4/10, 45%   00:00:00.0983446
    5/10, 50%   00:00:00.1155084
    5/10, 55%   00:00:00.1015509
    6/10, 60%   00:00:00.1353545
    6/10, 65%   00:00:00.1145698
    7/10, 70%   00:00:00.1506178
    7/10, 75%   00:00:00.1362841
    8/10, 80%   00:00:00.1374323
    8/10, 85%   00:00:00.1444196
    9/10, 90%   00:00:00.1568161
    9/10, 95%   00:00:00.1863858
   10/10,100%   00:00:00.1542490
Total: 00:00:02.2001880数组大小为10的情况。最后一种算法开始超越。

Answer 35

Ivony1:
    0/1000,  0% 00:00:00.2520465
   50/1000,  5% 00:00:00.3661713
  100/1000, 10% 00:00:00.5028542
  150/1000, 15% 00:00:00.6932537
  200/1000, 20% 00:00:00.8509767
  250/1000, 25% 00:00:00.9766623
  300/1000, 30% 00:00:01.2477725
  350/1000, 35% 00:00:01.3586572
  400/1000, 40% 00:00:01.5295140
  450/1000, 45% 00:00:01.5258115
  500/1000, 50% 00:00:01.7011048
  550/1000, 55% 00:00:01.8564046
  600/1000, 60% 00:00:01.8946487
  650/1000, 65% 00:00:01.8463093
  700/1000, 70% 00:00:01.8174169
  750/1000, 75% 00:00:01.8679492
  800/1000, 80% 00:00:01.8230236
  850/1000, 85% 00:00:01.8618347
  900/1000, 90% 00:00:01.9196790
  950/1000, 95% 00:00:01.8912743
 1000/1000,100% 00:00:01.9371167
Total: 00:00:29.7204817Ivony2:
    0/1000,  0% 00:00:00.3204861
   50/1000,  5% 00:00:00.4087896
  100/1000, 10% 00:00:00.5304354
  150/1000, 15% 00:00:00.6323690
  200/1000, 20% 00:00:00.7593397
  250/1000, 25% 00:00:00.8642584
  300/1000, 30% 00:00:00.9694876
  350/1000, 35% 00:00:01.0724128
  400/1000, 40% 00:00:01.1566039
  450/1000, 45% 00:00:01.2196668
  500/1000, 50% 00:00:01.2907953
  550/1000, 55% 00:00:01.3719939
  600/1000, 60% 00:00:01.3522122
  650/1000, 65% 00:00:01.3304559
  700/1000, 70% 00:00:01.3038983
  750/1000, 75% 00:00:01.2964886
  800/1000, 80% 00:00:01.2949009
  850/1000, 85% 00:00:01.3189783
  900/1000, 90% 00:00:01.2530631
  950/1000, 95% 00:00:01.2988905
 1000/1000,100% 00:00:01.2232934
Total: 00:00:22.2688197icefeiji:
    0/1000,  0% 00:00:00.4696626
   50/1000,  5% 00:00:00.6986972
  100/1000, 10% 00:00:00.8909972
  150/1000, 15% 00:00:01.1232186
  200/1000, 20% 00:00:01.3089599
  250/1000, 25% 00:00:01.5592421
  300/1000, 30% 00:00:01.7734088
  350/1000, 35% 00:00:01.9855110
  400/1000, 40% 00:00:02.1420328
  450/1000, 45% 00:00:02.3206825
  500/1000, 50% 00:00:02.3654877
  550/1000, 55% 00:00:02.4716838
  600/1000, 60% 00:00:02.5000800
  650/1000, 65% 00:00:02.4537108
  700/1000, 70% 00:00:02.4852319
  750/1000, 75% 00:00:02.3889613
  800/1000, 80% 00:00:02.3362019
  850/1000, 85% 00:00:02.2819742
  900/1000, 90% 00:00:02.2431570
  950/1000, 95% 00:00:02.2553039
 1000/1000,100% 00:00:02.2314906
Total: 00:00:40.2856958数组大小为1000的情况，第一种算法已经无法在同等条件下测试。放弃总体来说，第一种算法所需的时间波动很大，我实在不明白上面那些恒为XX毫秒是怎么得出来的。List的算法在非空元素少的情况下还是占优的，但随着元素的增加，平均速度上还是败给了非List的方案。

Answer 36

测试代码如下：using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;namespace ClassTest
{
  class Program
  {    private static Random rand = new Random();
    private static int count = 50000;
    private static int percentStep = 5;
    private static int arraySize = 100;
    public static void Main()
    {
      Stopwatch watch = new Stopwatch();
      TimeSpan totalSpan = new TimeSpan();
      string[] array = new string[arraySize];      Console.WriteLine( "zswang:" );      for ( int percent = 0; percent <= 100; percent += percentStep )
      {
        array = new string[arraySize];
        FillArray( array, array.Length * percent / 100 );        watch.Start();
        for ( int i = 0; i < count; i++ )
          zswang( array );
        watch.Stop();        Console.WriteLine( "{0,5}/{1},{2,3}%\t{3}", (percent * array.Length / 100), array.Length, percent, watch.Elapsed );
        totalSpan += watch.Elapsed;
        watch.Reset();
      }
      Console.WriteLine( "Total: {0}", totalSpan );
      Console.WriteLine();
      totalSpan = new TimeSpan();
      array = new string[arraySize];      Console.WriteLine( "Ivony1:" );      for ( int percent = 0; percent <= 100; percent += percentStep )
      {
        array = new string[arraySize];
        FillArray( array, array.Length * percent / 100 );        watch.Start();
        for ( int i = 0; i < count; i++ )
          Ivony1( array );
        watch.Stop();        Console.WriteLine( "{0,5}/{1},{2,3}%\t{3}", (percent * array.Length / 100), array.Length, percent, watch.Elapsed );
        totalSpan += watch.Elapsed;
        watch.Reset();
      }
      Console.WriteLine( "Total: {0}", totalSpan );
      Console.WriteLine();
      totalSpan = new TimeSpan();
      array = new string[arraySize];
      Console.WriteLine( "Ivony2:" );      for ( int percent = 0; percent <= 100; percent += percentStep )
      {
        array = new string[arraySize];
        FillArray( array, array.Length * percent / 100 );        watch.Start();
        for ( int i = 0; i < count; i++ )
          Ivony2( array );
        watch.Stop();        Console.WriteLine( "{0,5}/{1},{2,3}%\t{3}", (percent * array.Length / 100), array.Length, percent, watch.Elapsed );
        totalSpan += watch.Elapsed;
        watch.Reset();
      }
      Console.WriteLine( "Total: {0}", totalSpan );
      Console.WriteLine();
      totalSpan = new TimeSpan();
      array = new string[arraySize];
      Console.WriteLine( "icefeiji:" );      for ( int percent = 0; percent <= 100; percent += percentStep )
      {
        array = new string[arraySize];
        FillArray( array, array.Length * percent / 100 );        watch.Start();
        for ( int i = 0; i < count; i++ )
          icefeiji( array );
        watch.Stop();        Console.WriteLine( "{0,5}/{1},{2,3}%\t{3}", (percent * array.Length / 100), array.Length, percent, watch.Elapsed );
        totalSpan += watch.Elapsed;
        watch.Reset();
      }
      Console.WriteLine( "Total: {0}", totalSpan );
      Console.WriteLine();
      Console.ReadLine();
    }    public static void FillArray( string[] array, int count )
    {
      for ( int i = 0; i < count; i++ )
      {
        int index = rand.Next( array.Length );        if ( array[index] == null )
          array[index] = rand.Next().ToString();
        else
          i--;
      }
    }    public static string[] zswang( string[] array )
    {
      int l = array.Length;
      for ( int i = 0; i < l; i++ )
      {
        if ( array[i] == null )
        {
          Array.ConstrainedCopy( array, i + 1, array, i, l - i - 1 );
          l--;
          i--;
        }
      }      string[] result = new string[l];
      Array.ConstrainedCopy( array, 0, result, 0, l );
      return result;
    }    public static string[] Ivony1( string[] array )
    {
      List<string> list = new List<string>();
      foreach ( string s in array )
      {
        if ( s != null )
          list.Add( s );
      }      return list.ToArray();
    }    public static string[] Ivony2( string[] array )
    {
      int i = 0;
      string[] array1 = new string[array.Length];
      foreach ( string s in array )
      {
        if ( s != null )
          array1[i++] = s;
      }
      array = new string[i];
      Array.Copy( array1, array, i );
      return array;
    }    public static string[] icefeiji( string[] array )
    {      int count = 0;
      foreach ( string s in array )
      {
        if ( s != null )
          count++;
      }
      string[] resault = new string[count];
      count = 0;
      foreach ( string s in array )
      {
        if ( s != null && s != "" )
          resault[count++] = s;
      }
      return resault;
    }  }
}

Answer 37

....这个测试做得够专业非List方案由于在循环中没有重新分配内存空间所以很快而List方案每次添加就需要考虑分配内存ConstrainedCopy这种方法看来每次都会开辟空间来操作
当每次要移动的数据量超过4096(一个内存页)那就特慢了

Answer 38

看了Ivony的测试真是汗到极点,这样才有点专业测试的样子，呵呵!
我看我在学好测试前还是不要写瞎弄什么算法了，算了，继续学习了。

Answer 39

Ivony 同学。 如是你的测试结果。那么。我后面写的方法应该和“非List方案”的区别不会怎么明显了。不过我还是想知道我写的复杂方法和“非List方案”到底有没有优势。
哪位朋友帮忙测试一下啊。。（再帖一下，被上面的刷掉了。）
//可能有错误，测试的时候还要调试一下。昨晚是直接在这里写的；我没调试过。
public static void DeleteEmpty(ref string[] AArray)
{
    int k = l = AArray.Length;
    bool f;
    for (int i=0; i<k; i++)
    {
        if (AArray[i] == null || AArray[i] == string.Empty)
        {
            f = false;
            for (int j=k-1; j>i; j--)
            {
                if (AArray[j] != null && AArray[j] != string.Empty)
                {
                //  最后一非空数据copy到第一空数据处。并把k向前提一位！
                    AArray[i] = AArray[j];  //就这里变了。
                    k = j;
                    f = true;
                    break;
                }
            }
            if (!f)
            {
            //  找不到了;这时候i没有+1,补它。;
                k = i + 1;
                break;
            }
        }
    }    string[] Result = new string[k];
    Array.ConstrainedCopy(AArray, 0, Result, 0, k);
/*
    for (int i=0; i<k; i++)
    {
        Result[i] = AArray[i]; 
    //  感觉说不定。。
    //  因为这里都是string。赋值不会再创建新string。
    //  好比s1 = "aaa"; s2 = s1;原理一样。
    //  而ConstrainedCopy如果是一个copy操作的话，内存中就会有两个"aaa"。说不定这样写快
    }
*/
    AArray = Result;
}

Answer 40

好象就是和njucser2001同学的一样、、

Answer 41

c code:(兼顾效率和空间)#include <stdio.h>
#include <memory>char* delete_null( char *pSrc, int len )
{
for(int i=0,j=0; j<len; j++)
{
if( pSrc[j] )
{
if( i < j )
{
pSrc[i] = pSrc[j];
} i++;
}
}

memset(pSrc+i, 0, len-i); return pSrc;
}void main()
{
char src[11] = "123 45 678";
src[3] = '\0';
src[6] = '\0'; printf("%s", delete_null(src, 11));

getchar();
}

Answer 42

请 Ivony(授人以鱼不如授人以渔，上海谋生) 帮我测试一下,谢谢