使用 IComparable 对缺失和重复的序号进行排序

Question

我的任务是编写代码以将 IComparable 用于我们的自定义类型（产品）。

Product 类型有一个名为 OrdinalNumber 的属性，它是为排序操作进行比较的属性。序数的示例可以是这样的：1 2 3 3 5 6 7 7 9 等。例程必须替换重复或缺失的序数并对结果进行排序。

我找到了这个例子并让它运行。 https://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx

有人可以帮我吗？

我不想对 DataTable 进行排序。我们目前有对 DataTable 进行排序的代码，我们想重写该代码以使用名为 Product 的自定义类型。我在此处粘贴的示例代码使用了新产品 class.

这是我目前的情况：

Imports System.Collections.Generic

Public Class Product
    Implements IEquatable(Of Product)
    Implements IComparable(Of Product)
    Public Property ProductName() As String
        Get
            Return m_ProductName
        End Get
        Set(value As String)
            m_ProductName = value
        End Set
    End Property
    Private m_ProductName As String

    Public Property ProductId() As Integer
        Get
            Return m_ProductId
        End Get
        Set(value As Integer)
            m_ProductId = value
        End Set
    End Property
    Private m_ProductId As Integer

    Public Property OrdinalNumber() As Integer
        Get
            Return m_OrdinalNumber
        End Get
        Set(value As Integer)
            m_OrdinalNumber = value
        End Set
    End Property
    Private m_OrdinalNumber As Integer

    Public Overrides Function ToString() As String
        Return "Ordinal Number: " & OrdinalNumber & "   ID: " & ProductId & "   Name: " & ProductName
    End Function

    Public Overrides Function Equals(obj As Object) As Boolean
        If obj Is Nothing Then
            Return False
        End If
        Dim objAsProduct As Product = TryCast(obj, Product)
        If objAsProduct Is Nothing Then
            Return False
        Else
            Return Equals(objAsProduct)
        End If
    End Function

    Public Function SortByNameAscending(name1 As String, name2 As String) As Integer

        Return name1.CompareTo(name2)
    End Function

    Public Function CompareTo(compareProduct As Product) As Integer _
            Implements IComparable(Of Product).CompareTo

        If compareProduct Is Nothing Then
            Return 1
        Else

            Return Me.OrdinalNumber.CompareTo(compareProduct.OrdinalNumber)
        End If
    End Function

    Public Overrides Function GetHashCode() As Integer
        Return OrdinalNumber
    End Function

    Public Overloads Function Equals(other As Product) As Boolean Implements IEquatable(Of Product).Equals
        If other Is Nothing Then
            Return False
        End If
        Return (Me.OrdinalNumber.Equals(other.OrdinalNumber))
    End Function

End Class

Answer 1

我不确定为什么如此关注 SelectionSort 的 Bingo 变体（现已通过编辑编辑）。当有许多个重复值时，Bingo 版本是 SelectionSort 稍微快一点的版本，但只是略微如此。它不是专门用于存在一些欺骗的情况的分拣机。他们都很慢。

How would I implement a selection or "bingo" sort using List.Sort
那不是它的工作原理。实际的排序机制内置于 NET Framework 中。在 List.Sort() 的情况下，它将 select 它认为合适的 3 种类型之一。您可以提供比较机制。

给定一个数据集 {1,3,5,5,7,9,15} 具有 1 和 3 的元素将始终排序低于 5 或 1024，因此缺少的元素是这不是问题。您希望如何比较重复值，可能是。

有几种选择：

Linq 的 OrderBy

Dim sortedProds = myProducts.OrderBy(Function (j) j.Ordinal).ToList()

时间：~6 毫秒 20k 个项目
如果你想对 dupes 做一些事情，比如按 Id:

对 them 进行排序

Dim ProdsL = myProducts.OrderBy(Function(j) j.Ordinal).
                   ThenBy(Function(k) k.Id).ToList()

时间：~8 毫秒 20k 个项目

List.Sort 使用比较器

制作 class 工具 IComparable:

Public Function CompareTo(other As ProductItem) As Integer _ 
                         Implements IComparable(Of ProductItem).CompareTo
    If Ordinal < other.Ordinal Then Return -1
    If Ordinal > other.Ordinal Then Return 1

    ' equal, return the lower ID or:
    'Return 0

    If Id < other.Id Then Return -1
    Return 1
End Function

用法：

myProducts.Sort(Function(x, y) x.CompareTo(y))

时间：~28 毫秒 20k 个项目

您还可以使用执行比较的方法，这意味着您不必实施 IComparable 除非它在其他情况下有价值。

Private Function ProductComparer(x As ProductItem, y As ProductItem) As Integer
    If x.Ordinal < y.Ordinal Then Return -1
    If x.Ordinal > y.Ordinal Then Return 1

    ' equal, return the lower ID or:
    'Return 0

    If x.Id < y.Id Then Return -1
    Return 1
End Function

用法：

myProducts.Sort(AddressOf ProductComparer)

时间：11 毫秒

宾果排序

SelectionSort（~3650 毫秒）和 Bingo 变体（~3590 毫秒）远远落后于其他变体，它们似乎不值得考虑。包含宾果游戏只是为了满足原始问题（即使其他地方已经在使用宾果游戏）。

  Private Sub BingoSort(items As List(Of ProductItem))
    ' converted from https://en.wikipedia.org/wiki/Selection_sort#Variants
    ' for 

    Dim max As Int32 = items.Count - 1
    Dim nextVal = items(max).Ordinal
    Dim value As Int32
    Dim tmp As ProductItem

    For i As Int32 = max - 1 To 0 Step -1
        If items(i).Ordinal > nextVal Then
            nextVal = items(i).Ordinal
        End If
    Next
    While (max > 0) And (items(max).Ordinal = nextVal)
        max -= 1
    End While
    While (max > 0)
        value = nextVal
        nextVal = items(max).Ordinal
        For i As Int32 = max - 1 To 0 Step -1
            If items(i).Ordinal = value Then
                tmp = items(i)
                items(i) = items(max)
                items(max) = tmp
                max -= 1
            ElseIf items(i).Ordinal > nextVal Then
                nextVal = items(i).Ordinal
            End If
        Next
        While (max > 0) And (items(max).Ordinal = nextVal)
            max -= 1
        End While
    End While
End Sub

用法：

BingoSort(myProducts)

时间：~3590 毫秒 20k 个项目。

注意当没有dupes时（或者原始列表以Id顺序开始），结果和linq的OrderBy

一样

Dim Valid = ProdsLinq.SequenceEqual(ProdsBingo)

鉴于性能不佳，似乎没有理由在此处使用它。 IComparable 让您决定如何 tie-break 复制并且 Linq 和 List.Sort(IComparable) 都是 gobs 和 gobs 更快。

请注意 DataTable:

myDT.DefaultView.Sort = "Ordinal ASC"
' or
myDT.DefaultView.Sort = "Ordinal ASC, Id ASC"

使用 IComparable 对缺失和重复的序号进行排序

Sort Missing and Duplicate Ordinal Numbers Using IComparable

.net

vb.net

sorting

icomparable

Linq 的 OrderBy

List.Sort 使用比较器

宾果排序