c# - ¿Cuándo es justo y sensato un stackoverflow?

ienumerable infinite

Question

Código actualizado

Para corregir el error de un Interminable filtrado, el siguiente código se actualiza y se combina con el original:

public static bool IsInfinity(this IEnumerable x) {
    var it=
        x as Infinity??((Func<object>)(() => {
            var info=x.GetType().GetField("source", bindingAttr);
            return null!=info?info.GetValue(x):x;
        }))();

    return it is Infinity;
}

bindingAttr se declara una constante.

• Resumen

  Estoy tratando de implementar una enumeración infinita , pero encontré algo que parece ser ilógico y se queda temporalmente sin idea. Necesito alguna dirección para completar el código, convirtiéndome en un diseño semántico, lógico y razonable.

• La historia completa

  He hecho la pregunta hace unas horas:

  ¿Es un enumerable infinito todavía "enumerable"?

  Esto podría no ser un buen patrón de implementación. Lo que estoy tratando de hacer, es implementar un enumerable para presentar el infinito, de una manera lógica y semántica (pensé ...). Yo pondría el código al final de esta publicación.

  El gran problema es que es solo para la presentación de infinitos enumerables, pero la enumeración de los mismos, de hecho, no tiene ningún sentido, ya que no hay elementos reales de los mismos.

  Entonces, además de proporcionar elementos ficticios para la enumeración, hay cuatro opciones que puedo imaginar, y tres llevan a la StackOverflowException .

  1. Lanzar una InvalidOperationException una vez que se va a enumerar.

     public IEnumerator<T> GetEnumerator() {
         for(var message="Attempted to enumerate an infinite enumerable"; ; )
             throw new InvalidOperationException(message);
     }

  2. y 3. son técnicamente equivalentes, deja que el desbordamiento de pila se produzca cuando está realmente desbordado.

     public IEnumerator<T> GetEnumerator() {
         foreach(var x in this)
             yield return x;
     }

     public IEnumerator<T> GetEnumerator() {
         return this.GetEnumerator();
     }

  3. (descrito en 2)

  4. No espere a que suceda, lance StackOverflowException directamente.

     public IEnumerator<T> GetEnumerator() {
         throw new StackOverflowException("... ");
     }

Las cosas difíciles son:

Si se aplica la option 1 , es decir, la enumeración en este enumerable, se convierte en una operación no válida . ¿No es extraño decir que esta lámpara no se utiliza para iluminar (aunque es cierto en mi caso)?

Si se aplica la option 2 o la option 3 , es decir, planeamos el desbordamiento de la pila. ¿Es realmente como el título, justo cuando el stackoverflow es justo y sensato ? ¿Perfectamente lógico y razonable?

La última opción es la option 4 . Sin embargo, la pila en realidad no se desborda, ya que lo evitamos lanzando una falsa StackOverflowException . Esto me recuerda que cuando Tom Cruise interpreta a John Anderton dijo: " Pero no se cayó. Lo atrapaste. El hecho de que evitaste que esto suceda no cambia el hecho de que iba a suceder " .

¿Algunas buenas maneras de evitar los problemas ilógicos?

El código es OPTION_4 y verificable, tenga en cuenta que uno de OPTION_4 a OPTION_4 debe definirse antes de compilar.

• Prueba simple

  var objects=new object[] { };
  Debug.Print("{0}", objects.IsInfinity());
  var infObjects=objects.AsInterminable();
  Debug.Print("{0}", infObjects.IsInfinity());

• Las clases

  using System.Collections.Generic;
  using System.Collections;
  using System;
  
  public static partial class Interminable /* extensions */ {
      public static Interminable<T> AsInterminable<T>(this IEnumerable<T> x) {
          return Infinity.OfType<T>();
      }
  
      public static Infinity AsInterminable(this IEnumerable x) {
          return Infinity.OfType<object>();
      }
  
      public static bool IsInfinity(this IEnumerable x) {
          var it=
              x as Infinity??((Func<object>)(() => {
                  var info=x.GetType().GetField("source", bindingAttr);
                  return null!=info?info.GetValue(x):x;
              }))();
  
          return it is Infinity;
      }
  
      const BindingFlags bindingAttr=
          BindingFlags.Instance|BindingFlags.NonPublic;
  }
  
  public abstract partial class Interminable<T>: Infinity, IEnumerable<T> {
      IEnumerator IEnumerable.GetEnumerator() {
          return this.GetEnumerator();
      }
  
  #if OPTION_1
      public IEnumerator<T> GetEnumerator() {
          for(var message="Attempted to enumerate an infinite enumerable"; ; )
              throw new InvalidOperationException(message);
      }
  #endif
  
  #if OPTION_2
      public IEnumerator<T> GetEnumerator() {
          foreach(var x in this)
              yield return x;
      }
  #endif
  
  #if OPTION_3
      public IEnumerator<T> GetEnumerator() {
          return this.GetEnumerator();
      }
  #endif
  
  #if OPTION_4
      public IEnumerator<T> GetEnumerator() {
          throw new StackOverflowException("... ");
      }
  #endif
  
      public Infinity LongCount<U>(
          Func<U, bool> predicate=default(Func<U, bool>)) {
          return this;
      }
  
      public Infinity Count<U>(
          Func<U, bool> predicate=default(Func<U, bool>)) {
          return this;
      }
  
      public Infinity LongCount(
          Func<T, bool> predicate=default(Func<T, bool>)) {
          return this;
      }
  
      public Infinity Count(
          Func<T, bool> predicate=default(Func<T, bool>)) {
          return this;
      }
  }
  
  public abstract partial class Infinity: IFormatProvider, ICustomFormatter {
      partial class Instance<T>: Interminable<T> {
          public static readonly Interminable<T> instance=new Instance<T>();
      }
  
      object IFormatProvider.GetFormat(Type formatType) {
          return typeof(ICustomFormatter)!=formatType?null:this;
      }
  
      String ICustomFormatter.Format(
          String format, object arg, IFormatProvider formatProvider) {
          return "Infinity";
      }
  
      public override String ToString() {
          return String.Format(this, "{0}", this);
      }
  
      public static Interminable<T> OfType<T>() {
          return Instance<T>.instance;
      }
  }

Answer 1

Como se mencionó en la otra publicación que vinculó, una enumeración infinita tiene mucho sentido para que C # enumere y hay una gran cantidad de ejemplos del mundo real en los que las personas escriben enumeradores que nunca terminan (lo primero que surge de mi mente es un azar). generador de números).

Entonces, tiene un caso particular en su problema matemático, donde necesita definir un valor especial (número infinito de puntos de intersección). Usualmente, ahí es donde uso constantes estáticas simples para. Simplemente defina una constante estática IEnumerable y pruebe con ella para averiguar si su algoritmo tuvo el " número infinito de intersección " como resultado.

Para una respuesta más específica a su pregunta actual: NUNCA NUNCA cause un desbordamiento de pila real. Esto es lo más desagradable que puede hacer a los usuarios de su código. No se puede detectar y terminará de inmediato su proceso (probablemente la única excepción es cuando se ejecuta dentro de un depurador de instrumentación adjunto).

Si es así, usaría NotSupportedException que se usa en otros lugares para indicar que alguna clase no admite una función (por ejemplo, ICollection s puede lanzar esto en Remove() si son de solo lectura).

Answer 2

Las secuencias infinitas pueden ser perfectamente iterables / enumerables. Los números naturales son enumerables y también lo son los números racionales o los dígitos PI. Infinito es lo opuesto de finito, no enumerable.

Las variantes que has proporcionado no representan las secuencias infinitas. Hay infinitas secuencias infinitas diferentes y puedes ver que son diferentes iterando a través de ellas. Tu idea, por otro lado, es tener un singleton, que va en contra de esa diversidad.

Si tiene algo que no se puede enumerar (como el conjunto de números reales), entonces no debe definirlo como IEnumerable ya que está incumpliendo el contrato. Si desea discernir entre secuencias enumerables finitas e infinitas, simplemente IInfiniteEnumerable : IEnumerable una nueva interfaz IInfiniteEnumerable : IEnumerable y marque secuencias infinitas con ella.

Interfaz que marca secuencias infinitas.

public interface IInfiniteEnumerable<T> : IEnumerable<T> {
}

Un contenedor para convertir un IEnumerable<T> a IInfiniteEnumerable<T> (los IEnumerable s se crean fácilmente con la sintaxis de yield C #, pero necesitamos convertirlos a IInfiniteEnumerable )

public class InfiniteEnumerableWrapper<T> : IInfiniteEnumerable<T> {
    IEnumerable<T> _enumerable;

    public InfiniteEnumerableWrapper(IEnumerable<T> enumerable) {
        _enumerable = enumerable;
    }

    public IEnumerator<T> GetEnumerator() {
        return _enumerable.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return _enumerable.GetEnumerator();
    }
}

Algunas rutinas conscientes del infinito (como calcular la longitud de la secuencia)

//TryGetCount() returns null if the sequence is infinite
public static class EnumerableExtensions {
    public static int? TryGetCount<T>(this IEnumerable<T> sequence) {
        if (sequence is IInfiniteEnumerable<T>) {
            return null;
        } else {
            return sequence.Count();
        }
    }
}

Dos ejemplos de secuencias: una secuencia de rango finito y la secuencia infinita de Fibonacci.

public class Sequences {
    public static IEnumerable<int> GetIntegerRange(int start, int count) {
        return Enumerable.Range(start, count);
    }

    public static IInfiniteEnumerable<int> GetFibonacciSequence() {
        return new InfiniteEnumerableWrapper<int>(GetFibonacciSequenceInternal());
    }

    static IEnumerable<int> GetFibonacciSequenceInternal() {
        var p = 0;
        var q = 1;
        while (true) {
            yield return p;
            var newQ = p + q;
            p = q;
            q = newQ;
        }
    }
}

Una aplicación de prueba que genera secuencias aleatorias y trata de calcular sus longitudes.

public class TestApp {
    public static void Main() {
        for (int i = 0; i < 20; i++) {
            IEnumerable<int> sequence = GetRandomSequence();
            Console.WriteLine(sequence.TryGetCount() ?? double.PositiveInfinity);
        }
        Console.ReadLine();
    }

    static Random _rng = new Random();
    //Randomly generates an finite or infinite sequence
    public static IEnumerable<int> GetRandomSequence() {
        int random = _rng.Next(5) * 10;
        if (random == 0) {
            return Sequences.GetFibonacciSequence();
        } else {
            return Sequences.GetIntegerRange(0, random);
        }
    }
}

El programa de salida algo como esto:

20
40
20
10
20
10
20
Infinity
40
30
40
Infinity
Infinity
40
40
30
20
30
40
30

Answer 3

Si entiendo correctamente, infinito es una palabra confusa aquí. Creo que necesitas una mónada que sea enumerable o no. Pero sigamos con el infinito por ahora.

No puedo pensar en una buena manera de implementar esto en C #. Todas las formas en que esto podría implementarse no se integran con los generadores de C #.

Con el generator C #, solo puedes emitir valores válidos; así que no hay manera de indicar que esto es un enumerable infinito . No me gusta la idea de lanzar excepciones desde el generador para indicar que es infinito ; porque para comprobar que es infinito , tendrás que intentar atrapar todas las veces.

Si no necesita admitir generadores, veo las siguientes opciones:

1. Implementar centinela enumerable:

   public class InfiniteEnumerable<T>: IEnumerable<T> {
       private static InfiniteEnumerable<T> val;
   
       public static InfiniteEnumerable<T> Value {
           get {
               return val;
           }
       }
   
       public IEnumerator<T> GetEnumerator() {
           throw new InvalidOperationException(
               "This enumerable cannot be enumerated");
       }
   
       IEnumerator IEnumerable.GetEnumerator() {
           throw new InvalidOperationException(
                "This enumerable cannot be enumerated");
       }
   }

   Uso de la muestra:

   IEnumerable<int> enumerable=GetEnumerable();
   
   if(enumerable==InfiniteEnumerable<int>.Value) {
       // This is ''infinite'' enumerable.
   }
   else {
       // enumerate it here.
   }

2. Implementar envoltorio Infinitable<T> :

   public class Infinitable<T>: IEnumerable<T> {
       private IEnumerable<T> enumerable;
       private bool isInfinite;
   
       public Infinitable(IEnumerable<T> enumerable) {
           this.enumerable=enumerable;
           this.isInfinite=false;
       }
   
       public Infinitable() {
           this.isInfinite=true;
       }
   
       public bool IsInfinite {
           get {
               return isInfinite;
           }
       }
   
       public IEnumerator<T> GetEnumerator() {
           if(isInfinite) {
               throw new InvalidOperationException(
                   "The enumerable cannot be enumerated");
           }
   
           return this.enumerable.GetEnumerator();
       }
   
       IEnumerator IEnumerable.GetEnumerator() {
           if(isInfinite) {
               throw new InvalidOperationException(
                    "The enumerable cannot be enumerated");
           }
   
           return this.enumerable.GetEnumerator();
       }
   }

   Uso de la muestra:

   Infinitable<int> enumerable=GetEnumerable();
   
   if(enumerable.IsInfinite) {
       // This is ''infinite'' enumerable.
   }
   else {
       // enumerate it here.
       foreach(var i in enumerable) {
       }
   }

Answer 4

public IEnumerator<T> GetEnumerator()
{
    while (true)
        yield return default(T);
}

Esto creará un enumerador infinito; un foreach en él nunca terminará y solo continuará dando el valor predeterminado.

Tenga en cuenta que no podrá determinar IsInfinity() la forma que escribió en su código. Esto se debe a que el new Infinity().Where(o => o == /*do any kind of comparison*/) seguirá siendo infinito pero tendrá un tipo diferente.