Самый быстрый способ нахождения числа различных элементов в массиве

Question

У меня есть квадратная матрица, содержащая целые числа (не обязательно различные). Мне нужен самый быстрый способ найти в нем количество отдельных элементов. Я попытался сохранить целые числа в массиве 1D, отсортировал его, а затем нашел количество отдельных элементов ... но, по-видимому, он не достаточно быстр. Не могли бы вы предложить лучшую и быструю процедуру на языке C?

Answer 1

Что будет быстро очень зависит от данных, которые вы имеете дело с, размеры структур, вовлеченных и т.д.

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

Если нет, то, возможно, использование хеш-таблицы, чтобы сделать что-то подобное, будет самым быстрым.

Но в любом случае более точные параметры проблемы будут очень полезными.

Answer 2

Обычно для любого алгоритма существует компромисс между скоростью, памятью и сложностью. Как говорили другие, чем больше информации вы знаете о своих данных, тем быстрее вы сможете сделать свой алгоритм. Скажем, у вас были номера от 1 до 100 (в качестве примера), вы могли бы действительно оптимизировать алгоритм с помощью этой информации.

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

#include <stdio.h>  /* printf, scanf, puts, NULL */ 
#include <stdlib.h>  /* srand, rand */ 
#include <time.h>  /* time */ 
typedef int bool; 
#define TRUE 1 
#define FALSE 0 

/* The actual algorithm function - finds the number of unique values */ 
int NumberUniqueValues(int **array, int width, int height) 
{ 
    int i = 0, j = 0, k = 0, maxFilled = 0; 
    bool wasFound = FALSE; 
    int *newElements = malloc(sizeof(int) * width * height); 

    for (i = 0; i < height; i++) { 
    for (j = 0; j < width; j++) { 
     wasFound = FALSE; 
     for (k = 0; k < maxFilled; k++) { 
     if (newElements[k] == array[i][j]) { 
      wasFound = TRUE; 
      break; 
     } 
     } 

     if (!wasFound) newElements[maxFilled++] = array[i][j]; 
    } 
    } 

    /* Free space */ 
    free(newElements); 
    return maxFilled; 
} 

int main() 
{ 
    /* variables */ 
    int i = 0, j = 0; 
    int originalWidth = 10; 
    int originalHeight = 10; 

    /* initialize array */ 
    int **originalArray = (int **)malloc(originalHeight * sizeof(int*)); 
    for (i = 0; i < originalHeight; i++) { 
    originalArray[i] = (int *)malloc(originalWidth * sizeof(int)); 
    } 

    /* initialize random seed, then fill with random values */ 
    srand (time(NULL)); 
    for (i = 0; i < originalHeight; i++) { 
    for (j = 0; j < originalWidth; j++) { 
     originalArray[i][j] = rand() % 100; 
    } 
    } 

    printf("Number unique values: %d\n", NumberUniqueValues(originalArray, originalWidth, originalHeight)); 

    /* Free space */ 
    for (i = 0; i < originalHeight; i++) free(originalArray[i]); 
    free(originalArray); 

    return 0; 
} 

Опять же, это может быть не самый быстрый алгоритм для случая, так как я не знаю всех деталей, но это будет по крайней мере, работа. Удачи!

Answer 3

ограниченное множество целочисленных значений 0-99

матричный размер 300 х 300

int array[100]; 
int i; 
int j; 
int n_unique = 0; 

for (i=0;i<300;i++) { 
    if (n_unique == 100) break; 
    for (j=0;j<300;j++) { 
     if (array[mat[i][j]] == 0) { 
      array[mat[i][j]] = 1; 
      n_unique++; 
      if (n_unique == 100) break; 
     } 
    } 
} 

алгоритм O (п)

Answer 4

Во-первых, это зависит от того, как вы относитесь ваш массив. Если он динамический или нет, вы можете использовать массив 2d как массив 1d, потому что статический массив 2d массива IS 1d и динамический массив могут быть созданы как 1d-массив.

const int M = 100; 
const int N = 200; 
int **a = NULL; 
int i, j; 

a = (int**) malloc(M * sizeof(int*) + N * M * sizeof(int)); 
a[0] = (int*)(a + M); 
for (i = 1; i < M; i++) { 
    a[i] = a[0] + i * N; 
} 
//code 
free(a); 

и

a[i][j] === a[0][i*num_of_columns + j] 

так, 2 алгоритмы для 1d массивов

typedef int T; 
#define EQ(a, b) ((a)==(b)) 

void quadDiff(T *a, size_t *out_size) { 
    size_t i, j; 
    size_t size = *out_size; 
    size_t pos = 0; 
    int unique; 

    for (i = 0; i < size; i++) { 
     unique = 1; 
      for (j = i; j > 0; j--) { 
       if (EQ(a[i], a[j-1])) { 
        unique = 0; 
        break; 
       } 
      } 
      if (unique) { 
       a[pos++] = a[i]; 
     } 
    } 
    *out_size = pos; 
} 

и

void sortDiff(T *a, size_t item_size, size_t *out_size, int (*cmp)(const void *, const void *)) { 
    size_t i; 
    T prev = a[0]; 
    size_t pos = 0; 
    qsort(a, *out_size, item_size, cmp); 
    for (i = 0; i < *out_size; i++) { 
     if (EQ(prev, a[i])) { 
      continue; 
     } 
     prev = a[i]; 
     a[pos++] = a[i]; 
    } 
    *out_size = pos; 
} 

Answer 5

Я хотел бы предложить следующий подход:

1. Создайте hashmap над значениями в матрице.
2. Возвращает размер hashmap.

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

(Я не умею реализовывать материал на C) Я буду включать Java-код, который демонстрирует подход.

class Distinct { 
    public static void main(String ar[]) { 
      int size; 
      int matrix[][] = new int[size][size]; 
      // POPULATE THE MATRIX BY IMPLEMENTING CUSTOM METHOD 
      populate(matrix); 
      // ALGORITHM: 
      HashMap<Integer,Boolean> distinct = new HashMap<Integer,Boolean>(); 
      for(int i=0;i<size;i++) { 
       for(int j=0;j<size;j++) { 
        distinct.put(matrix[i][j],true); 
       } 
      } 
      System.out.println("Number of distinct elements:"+distinct.size()); 
    } 
} 

Указатели на реализацию HashMap в C можно найти здесь: Implementing a HashMap

Я надеюсь, что это помогает!