Как найти одинаковые элементы в двумерном массиве

Поиск повторений в двумерном массиве, или вычислительная сложность на примере

Доброго времени суток, уважаемое хабрасообщество.

Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.

«Наверняка заморачиваться с исследованием алгоритма на пространственную и временную сложность нужно только при разработке либо очень высокопроизводительных/высоконагруженных систем, либо при работе с действительно большими объемами данных», — примерно такие мысли посещали меня (да и, наверное, не только меня) тогда.

Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.

Задача представляла собой следующее: имелись 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 ячеек (10×10) — 70 миллисекунд
• 200 ячеек (10х20) — 240 миллисекунд
• 400 ячеек (10х40) — 920 миллисекунд
• 2000 ячеек (20х100) — 23535 миллисекунд

В целом можно сказать, что при увеличении количества элементов на входе в n раз, время работы увеличится в n² раз. Разумеется, такое решение было для меня неприемлемым.

Чуть менее простое решение

Итак, попытаемся немного ускорить наш алгоритм. Первое, что я понял — это то, что операция доступа непосредственно к ячейкам листа занимает огромное количество времени, и количество этих операций нужно попытаться минимизировать. В качестве решения этой проблемы я выбрал первоначальную запись данных из ячеек в память, и работу уже с этой памятью. Для этого нам идеально подойдет двумерный массив.

Для общего же уменьшения количества операций, я решил записывать каждое уникальное значение в отдельный массив, и производить сравнение только с этим массивом уникальных элементов. Выглядит это примерно так:

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. 
            IsUnique = True
            For i = 0 To DistinctCount - 1 
                If DistinctValues(i) = Values(row, col) Then
//При наличии совпадения, мы закрашиваем соответствующую ячейку на листе красным.
                    IsUnique = False
                    Cells(row, col).Font.Color = RGB(255, 75, 75)
                    Exit For
                End If
            Next i
//Если совпадений нет, то мы имеем первое вхождение элемента, и приписываем его в наш массив DistinctValues, заодно окрашивая в зеленый цвет            
            If IsUnique = True 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 минут.

Однако стремление к лучшему не знает предела. После некоторых раздумий, я решил не изобретать велосипед, а воспользоваться проверенными алгоритмами. Мой выбор пал на алгоритм быстрой сортировки, имеющий, как известно, сложность O(n log n).

Быстрое решение

Итак, каким же образом можно использовать быструю сортировку для решения поставленной мной задачи?

//Тип данных, представляющий ячейку. 
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 секунды, что, на мой взгляд, является вполне приемлемым результатом.

Итак, какие же выводы можно сделать из всего этого?

1. Во-первых, проблема вычислительной сложности алгоритма является актуальной даже для совсе, казалось бы, простых задач, и чтобы столкнуться с ней не обязательно работать с какими-то совсем невероятными объемами данных;
2. Во-вторых, не нужно пытаться изобретать велосипед. Во многих случаях лучшим вариантом будет адаптация проверенных классических алгоритмов под конкретную задачу.

P.S. Поскольку тег <source> не поддерживает подсветку VBA, то чтобы подсветить хотя бы комментарии, мне пришлось использовать подсветку C и комментарии в C-стиле.

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
43
44
45
46
47
48

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace CF_Examples
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] mas = {{ 4, 1, 3 },
                          { 2, 4, 4 },
                          { 6, 5, 7 }};
            Search(mas);
            System.Console.ReadKey();
        }
 
        private static void Search(int[,] numbers)
        {
            var h = new Dictionary<int, int>();
            foreach (var i in numbers)
            {
                int res;
                if (h.TryGetValue(i, out res))
                {
                    h[i] += 1;
                }
                else
                {
                    h.Add(i, 0);
                }
            }
            foreach (var kv in h)
            {
                if (kv.Value == 0)
                {
                    continue;
                }
                else
                {
                    System.Console.WriteLine(kv.Key + " - встречается: " + kv.Value + " раза.");
                }
            }       
        }
    }
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace CF_Examples
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] mas = {{ 4, 1, 1 },
                          { 2, 4, 4 },
                          { 9, 5, 6 }};
 
            int[] numbers = new int[mas.GetLength(1)];
            int z = 0, q = 0;
            for (int i = 0; i < mas.GetLength(0); i++)
            {
                for (int j = 0; j < mas.GetLength(1); j++)
                {
                    numbers[z] = mas[i, j];
                    z++;
                    
                }
                q = i + 1;
                z = 0;
                Console.WriteLine("Строка № "+q);
                Search(numbers);
                Console.WriteLine("n");
            }
                
            System.Console.ReadKey();
        }
 
        private static void Search(int[] numbers)
        {
            bool myflag = true;
            var h = new Dictionary<int, int>();
            foreach (var i in numbers)
            {
                int res;
                if (h.TryGetValue(i, out res))
                {
                    h[i] += 1;
                }
                else
                {
                    h.Add(i, 0);
                }
            }
            foreach (var kv in h)
            {
                if (kv.Value == 0)
                {
                    continue;    
                }
                else
                {
                    int m = kv.Value + 1;
                    System.Console.WriteLine(kv.Key + " - встречается: " + m + " раз.");
                    myflag = false;
                }
            }
            if (myflag)
            {
                System.Console.WriteLine("Повторов НЕТ!");
            }
            h.Clear();
        }
    }
}

1
2

mas.GetLength(0)
mas.GetLength(1)

1

Got something against index zero, zero?

I also don’t see the point of the pointer shenanigans.

It’s a general safety thing to initialize all your data. You know, to zero or something.

The algorithm you suggest in your solution is rather hard to be faithful to, but this will find your duplicates. You have to walk through the entire array, in both dimensions, twice.

This will also match all the zeroes in your data, so you could add an exception to ignore routes values of zero.

//Cycling through the array the first time.
for (i = 0; i < 6 ; i++)
{
    for (j = 0; j < 6; j++)
    {
        //Cycling through the array the second time
        for (x = 0; x < 6 ; x++)
        {
            for (y = 0; y < 6; y++)
            {
               if(i==x && j==y)
                   continue;
               if(routestore.route[i][j] == routestore.route[x][y])
                   printf("You have a match [%d][%d] =  [%d][%d]", i, j, x,y);
            }
        }
    }
}

Ok, so if you only want to see matches once, ie [0][2] == [2][1] but not [2][1] == [0][2], then you can do something like what I have below. This one made me scratch my head. Usually, when it’s a simple list of items, you initialize the inner loop to the value of the outer loop, plus one. But you can’t quite do that when it’s a 2D array. So I gave up and made a super-lame hack-job. I’m a big fan of brute forcing things when possible. I’d normally tell you not to use pointers like this.

Now… this will still have multiple hits if you have three similar values. If that irks you then you need to start building a list and comparing hits against that as you walk through the data.

#include <stdio.h>
#include <string.h>

struct route{
    int route[6][6];
    int no_routes_found;
    int count_each_route[6];
};

int lameAddOneAlternative(int *i, int *j)
{
  if((*j)<6)
  {
    (*j)++;
    return 1;
  }
  else if (*i<6)
  {
    (*i)++;
    (*j) = 0;
    return 1;
  }  
  return 0;
}

int main(int argc, char **argv)
{
  struct route routeStore;  
  int i,j,x,y;

  memset(routeStore.route,0,sizeof(int)*36);

  // the data
  routeStore.route[0][1] = 24;
  routeStore.route[0][2] = 18;
  routeStore.route[1][1] = 25;
  routeStore.route[2][1] = 18;
  routeStore.route[3][1] = 26;
  routeStore.route[3][2] = 19;
  routeStore.route[4][1] = 25;
  routeStore.route[4][2] = 84;

  //Cycling through the array the first time.
  for (i = 0; i < 6 ; i++)
  {
    for (j = 0; j < 6; j++)
    {
      x=i;
      y=j;
      //Cycling through the array the second time
      while(lameAddOneAlternative(&x,&y))
      {
        if(routeStore.route[i][j] == 0 )
          continue;
        if(routeStore.route[i][j] == routeStore.route[x][y])
          printf("You have a match [%d][%d], [%d][%d] == %dn", i, j, x,y, routeStore.route[i][j] );

      }
    }
  }
}