Доброго времени суток, уважаемое читатели.
Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.
«Наверняка заморачиваться с исследованием алгоритма на пространственную и временную сложность нужно только при разработке либо очень высокопроизводительных/высоконагруженных систем, либо при работе с действительно большими объемами данных», — примерно такие мысли посещали меня (да и, наверное, не только меня) тогда.
Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.
Задача представляла собой следующее: имелись Excel таблицы с некоторыми (в основном числовыми) данными. Данные эти, не вдаваясь в подробности, представляли собой идентификаторы, используемые в подсистемах. Требовалось находить в таблицах повторяющиеся значения, и, в зависимости от разных факторов, решать, что с ними делать. На этом этапе у вас уже может появится вопрос: «Почему бы не делать это автоматически?». На самом деле, в таблицы попадали те наборы данных, с которыми автоматизированная система не справилась, и для которых требовалось человеческое вмешательство.
Естественно, перебирать вручную большое количество данных (в среднем порядка 5-10 столбцов и 1000 строк на документ) — занятие неблагодарное, поэтому мной было принято решение немного упростить процесс, хотя бы в плане поиска повторений.
Поскольку написать отдельную утилиту на С было нельзя из-за строгих правил организации, мне пришлось немного почитать про VBA (который я не знал совершенно), и придумать решение в виде VBA-макроса.
Итак, перейдем непосредственно к алгоритмам.
По сути, задача поиска повторений на Excel-листе — это просто задача поиска повторений в двумерном массиве. Но как это сделать? Как ни странно, гугл совершенно не смог мне помочь в решении такой, казалось бы, тривиальной задачи, и пришлось немного пораскинуть мозгами.
Простое решение
Самое простое, прямое и элементарное решение, которое приходит в голову — это просто поэлементное сравнение. На VBA это выглядит примерно так:
Sub FindMatches()
Dim sCol, sRow, cCol, cRow As Integer
For sCol = 1 To 10
For sRow = 1 To 10
For cCol = sCol + 1 To 10
For cRow = 1 To 10
If Cells(sRow, sCol) = Cells(cRow, cCol) Then
If Cells(sRow, sCol).Font.Color = RGB(0, 0, 0) Then
Cells(sRow, sCol).Font.Color = RGB(0, 150, 0)
End If
Cells(cRow, cCol).Font.Color = RGB(150, 0, 0)
End If
Next cRow
Next cCol
Next sRow
Next sCol
End Sub
Таким образом, мы берем каждую ячейку таблицы, и сравниваем ее со всеми ячейками, которые находятся после нее (стоит отметить, что в том столбце, где вхождение элемента встречается первый раз, повторений быть не может, поэтому мы начинаем сравнение со следующего столбца), и, если находим совпадения, красим их красным цветом. Удобно? Вполне. Однако именно здесь вычислительная сложность показывает зубы. Вот какое время занимает обработка на моей не самой, вроде бы, слабой машине:
- 100 ячеек (10x10) — 70 миллисекунд
- 200 ячеек (10х20) — 240 миллисекунд
- 400 ячеек (10х40) — 920 миллисекунд
- 2000 ячеек (20х100) — 23535 миллисекунд
В целом можно сказать, что при увеличении количества элементов на входе в n раз, время работы увеличится в n2 раз. Разумеется, такое решение было для меня неприемлемым.
Чуть менее простое решение
Итак, попытаемся немного ускорить наш алгоритм. Первое, что я понял — это то, что операция доступа непосредственно к ячейкам листа занимает огромное количество времени, и количество этих операций нужно попытаться минимизировать. В качестве решения этой проблемы я выбрал первоначальную запись данных из ячеек в память, и работу уже с этой памятью. Для этого нам идеально подойдет двумерный массив.
Для общего же уменьшения количества операций, я решил записывать каждое уникальное значение в отдельный массив, и производить сравнение только с этим массивом уникальных элементов. Выглядит это примерно так:
Sub FindMatches()
Dim row As Integer //номер строки
Dim col As Integer //номер столбца
Dim Values(5000, 5) As Integer //Значения из листа
Dim DistinctValues() As Integer //уникальные значения
Dim DistinctCount As Integer //количество уникальных значений
Dim i As Integer //итератор
Dim IsUnique As Boolean //признак уникальности
//Перераспределяем память массива уникальных элементов под один элемент
ReDim DistinctValues(0 To 0)
DistinctCount = 0
//Заносим в массив Values данные из листа.
For col = 1 To 5
For row = 1 To 5000
Values(row, col) = Cells(row, col)
Next row
Next col
//ищем совпадения.
For col = 1 To 5
For row = 1 To 5000
//проверяем каждый элемент массива Values на уникальность. для этого мы сравниваем его с каждым элементом массива уникальных значений DistinktValues.
For i = 0 To DistinctCount - 1
IsUnique = False
If DistinctValues(i) = Values(row, col) Then
//При наличии совпадения, мы закрашиваем соответствующую ячейку на листе красным.
IsUnique = True
Cells(row, col).Font.Color = RGB(255, 75, 75)
Exit For
End If
Next i
//Если совпадений нет, то мы имеем первое вхождение элемента, и приписываем его в наш массив DistinctValues, заодно окрашивая в зеленый цвет
If IsUnique = False Then
DistinctCount = DistinctCount + 1
ReDim Preserve DistinctValues(0 To DistinctCount)
DistinctValues(DistinctCount - 1) = Values(row, col)
Cells(row, col).Font.Color = RGB(75, 175, 75)
End If
Next row
Next col
End Sub
Итак, мы значительно уменьшили количество операций сравнения элементов за счет сравнения только с уже встреченными уникальными элементами. Также мы сократили количества операций над ячейками в листе до двух (первая — сохранение значения ячейки в массиве, вторая — покраска ячейки). Насколько же уменьшилось время работы?
К сожалению, скорость работы данного алгоритма сильно зависит от энтропии входных данных. Поскольку мы производим сравнение с массивом уникальных элементов, то чем этот массив больше, тем большее время нам понадобится. Иными словами, чем больше во входных данных уникальных элементов, тем медленнее будет работать алгоритм. Я провел два теста для 25000 ячеек ( 5 столбцов и 5000 строк). В первом тесте все ячейки были заполнены одинаковым значением (1), во втором — наоборот, они были заполнены различными значениями без повторений.
Для первого случая работа алгоритма заняла 816 миллисекунд, а для второго — почти 19 секунд. И все же, это значительно быстрее, чем наш первый вариант полного перебора, который смог бы переварить 25000 ячеек за умопомрачительные 58 минут.
Однако стремление к лучшему не знает предела. После некоторых раздумий, я решил не изобретать велосипед, а воспользоваться проверенными алгоритмами. Мой выбор пал на алгоритм быстрой сортировки, имеющий, как известно, логарифмическую сложность.
Быстрое решение
Итак, каким же образом можно использовать быструю сортировку для решения поставленной мной задачи?
//Тип данных, представляющий ячейку.
Type MyCell
row As Long
col As Long
Value As Long
End Type
//Функция быстрой сортировки, которую я без зазрения совести взял из интернета и лишь слегка модифицировал.
Sub QSort(sortArray() As MyCell, ByVal leftIndex As Long, _
ByVal rightIndex As Long)
Dim compValue As MyCell
Dim i As Long
Dim J As Long
Dim tempNum As MyCell
i = leftIndex
J = rightIndex
compValue = sortArray(CLng((i + J) / 2))
//делаем сортировку устойчивой.
Do
Do While (sortArray(i).Value < compValue.Value And i < rightIndex Or _
(sortArray(i).Value = compValue.Value And sortArray(i).col < compValue.col) Or _
(sortArray(i).Value = compValue.Value And sortArray(i).col = compValue.col And sortArray(i).row < compValue.row))
i = i + 1
Loop
Do While (compValue.Value < sortArray(J).Value And J > leftIndex Or _
(sortArray(J).Value = compValue.Value And sortArray(J).col > compValue.col) Or _
(sortArray(J).Value = compValue.Value And sortArray(J).col = compValue.col And sortArray(J).row > compValue.row))
J = J - 1
Loop
If i <= J Then
tempNum = sortArray(i)
sortArray(i) = sortArray(J)
sortArray(J) = tempNum
i = i + 1
J = J - 1
End If
Loop While i <= J
If leftIndex < J Then QSort sortArray(), leftIndex, J
If i < rightIndex Then QSort sortArray(), i, rightIndex
End Sub
Sub FindMatches()
//Получаем выделенную область
Dim myRange As Range
Set myRange = Selection
//получаем размер и координаты выделенной области
Dim ColCount, RowCount As Integer
ColCount = myRange.Columns.Count
RowCount = myRange.rows.Count
Dim FirstCol, FirstRow As Integer
FirstCol = myRange.Column
FirstRow = myRange.row
//Создаем массив из структур, и заносим туда данные о всех ячейках.
Dim MyCells() As MyCell
ReDim MyCells(ColCount * RowCount)
Dim col, row As Integer
Dim i As Long
For col = FirstCol To FirstCol + ColCount - 1
For row = FirstRow To FirstRow + RowCount - 1
MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).row = row
MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).col = col
MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).Value = CLng(Val(Cells(row, col)))
Next row
Next col
//вызываем быструю сортировку для этого массива
Call QSort(MyCells, 0, ColCount * RowCount - 1)
//окрашиваем ячейки.
Cells(1, 1).Font.Color = RGB(0, 255, 0)
For i = 1 To ColCount * RowCount - 1
If MyCells(i).Value <> MyCells(i - 1).Value Then
Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(0, 255, 0)
Else
Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(255, 0, 0)
End If
Next i
Cells(MyCells(firstOccurance).row, MyCells(firstOccurance).col).Font.Color = RGB(0, 255, 0)
End Sub
Помимо самой сортировки, я также добавил обработку выделенной области на листе, ибо так удобнее.
Принцип работы этого алгоритма весьма прост. Мы создаем структуру данных, которая хранит адрес ячейки (номер строки и столбца) и ее значение. Затем из этих структур создается массив, в который заносятся все данные из листа. Массив сортируется быстрой сортировкой.
После этого достаточно пройти по отсортированному массиву один раз, раскрашивая элементы: первый элемент в группе с одинаковыми значениями- зеленым, все остальные — красным.
Стоит заметить, что сам по себе алгоритм быстрой сортировки является неустойчивым, то есть он не сохраняет порядок элементов с одинаковым ключем. Поскольку в нашем случае ключем являлось значение ячейки, то в классическом варианте в каждой группе элементов с одинаковым значением элементы располагались бы в случайном порядке. Очевидно, что мне это не подходит, так как тогда для поиска первого вхождения в таблице нужно было бы еще раз сортировать каждую группу, уже по номеру ячейки. Чтобы избежать этого, я расширил ключ быстрой сортировки, добавив два дополнительных условия для перестановки элементов местеми: теперь в случае совпадения значений элементы будут выстраиваться в том порядке, в котором они встречаются на листе.
Насколько велик был выигрыш в производительности? Лист с 100000 ячеек со случаынйми значениями данный алгоритм обрабатывает за 4,2 секунды, что, на мой взгляд, является вполне приемлимым результатом.
Итак, какие же выводы можно сделать из всего этого?
- Во-первых, проблема вычислительной сложности алгоритма является актуальной даже для совсе, казалось бы, простых задач, и чтобы столкнуться с ней не обязательно работать с какими-то совсем невероятными объемами данных;
- Во-вторых, не нужно пытаться изобретать велосипед. Во многих случаях лучшим вариантом будет адаптация проверенных классических алгоритмов под конкретную задачу.
P.S. Поскольку тег <source> не поддерживает подсветку VBA, то чтобы подсветить хотя бы комментарии, мне пришлось использовать подсветку C и комментарии в C-стиле.
Автор: Singerofthefall
