Есть ли простой способ иметь функцию "mode" на массиве синглов в vb6?

Question

Мне нужно запустить «режим» (это значение встречается чаще всего) на массиве синглов в vb6. Есть ли быстрый способ сделать это на больших массивах?

Answer 1

Вы можете использовать хеш-таблицу. Хэшируйте все элементы вашего массива (это O (n)). Вам понадобится внутренняя структура данных для хранения уникальных значений, содержащихся в каждом хэш-бине, и количества вхождений (своего рода ассоциативная память, похожая на C ++ std :: map). До тех пор, пока вы можете гарантировать, что в любом заданном бине будет не более константы m коллизий (для разнородных входных значений хеша), это O (m log m), но, поскольку m является константой, действительно O (1). Это предположение может быть неоправданным, но ключ к получению достаточно хорошего спреда для ваших входных значений.

Чтобы выйти из режима, изучите все элементы в хеш-таблице, которые будут значениями, которые встречаются в исходном входном массиве, и числом раз, которое они встречаются. Найдите значение с наибольшим числом вхождений (снова O (n)). Общая сложность равна O (n), если вы можете найти подходящую хеш-функцию. В худшем случае производительность будет O (n log n), если хеш-функция не обеспечивает хорошую производительность при столкновении.

С другой стороны, .Net предоставляет большую библиотеку времени выполнения, которая может упростить эту задачу. Если это возможно, вы можете рассмотреть возможность использования новой версии VB.

Answer 2

Включил ссылку на Microsoft Scripting Runtime и использовал объект Dictionary, чтобы вести подсчет частоты, затем искал индекс наивысшей частоты, и соответствующий ключ - режим.Не самое быстрое / самое элегантное решение, но мне просто нужно что-то быстрое, что сработало.

Function fnModeSingle(ByRef pValues() As Single) As Single
    Dim dict As Dictionary
    Set dict = New Dictionary
    dict.CompareMode = BinaryCompare
    Dim i As Long    
    Dim pCurVal As Single
    For i = 0 To uBound(pValues)
    'limit the values that have to be analyzed to desired precision'
        pCurVal = Round(pValues(i), 2) 
            If (pCurVal > 0) Then
                'this will create a dictionary entry if it doesn't exist
                dict.Item(pCurVal) = dict.Item(pCurVal) + 1
            End If
    Next

    'find index of first largest frequency'
    Dim KeyArray, itemArray
    KeyArray = dict.Keys
    itemArray = dict.Items
    pCount = 0
    Dim pModeIdx As Integer
    'find index of mode'
    For i = 0 To UBound(itemArray)
        If (itemArray(i) > pCount) Then
            pCount = itemArray(i)
            pModeIdx = i
        End If
    Next
    'get value corresponding to selected mode index'
    fnModeSingle = KeyArray(pModeIdx)
    Set dict = Nothing

End Function

Answer 3

Найдите в Интернете достойную реализацию алгоритма сортировки для VB6 (я не могу поверить, что у него нет встроенного алгоритма!), Отсортируйте массив, а затем просмотрите его, считая вхождения (который будет просто, так как все элементы в массиве объединены) - отслеживайте наиболее часто встречающиеся элементы на своем пути, и все готово. Это должно быть O (n ln (n)), то есть достаточно быстро, если вы использовали алгоритм достойной сортировки (быстрая сортировка или подобный).