递归,堆栈,迭代器,yield return;;

!):递归是不是就是用的堆栈来计算的啊?我的理解是这样的,大侠指点下...看到sp1234 提到才想到 递归有堆栈的联系..::    假如一个递归算法,需要递归100次... 然后pop.push(100)......pop.push(1)..这样先堆好了 在 pop.drop(1)............ pop.drop(100),这样来计算的....假如drop(1)执行的时间复杂度是N 
那么时间复杂度是多少?100N?....
!!):迭代器 是不是与指针有关..比如存储数据: 是通过指针++来逐步存储数据的...迭代器这个请详细解释下;;;
!!!):yield return a 是不是就是在当前迭代快中 add a 这个值 啊.....
     假如是这样的话,我完全可以用List<T> 这样的链表来代替啊... for(i....) list[T] 实例.add(值)..那么迭代器感觉可以不需要啊

14 个解决方案

#1

注意你的用词，O(n)和O(N)是不同的。
yield return本质上是一个状态机，C#会创建一个线程，并且每次迭代后都会将这个线程挂起，再次调用则继续。它向调用者返回当前迭代值，但是它不会保存到存储中，和List不同，也不能随机访问迭代器。

#2

引用 1 楼  的回复:

注意你的用词，O(n)和O(N)是不同的。
yield return本质上是一个状态机，C#会创建一个线程，并且每次迭代后都会将这个线程挂起，再次调用则继续。它向调用者返回当前迭代值，但是它不会保存到存储中，和List不同，也不能随机访问迭代器。

第3个问题解决了  3Q .. 1 ,2 问题 求继续解答.. .注意你的用词，O(n)和O(N)是不同的。这个啥意思?

#3

之前我说错了，O(n)和o(n)是不同的。
O(n)表示的是函数数量级的渐近上界。因此100N这个说法是不对的，不应该有常数项。

#4

“那么时间复杂度是多少?100N?....” --- 1
不需要循环，直接取值，因为它有一个栈顶指针啊，任何时候操作都是在栈顶

#5

用yield的好处是你可以再迭代的时候同时完成其他操作 效率更高

引用楼主  的回复:

!):递归是不是就是用的堆栈来计算的啊?我的理解是这样的,大侠指点下...看到sp1234 提到才想到 递归有堆栈的联系..:: 假如一个递归算法,需要递归100次... 然后pop.push(100)......pop.push(1)..这样先堆好了 在 pop.drop(1)............ pop.drop(100),这样来计算的....假如drop(1)执行的时间复杂度是N 
那……

#6

用yield的好处是你可以再迭代的时候同时完成其他操作 效率更高

引用楼主  的回复:

!):递归是不是就是用的堆栈来计算的啊?我的理解是这样的,大侠指点下...看到sp1234 提到才想到 递归有堆栈的联系..:: 假如一个递归算法,需要递归100次... 然后pop.push(100)......pop.push(1)..这样先堆好了 在 pop.drop(1)............ pop.drop(100),这样来计算的....假如drop(1)执行的时间复杂度是N 
那……

#7

引用 4 楼  的回复:

“那么时间复杂度是多少?100N?....” --- 1
不需要循环，直接取值，因为它有一个栈顶指针啊，任何时候操作都是在栈顶

但是当前 栈顶执行完之后 必须的 drop()才行啊,,假如这个时间复杂度为 O(n),.递归一百次 时间复杂度为100 O(n)对不对?

#8

引用 1 楼  的回复:

注意你的用词，O(n)和O(N)是不同的。
yield return本质上是一个状态机，C#会创建一个线程，并且每次迭代后都会将这个线程挂起，再次调用则继续。它向调用者返回当前迭代值，但是它不会保存到存储中，和List不同，也不能随机访问迭代器。

可以这么理解么??实际上就是一小段内存,在foreach的时候,取当前值.假如foreach执行完了第一次了.这段内存就清空,然后在第二次的时候,把取到的值,放到内存中去??

#9

本帖最后由 caozhy 于 2012-09-13 16:54:43 编辑

贴一个手动实现迭代器的代码

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class OneToThree : IEnumerable<int>
    {
        public class OneToThreeEnumerator : IEnumerator<int>, IEnumerator
        {
            private int _current = 0;

            public int Current
            {
                get { return _current; }
            }

            public void Dispose()
            {
                //这里我们不需要清理
            }

            object System.Collections.IEnumerator.Current
            {
                get { return _current; }
            }

            public bool MoveNext()
            {
                _current++;
                return _current <= 3;
            }

            public void Reset()
            {
                _current = 0;
            }
        }

        public IEnumerator<int> GetEnumerator()
        {
            return new OneToThree.OneToThreeEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return new OneToThree.OneToThreeEnumerator();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            foreach (int x in new OneToThree())
            {
                Console.WriteLine(x);
            }
        }
    }
}

对照yield return

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        //这个方法会创建一个匿名迭代器类，等价之前的代码
        static IEnumerable<int> GetOneToThreeClass()
        {
            int _current = 1;
            while (_current <= 3)
            {
                yield return _current++;
            }
        }

        static void Main(string[] args)
        {
            foreach (int x in GetOneToThreeClass())
            {
                Console.WriteLine(x);
            }
        }
    }
}

#10

 class Program
        {
            //这个方法会创建一个匿名迭代器类，等价之前的代码
            static IEnumerable<int> GetOneToThreeClass()
            {
                int _current = 1;
                while (_current <= 3)
                {
                    yield return _current++;
                }
            }

            static void Main(string[] args)
            {
                GetOneToThreeClass();//疑问1;
                GetOneToThreeClass().ToArray();//疑问2
                foreach (int x in GetOneToThreeClass())
                {
                    Console.WriteLine(x);
                }
            }
        }

我不明白的就是这个...
在疑问1 和疑问2 以及GetOneToThreeClass() 打好断点..
在执行疑问1的时候不会跟到GetOneToThreeClass()中去..
执行疑问2的时候就跟到GetOneToThreeClass()中去了..
这个有点想不通..这个应该就是和yield 有关的吧?

#11

就是在疑问1处的时候他并不存储数据..
到疑问2 toarry()的时候.需要数组来保存的时候才去读数据处理数据.?这个是不是就是yield的延迟特性?

#12

人了???

#13

这个问题说来话长，这次我再展开foreach，看看你能不能琢磨出什么。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class OneToThree : IEnumerable<int>
    {
        public class OneToThreeEnumerator : IEnumerator<int>, IEnumerator
        {
            private int _current = 0;

            public int Current
            {
                get { return _current; }
            }

            public void Dispose()
            {
                //这里我们不需要清理
            }

            object System.Collections.IEnumerator.Current
            {
                get { return _current; }
            }

            public bool MoveNext()
            {
                _current++;
                return _current <= 3;
            }

            public void Reset()
            {
                _current = 0;
            }
        }

        public IEnumerator<int> GetEnumerator()
        {
            return new OneToThree.OneToThreeEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return new OneToThree.OneToThreeEnumerator();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var onetothreeclass = new OneToThree();
            var itor = onetothreeclass.GetEnumerator();
            while (itor.MoveNext())
            {
                Console.WriteLine(itor.Current);
            }
        }
    }
}

对照

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static IEnumerable<int> GetOneToThreeClass()
        {
            int _current = 1;
            while (_current <= 3)
            {
                yield return _current++;
            }
        }

        static void Main(string[] args)
        {
            var onetothreeclass = GetOneToThreeClass();
            var itor = onetothreeclass.GetEnumerator();
            while (itor.MoveNext())
            {
                Console.WriteLine(itor.Current);
            }
        }
    }
}

#14

一般来说，一个函数的调用过程是，将调用者的地址保存，参数压入堆栈，函数执行，然后恢复堆栈，返回结果，转到调用者继续执行。
而yield return则可以自动产生一个匿名类，这个类的迭代器的current和movenext方法有些不同——它会将你的原来yield return的那个方法“拆开来”，使得它可以分段执行——在每次movenext被调用的时候，这个函数就会执行，直到遇到yield return，它会把函数的当前状态保存下来，并且挂起执行（事实上内部是用了一个线程）。当调用current的时候，就返回yield return的内容。当再次调用movenext的时候，就会恢复之前的函数调用，运行直到再次遇到yield return或者运行完，如果是运行到yield return，和之前说的一样，如果运行完也没有遇到yield return，movenext就会返回false。

为什么说这个过程是延迟执行的——很容易理解。因为当你遍历的时候，只有在调用movenext时候，这个函数才会执行一小部分，而不是像list那样，先运行完成，得到所有结果，装入内存，再开始迭代。