Быстрее альтернатива вложенным циклам?

Ответ 1

Вы можете использовать свойства структуры и заранее выделить структуру. Я отключил некоторые уровни в примере ниже, но я уверен, что вы сможете выяснить особенности. Работает примерно в 5-6 раз быстрее, чем исходный (режим выпуска).

Блок:

struct ByteBlock
{
    public byte A;
    public byte B;
    public byte C;
    public byte D;
    public byte E;
}

Цикл:

var data = new ByteBlock[2*3*4*3*4];
var counter = 0;

var bytes = new ByteBlock();

for (byte a = 0; a < 2; a++)
{
    bytes.A = a;
    for (byte b = 0; b < 3; b++)
    {
        bytes.B = b;
        for (byte c = 0; c < 4; c++)
        {
            bytes.C = c;
            for (byte d = 0; d < 3; d++)
            {
                bytes.D = d;
                for (byte e = 0; e < 4; e++)
                {
                    bytes.E = e;
                    data[counter++] = bytes;
                }
            }
        }
    }
}

Это быстрее, потому что он не выделяет новый список при каждом добавлении его в список. Кроме того, поскольку он создает этот список, ему нужна ссылка на все другие значения (a, b, c, d, e). Вы можете предположить, что каждое значение изменяется только один раз внутри цикла, поэтому мы можем оптимизировать его для этого (локализация данных).

Также читайте комментарии к побочным эффектам.

Отредактирован ответ на использование T[] вместо List<T>.

Ответ 2

То, что вы делаете, - это подсчет (с переменным основанием, но все еще считая).

Поскольку вы используете С#, я предполагаю, что вы не хотите играть с полезным макетом памяти и структурами данных, которые позволяют вам действительно оптимизировать ваш код.

Итак, я публикую что-то другое, что может не понравиться вашему делу, но стоит отметить: если вы действительно получаете доступ к списку в разреженном порядке, вот класс, который позволяет вам вычислить i-й элемент в линейном времени (а не экспоненциально, как другие ответы)

class Counter
{
    public int[] Radices;

    public int[] this[int n]
    {
        get 
        { 
            int[] v = new int[Radices.Length];
            int i = Radices.Length - 1;

            while (n != 0 && i >= 0)
            {
                //Hope C# has an IL-opcode for div-and-reminder like x86 do
                v[i] = n % Radices[i];
                n /= Radices[i--];
            }
            return v;
        }
    }
}

Вы можете использовать этот класс таким образом

Counter c = new Counter();
c.Radices = new int[] { 2,3,4,3,4,3,3,4,2,4,4,3,4};

теперь c[i] совпадает с вашим списком, назовите его l, l[i].

Как вы можете видеть, вы можете легко избежать всех этих циклов:), даже если вы предварительно вычислили весь список в целом, поскольку вы можете просто выполнить счетчик Carry-Ripple.

Счётчики - очень изученный предмет, я настоятельно советю искать какую-то литературу, если вы чувствуете.

Ответ 3

Метод 1

Один из способов сделать это быстрее - указать емкость, если вы планируете использовать List<byte[]>, например.

var data = new List<byte[]>(2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4);

Метод 2

Кроме того, вы можете использовать System.Array для получения более быстрого доступа. Я рекомендую этот подход, если ваш вопрос настаивает на том, чтобы каждый элемент был физически заполнен в памяти, заранее.

var data = new byte[2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4][];
int counter = 0;

for (byte a = 0; a < 2; a++)
    for (byte b = 0; b < 3; b++)
        for (byte c = 0; c < 4; c++)
            for (byte d = 0; d < 3; d++)
                for (byte e = 0; e < 4; e++)
                    for (byte f = 0; f < 3; f++)
                        for (byte g = 0; g < 3; g++)
                            for (byte h = 0; h < 4; h++)
                                for (byte i = 0; i < 2; i++)
                                    for (byte j = 0; j < 4; j++)
                                        for (byte k = 0; k < 4; k++)
                                            for (byte l = 0; l < 3; l++)
                                                for (byte m = 0; m < 4; m++)
                                                    data[counter++] = new[] { a, b, c, d, e, f, g, h, i, j, k, l, m };

Для этого на моем компьютере требуется 596 ms, что примерно на на 10,4% быстрее, чем этот код (который занимает 658 мс).

Метод 3

В качестве альтернативы вы можете использовать следующую технику для инициализации с низкой стоимостью, которая подходит для доступа разреженно. Это особенно выгодно, когда могут потребоваться только некоторые элементы и определить их все заранее считается ненужным. Более того, такие методы могут стать единственным жизнеспособным вариантом при работе с более обширными элементами при короткой работе памяти.

В этой реализации каждый элемент должен быть определен лениво, "на лету", при доступе. Естественно, это связано с дополнительным процессором, который возникает при доступе.

class HypotheticalBytes
{
    private readonly int _c1, _c2, _c3, _c4, _c5, _c6, _c7, _c8, _c9, _c10, _c11, _c12;
    private readonly int _t0, _t1, _t2, _t3, _t4, _t5, _t6, _t7, _t8, _t9, _t10, _t11;

    public int Count
    {
        get { return _t0; }
    }

    public HypotheticalBytes(
        int c0, int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9, int c10, int c11, int c12)
    {
        _c1 = c1;
        _c2 = c2;
        _c3 = c3;
        _c4 = c4;
        _c5 = c5;
        _c6 = c6;
        _c7 = c7;
        _c8 = c8;
        _c9 = c9;
        _c10 = c10;
        _c11 = c11;
        _c12 = c12;
        _t11 = _c12 * c11;
        _t10 = _t11 * c10;
        _t9 = _t10 * c9;
        _t8 = _t9 * c8;
        _t7 = _t8 * c7;
        _t6 = _t7 * c6;
        _t5 = _t6 * c5;
        _t4 = _t5 * c4;
        _t3 = _t4 * c3;
        _t2 = _t3 * c2;
        _t1 = _t2 * c1;
        _t0 = _t1 * c0;
    }

    public byte[] this[int index]
    {
        get
        {
            return new[]
            {
                (byte)(index / _t1),
                (byte)((index / _t2) % _c1),
                (byte)((index / _t3) % _c2),
                (byte)((index / _t4) % _c3),
                (byte)((index / _t5) % _c4),
                (byte)((index / _t6) % _c5),
                (byte)((index / _t7) % _c6),
                (byte)((index / _t8) % _c7),
                (byte)((index / _t9) % _c8),
                (byte)((index / _t10) % _c9),
                (byte)((index / _t11) % _c10),
                (byte)((index / _c12) % _c11),
                (byte)(index % _c12)
            };
        }
    }
}

Для этого на моем компьютере требуется 897 ms (также создавая и добавляя к Array, как в методе 2), что примерно на на 36,3% медленнее, чем соответствующий код (который принимает 658 мс).

Ответ 4

На моей машине это генерирует комбинации в 222 мс против 760 мс (13 циклов):

private static byte[,] GenerateCombinations(params byte[] maxNumberPerLevel)
{
    var levels = maxNumberPerLevel.Length;

    var periodsPerLevel = new int[levels];
    var totalItems = 1;
    for (var i = 0; i < levels; i++)
    {
        periodsPerLevel[i] = totalItems;
        totalItems *= maxNumberPerLevel[i];
    }

    var results = new byte[totalItems, levels];

    Parallel.For(0, levels, level =>
    {
        var periodPerLevel = periodsPerLevel[level];
        var maxPerLevel = maxNumberPerLevel[level];
        for (var i = 0; i < totalItems; i++)
            results[i, level] = (byte)(i / periodPerLevel % maxPerLevel);
    });

    return results;
}

Ответ 5

var numbers = new[] { 2, 3, 4, 3, 4, 3, 3, 4, 2, 4, 4, 3, 4 };
var result = (numbers.Select(i => Enumerable.Range(0, i))).CartesianProduct();

Использование метода расширения в http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    // base case: 
    IEnumerable<IEnumerable<T>> result =
        new[] { Enumerable.Empty<T>() };
    foreach (var sequence in sequences)
    {
        // don't close over the loop variable (fixed in C# 5 BTW)
        var s = sequence;
        // recursive case: use SelectMany to build 
        // the new product out of the old one 
        result =
            from seq in result
            from item in s
            select seq.Concat(new[] { item });
    }
    return result;
}

Ответ 6

Список имеет массив внутри, где он хранит его значения с фиксированной длиной. Когда вы вызываете List.Add, он проверяет, достаточно ли места. Когда dcannot добавит новый элемент, он создаст новый массив большего размера, скопирует все предыдущие элементы и добавит новый. Это занимает довольно много циклов.

Поскольку вы уже знаете количество элементов, вы можете создать список правильного размера, который должен быть намного быстрее уже.

Кроме того, не уверен, как вы получаете доступ к значениям, но вы можете создать эту вещь и сохранить изображение в коде (загрузка его с диска, вероятно, будет медленнее, чем вы, сделайте сейчас. Сколько раз вы читаете/пишите на эту вещь?

Ответ 7

Здесь другой способ, которому нужен только цикл 2. Идея состоит в том, чтобы увеличить первый элемент, и если это число будет больше, чем увеличить следующий.

Вместо отображения данных вы можете использовать currentValues.Clone и добавить эту клонированную версию в свой список. Для меня это быстрее, чем ваша версия.

byte[] maxValues = {2, 3, 4};
byte[] currentValues = {0, 0, 0};

do {
    Console.WriteLine("{0}, {1}, {2}", currentValues[0], currentValues[1], currentValues[2]);

    currentValues[0] += 1;

    for (int i = 0; i <= maxValues.Count - 2; i++) {
        if (currentValues[i] < maxValues[i]) {
            break;
        }

        currentValues[i] = 0;
        currentValues[i + 1] += 1;
    }

// Stop the whole thing if the last number is over
// } while (currentValues[currentValues.Length-1] < maxValues[maxValues.Length-1]);
} while (currentValues.Last() < maxValues.Last());

• Надеюсь, что этот код работает, я преобразовал его из vb

Ответ 8

Все ваши номера являются константой времени компиляции.

Как развернуть все циклы в списке (используя вашу программу для написания кода):

data.Add(new [] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
data.Add(new [] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
etc.

Это должно по крайней мере убрать служебные данные для циклов for (если они есть).

Я слишком плохо знаком с С#, но, похоже, некоторые средства сериализации объектов. Что делать, если вы только что сгенерировали этот список и сериализовали его в той или иной форме? Я не уверен, что десериализация выполняется быстрее, чем создание списка и добавление элементов.

Ответ 9

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

Подход ниже намного быстрее (41 мс против 1071 мс для оригинала на моем ящике):

struct element {
    public byte a;
    public byte b;
    public byte c;
    public byte d;
    public byte e;
    public byte f;
    public byte g;
    public byte h;
    public byte i;
    public byte j;
    public byte k;
    public byte l;
    public byte m;
}

element[] WithStruct() {
    var t = new element[3981312];
    int z = 0;
    for (byte a = 0; a < 2; a++)
    for (byte b = 0; b < 3; b++)
    for (byte c = 0; c < 4; c++)
    for (byte d = 0; d < 3; d++)
    for (byte e = 0; e < 4; e++)
    for (byte f = 0; f < 3; f++)
    for (byte g = 0; g < 3; g++)
    for (byte h = 0; h < 4; h++)
    for (byte i = 0; i < 2; i++)
    for (byte j = 0; j < 4; j++)
    for (byte k = 0; k < 4; k++)
    for (byte l = 0; l < 3; l++)
    for (byte m = 0; m < 4; m++)
    {
        t[z].a = a;
        t[z].b = b;
        t[z].c = c;
        t[z].d = d;
        t[z].e = e;
        t[z].f = f;
        t[z].g = g;
        t[z].h = h;
        t[z].i = i;
        t[z].j = j;
        t[z].k = k;
        t[z].l = l;
        t[z].m = m;
        z++;
    }
    return t;
}

Ответ 10

Как использовать Parallel.For() для запуска? (Оптимизация конструкции для @Caramiriel). Я слегка изменил значения (a - 5 вместо 2), поэтому я более уверен в результатах.

    var data = new ConcurrentStack<List<Bytes>>();
    var sw = new Stopwatch();

    sw.Start();

    Parallel.For(0, 5, () => new List<Bytes>(3*4*3*4*3*3*4*2*4*4*3*4),
      (a, loop, localList) => {
        var bytes = new Bytes();
        bytes.A = (byte) a;
        for (byte b = 0; b < 3; b++) {
          bytes.B = b;
          for (byte c = 0; c < 4; c++) {
            bytes.C = c; 
            for (byte d = 0; d < 3; d++) {
              bytes.D = d; 
              for (byte e = 0; e < 4; e++) {
                bytes.E = e; 
                for (byte f = 0; f < 3; f++) {
                  bytes.F = f; 
                  for (byte g = 0; g < 3; g++) {
                    bytes.G = g; 
                    for (byte h = 0; h < 4; h++) {
                      bytes.H = h; 
                      for (byte i = 0; i < 2; i++) {
                        bytes.I = i; 
                        for (byte j = 0; j < 4; j++) {
                          bytes.J = j; 
                          for (byte k = 0; k < 4; k++) {
                            bytes.K = k; 
                            for (byte l = 0; l < 3; l++) {
                              bytes.L = l;
                              for (byte m = 0; m < 4; m++) {
                                bytes.M = m;
                                localList.Add(bytes);
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }


        return localList;
      }, x => {
        data.Push(x);
    });

    var joinedData = _join(data);

_join() - частный метод, определяемый как:

private static IList<Bytes> _join(IEnumerable<IList<Bytes>> data) {
  var value = new List<Bytes>();
  foreach (var d in data) {
    value.AddRange(d);
  }
  return value;
}

В моей системе эта версия работает примерно в 6 раз быстрее (1.718 секунд против 0.266 секунды).

Ответ 11

Некоторые из ваших чисел полностью соответствуют целому числу бит, поэтому вы можете "упаковать" их с номером верхнего уровня:

for (byte lm = 0; lm < 12; lm++)
{
    ...
    t[z].l = (lm&12)>>2;
    t[z].m = lm&3;
    ...
}

Конечно, это делает код менее читаемым, но вы сохранили один цикл. Это можно сделать каждый раз, когда одно из чисел имеет силу два, что в вашем случае семь раз.

Ответ 12

Вот еще одно решение. Вне VS он работает так же быстро, как 437,5 мс, что на 26% быстрее исходного кода (593,7 на моем компьютере):

static List<byte[]> Combinations(byte[] maxs)
{
  int length = maxs.Length;
  int count = 1; // 3981312;
  Array.ForEach(maxs, m => count *= m);
  byte[][] data = new byte[count][];
  byte[] counters = new byte[length];

  for (int r = 0; r < count; r++)
  {
    byte[] row = new byte[length];
    for (int c = 0; c < length; c++)
      row[c] = counters[c];
    data[r] = row;

    for (int i = length - 1; i >= 0; i--)
    {
      counters[i]++;
      if (counters[i] == maxs[i])
        counters[i] = 0;
      else
        break;
    }
  }

  return data.ToList();
}