优化版本
令我失望的是，我的优化函数的运行速度仅比 LINQ“直接”版本快 7 倍。未优化的 LINQ1m43s优化14.7s.
- linux 32 位
- Mono 2.11 (C# 4.0) 编译器
-optimize+,
- 1,000,000
TESTITERATIONS
-
VERBOSE not #define-d
优化了什么：
- 假设输入和输出为数组
- 在输入数组上就地工作
- “手动”分析相同值的运行，而不是使用
GroupBy (using ValueRun struct)
- 有这些
ValueRun数组中的结构而不是可枚举（列表）；就地排序/随机播放
- use
unsafe块和指针（没有明显区别...)
- 使用模索引代替
MAGIC林克代码
- 通过迭代追加而不是嵌套 LINQ 生成输出。这可能是最有效的。事实上，如果我们能走捷径的话那就更好了
ValueRun具有 countruns 集合的 s 是按此计数排序的，这似乎很容易做到；然而，转置索引（循环约束所需）使事情变得复杂。无论如何，通过更大的输入和许多唯一值以及一些高度重复的值，以某种方式应用此优化的收益将会更大。
这是优化版本的代码。 _可以通过移除 RNG 的种子来获得额外的速度增益；这些只是为了能够对输出进行回归测试。
[... old code removed as well ...]
原始回复（部分的）
如果我的理解是对的，那么您正在尝试设计一种洗牌方法，以防止重复项在输出中连续出现（最小交错为 2 个元素）。
这在一般情况下是无法解决的。想象一下只有相同元素的输入:)
更新：事态陷入困境
正如我在笔记中提到的，我认为我一直没有走在正确的轨道上。要么我应该调用图论（有人吗？），要么使用简单的“暴力”算法，这是埃里克的长建议。
无论如何，这样你就可以看到我一直在做什么，以及问题是什么（使随机样本能够快速看到问题）：
#define OUTPUT // to display the testcase results
#define VERIFY // to selfcheck internals and verify results
#define SIMPLERANDOM
// #define DEBUG // to really traces the internals
using System;
using System.Linq;
using System.Collections.Generic;
public static class Q5899274
{
// TEST DRIVER CODE
private const int TESTITERATIONS = 100000;
public static int Main(string[] args)
{
var testcases = new [] {
new [] {0,1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,10},
new [] {0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10},
new [] { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41, 42, 42, 42, },
new [] {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
}.AsEnumerable();
// // creating some very random testcases
// testcases = Enumerable.Range(0, 10000).Select(nr => Enumerable.Range(GROUPWIDTH, _seeder.Next(GROUPWIDTH, 400)).Select(el => _seeder.Next(-40, 40)).ToArray());
foreach (var testcase in testcases)
{
// _seeder = new Random(45); for (int i=0; i<TESTITERATIONS; i++) // for benchmarking/regression
{
try
{
var output = TestOptimized(testcase);
#if OUTPUT
Console.WriteLine("spread\t{0}", string.Join(", ", output));
#endif
#if VERIFY
AssertValidOutput(output);
#endif
} catch(Exception e)
{
Console.Error.WriteLine("Exception for input {0}:", string.Join(", ", testcase));
Console.Error.WriteLine("Sequence length {0}: {1} groups and remainder {2}", testcase.Count(), (testcase.Count()+GROUPWIDTH-1)/GROUPWIDTH, testcase.Count() % GROUPWIDTH);
Console.Error.WriteLine("Analysis: \n\t{0}", string.Join("\n\t", InternalAnalyzeInputRuns(testcase)));
Console.Error.WriteLine(e);
}
}
}
return 0;
}
#region Algorithm Core
const int GROUPWIDTH = 3; /* implying a minimum distance of 2
(GROUPWIDTH-1) values in between duplicates
must be guaranteed*/
public static T[] TestOptimized<T>(T[] input, bool doShuffle = false)
where T: IComparable<T>
{
if (input.Length==0)
return input;
var runs = InternalAnalyzeInputRuns(input);
#if VERIFY
CanBeSatisfied(input.Length, runs); // throws NoValidOrderingExists if not
#endif
var transpositions = CreateTranspositionIndex(input.Length, runs);
int pos = 0;
for (int run=0; run<runs.Length; run++)
for (int i=0; i<runs[run].runlength; i++)
input[transpositions[pos++]] = runs[run].value;
return input;
}
private static ValueRun<T>[] InternalAnalyzeInputRuns<T>(T[] input)
{
var listOfRuns = new List<ValueRun<T>>();
Array.Sort(input);
ValueRun<T> current = new ValueRun<T> { value = input[0], runlength = 1 };
for (int i=1; i<=input.Length; i++)
{
if (i<input.Length && input[i].Equals(current.value))
current.runlength++;
else
{
listOfRuns.Add(current);
if (i<input.Length)
current = new ValueRun<T> { value = input[i], runlength = 1 };
}
}
#if SIMPLERANDOM
var rng = new Random(_seeder.Next());
listOfRuns.ForEach(run => run.tag = rng.Next()); // this shuffles them
#endif
var runs = listOfRuns.ToArray();
Array.Sort(runs);
return runs;
}
// NOTE: suboptimal performance
// * some steps can be done inline with CreateTranspositionIndex for
// efficiency
private class NoValidOrderingExists : Exception { public NoValidOrderingExists(string message) : base(message) { } }
private static bool CanBeSatisfied<T>(int length, ValueRun<T>[] runs)
{
int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
int remainder = length % GROUPWIDTH;
// elementary checks
if (length<GROUPWIDTH)
throw new NoValidOrderingExists(string.Format("Input sequence shorter ({0}) than single group of {1})", length, GROUPWIDTH));
if (runs.Length<GROUPWIDTH)
throw new NoValidOrderingExists(string.Format("Insufficient distinct values ({0}) in input sequence to fill a single group of {1})", runs.Length, GROUPWIDTH));
int effectivewidth = Math.Min(GROUPWIDTH, length);
// check for a direct exhaustion by repeating a single value more than the available number of groups (for the relevant groupmember if there is a remainder group)
for (int groupmember=0; groupmember<effectivewidth; groupmember++)
{
int capacity = remainder==0? groups : groups -1;
if (capacity < runs[groupmember].runlength)
throw new NoValidOrderingExists(string.Format("Capacity exceeded on groupmember index {0} with capacity of {1} elements, (runlength {2} in run of '{3}'))",
groupmember, capacity, runs[groupmember].runlength, runs[groupmember].value));
}
// with the above, no single ValueRun should be a problem; however, due
// to space exhaustion duplicates could end up being squeezed into the
// 'remainder' group, which could be an incomplete group;
// In particular, if the smallest ValueRun (tail) has a runlength>1
// _and_ there is an imcomplete remainder group, there is a problem
if (runs.Last().runlength>1 && (0!=remainder))
throw new NoValidOrderingExists("Smallest ValueRun would spill into trailing incomplete group");
return true;
}
// will also verify solvability of input sequence
private static int[] CreateTranspositionIndex<T>(int length, ValueRun<T>[] runs)
where T: IComparable<T>
{
int remainder = length % GROUPWIDTH;
int effectivewidth = Math.Min(GROUPWIDTH, length);
var transpositions = new int[length];
{
int outit = 0;
for (int groupmember=0; groupmember<effectivewidth; groupmember++)
for (int pos=groupmember; outit<length && pos<(length-remainder) /* avoid the remainder */; pos+=GROUPWIDTH)
transpositions[outit++] = pos;
while (outit<length)
{
transpositions[outit] = outit;
outit += 1;
}
#if DEBUG
int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
Console.WriteLine("Natural transpositions ({1} elements in {0} groups, remainder {2}): ", groups, length, remainder);
Console.WriteLine("\t{0}", string.Join(" ", transpositions));
var sum1 = string.Join(":", Enumerable.Range(0, length));
var sum2 = string.Join(":", transpositions.OrderBy(i=>i));
if (sum1!=sum2)
throw new ArgumentException("transpositions do not cover range\n\tsum1 = " + sum1 + "\n\tsum2 = " + sum2);
#endif
}
return transpositions;
}
#endregion // Algorithm Core
#region Utilities
private struct ValueRun<T> : IComparable<ValueRun<T>>
{
public T value;
public int runlength;
public int tag; // set to random for shuffling
public int CompareTo(ValueRun<T> other) { var res = other.runlength.CompareTo(runlength); return 0==res? tag.CompareTo(other.tag) : res; }
public override string ToString() { return string.Format("[{0}x {1}]", runlength, value); }
}
private static /*readonly*/ Random _seeder = new Random(45);
#endregion // Utilities
#region Error detection/verification
public static void AssertValidOutput<T>(IEnumerable<T> output)
where T:IComparable<T>
{
var repl = output.Concat(output.Take(GROUPWIDTH)).ToArray();
for (int i=1; i<repl.Length; i++)
for (int j=Math.Max(0, i-(GROUPWIDTH-1)); j<i; j++)
if (repl[i].Equals(repl[j]))
throw new ArgumentException(String.Format("Improper duplicate distance found: (#{0};#{1}) out of {2}: value is '{3}'", j, i, output.Count(), repl[j]));
}
#endregion
}
