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

Мне нужно составить список комбинаций чисел. Цифры довольно маленькие, поэтому я могу использовать byteвместо int. Однако для получения всех возможных комбинаций требуется много вложенных циклов. Мне интересно, есть ли более эффективный способ сделать то, что мне нужно. Код на данный момент:

var data = new List<byte[]>();
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.Add(new [] {a, b, c, d, e, f, g, h, i, j, k, l, m});
}

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

Приветствуются любые рекомендации. Или, может быть, это самый быстрый способ делать то, что я хочу?

ИЗМЕНИТЬ Пара быстрых замечаний (и извинения, я не поместил их в исходный пост):

• Числа и порядок их (2, 3, 4, 3, 4, 3, 3 и т. Д.) Очень важны, поэтому использование такого решения, как Генерация перестановок с использованием LINQ , не поможет, потому что максимумы в каждом «столбце» равны разные
• Я не математик, поэтому прошу прощения, если неправильно использую такие технические термины, как «перестановки» и «комбинации» :)
• Я действительно нужно заполнить все эти комбинации сразу - я не могу просто взять один или другой на основе индекса
• Использование byteбыстрее, чем использование int, я гарантирую это. Также намного лучше использовать память, чтобы иметь массивы байтов более 67 млн, а не целые числа.
• Моя конечная цель - найти более быструю альтернативу вложенным циклам.
• Я подумывал об использовании параллельного программирования, но из-за итеративного характера того, чего я пытаюсь достичь, я не смог найти способ сделать это успешно (даже с ConcurrentBag) - однако я счастлив, что ошибся :)

ВЫВОД

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

Если вы хотите попробовать именно то, что я пытался протестировать StopWatch, используйте 13 циклов, считая до 4 в каждом цикле, что составляет около 67 миллионов строк в списке. На моей машине (i5-3320M 2,6 ГГц) оптимизированная версия занимает около 2,2 с.

Вы можете использовать свойства структуры и заранее выделить структуру. Я вырезал некоторые уровни в приведенном ниже примере, но я уверен, что вы сможете понять особенности. Работает примерно в 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>.

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

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

Итак, здесь я публикую что-то другое, что может не соответствовать вашему случаю, но стоит отметить: если вы действительно получаете доступ к списку в разреженном виде, вот класс, который позволяет вам вычислять 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.

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

Способ 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 мс, что примерно на 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 мсек на моем компьютере (также создается и добавляется Arrayкак в методе 2 ), что примерно на 36,3% медленнее, чем рассматриваемый код (который занимает 658 мс).

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

private static byte[,] GenerateCombinations(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;
}

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

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

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

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

Вот другой способ, для которого нужно всего 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

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

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

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 (если они есть).

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

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

Приведенный ниже подход намного быстрее (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;
}

Что насчет использования 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 секунды).

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

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

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

Вот еще одно решение. Вне 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();
}