Code-Effizienz und Genauigkeit

Question

Ich versuche, ein Problem auf Code Kriege und die Unit-Tests zur Verfügung gestellt zu lösen machen absolut keinen Sinn ...

Das Problem ist wie folgt und klingt absolut einfach genug, um etwas in 5 Arbeits haben

Minuten

Consider a sequence u where u is defined as follows: 

The number u(0) = 1 is the first one in u. 
For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too. 
There are no other numbers in u. 
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...] 

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on... 

Task: 

Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u. 

Example: 

dbl_linear(10) should return 22 

zuerst habe ich eine SortedSet mit einer Linq-Abfrage verwendet, als ich über die Effizienz wirklich interessieren den Ball hielt, habe ich schnell gelernt, dass dieser Vorgang auf Bereiche berechnen haben, wobei n ~ 100000 in unter 12 Sekunden betragen könnte.

So wurde diese Abscheulichkeit geboren, dann wieder und wieder geschlachtet, da eine for-Schleife aus irgendeinem Grund Probleme erzeugen würde. Es wurde dann zu einer While-Schleife "aufgewertet", die etwas mehr bestandene Unit-Tests (4 -> 8) ergab.

public class DoubleLinear { 
    public static int DblLinear(int n) { 
     ListSet<int> table = new ListSet<int> {1}; 
     for (int i = 0; i < n; i++) { 
      table.Put(Y(table[i])); 
      table.Put(Z(table[i])); 
     } 
     table.Sort(); 
     return table[n]; 
    } 

    private static int Y(int y) { 
     return 2 * y + 1; 
    } 

    private static int Z(int z) { 
     return 3 * z + 1; 
    } 

} 

public class ListSet<T> : List<T> { 
    public void Put(T item) { 
     if (!this.Contains(item)) 
      this.Add(item); 
    } 

} 

Mit diesem Code schlägt es immer noch die Berechnung über n = 75000, aber besteht bis zu 8 Tests.

Ich habe überprüft, ob andere Leute diese bestanden haben, und sie haben. Allerdings kann ich nicht überprüfen, was sie geschrieben haben, um daraus zu lernen.

Kann jemand Einblick geben, was hier falsch sein könnte? Ich bin sicher, die Antwort ist offensichtlich und ich bin dumm.

Auch ist eine benutzerdefinierte Liste auf diese Weise eine schlechte Idee? Gibt es einen besseren Weg?

Answer 1

ListSet ist langsam zum Sortieren, und Sie erhalten ständig Speicher Neuzuweisung, wie Sie das Set erstellen. Ich würde damit beginnen, zuerst die Tabelle in ihrer vollen Größe zuzuordnen, obwohl ich ehrlich gesagt auch sagen würde, dass ein Barebone-Array der benötigten Größe für die Leistung am besten ist.

Wenn Sie wissen, dass Sie n = 75.000+ benötigen, ordnen Sie ein ListSet (oder ein ARRAY!) Dieser Größe zu. Wenn die Unit Tests dich in die Stratosphäre bringen, gibt es eine binäre Segmentierungstechnik, die wir diskutieren können, aber das ist ein bisschen kompliziert und logisch schwieriger aufzubauen.

Ich sehe nichts logisch falsch mit dem Code. Die Zahlen, die es erzeugt, sind korrekt von wo ich stehe.

EDIT: Da Sie wissen, 3n + 1> 2n + 1, Sie immer nur 6 Werte zu halten haben:

Target index in u 
Current index in u 
Current x for y 
Current x for z 
Current val for y 
Current val for z 
public static int DblLinear(int target) { 
    uint index = 1; 
    uint ind_y = 1; 
    uint ind_z = 1; 
    uint val_y = 3; 
    uint val_z = 4; 

    if(target < 1) 
     return 1; 

    while(index < target) { 
     if(val_y < val_z) { 
      ind_y++; 
      val_y = 2*ind_y + 1; 
     } else { 
      ind_z++; 
      val_z = 3*ind_z + 1; 
     } 
     index++; 
    } 

    return (val_y < val_z) ? val_y : val_z; 

} 

Sie könnten die val_y ändern, wenn eine while-Schleife (effiziente, kritisch zu sein Pfad), wenn Sie den Zweig entweder auf 2 Bedingungen erweitern oder eine Backstep-Schleife implementieren, wenn Sie Ihren Zielindex überschreiten.

Keine Speicherzuweisung wird definitiv Ihre Berechnungen beschleunigen, auch wenn Menschen (falsch) Bauchschmerzen über Verzweigungsprognose in solch einem leicht vorhersehbaren Fall haben wollen.

Haben Sie auch die Optimierung in Ihrem Visual Studio-Projekt aktiviert? Wenn Sie eine Binärdatei und keine Codedatei einreichen, kann das auch ziemlich viel Zeit sparen.