在 C# 和非托管 C++ 中生成无限序列
5.00/5 (1投票)
如何在 C# 和非托管 C++ 中生成无限序列
引言
无限序列，例如斐波那契数列或质数，在计算中具有重要的应用。例如，斐波那契数列被用于一些伪随机数生成器，而质数的一个应用是 RSA（Rivest-Shamir-Adleman）密码系统。考虑斐波那契数列的计算，定义如下
定义是递归的，并且可以简单地在 C# 中实现，例如在一个控制台应用程序中，如下所示
static int Fib( int n )
{
if ( n <= 1 )
{
return n;
}
else
{
return Fib( n - 1 ) + Fib( n - 2 );
}
}// Fib
如果希望跟踪斐波那契数列的所有元素，直到 n，则另一个函数将不得不将它们存储在一个适当大小的全局数组中。这种方法的缺点是数组的分配以及需要预先知道其大小（或在 C# 中的长度）。
在非托管 C++ 中生成任意长度的斐波那契数列
C 和 C++ 编程语言允许在函数中声明静态局部变量。此类变量在每次调用使用它们的函数时都会保留其最后一个值。有了这样的功能，就可以定义一个函数，该函数每次调用时都会返回下一个斐波那契数，如下所示
int NextFib( int reset = 0 )
{
static int fI = 0, fIp1 = 1;
int retVal, nextVal;
if ( reset )
{
fI = 0; fIp1 = 1;
}
retVal = fI;
nextVal = fI + fIp1;
fI = fIp1;
fIp1 = nextVal;
return retVal;
}// NextFib
void TestNextFib( int n )
{
int i;
for ( i = 0; i < n; ++i )
{
printf( "%d\n", NextFib() );
}
}// TestNextFib
函数 NextFib 生成任意长度的斐波那契数列，这取决于传递给函数 TestNextFib 的参数的值。
在 C# 中生成任意长度的斐波那契数列
C# 编程语言不 允许在函数中声明 static 局部变量。 如果试图在 Visual Studio 代码编辑器中声明它们，编译器会发出错误。
static int NextFib( bool reset = false )
{
// The modifier 'static' is not valid for this item
static int fI = 0, fIp1 = 1;
} // NextFib
但是，通过实现合适的 IEnumerator 函数，可以使用 C# 中与非托管 C++ 代码相同的结果，如以下控制台应用程序所示
// C:\Users\Jorge\Documents\Visual Studio 2010\Projects\C#
// \FibStream\Program.cs
//
// Generation of sequences (streams) of Fibonacci numbers of
// arbitrary length by means of an IEnumerator function.
//
// Programmer: Jorge L. Orejel
//
// Last update: 09/18/2020 : Removal of unnecessary 'using' statements.
//
// 01/01/2016 : Original coding.
using System;
using System.Collections.Generic;
namespace FibStream
{
class Program
{
static void Main( string[] args )
{
Console.WriteLine();
IEnumerator<int> Fibs = NextFib();
for ( int i = 0; i < 40; ++i )
{
if ( Fibs.MoveNext() )
{
Console.WriteLine( "Fib( {0,2} ) = {1}",
i, Fibs.Current );
}
else break;
}
Console.WriteLine();
}// Main
static IEnumerator<int> NextFib()
{
int a = 0, b = 1, t;
while ( true )
{
yield return a;
t = a + b;
a = b;
b = t;
}
}// NextFib
}// Program (class)
}// FibStream (namespace)
序列的长度取决于枚举器 NextFib 被调用的次数。 执行控制台应用程序将产生以下输出
Fib( 0 ) = 0
Fib( 1 ) = 1
Fib( 2 ) = 1
Fib( 3 ) = 2
Fib( 4 ) = 3
Fib( 5 ) = 5
Fib( 6 ) = 8
Fib( 7 ) = 13
Fib( 8 ) = 21
Fib( 9 ) = 34
Fib( 10 ) = 55
Fib( 11 ) = 89
Fib( 12 ) = 144
Fib( 13 ) = 233
Fib( 14 ) = 377
Fib( 15 ) = 610
Fib( 16 ) = 987
Fib( 17 ) = 1597
Fib( 18 ) = 2584
Fib( 19 ) = 4181
Fib( 20 ) = 6765
Fib( 21 ) = 10946
Fib( 22 ) = 17711
Fib( 23 ) = 28657
Fib( 24 ) = 46368
Fib( 25 ) = 75025
Fib( 26 ) = 121393
Fib( 27 ) = 196418
Fib( 28 ) = 317811
Fib( 29 ) = 514229
Fib( 30 ) = 832040
Fib( 31 ) = 1346269
Fib( 32 ) = 2178309
Fib( 33 ) = 3524578
Fib( 34 ) = 5702887
Fib( 35 ) = 9227465
Fib( 36 ) = 14930352
Fib( 37 ) = 24157817
Fib( 38 ) = 39088169
Fib( 39 ) = 63245986
Press any key to continue . . .
令人惊讶的是，使用 yield 关键字，NextFib 中的局部变量 a、b 和 t 的行为就像它们被声明为 static 一样。
示例应用程序：Dijkstra 的经典生产者-消费者问题
生产者-消费者问题由已故 Edsger W. Dijkstra 在他的章节“协作顺序进程”中描述，该章节发表在书籍《编程语言》（由 F. Genuys 编辑，Academic Press，1968 年，第 43-112 页）中。 该问题涉及两个进程（生产者和消费者）之间的交互，它们通过共享缓冲区交换项目，以使它们完美同步。出于历史原因，并为了尊重作者在德克萨斯大学奥斯汀分校计算机科学系的前教授，Dijkstra 对该问题的 Algol 60 解决方案（在他的章节的第 71 页和第 72 页）重现如下
关键字 begin 和 end 括起顺序代码，关键字 parbegin 和 parend 括起并行运行的协作顺序进程。字符 := 表示赋值语句。 P（荷兰语中的 passeren）和 V（荷兰语中的 vrijeven）是互斥或计数信号量上的众所周知的操作。 它们需要是不可分割的，也就是说，如果两个进程对同一个信号量执行这些操作中的任何一个，则执行会一个接一个地进行，无论哪个顺序。
信号量是包含一个整数值和一个阻塞进程队列的数据结构。互斥信号量的初始值为 1，而计数信号量具有任意正的初始值。P 和 V 操作的伪代码实现如下
P( S ):
--S.value;
if ( S.value < 0 )
{
Block the process that called P;
Execute another available process;
}
V( S ):
++S.value;
if ( S.value < 0 )
{
Unblock the process at the front of the queue;
}
示例应用程序的 Win32 实现
Dijkstra 的经典生产者-消费者问题的非托管 C++ (Win32) 实现涉及使用两个线程（一个运行生产者代码，另一个运行消费者代码）、互斥锁和信号量同步机制、一个实现为循环队列的共享缓冲区，以及一个生成任意长度斐波那契数列的生成器。 生产者和消费者使用不同的参数值调用函数 Sleep，以证明适当的同步与它们相对的速度无关。
// C:\Users\Jorge\Documents\Visual Studio 2010\Projects\C++ unmanaged
// \ClassicProducerConsumer\ClassicProducerConsumer.cpp
// : Defines the entry point for the console application.
//
// Unmanaged C++ implementation of Dijkstra's classic producer/consumer
// problem using threads, mutex and semaphore synchronization mechanisms,
// a shared buffer implemented as a circular queue, and a generator of
// arbitrary-length sequences of Fibonacci numbers.
//
// Programmer: Jorge L. Orejel
//
// Last update: 09/17/2020 : Minor cosmetic changes.
//
// 06/12/2016 : Original coding.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#define SIZE 10 // Circular buffer effective size.
#define SIZEp1 (SIZE + 1) // Circular buffer allocated size.
#define MAX_ITEMS 25 // Number of items to produce.
#define MAX_WAIT 15000 // Maximum wait time (15 seconds)
int buffer[ SIZE + 1 ]; // Shared buffer (one element never used).
int head, tail; // Indices into 'buffer'.
HANDLE hMutex; // Mutual-exclusion semaphore.
HANDLE hFull, hEmpty; // Counting semaphores.
void InitBuffer();
int Succ( int );
void PrintBuffer();
int NextFib( int = 0 );
void TestNextFib( int );
void Producer();
void Consumer();
int _tmain( int argc, _TCHAR* argv[] )
{
HANDLE hThreadVector[ 2 ]; // Vector for the handles to the producer/consumer threads
DWORD threadID;
InitBuffer();
// Mutual-exclusion semaphore for the buffer
hMutex = CreateMutex( NULL, FALSE, NULL );
// Counting semaphore of full buffer slots
hFull = CreateSemaphore( NULL, 0, (LONG)SIZE, NULL );
// Counting semaphore of empty buffer slots
hEmpty = CreateSemaphore( NULL, (LONG)SIZE, (LONG)SIZE, NULL );
hThreadVector[ 0 ]
=
CreateThread( NULL, // No security attributes
0, // Default stack size
(LPTHREAD_START_ROUTINE)Producer, // Code executed by the thread
NULL, // No parameter passed to the thread
CREATE_SUSPENDED, // Creation flag
(LPDWORD)&threadID ); // Thread identifier (not used)
hThreadVector[ 1 ]
=
CreateThread( NULL, // No security attributes
0, // Default stack size
(LPTHREAD_START_ROUTINE)Consumer, // Code executed by the thread
NULL, // No parameter passed to the thread
CREATE_SUSPENDED, // Creation flag
(LPDWORD)&threadID ); // Thread identifier (not used)
ResumeThread( hThreadVector[ 0 ] ); // Start Producer thread
ResumeThread( hThreadVector[ 1 ] ); // Start Consumer thread
WaitForMultipleObjects( 2, hThreadVector, TRUE, INFINITE ); // Wait for both threads to end
printf( "\n" );
return 0;
}// _tmain
// Producer thread.
//
// Requirement: The Producer must be prevented from placing an item into a full buffer.
void Producer()
{
int i, item;
for ( i = 0; i < MAX_ITEMS; ++i )
{
item = NextFib(); // Produce
Sleep( 1000 ); // item
WaitForSingleObject( hEmpty, MAX_WAIT ); // == P( hEmpty ): Is there an empty slot ?
WaitForSingleObject( hMutex, MAX_WAIT ); // == P( hMutex ): Lock buffer
//
tail = Succ( tail );
buffer[ tail ] = item;
printf( "Producer: %5d -> buffer[ %2d ]: ", item, tail );
PrintBuffer();
//
ReleaseMutex( hMutex ); // == V( hMutex ): Unlock buffer
ReleaseSemaphore( hFull, 1, NULL ); // == V( hFull): Signal one full slot
}
printf( "Producer ended\n" );
}// Producer
// Consumer thread.
//
// Requirement: The Consumer must be prevented from removing an item from an empty buffer.
void Consumer()
{
int item;
while ( 1 )
{
WaitForSingleObject( hFull, MAX_WAIT ); // == P( hFull ): Is there a full slot ?
WaitForSingleObject( hMutex, MAX_WAIT ); // == P( hMutex ): Lock buffer
//
head = Succ( head );
item = buffer[ head ];
buffer[ head ] = -1; // Mark the slot as empty
if ( item == -1 ) // The buffer is empty
{ // because the Producer has stopped
//
ReleaseMutex( hMutex ); // == V( hMutex ): Unlock buffer
break; // Break from the while loop
}
printf( "Consumer: %5d <- buffer[ %2d ]: ", item, head );
PrintBuffer();
//
ReleaseMutex( hMutex ); // == V( hMutex ): Unlock buffer
ReleaseSemaphore( hEmpty, 1, NULL ); // == V( hEmpty ):Signal one empty slot
Sleep( 3000 ); // Consume item
}
printf( "Consumer ended\n" );
}// Consumer
void InitBuffer()
{
int i;
for ( i = 0; i < SIZEp1; ++i )
{
buffer[ i ] = -1; // empty slot
}
head = tail = 0; // empty buffer
}// InitBuffer
int Succ( int index ) // Next index into buffer
{
return (index + 1) % SIZEp1;
}// Succ
void PrintBuffer()
{
int i;
printf( "[ " );
for ( i = 0; i < SIZEp1; ++i )
{
if ( buffer[ i ] == -1 )
{
printf( "%5c ", '.' );
}
else
{
printf( "%5d ", buffer[ i ] );
}
}
printf( "]\n" );
}// PrintBuffer
// Generate next Fibonacci number
//
// From the function prototype, parameter 'reset' is
// optional, with a default value of 0.
int NextFib( int reset )
{
static int fI = 0, fIp1 = 1;
int retVal, nextVal;
if ( reset )
{
fI = 0; fIp1 = 1;
}
retVal = fI;
nextVal = fI + fIp1;
fI = fIp1;
fIp1 = nextVal;
return retVal;
}// NextFib
void TestNextFib( int n )
{
int i;
for ( i = 0; i < n; ++i )
{
printf( "%d\n", NextFib() );
}
}// TestNextFib
执行上述 Win32 控制台应用程序会产生以下输出。（缓冲区中的空槽用句点表示。）
Producer: 0 -> buffer[ 1 ]: [ . 0 . . . . . . . . . ]
Consumer: 0 <- buffer[ 1 ]: [ . . . . . . . . . . . ]
Producer: 1 -> buffer[ 2 ]: [ . . 1 . . . . . . . . ]
Producer: 1 -> buffer[ 3 ]: [ . . 1 1 . . . . . . . ]
Consumer: 1 <- buffer[ 2 ]: [ . . . 1 . . . . . . . ]
Producer: 2 -> buffer[ 4 ]: [ . . . 1 2 . . . . . . ]
Producer: 3 -> buffer[ 5 ]: [ . . . 1 2 3 . . . . . ]
Producer: 5 -> buffer[ 6 ]: [ . . . 1 2 3 5 . . . . ]
Consumer: 1 <- buffer[ 3 ]: [ . . . . 2 3 5 . . . . ]
Producer: 8 -> buffer[ 7 ]: [ . . . . 2 3 5 8 . . . ]
Producer: 13 -> buffer[ 8 ]: [ . . . . 2 3 5 8 13 . . ]
Producer: 21 -> buffer[ 9 ]: [ . . . . 2 3 5 8 13 21 . ]
Consumer: 2 <- buffer[ 4 ]: [ . . . . . 3 5 8 13 21 . ]
Producer: 34 -> buffer[ 10 ]: [ . . . . . 3 5 8 13 21 34 ]
Producer: 55 -> buffer[ 0 ]: [ 55 . . . . 3 5 8 13 21 34 ]
Producer: 89 -> buffer[ 1 ]: [ 55 89 . . . 3 5 8 13 21 34 ]
Consumer: 3 <- buffer[ 5 ]: [ 55 89 . . . . 5 8 13 21 34 ]
Producer: 144 -> buffer[ 2 ]: [ 55 89 144 . . . 5 8 13 21 34 ]
Producer: 233 -> buffer[ 3 ]: [ 55 89 144 233 . . 5 8 13 21 34 ]
Producer: 377 -> buffer[ 4 ]: [ 55 89 144 233 377 . 5 8 13 21 34 ]
Consumer: 5 <- buffer[ 6 ]: [ 55 89 144 233 377 . . 8 13 21 34 ]
Producer: 610 -> buffer[ 5 ]: [ 55 89 144 233 377 610 . 8 13 21 34 ]
Consumer: 8 <- buffer[ 7 ]: [ 55 89 144 233 377 610 . . 13 21 34 ]
Producer: 987 -> buffer[ 6 ]: [ 55 89 144 233 377 610 987 . 13 21 34 ]
Consumer: 13 <- buffer[ 8 ]: [ 55 89 144 233 377 610 987 . . 21 34 ]
Producer: 1597 -> buffer[ 7 ]: [ 55 89 144 233 377 610 987 1597 . 21 34 ]
Consumer: 21 <- buffer[ 9 ]: [ 55 89 144 233 377 610 987 1597 . . 34 ]
Producer: 2584 -> buffer[ 8 ]: [ 55 89 144 233 377 610 987 1597 2584 . 34 ]
Consumer: 34 <- buffer[ 10 ]: [ 55 89 144 233 377 610 987 1597 2584 . . ]
Producer: 4181 -> buffer[ 9 ]: [ 55 89 144 233 377 610 987 1597 2584 4181 . ]
Consumer: 55 <- buffer[ 0 ]: [ . 89 144 233 377 610 987 1597 2584 4181 . ]
Producer: 6765 -> buffer[ 10 ]: [ . 89 144 233 377 610 987 1597 2584 4181 6765 ]
Consumer: 89 <- buffer[ 1 ]: [ . . 144 233 377 610 987 1597 2584 4181 6765 ]
Producer: 10946 -> buffer[ 0 ]: [ 10946 . 144 233 377 610 987 1597 2584 4181 6765 ]
Consumer: 144 <- buffer[ 2 ]: [ 10946 . . 233 377 610 987 1597 2584 4181 6765 ]
Producer: 17711 -> buffer[ 1 ]: [ 10946 17711 . 233 377 610 987 1597 2584 4181 6765 ]
Consumer: 233 <- buffer[ 3 ]: [ 10946 17711 . . 377 610 987 1597 2584 4181 6765 ]
Producer: 28657 -> buffer[ 2 ]: [ 10946 17711 28657 . 377 610 987 1597 2584 4181 6765 ]
Consumer: 377 <- buffer[ 4 ]: [ 10946 17711 28657 . . 610 987 1597 2584 4181 6765 ]
Producer: 46368 -> buffer[ 3 ]: [ 10946 17711 28657 46368 . 610 987 1597 2584 4181 6765 ]
Producer ended
Consumer: 610 <- buffer[ 5 ]: [ 10946 17711 28657 46368 . . 987 1597 2584 4181 6765 ]
Consumer: 987 <- buffer[ 6 ]: [ 10946 17711 28657 46368 . . . 1597 2584 4181 6765 ]
Consumer: 1597 <- buffer[ 7 ]: [ 10946 17711 28657 46368 . . . . 2584 4181 6765 ]
Consumer: 2584 <- buffer[ 8 ]: [ 10946 17711 28657 46368 . . . . . 4181 6765 ]
Consumer: 4181 <- buffer[ 9 ]: [ 10946 17711 28657 46368 . . . . . . 6765 ]
Consumer: 6765 <- buffer[ 10 ]: [ 10946 17711 28657 46368 . . . . . . . ]
Consumer: 10946 <- buffer[ 0 ]: [ . 17711 28657 46368 . . . . . . . ]
Consumer: 17711 <- buffer[ 1 ]: [ . . 28657 46368 . . . . . . . ]
Consumer: 28657 <- buffer[ 2 ]: [ . . . 46368 . . . . . . . ]
Consumer: 46368 <- buffer[ 3 ]: [ . . . . . . . . . . . ]
Consumer ended
Press any key to continue . . .
Using the Code
代码包含两个文件。 文件 Program.cs 是用于生成任意长度斐波那契数列的 C# 源代码。 文件 ClassicProducerConsumer.cpp 是 Dijkstra 生产者-消费者问题的 Win32 实现。
历史
- 2020 年 9 月 20 日：初始版本