숫자 조합 목록을 만들어야합니다. 숫자가 매우 적기 때문에 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것을 보증 합니다. 또한 int보다 67m 이상의 바이트 배열을 갖는 것이 메모리 사용량에 훨씬 좋습니다. - 내 궁극적 인 목표는 중첩 루프에 대한 더 빠른 대안을 찾는 것입니다.
- 병렬 프로그래밍 사용을 고려했지만 달성하려는 반복적 특성으로 인해 성공적으로 수행 할 방법을 찾을 수 없었습니다 (를 사용하더라도
ConcurrentBag). 그러나 잘못된 것으로 입증되어 기쁩니다. 🙂
결론
Caramiriel은 루프에서 약간의 시간을 단축하는 좋은 마이크로 최적화를 제공했기 때문에 그 대답을 올바른 것으로 표시했습니다. Eric은 또한 List를 미리 할당하는 것이 더 빠르다고 언급했습니다. 그러나이 단계에서는 중첩 된 루프가 실제로이를 수행 할 수있는 가장 빠른 방법 인 것 같습니다 (우울 해요, 알아요!).
내가 벤치마킹하려고했던 것을 정확히 시도하고 싶다면 StopWatch각 루프에서 최대 4 개까지 세는 13 개의 루프를 사용하여 목록에서 약 67m + 라인을 만듭니다. 내 컴퓨터 (i5-3320M 2.6GHz)에서 최적화 된 버전을 수행하는 데 약 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 % (658ms 소요) 문제의 코드보다.
방법 3
또는 스파 스 방식의 액세스에 적합한 저렴한 초기화를 위해 다음 기술을 사용할 수 있습니다. 이는 일부 요소 만 필요할 수 있고 모든 요소를 미리 결정할 필요가 없다고 간주 될 때 특히 유리합니다. 또한 이와 같은 기술은 메모리가 부족할 때 더 방대한 요소로 작업 할 때 유일하게 실행 가능한 옵션이 될 수 있습니다.
이 구현에서 모든 요소는 액세스시 느리게, 즉석에서 결정됩니다. 당연히 이것은 액세스 중에 발생하는 추가 CPU 비용이 발생합니다.
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 % (658ms 소요) 문제의 코드보다.
답변
내 컴퓨터에서 이것은 222ms 대 760ms (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에는 내부적으로 배열이 있으며 고정 길이로 값을 저장합니다. 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에서 변환했습니다.
