эффективность и точность

Question

Я пытаюсь решить проблему на кодовых войнах и юнит-тесты, предусмотренные код делают абсолютно никакого смысла ...

Проблемы не так и звучит абсолютно достаточно просто иметь что-то работает в 5 минуты

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 

Сначала я использовал SortedSet с Linq запросом, как я действительно не забочусь об эффективности, я быстро понял, что эта операция будет вычислять диапазоны где п может равняться ~ 100000 в возрасте до 12 секунд.

Так что эта мерзость родилась, а затем снова и снова забивалась, так как цикл по какой-то причине создавал проблемы. Затем он был «обновлен» до цикла while, который дал несколько более отдаленные модульные тесты (4 -> 8).

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); 
    } 

} 

С помощью этого кода он все еще терпит неудачу при вычислении сверх n = 75000, но проходит до 8 тестов.

Я проверил, прошли ли другие люди, и у них есть. Однако я не могу проверить, что они написали, чтобы учиться на нем.

Может ли кто-нибудь дать представление о том, что может быть неправильным здесь? Я уверен, что ответ откровенно очевиден, и я тупой.

Также использует пользовательский список таким образом, плохая идея? Есть ли способ лучше?

Answer 1

ListSet медленный для сортировки, и вы постоянно получаете перераспределение памяти при создании набора. Сначала я сначала выделил таблицу в своем полном размере, хотя, честно говоря, я бы также сказал, что использование массива barebone размером, который вам нужен, лучше всего подходит для производительности.

Если вы знаете, что вам нужно n = 75 000+, выделите ListSet (или ARRAY!) Этого размера. Если тесты модуля начнут принимать вас в стратосферу, мы можем обсудить технику двоичной сегментации, но это немного связано и логически сложнее строить.

Я не вижу ничего логически неправильно с кодом. Числа, которые он генерирует, верны с того места, где я стою.

EDIT: Поскольку вы знаете 3n + 1> 2n + 1, вам нужно всего лишь поддерживать 6 значений:

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; 

} 

Вы можете модифицируют val_y, если петля в то время (более эффективное критическое путь), если вы либо расширяете ветвь до 2 условий, либо реализуете задний цикл, когда вы пробиваете свой целевой показатель.

Нет распределения памяти, безусловно, ускорит расчеты, даже если люди хотят (неправильно) живота болеть о предсказании ветвления в таком легко предсказуемом случае.

Кроме того, вы включили оптимизацию в свой проект Visual Studio? Если вы отправляете двоичный файл, а не файл кода, то это также может побрить довольно много времени.