C# 检查数组是否已排序的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11989071/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest way to check if an array is sorted
提问by Cannon
Considering there is an array returned from a function which is of very large size.
考虑到有一个从非常大的函数返回的数组。
What will be the fastestapproach to test if the array is sorted?
fastest测试数组是否已排序的方法是什么？
A simplest approach will be:
一个最简单的方法是：
/// <summary>
/// Determines if int array is sorted from 0 -> Max
/// </summary>
public static bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i - 1] > arr[i])
{
return false;
}
}
return true;
}
采纳答案by Eric J.
You will have to visit each element of the array to see if anything is unsorted.
您必须访问数组的每个元素以查看是否有未排序的内容。
Your O(n) approach is about as fast as it gets, without any special knowledge about the likely state of the array.
你的 O(n) 方法是尽可能快的，没有任何关于数组可能状态的特殊知识。
Your code specifically tests if the array is sorted with smaller values at lower indices. If that is not what you intend, your ifbecomes slightly more complex. Your code comment does suggest that is what you're after.
您的代码专门测试数组是否在较低的索引处使用较小的值进行排序。如果这不是你想要的，你的if会变得稍微复杂一些。您的代码注释确实表明这就是您所追求的。
If you were to have special knowledge of the probable state (say, you know it's generally sorted but new data might be added to the end), you can optimize the order in which you visit array elements to allow the test to fail faster when the array is unsorted.
如果您对可能的状态有特殊的了解（例如，您知道它通常已排序但新数据可能会添加到末尾），您可以优化访问数组元素的顺序，以便在出现以下情况时测试更快地失败数组未排序。
You can leverage knowledge of the hardware architecture to check multiple parts of the array in parallel by partitioning the array, first comparing the boundaries of the partition (fail fast check) and then running one array partition per core on a separate thread (no more than 1 thread per CPU core). Note though that if a array partition is much smaller than the size of a cache line, the threads will tend to compete with each other for access to the memory containing the array. Multithreading will only be very efficient for fairly large arrays.
您可以利用硬件体系结构的知识通过对阵列进行分区来并行检查阵列的多个部分，首先比较分区的边界（快速检查失败），然后在单独的线程上为每个内核运行一个阵列分区（不超过每个 CPU 内核 1 个线程）。但请注意，如果数组分区远小于缓存行的大小，线程将倾向于相互竞争以访问包含该数组的内存。多线程只会对相当大的数组非常有效。
回答by saul672
The only improvement i can think of is check both ends of the array at the same time, this little change will do it in half time...
我能想到的唯一改进是同时检查数组的两端，这个小小的改变会在半场时间内完成......
public static bool IsSorted(int[] arr)
{
int l = arr.Length;
for (int i = 1; i < l/2 + 1 ; i++)
{
if (arr[i - 1] > arr[i] || arr[l-i] < arr[l-i-1])
{
return false;
}
}
return true;
}
回答by user1277476
The question that comes to my mind is "why"?
我想到的问题是“为什么”？
Is it to avoid re-sorting an already-sorted list? If yes, just use Timsort (standard in Python and Java). It's quite good at taking advantage of an array/list being already sorted, or almost sorted. Despite how good Timsort is at this, it's better to not sort inside a loop.
是为了避免重新排序已经排序的列表吗？如果是，只需使用 Timsort（Python 和 Java 中的标准）。它非常擅长利用已经排序或几乎排序的数组/列表。尽管 Timsort 在这方面做得很好，但最好不要在循环内排序。
Another alternative is to use a datastructure that is innately sorted, like a treap, red-black tree or AVL tree. These are good alternatives to sorting inside a loop.
另一种选择是使用先天排序的数据结构，如收获树、红黑树或 AVL 树。这些是在循环内排序的不错选择。
回答by Raz Megrelidze
Linq solution.
林克解决方案。
public static bool IsSorted<T>(IEnumerable<T> list) where T:IComparable<T>
{
var y = list.First();
return list.Skip(1).All(x =>
{
bool b = y.CompareTo(x) < 0;
y = x;
return b;
});
}
回答by atomCode
This might not be the fastest but it's the complete solution. Every value with index lower than iis checked against the current value at i. This is written in php but can easily be translated into c# or javascript
这可能不是最快的，但它是完整的解决方案。索引低于 i 的每个值都根据i处的当前值进行检查。这是用 php 编写的，但可以很容易地翻译成 c# 或 javascript
for ($i = 1; $i < $tot; $i++) {
for ($j = 0; $j <= $i; $j++) {
//Check all previous values with indexes lower than $i
if ($chekASCSort[$i - $j] > $chekASCSort[$i]) {
return false;
}
}
}
回答by P_P
Faster approach, platform target: Any CPU, Prefer 32-bit.
A sorted array with 512 elements: ~25% faster.
更快的方法，平台目标：任何 CPU，首选 32 位。
一个包含 512 个元素的排序数组：快 25%。
static bool isSorted(int[] a)
{
int j = a.Length - 1;
if (j < 1) return true;
int ai = a[0], i = 1;
while (i <= j && ai <= (ai = a[i])) i++;
return i > j;
}
Target: x64, same array: ~40% faster.
目标：x64，相同的阵列：快 40%。
static bool isSorted(int[] a)
{
int i = a.Length - 1;
if (i <= 0) return true;
if ((i & 1) > 0) { if (a[i] < a[i - 1]) return false; i--; }
for (int ai = a[i]; i > 0; i -= 2)
if (ai < (ai = a[i - 1]) || ai < (ai = a[i - 2])) return false;
return a[0] <= a[1];
}
Forgot one, marginally slower than my first code block.
忘记了，比我的第一个代码块慢一点。
static bool isSorted(int[] a)
{
int i = a.Length - 1; if (i < 1) return true;
int ai = a[i--]; while (i >= 0 && ai >= (ai = a[i])) i--;
return i < 0;
}
Measuring it (see greybeard's comment).
测量它（见灰胡子的评论）。
using System; // ????????? DEBUG ?????????
using sw = System.Diagnostics.Stopwatch; // static bool abc()
class Program // { // a <= b <= c ?
{ // int a=4,b=7,c=9;
static void Main() // int i = 1;
{ // if (a <= (a = b))
//abc(); // {
int i = 512; // i++;
int[] a = new int[i--]; // if (a <= (a = c))
while (i > 0) a[i] = i--; // {
sw sw = sw.StartNew(); // i++;
for (i = 10000000; i > 0; i--) // }
isSorted(a); // }
sw.Stop(); // return i > 2;
Console.Write(sw.ElapsedMilliseconds); // }
Console.Read(); // static bool ABC();
} // {
// int[]a={4,7,9};
static bool isSorted(int[] a) // OP Cannon // int i=1,j=2,ai=a[0];
{ // L0: if(i<=j)
for (int i = 1; i < a.Length; i++) // if(ai<=(ai=a[i]))
if (a[i - 1] > a[i]) return false; // {i++;goto L0;}
return true; // return i > j;
} // }
}
Target: x64. Four cores/threads. A sorted array with 100,000 elements: ~55%.
目标：x64。四核/线程。具有 100,000 个元素的排序数组：~55%。
static readonly object _locker = new object();
static bool isSorted(int[] a) // a.Length > 3
{
bool b = true;
Parallel.For(0, 4, k =>
{
int i = 0, j = a.Length, ai = 0;
if (k == 0) { j /= 4; ai = a[0]; } // 0 1
if (k == 1) { j /= 2; i = j / 2; ai = a[i]; } // 1 2
if (k == 2) { i = j - 1; ai = a[i]; j = j / 2 + j / 4; } // 4 3
if (k == 3) { i = j - j / 4; ai = a[i]; j = j / 2; } // 3 2
if (k < 2)
while (b && i <= j)
{
if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2])) i += 2;
else lock (_locker) b = false;
}
else
while (b && i >= j)
{
if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2])) i -= 2;
else lock (_locker) b = false;
}
});
return b;
}
1,000,000 items?
1,000,000 件物品？
if (k < 2)
while (b && i < j)
if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2]) &&
ai <= (ai = a[i + 3]) && ai <= (ai = a[i + 4])) i += 4;
else lock (_locker) b = false;
else
while (b && i > j)
if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2]) &&
ai >= (ai = a[i - 3]) && ai >= (ai = a[i - 4])) i -= 4;
else lock (_locker) b = false;
Let's forget percentages.
Original: 0.77 ns/item, now: 0.22 ns/item.
2,000,000 items? Four cores: 4 times faster.
让我们忘记百分比。
原始：0.77 ns/项，现在：0.22 ns/项。
2,000,000 件物品？四核：快 4 倍。
回答by Michael Dera
This is what I came up with and find works better particularly with greater sized arrays. The function is recursive and will be called for the very first time, say in a while loop like this
这就是我想出来的，发现效果更好，尤其是对于更大尺寸的数组。该函数是递归的，将在第一次被调用，比如在这样的 while 循环中
while( isSorted( yourArray, 0 )
The if statement checks if the bounds of the array have been reached.
if 语句检查是否已达到数组的边界。
The else if statement will call itself recursively and break at any time when the condition becomes false
else if 语句将递归调用自身并在条件变为假时随时中断
public static bool IsSorted(int[] arr, int index)
{
if (index >= arr.Length - 1)
{
return true;
}
else if ((arr[index] <= arr[ index + 1]) && IsSorted(arr, index + 1))
{
return true;
}
else
{
return false;
}
}
回答by GSoft Consulting
Here is my version of the function IsSorted
这是我的 IsSorted 函数版本
public static bool IsSorted(int[] arr)
{
int last = arr.Length - 1;
if (last < 1) return true;
int i = 0;
while(i < last && arr[i] <= arr[i + 1])
i++;
return i == last;
}
While this function is a bit faster than in the question, it will do fewer assignments and comparisons than anything has been posted so far. In the worst case, it does 2n+1 comparisons. It still can be improved if you can make a reasonable assumption about the nature of the data like minimum data size or array contains even number of elements.
虽然这个函数比问题中的要快一点，但它的分配和比较比迄今为止发布的任何东西都要少。在最坏的情况下，它会进行 2n+1 次比较。如果您可以对数据的性质做出合理的假设，例如最小数据大小或数组包含偶数个元素，它仍然可以改进。
